离散数学习题答案.doc

习题1：1. 解 （1）2，3，5，7，11，13，17，19 （2）x|x=20*k,k是自然数 （3）2，-12. 解 （1）2，4 （2）1，2，3，4，5 （3）1，3 （4）1，3，53. 解 （1）1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 （2）f （3）全体自然数 （4）0，2，4，6，8，10，12，14，16，18，20 （5）1，3，5，7，9，11，13，15，17，194. 解 （1）正确 （2）正确 （3）错误 （4）正确5. 解 （1）A=1，B=1，C=1 （2）A=1，B=1，C=16. 解 （1）正确。由子集的定义。 （2） 不一定。如：A=1，B=1，C=1。 （3）不一定。如：A=1，B=1，2，C=1，2 （4）不一定。如：A=1，B=1，2，C=1，2。7. 解 A=1，2，B=1，C=2，有，但是成立。 A=1，2，B=1，C=1，有，但是成立。8. 解 （1）f （2）f （3）f （4）f，f9. 解 （1）1,2,3,4,5,6,7,8,9 （2）0,1,2,3,4,5,6,7,8,9,10 （3）0,3,6,7,8,910. 解 33311. 解 2512. 解（1）454 （2）124 （3）22013. 解 （1）f （2）f，a （3）f，f，a，f,a （4）f，f，f，f,f （5）f，f，f，a，f,f，f,a，f,a，f,f,a14. 证明：假设BC，则至少存在一元素xB且xC。 (1) 若xA，因为xB，所以xAB；因为xC，所以x AC，则AB AC，与已知条件AB= AC矛盾。 (2) 若x A，因为xB，所以xAB；因为xC，所以xAC，则AB AC，与已知条件AB= AC矛盾。由(1)，(2)可知，假设不成立，因此B=C成立。15. 证明： （1）左边=（AIB）IC=AIB IC=AI(B IC)=AI(BUC)=A- BUC=右边. （2）左边=(AUB) IC=( AU C) I(B UC)=(A-C) I(B-C) (3) 左边=A I( BUC)=AIB IC=( AIB) I(AIC)=(A-B) I(A-C)16. 证明：(1)反证法，假设BC, 则至少存在一元素xB且xC。 若xA，因为xB，所以xA U B；因为xC，所以x AUC，则AUB AUC，与已知条件AUB= AUC矛盾。 若x A，因为xB，所以x A U B；因为xC，所以x AUC，则A U B AUC，与已知条件A U B = AUC矛盾。 所以，假设不成立，因此B=C成立。 （2）因为A U B = AUC，A I B = AIC，所以A U B - A I B = AUC- AIC，即A B = AC，由第14题可得，B=C。习题二：1. 原题改为：设，计算P(A),P(B),AB,P(A)P(B)。解P(A)= f,1,2,1,2; P(B)= f,a,b,a,b; AB=(1,a),(1,b),(2,a),(2,b);P(A)P(B)=(f,f),(f,a),(f,b),(f,a,b),(1,f),(1,a),(1,b),(1,a,b), (2,f),(2,a),(2,b),(2,a,b),(1,2,f),(1,2,a),(1,2,b),(1,2,a,b)2. 略3. 解 （1）成立 （2）不一定成立。反例：A=1，2，B=2，C=a，b，D=b（3）不一定成立。反例：A=1，2，B=2，C=a，b，D=b（4）不一定成立。反例：A=1，B=2，C=a ，D=b4. 解 f，(1,3), (2,3), (1,3),(2,3)5解IA=(1,1),(2,2),(3,3) UA=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)6. 解（1） （2）略 （3）domR=1,2,3; ranR=a,b,c7. 解RS=(1,a),(1,b),(1,c),(2,a),(2,c),(3,a),(3,b)RS=(1,a),(2,c),(3,a)R-S=(1,b)R-1=(a,1),(b,1),(c,2),(a,3)8. 解 R.S=(a,a),(b,b),(b,d) S.R=(a,a),(a,b),(b,a),(b,b),(c,c) R-1.S-1=(a,a),(a,b),(b,a),(b,b),(c,c) S-1.R-1=(a,a),(b,b),(d,b)9. 解 R=(a,a),(b,b),(c,c)10. 解 (1) R=(a,a),(b,b),(c,c),(a,b),(b,a),(b,c) (2) R=(a,b),(b,a) (3) R=(a,b)11. 解 设集合A=1,2,3,4,5（1）正确。 （2）不成立。反例：R=(1,2),S=(2,1) （3）不成立。反例：R=(1,2),(2,1),S=(2,3),(3,2) （4）不成立。反例：R=(1,2),(3,4),S=(2,3),(4,5)12. 解 r(R)=(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d) s(R)=(a,b),(b,a),(b,c),(c,b),(c,d),(d,c) t(R)=(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)13. 证明：直接利用闭包的构造式即可得证。14.解 等价关系是(a,a),(b,b),(c,c),(d,d),(a,c),(c,a),(b,d),(d,b)15.证明:必要性： R是一个等价关系，则当(a,b)R，(a,c)R必有(b,c)R。因为R对称，所以当(a,b)R时，有(b,a)R， 因为R传递，所以当(b,a)R，(a,c)R时有(b,c)R。充分性：R是A上的一个自反关系，当(a,b)R，(a,c)R必有(b,c)R，证明R是等价关系。自反:条件已知；对称:若(a,b)R,因为R自反,故(a,a)R, 现在(a,b)R,(a,a)R,则根据条件(b,a)R；传递: 若(a,b)R,(b,c)R 因为(a,b)R,(b,c)R, 而R对称,所以(b,a)R, 现在(b,a)R,(b,c)R, 所以根据条件有(a,c)R16. 解 15。17. 解 A/R=a,b,c,d。18. 解 R=(a,a),(b,b),(c,c),(d,d),(b,c),(c,b)65432119. 解 最大元是e，最小元是a，极大元是e，极小元是a。20. 解 21. 是全序、良序。习题六：1. 解 （1）不是命题 （2）是命题，（看具体日期确定）。 （3）是命题，（看具体情况）。 （4）若进行的布尔运算，则是真命题；若十进制运算则是假命题。 （5）不是命题。 （6）是真命题。 （7）是真命题。 （8）不是命题。 （9）是命题。目前不能知道真值。 （10）是命题变元。根据x，y的取值确定真值。 （11）不是命题。2. 解 （1）P：付出劳动；Q：有收获。 则命题符号化为：PQ （2）P：今天下雨；Q：我去看电影。 则命题符号化为：PQ （3）P：a是奇数；Q：b是奇数；R：a与b的和是偶数。 则命题符号化为：PQR （4）P：小明学习好；Q：小明乐于助人。 则命题符号化为：PQ （5）P：小明骑自行车；Q：小明听音乐。 则命题符号化为：PQ （6）P：今天是周二；Q：我准备下周开会的材料。 则命题符号化为：PQ3. 解(1) pq(2) pr(3) prq4. 解 （1）可满足式 （2）可满足式 （3）可满足式 （4）可满足式 （5）重言式5. 证明 （1）左边PQP P(PQ) P(PQ) 右边。 （2）左边(PQ) PQ 右边。 (3) 左边 P(PQ) P(Q P) P( Q P) 右边。 (4) 右边(PR) (QR) PQR(PQ) R(PQ) R 左边。6. 解 此题答案不唯一。 （1）合取范式与析取范式都可以是PQ。 （2）原式是重言式。合取范式与析取范式都可以是1。 （3）合取范式可以是（PQ） (PQ) 析取范式可以是（PQ） (PQ) （4）原式是重言式。合取范式与析取范式都可以是1。7. 解 （1）主析取范式：(PQ) ( PQ) 主合取范式：（PQ）（PQ） (2) 主析取范式：(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) 主合取范式：空 （3）主析取范式：（PQ）（PQ） 主合取范式：（PQ）（PQ） （4）主析取范式：(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) 主合取范式：PQR8. 证明 (1) 利用真值表可知：左边的主合取范式(PQRS) (PQRS) (PQRS) 右边的主合取范式(PQRS) (PQRS) (PQRS) 因此（1）成立。 （2）利用真值表可知“ 左边的主合取范式 PQ右边的主合取范式 PQ因此（2）成立。 （3）利用真值表可知“ 左边的主合取范式（PQR）（PQR）（PQR）右边的主合取范式（PQR）（PQR）（PQR）因此（3）成立。9. 证明 （1）(PQ）( PR) (QS) (SR) (PQ）( PR) (QS) (SR) (PQ） (PR) (QS) (SR) (PR) QS SR 1 因此，原推理成立。 （2）( (PQ) ( QR) R) P ( (PQ) ( QR) R) P (PQ) ( QR) R) P (PQ) ( QR) R P (PQRP) (PR RP) (Q Q RP) (Q R RP) 1111 1 因此，原推理成立。10. 证明(1) R P RS P S , ,I SQ P Q ,I PQ P P , I (2) C P (BA) C P BA , ,I (AB) (CD) P (AB) (CD) ,E AB , ,I AB , I 11. 证明 (1) AB CP A , I B , I A(B C) P C , ,I (CD) E P CDE , E DE , ,I DEH P H , ,I 11) ABH , ,CP (2) P CP Q CP P(QR) P QR , ,I R ,I R(QS) P QS , ,I P(QS) , ,CP12. 解：P：他是计算机系的本科生；Q：他一定学过C语言R：他学过Java语言；S：他会编程序。则原命题符号化为：前提：P（QR）；（QR）S。结论：PS 证明过程如下： P CP P（QR） P QR , ,I （QR）S P S , ,I PS , ,CP13. 解：P：6是偶数；Q：2整除7；R：7是素数。则原命题符号化为：前提：PQ；RQ；R。结论：P。证明过程如下： R P RQ P Q , ,I PQ P P , ,I习题七：1. 解（1）G（x，y）：xy，N（x）：x是自然数。 则原命题符号化为：$x(N(x)y(N(y)G(x,y) （2）M（x）：x是人；N（x）：x爱看科幻片。 则原命题符号化为：$x(M(x) N(x) （3）M（x）：x是人；N（x）：x喜欢吃甜食 则原命题符号化为：x(M(x) N(x) （4）M（x）：x是人；N（x）：x是药品；P（x，y）：x对y过敏。 则原命题符号化为：$x (M(x) $x (N (x)P (x,y) （5）M（x）：x是人；N（x）：x来参加这次会议。 则原命题符号化为：x(M(x) N(x) （6）M（x）：x是大学生；N（x）：x热爱祖国。批评； 则原命题符号化为： x(M(x) N(x)2. 解（1）$xL(x,0) (x(L(0,x) $y(L(y,x) G(x,y) （2）x$y(G(x,y) L(x,y) （3）x($yS(x,y,x) G(y,0)3解（1）x(P(x) $yQ(y)中的x，y均为约束变元，x的辖域为P(x) $yQ(y)，$y的辖域为Q(y)；$xR(x,y) 中x为约束变元,y为自由变元，$x的辖域为R(x,y).（2）xP(x)中的x为约束变元，x的辖域为P(x)；Q(x)中的x为自由变元。（3）x$y(P(x)Q(x) R(x,y)中的x,y均为约束变元，其中x的辖域为$y(P(x)Q(x) R(x,y)，$y的辖域为(P(x)Q(x) R(x,y)（4）x$y(P(x)Q(x,y)中的x,y均为约束变元，其中x的辖域为$y(P(x)Q(x,y), $y的辖域为Q(x,y)；x(P(x)R(x,y)中的x为约束变元，y为自由变元，x的辖域为P(x)R(x,y)。4. 解（1）xP(x) yQ(y)(2) z(P(z) Q(z) R(x,y)(3) xP(x) z$y(Q(z) R(z,y)5. 解（1）xP(x) Q(y) （2）xP(x,z) $y(Q(y) R(u,y) （3）xP(x,u) ($zQ(v,z) yR(v,y)6. 解 （1）P(1) P(2) Q(1) Q(2) （2）(P(1) P(2) ( Q(1) Q(2) （3）(P(1) P(2) ( Q(1) Q(2)7. 解（1）1 （2）08解（1）x$y(P(x) Q(x,y) （2）x$y $z(P(x,y) Q(y) R(x,y,z) （3）x$y $uz$v(P(x,y) Q(u,z) R(v) （4）xz$u(P(x,y) G(z,y) H(u)9. 解（1）前束合取范式：x$yz(P(x) Q(x,y) (P(x) Q(x,z) 前束析取范式：x$yz(P(x) Q(x,z) ( P(x) Q(x,y) （2）前束合取范式：xy$z(P(x,y) R(u,y,z) (Q(y) R(u,y,z) 前束析取范式：xy$z(P(x,y) Q(y) R(u,y,z) （3）前束合取范式：$xyu$z$v(P(x,y) Q(u,z) (P(x,y) R(v) 前束析取范式：$xyu$z$v(P(x,y) (Q(u,z) R(v)10. 证明（1） xG(x) P $xG(x) ,E G(a) ,ES x(G(x) Q(x) P G(a) Q(a) ,US Q(a) ,I $xQ(x) ,EG （2） xP(x) P P(u) ,US x(P(x) (Q(y) R(x) P P(u) (Q(y) R(u) ,US Q(y) R(u) , ,I Q(y) ,I R(u) ,I P(u) R(u) , ,I $x(P(x) R(x) ,UG Q(y) $x(P(x) R(x) , ,I11. 证明 $xF(x) P F(a) ,ES $x(R(x) T(x) P R(b) T(b) ,ES R(b) ,I T(b) ,I z(F(z) x$yQ(x,y) y(R(x) T(y) P (F(a) x$yQ(x,y) (R(b) T(b) ,US (R(b) T(b) ,I x$yQ(x,y) , ,I y $ x Q(x,y) ,E12. 解 前提：x(H(x) (F(x) G(x)；$ x(H(x) F(x) 结论：$ x(H(x) G(x)证明如下： $ x(H(x) F(x) P H(a) F(a) ,ES H(a) ,I F(a) ,I x(H(x) (F(x) G(x) P H(a) (F(a) G(a) ,US F(a) G(a) , ,I G(a) , ,I H(a) G(a) , ,I $ x(H(x) G(x) ,EG13. 解 (1) 设个体域为人。F(x):x喜欢玩电子游戏，M(x):x喜欢看电影，G(x):x喜欢逛街。则原命题符号化为： 前提：x(F(x) M(x)；x(M(x) G(x)；$ x G(x) 结论：$ x F(x) 证明如下： $ x G(x) P G(a) ,ES x(F(x) M(x) P F(a) M(a) ，US x(M(x) G(x) P M(a) G(a) ,US M(a) , ,I F(a) , ,I $ x F(x) ,EG（2）设个体域为人。F(x):x是学术委员会成员，P(x):x是教授，B(x):x是博士生导师，C(x):x是院士。则原命题符号化为： 前提：x(F(x) (B(x) P(x)；$x(F(x) C(x) 结论：$ x(F(x) B(x) C(x)证明如下： $x(F(x) C(x) P F(a) C(a) ,ES F(a) ,I C(a) ,I x(F(x) (B(x) P(x) P F(a) (B(a) P(a) ,US B(a) P(a) , ,I B(a) ,I F(a) B(a) C(a) , , ,I $ x(F(x) B(x) C(x) ,EG习题八：1. 证明：假设图有两个或更多个孤立点，那么这些孤立点便是具有相同的度的两个顶点，命题得证。如果图正好有一个孤立点，那么对有n-1个顶点且没有孤立点的子图，则这n-1个顶点的度数应是1，2，n-1，而这不可能，因为这n-1个顶点是简单图，最大度不能大于等于n-1。所以，必定有两个顶点的度数相同。2. 解 (1)可简单图化 （2）不可图化 （3）可简单图化 （4）可简单图化 （5）可简单图化3. 解4个顶点的完全图有6条边，只需取由6条边构成的任意一个子集加上4个顶点构成的简单图，即可形成G的所有生成子图。其中互不同构子图有：0条边的不同构子图：1个1条边的不同构子图：1个2条边的不同构子图：2个3条边的不同构子图：3个4条边的不同构子图：2个5条边的不同构子图：1个4. 解 （1） （2） （3）证明：根据自补图的定义，该自补图应同构他的补图，则他们应该具有相同的边数，而他们的和在一定是偶数，即该补图对应的完全图的边数为偶数。5. 解 （24-1*2-2*1-3*1-5*1）/4=3个4度顶点。6. 原题改为：证明在简单无向图中，从顶点到顶点，如果既有奇数长度的通路又有偶数长度的通路，则中必有一条奇数长度的回路。证明 设从u到v长度为偶数的路径为ue1u1e2e2kv，长度为奇数的路径为ue1u1e2e2n+1v。因为G是无向图，所以ue1u1e2e2kve2n+1e1u就是一个长度为奇数的回路。7. 证明 设图G中有n个顶点v1，v2，vn。由于v1的度数大于等于2，所以v1一定与v2，vn中的某些点相邻。假设v1和v2相邻，于是得到由2个点构成的基本通路v1v2；又由于v2的度数大于等于2，所以v2一定与v3，vn中的某一点相邻，不放设为v3，于是得到由3个点构成的基本通路v1v 2v3。由此可见，在满足提设条件的图G中，必有i个顶点（i大于等于3）构成的基本通路，设为v1v2vi。（1） 如果i=n。即存在一条通过n个顶点的基本通路：v1v2vn，由于vn的度数大于等于2，所以vn一定与v1，v2，,vn-1中的某一点vk相邻，于是得到基本回来vnvkvk+1vn，问题得证。（2） 如果in。由于vi的度数大于等于2，所以vi应与v1，v2，vi-1中的某一点或vi+1，vi+2，vn中的某一点相邻，如果vi与v1，v2，vi-1中的某一点相邻，则得到基本回路vivkvk+1vi，问题得证。如过vi与v1，v2，vi-1中的任一点都不相邻，仅与vi+1，vi+2，vn中的某一点相邻，假设该点为vi+1，由此得到基本通路v1v2vi+1。如果i=n，则由（1）可知，在图G中存在基本回路。得证。如果i+1n，对vi+1作同样讨论，直到找到一条基本回路为止。因此，原结论成立。8. 证明 此题可化为图论的问题来处理。把每个人对应为相应的顶点，两个人具有朋友关系当且仅当相应的顶点相邻。显然该图是简单图。原命题等价于证明在该无向简单图中一定存在两个顶点的度数相等。反设，该无向简单图G中任何一对顶点的度数都不相等。并设顶点数为n。又因图G是简单图，故顶点度数序列只可能为0,1,2,n-1。从图G中删去度数为0的顶点，那么在剩下的子图G中，顶点数为n-1，并且存在度数为n-1的顶点。所以，图G不是简单图，因此图G也不是简单图，矛盾。故在该无向简单图中一定存在两个顶点的度数相等。 9. 解（1）n-1,m-k （2）n, m-110. 原题改为：已知无向图的边数为15，中有3个2度顶点，2个3度顶点，3个1度顶点，其余的顶点均为5度顶点，试求中5度顶点的个数。解 (2*15-3*2-2*3-3*1)/5=3个5度顶点。11. 证明 假设G为非联通图，不妨假设G中有2个子图G1与G2，G1中有p个顶点，G2中有q个顶点，且p+q=n，因为G是简单图，所以G1中顶点的度大于等于（p-1）/2，G2中顶点的度大于等于（q-1）/2，则(p-1)/2+(q-1)/2=(p+q-2)/2=(n-2)/2,与已知条件矛盾，所以图G是联通图。12. 证明 假设G=不连通，不妨设G可分为两个连通分图G1,G2,设G1，G2分别有n1,n2个结点，n1+n2=n。由于ni1，i=1,2，则与条件矛盾。所以G是连通图。V4V3V2V113. 解 给图中的每个顶点标上序号，如下图： 邻接矩阵为： 可达矩阵为：14. 原矩阵改为：v4v3v2v1解根据M算出M的3次方为：则从v1到v1长度为3的回路数为2，v1到v2长度为3的通路数是3，v1到v3长度为3的通路数是3，v1到v4长度为3的通路数是3.习题九：1. 解 （1）三阶完全图是欧拉图，且n与m的奇偶性一样，都为奇数。 （2）五阶完全图是欧拉图，n为奇数5，m为偶数10.2. 解 顶点度数全部为偶数，即图的阶数是奇数。3. 解 （1）三阶完全图既是欧拉图又是哈密顿图。 （2）如下图所示，是欧拉图，但不是哈密顿图。 （3）四阶完全图是哈密顿图，不是欧拉图。 （4）彼得森图既不是欧拉图又不是哈密顿图。4. 解 节点数为20，每个节点度数都大于等于10，则