离散数学及其应用(课后习题)

(圆满版)失散数学及其应用(课后习题)(圆满版)失散数学及其应用(课后习题)(圆满版)失散数学及其应用(课后习题)习题指出以下命题是原子命题仍是复合命题。〔3〕大雁北回，春季来了。4〕不是东风压倒西风，就是西风压倒东风。5〕张三和李四在吵嘴。解：〔3〕和〔4〕是复合命题，〔5〕是原子命题。习题指出以下命题的真值：〔1〕假定224，那么太阳从西方升起。解：该命题真值为T〔由于命题的前件为假〕。〔3〕胎生动物当且仅当是哺乳动物。解：该命题真值为F〔如鸭嘴兽虽是哺乳动物，但不是胎生动物〕。令P：天气好。Q：我去公园。请将以下命题符号化。〔2〕只需天气好，我就去公园。〔3〕只有天气好，我才去公园。〔6〕天气好，我去公园。解：〔2〕PQ。〔3〕QP。〔6〕PQ。习题2.将以下命题符号化〔句中括号内提示的是相应的原子命题的符号表示〕：1〕我去新华书店〔P〕，仅当我有时间〔Q〕。3〕只需努力学习〔P〕，成绩就会好的〔Q〕。6〕我今日进城〔P〕，除非下雨〔Q〕。10〕人不犯我〔P〕，我不罪犯〔Q〕；人假定犯我，我必罪犯。解：〔1〕PQ。〔3〕PQ。〔6〕QP。〔10〕(PQ)(PQ)。习题写出以下公式的真值表：〔2〕P(QR)。1解：该公式的真值表以下表：PQRQRP(QR)0001100111010000111110011101111100111111证明以低等价公式：〔2〕(PQ)(PQ)(PQ)。证明：(PQ)((PQ)(PQ))(PQ)(PQ))(PQ)(PQ)(PQ)(PQ)〔4〕(PQ)(PR)P(QR)。证明：(PQ)(PR)(PQ)(PR)P(QR)(QR)甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。4个人的回复只有一个人符合实质，问成绩最好的是谁？解：设A：甲成绩最好。B：乙成绩最好。C：丙成绩最好。D：丁成绩最好。四个人所说的命题分别用P、Q、R、S表示，那么PA；QABCD；RABCD；SD。那么只有一人符合实质的命题K符号化为K(PQRS)(PQRS)(PQRS)(PQRS)2PQRSA(ABCD)(ABCD)DA(ABCD)(ABCD)D(AD)(ABCD)(ABCD)(ABCD)(ABD)(ABCD)(ACD)0;同理，PQRSAABCD(ABCD)D0;PQRSA(ABCD)ABCDD0;PQRSA(ABCD)(ABCD)DA(ABCD)(ABCD)DAD.所以，当K为真时，AD为真，即甲的成绩最好。习题证明以下各包括式：〔3〕P(QR)(PQ)(PR)。证明：方法一：真值表法〔列出命题公式(P(QR))((PQ)(PR))的真值表〕。PQRPQ

PRQRP(QR)(PQ)(PR)(P(QR))((PQ)(PR))0001111110011111110101101110111111111000011111010111111101000011111111113方法二：等值演算法(P(QR))((PQ)(PR))(P(QR))((PQ)(PR))(P(QR))(PQ)(PR)(PQR)(PQ)(PR)(PQR)((PPR)(QPR))(PQR)(QPR)(PQPR)(QQPR)(RQPR)1.方法三：分析法〔1〕直接分析法：假定前件P(QR)为真，分两种状况：〔I〕P为假，那么PQ为真，PR为真，(PQ)(PR)为真。〔II〕P为真，那么QR为真，此时假定Q为真，那么R为真，那么PQ为真，PR为真，(PQ)(PR)为真；假定Q为假，那么PR为假，(PQ)(PR)为真。综上，假定前件为真，后件必为真，故该包括式建立。(2〕间接分析法：假定后件(PQ)(PR)为假，那么PQ为真，PR为假。由PR为假可知，P为真，R为假。再由PQ可知，Q为真。此时QR为假，(QR)为假，即前件为假。故包括式建立。表达以下各个命题的逆换式和逆反式，并以符号写出。〔1〕假以下雨，我不去。解：设P：天下雨。Q：我去。逆换式：假如我不去，天就下雨。符号表示为QP。逆反式：假如我去，天就不下雨。符号表示为QP。〔2〕仅当你走我将留下。解：设P：我留下。Q：你走。逆换式：假如你走，我就留下。符号表示为：QP。逆反式：假如你不走，我就不留下。符号表示为：QP。4习题2.将以下命题公式用只含和的等价式表达，并要求尽可能简单。〔1〕(PQ)P.解：(PQ)P(PP)Q0Q0.〔2〕(P(QR))PQ.解：(P(QR))PQ(P(QR))PQ(PQR)PQ(PPQ)(PQQ)(PQR)(PQ)(PQ)(PQR)(PQ)(PQR)(PQ)(PQR)PQ(PQ).〔3〕PQ(RP).解：PQ(RP)PQ(RP)(PQR)(PQP)(PQR)0PQR(PQR).习题6．求以下命题公式的主析取范式和主合取范式：〔1〕((PQ)R)P.解：((PQ)R)P((PQ)R)P((PQ)R)P(PQP)(PR)(PQ)(PR)(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)M0M1M3〔主合取范式〕m2m4m5m6m7.〔主析取范式〕5习题1.证明(PQ)(PR)(RS)SQ.证明：〔1〕SP〔附带前提〕〔2〕RSP〔3〕SRT〔2〕E〔4〕RT〔1〕〔3〕I〔5〕PRP〔6〕RPT〔5〕E〔7〕PT〔4〕〔6〕I〔8〕PQP〔9〕QT〔7〕〔8〕I〔10〕SQCP2．用间接证法证明P(QR)，QP，SR，PS.证明：〔1〕SP〔附带前提〕〔2〕SRP〔3〕RT〔1〕〔2〕I〔4〕PP(5)P(QR)P(6)QRT(4)((5)I(7)QT(3)(6)I(8)QPP(9)PT(7)(8)I(10)PP(矛盾式)T(4)(9)I由〔10〕得出了矛盾，依据归谬法说明原推理正确。5.“假以下雨，春游就会更期；假如没有球赛，春游就不会更期。结果没有球赛，所以没有下雨。〞证明上述论断正确。解：设P：下雨。Q：有球赛。R：春游更期。那么上述论断转变为要证明PR，QR，P.证：〔1〕QP〔2〕QRP6〔3〕RT〔1〕〔2〕I〔4〕PRP〔5〕PT〔3〕〔4〕I所以，上述推理正确。7.证明RS是前提CD，CR，DS的有效结论。证明：〔1〕CDP〔2〕CDT〔1〕E〔3〕DSP〔4〕CST〔2〕〔3〕I〔5〕CRP〔6〕RCT〔5〕E〔7〕RST〔4〕〔6〕I〔8〕RST〔7〕E习题用谓词表达式写出以下命题：〔5〕每个有理数是实数。解：x(Q(x)R(x))，此中Q(x)：x是有理数。R(x)：x是实数。〔6〕有的函数连续。解：x(F(x)C(x))，此中F(x)：x是函数。C(x)：x连续。习题将以下命题符号化：〔3〕没有人登上过木星。解：设M(x)：x是人。A(x)：x登上过木星。那么命题可表示为(x)M(x)A(x).符号化以下命题：〔2〕只管有人聪慧，但未必全部人都聪慧。解：设M(x)：x是人。C(x)：x聪慧。那么命题可表示为x(M(x)C(x))x(M(x)C(x)).习题对以下谓词公式中拘束变元进行换名：〔1〕xy(P(x,z)Q(y))S(x,y)〔2〕(x(P(x)(R(x)Q(x)))xR(x))zS(x,z)7解：〔1〕uv(P(u,z)Q(v))S(x,y)〔2〕(u(P(u)(R(u)Q(u)))vR(v))zS(x,z)对以下谓词公式中自由变元进行代入：〔1〕(yA(x,y)xB(x,z))xzC(x,y,z)〔2〕(yP(x,y)zQ(x,z))xR(x,y)解：〔1〕(yA(s,y)xB(x,w))xzC(x,t,z)〔2〕(yP(s,y)zQ(s,z))xR(x,t)习题证明以低等价式：〔1〕x(P(x)Q(x))x(P(x)Q(x)).证明：x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))〔2〕x(P(x)Q(x))x(P(x)Q(x)).证明：x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))习题求以下谓词公式的前束析取范式和前束合取范式：〔1〕(x)P(x)(x)Q(x).解：(x)P(x)(x)Q(x)8(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x))〔前束析取范式、前束合取范式〕〔2〕(x)(y)((z)(P(x,z)P(y,z))(u)Q(x,y,u)).证明：(x)(y)((z)(P(x,z)P(y,z))(u)Q(x,y,u))(x)(y)(z)((P(x,z)P(y,z))(u)Q(x,y,u))(x)(y)(z)(u)((P(x,z)P(y,z))Q(x,y,u))

〔辖域扩大〕〔辖域扩大〕〔前束析取范式〕(x)(y)(z)(u)((P(x,z)Q(x,y,u))(P(y,z)Q(x,y,u)))〔前束合取范式〕习题1.证明以下各式。〔2〕x(A(x)B(x)),x(B(x)C(x)),xC(x)xA(x).证明：〔1〕xC(x)P〔2〕C(a)US〔1〕〔3〕x(B(x)C(x))P〔4〕B(a)C(a)US〔3〕〔5〕B(a)T(2)(4)I〔6〕x(A(x)B(x))P〔7〕A(a)B(a)US〔6〕〔8〕A(a)T〔5〕〔7〕I〔9〕xA(x)UG〔8〕符号化以下命题并推证其结论。〔3〕全部有理数是实数，某些有理数是整数，所以，某些实数是整数。解：设Q(x)：x是有理数。R(x)：x是实数。Z(x)：x是整数。那么命题可符号化为：9x(Q(x)R(x))，x(Q(x)Z(x))x(R(x)Z(x))。证明以下：〔1〕x(Q(x)Z(x))P〔2〕Q(c)Z(c)ES〔1〕〔3〕x(Q(x)R(x))P〔4〕Q(c)R(c)US〔3〕〔5〕Q(c)T〔2〕I〔6〕R(c)T〔4〕〔5〕I〔7〕Z(c)T〔2〕I〔8〕R(c)Z(c)T〔6〕〔7〕I〔9〕x(R(x)Z(x))EG〔8〕4〕每个大学生不是文科生就是理科生，有的大学生是优等生，小张不是理科生，但他是优等生，所以假如小张是大学生，他就是文科生。解：设S(x)：x是大学生。A(x)：x是文科生。B(x)：x是理科生。C(x)：x是优等生。a：小张。该命题可符号化为：x(S(x)A(x)B(x))，x(S(x)C(x))，B(a)，C(a)S(a)A(a)。证明以下：〔1〕x(S(x)A(x)B(x))P〔2〕S(a)A(a)B(a)US〔3〕〔3〕S(a)附带前提〔6〕A(a)B(a)T〔4〕〔5〕I〔7〕B(a)P〔8〕A(a)T〔6〕〔7〕I〔9〕S(a)A(a)CP10习题确立以下命题是真仍是假，并简要说明为何。〔1〕〔2〕〔3〕{}〔4〕{}解：〔1〕该命题为真，由于是任何会合的子集。〔2〕该命题为假，由于不包括任何元素。〔3〕该命题为真，由于属于会合{}。〔4〕该命题为真，由于是任何会合的子集。6.求以下会合的幂集：〔2〕{1,}〔3〕{,{}}解：〔2〕该会合的幂集为{,{1},{},{1,}}。〔3〕该会合的幂集为{,{},{{}},{,{}}}习题证明以低等式：〔4〕A(BC)(AB)(AC)。证明：A(BC)=A(BC)=A(BC)=A(BC)=(AB)(AC)=(AB)(AC)所以，A(BC)(AB)(AC)。〔5〕A(BC)(AB)(AC)。证明：A(BC)=A(BC)A(BC)=(AB)(AC)=(AB)(AC)。所以，A(BC)(AB)(AC)。〔8〕(AB)(AC)(AC)(AB)。证明：(AB)(AC)((AB)A)((AB)C)11(AA)(AB)(AC)(BC)(AB)(AC)(BC)(AC)(AB)[(BC)(AA)](AC)(AB)(BCA)(BCA)[(AC)(ABC)][(AB)(ABC)](AC)(AB)所以，(AB)(AC)(AC)(AB)。习题以低等式能否建立？〔3〕(BC)A(BA)(CA)。解：该等式建立。证明以下：设x,y(BC)AxBCyAxBxCyA(xByA)(xCyA)x,yBAx,yCAx,y(BA)(CA)所以，(BC)A(BA)(CA)。〔4〕(BC)A(BA)(CA)。解：该等式建立。证明以下：设x,y(BC)AxBCyA(xBxC)yA(xByA)(xCyA)x,yBAx,yCA12x,y(BA)(CA)所以，(BC)A(BA)(CA)。习题关于以下各样状况，用列举法求出X到Y的关系S、domS、ranS，画出S的关系图，写出S的关系矩阵。〔1〕X{0,1,2}，Y{0,2,4}，S{x,y|x,yXY}。解：S{0,0,0,2,2,0,2,2}，domS{0,2}，ranS{0,2}。关系图以下：001224关系矩阵为110MS000。110习题5.设X{a,b,c,d}，X上的关系R的关系矩阵以下，试问R是不是自反的、反自反的、对称的、反对称的和传达的？0101101100000101〔1〕00〔4〕10111101001111解：〔1〕R是反自反的、反对称的、非传达的。由于r121,r311,但r320。〔2〕R是自反的、对称的、非传达的。由于r341,r421,但r320。13习题5.〔1〕设X{a,b,c}，X上关系R的关系矩阵是101MR110111试求出MRoR、MRoRoR。101101111解：MRoR110o110111，111111111111101111MRoRoR111o110111。111111111习题4.设X{1,2,3,4,5}，试依据以下X的区分求X上相应的等价关系，并画出关系图。3〕{{1},{2},{3,4,5}}解：R1{1}{1}{1,1}R2{2}{2}{2,2}R3{3,4,5}{3,4,5}{3,3,3,4,3,5,4,3,4,4,4,5,5,3,5,4,5,5}RR1R2R3{1,1,2,2,3,3,3,4,3,5,4,3,4,4,4,5,5,3,5,4,5,5}关系图以下：1425314习题关于以下会合上的“整除〞关系，画出其哈斯图。〔1〕{1,2,3,4,6,8,12,24}解：该整除关系的哈斯图以下：2481246231习题1.指出以下各关系能否为X到Y的函数：〔1〕XYN，R{x,y|(xX)(yY)(xy100)}.〔3〕X{1,2,3,4}，YXX，R1{1,2,3,2,3,4,3,1,4,4,2,3}，R2{1,2,3,2,3,4,3,2,3}.解：〔1〕R不是从X到Y的函数；〔2〕R1是从X到Y的函数，R2不是从X到Y的函数。习题设Z，Z，R，C分别表示正整数集、整数集、实数集、复数集，试指出以下照耀中哪些是单射、满射、双射，并写出定义域和值域。〔1〕f:ZZ为f(x)2x1。〔2〕f:RR为f(x)cosx。〔4〕f:[0,][1,1]为f(x)cosx。215解：〔1〕为一般照耀，定义域为Z，值域为{y|y2k1,kN}。〔2〕为一般照耀，定义域为R，值域为[1,1]。〔4〕为单射，定义域为[0,]，值域为[0,1]。2习题设X{1,2,3,4}。〔3〕能否找到另一gIX的单射g:XX，有gogIX？解：能。比方g{1,2,2,1,3,4,4,3}。〔4〕试定义一个照耀f:XX使f2f且fIX。解：比方f{1,2,2,2,3,3,4,4}。习题1.设无向图GV,E,，V{v1,v2,L,v6}，E{e1,e2,L,e6}，(e1)(v1,v2)，(e2)(v2,v2)，(e3)(v2,v4)，(e4)(v4,v5)，(e5)(v3,v4)，(e6)(v1,v3)。1〕画出G的图形。2〕求G的各节点的度数，并考证握手定理。3〕G是不是简单图？解：〔1〕v3v5v1v2v4v6〔2〕deg(v)2，deg(v)4，deg(v)2，deg(v)3deg(v)1，deg(v)0。123456166deg(vi)12，2E12，握手定理建立。13〕图G中存在环，故G不是简单图。4.下边各图有几个节点？〔2〕21条边，3个度为4的节点，其他都是度为3的节点。解：设度数为3的节点个数为x，由握手定理，解得故该图有13个节点。

221343xx10习题4.分别指出图7-32中的3个图分别属于哪一各样类〔强连通，单侧连通，弱连通〕。〔a〕(b)(c)v1解：〔a〕是强连通的，〔b〕是单侧连通的，(c)是弱连通的。习题1.图7-39给出了一个有向图，试求v4v2〔1〕毗邻矩阵。〔2〕A2、A3、A4，并找出从v1到v4长度为1、2、3、4的路各有几条？v3〔3〕可达性矩阵。图7-3901010011解：〔1〕毗邻矩阵A10。010100010101010111〔2〕A2001100110201,01010101011101000100001117011101010212A302010011012201110101021,2001101000201021201010323A401220011041302120101032.3020101000122从毗邻矩阵及其幂可知，从v1到v4长度为1的路有1条，从v1到v4长度为2的路有1条，从v1到v4长度为3的路有2条，从v1到v4长度为4的路有3条。〔3〕令BAA2A3A4，07470111那么B0747，可达性矩阵P01110747011。104340111习题2.确立n取如何的值，圆满图Kn有一条欧拉回路。解：圆满图Kn有一条欧拉回路的充要条件是每个节点的度数都是偶数。而在Kn中，每个节点的度数都是n1。故当n为奇数时，圆满图Kn有一条欧拉回路。习题5.设G是一个连通平面图，它有n个节点，m条边，且每个面由k条边围成。试证mk(n2)。k2证明：设图G有r个面，由平面图的面的次数的定理，r2mdeg(Ri)kr.〔1〕i1再由欧拉定理，nmr2.〔2〕由〔1〕得r2m，代入〔2〕式得k18k(n2).k2习题一棵树T有5个度为2的节点，3个度为3的节