2022年电大离散数学本科期末复习题.docx

《2022年电大离散数学本科期末复习题.docx》由会员分享，可在线阅读，更多相关《2022年电大离散数学本科期末复习题.docx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源离散数学（本） 一、单项挑选题1. 设 P： a是偶数， Q ： b 是偶数； R ：a + b 是偶数，就命题“如 a 是偶数， b 是偶数，就a + b 也是偶数”符号化为（ D P Q R ）；2. 表达式x（P （ x， y）Q（ z）y（ Q（ x， y） zQ （ z）中x 的辖域是（ P （ x， y） Q（ z）；欢迎下载精品学习资源3. 设S1, S2, S3P, S4P 就命题为假的是（S2S4 ）；欢迎下载精品学习资源4. 设 G 是有 n 个结点的无向完全图，就G 的边数（ 1/2 n （ n-1 ）；5. 设 G 是连通平面图，有v 个结点， e 条边，

2、r 个面，就 r= （ e-v+2 ）；6 如集合 A=1 ， 2 ， 1 ， 2 ，就以下表述正确选项 1A 7. 已知一棵无向树T 中有 8 个顶点， 4 度、 3 度、 2 度的分支点各一个， T 的树叶数为 5 01111100111000011001110108. 设无向图 G 的邻接矩阵为就 G 的边数为 7 9. 设集合 A= a，就 A 的幂集为 ， a 10. 以下公式中 ABAB 为永真式11. 如 G 是一个汉密尔顿图，就G 肯定是 连通图 12. 集合 A=1, 2, 3, 4 上的关系 R=|x=y 且 x, yA，就 R 的性质为（传递的）13. 设集合 A=1 ，

3、 2， 3， 4， 5 ，偏序关系是 A 上的整除关系，就偏序集 上的元素 5 是集合 A 的（极大元 ）14. 图 G 如图一所示，以下说法正确选项 a, d , b, d是边割集 图一15. 设 A（ x）： x 是人， B（ x）： x 是工人，就命题“有人是工人”可符号化为（xAxBx ）16如集合 A=1 ， 2 ， B=1 ， 2， 1 ，2 ，就以下表述正确选项 AB，且 AB 17. 设有向图（ a）、（ b）、（ c）与（ d）如图一所示，就以下结论成立的是 （ d）是强连通的 欢迎下载精品学习资源011001001110000010010101018. 设图 G 的邻接矩阵

4、为就 G 的边数为 5 19. 无向简洁图 G 是棵树，当且仅当G 连通且边数比结点数少1 20. 以下公式 PQPPPQ 为重言式21如集合 A a， a， 1 ，2 ，就以下表述正确选项 aA欢迎下载精品学习资源22. 设图 G ， vV，就以下结论成立的是vdegvV2 E 欢迎下载精品学习资源23. 命题公式（ P Q）R 的析取范式是 （ P Q ）R 24. 以下等价公式成立的为PQPPPQ 25设 A=a, b， B=1,2 ， R1， R2 ， R3 是 A 到 B 的二元关系，且R1 =, ， R2=, ， R3=, ，就（ R 2 ）不是从 A 到 B 的函数26. 设 A

5、=1,2,3, 4,5,6,7, 8 ，R 是 A 上的整除关系， B=2,4, 6 ，就集合 B 的最大元、最小元、上界、下界依次为无、 2、无、 2 27. 如集合 A 的元素个数为10 ，就其幂集的元素个数为（1024 ）28. 如图一所示，以下说法正确选项e 是割点 图一29. 设完全图 K n 有 n 个结点 n2 ，m 条边，当（ n 为奇数）时， K n 中存在欧拉回路30. 已知图 G 的邻接矩阵为，就 G 有（ 5 点， 7 边 ）二、填空题（每道题3 分，共 15 分）1. 设 A， B 为任意命题公式，C 为重言式，如 ACBC ，那么 AB 是重言式（重言式、冲突式或可

6、满意式）；2. 命题公式（ PQ）P 的主合取范式为 PQPQ ；欢迎下载精品学习资源3 设集合 A=， a ，就 P （ A） = , a, , a；欢迎下载精品学习资源4. 设图 G = V ， E， G =V ，E ，如 V =V,E E, 就 G 是G 的生成子图；r欢迎下载精品学习资源5. 在平面 G =V ，E 中， 就（或 F，或 0 ）degri =2|E| ，其中i 1ri （ i=1 ， 2， r）是 G 的面； 6 命题公式 PP 的真值是假欢迎下载精品学习资源7. 如无向树 T 有 5 个结点，就 T 的边数为48. 设正就 m 叉树的树叶数为 t，分支数为 i，就m-

7、1 i=t-19. 设集合 A=1 ， 2 上的关系 R , ，就在 R 中仅需加一个元素，就可使新得到的关系为对称的10. xAxBx， z C y中的自由变元有z ， y11如集合 A=1 ， 3， 5， 7 ， B=2 ， 4 ， 6， 8 ，就 AB=空集（或）12设集合 A=1 ， 2， 3 上的函数分别为：f=,， g=,，就复合函数 g f =, , , 13. 设 G 是一个图，结点集合为V，边集合为 E，就 G 的结点度数之和为2| E|（或“边数的两倍”）14. 无向连通图 G 的结点数为 v，边数为 e，就 G 当 v 与 e 满意 e=v -1 关系时是树15. 设个体

8、域 D 1, 2, 3 ， Px 为“x 小于 2”，就谓词公式xPx 的真值为假（或 F，或 0） 16. 命题公式 PQP 的真值是 T （或 1）17. 如图 G=中具有一条汉密尔顿回路，就对于结点集V 的每个非空子集S，在 G 中删除 S 中的全部结点得到的连通分支数为 W，就 S 中结点数 |S|与 W 满意的关系式为W|S|18. 给定一个序列集合 000 ，001 ，01 ， 10， 0 ，如去掉其中的元素0，就该序列集合构成前缀码19. 已知一棵无向树T 中有 8 个结点， 4 度， 3 度， 2 度的分支点各一个， T 的树叶数为520. xPxQxRx， y中的自由变元为

9、Rx， y 中的 y欢迎下载精品学习资源21设集合 A=0, 1, 2, 3，B=2, 3, 4, 5，R 是 A 到 B 的二元关系， Rx, yxA且yB且x, yAB 就 R 的欢迎下载精品学习资源有序对集合为 ， ， ， 22. 设 G 是连通平面图， v, e, r 分别表示 G 的结点数，边数和面数，就v，e 和 r 满意的关系式v-e+ r=2 23. 设 G 是有 6 个结点， 8 条边的连通图，就从G 中删去3条边，可以确定图G 的一棵生成树24. 无向图 G 存在欧拉回路，当且仅当G 连通且全部结点的度数全为偶数25. 设个体域 D 1,2 ，就谓词公式xAx 消去量词后的

10、等值式为A1A2 26. 设集合 A a，b，那么集合 A 的幂集是 ,a,b, a, b 27. 假如 R1 和 R 2 是 A 上的自反关系，就R 1R 2， R1R 2， R 1- R2 中自反关系有2个28. 设图 G 是有 6 个结点的连通图，结点的总度数为18 ，就可从 G 中删去4条边后使之变成树欢迎下载精品学习资源29. 设连通平面图G 的结点数为 5，边数为 6 ，就面数为330. 设个体域 D a, b，就谓词公式 xAx（ x） B（ x）消去量词后的等值式为A aA bB（ a）B（ b） 31. 设集合 A=0 ， 1 ， 2 ， B=l ， 2 ， 3 ， 剖， R

11、 是 A 到 B 的二元关系， R= |xA 且 y B 且 x， y AB 就 R 的有序对集合为 , 32. 设 G 是连通平面图， v， e ， r 分别表示 G 的结点数， 边数和面数， 就 v， e 和 r 满意的关系式 v-e+r=2 33. G= 是有 20 个结点， 25 条边的连通图 ,就从 G 中删去 6条边，可以确定图G 的一棵生成树 .34. 无向图 G 存在欧拉回路， 当且仅当 G 全部结点的度数全为偶数且_ 连通 35. 设个体域 D= 1, 2 ， 就谓词公式xAx 消去量词后的等值式为 A1 A2 三、化简解答题11 设集合 A=1 ， 2 ， 3 ， 4 ，

12、A 上的二元关系R ， R= 1 ， 1 ， 1 ， 4 ， 2 ， 2 ， 2 ， 3 ， 3 ， 2 ， 3 ，3 ， 4 ，1 ， 4 ， 4 ，说明 R 是 A 上的等价关系；欢迎下载精品学习资源解 从 R 的表达式知，xA, x, xR, 即 R 具有自反性；欢迎下载精品学习资源三、规律公式翻译1. 将语句“今日上课”翻译成命题公式设P：今日上课， 就命题公式为： P 2. 将语句“他去操场锤炼，仅当他有时间”翻译成命题公式设P：他去操场锤炼， Q：他有时间，就命题公式为： P Q3. 将语句“他是同学”翻译成命题公式设P：他是同学， 就命题公式为： P4. 将语句“假如明天不下雨，

13、我们就去郊游”翻译成命题公式设P：明天下雨， Q：我们就去郊游，就命题公式为：PQ5. 将语句“他不去学校”翻译成命题公式设P：他去学校，P6. 将语句“他去旅行，仅当他有时间”翻译成命题公式设P：他去旅行， Q：他有时间，PQ7. 将语句“全部的人都学习努力”翻译成命题公式设Px： x 是人， Qx： x 学习努力， （x） PxQx 8. 将语句“假如你去了，那么他就不去”翻译成命题公式设P：你去， Q：他去， PQ9. 将语句“小王去旅行，小李也去旅行”翻译成命题公式设P：小王去旅行， Q：小李去旅行， P Q10. 将语句“全部人都去工作”翻译成谓词公式设P x ： x 是人， Qx：

14、 x 去工作， xPxQx 11. 将语句“假如全部人今日都去参与活动，就明天的会议取消”翻译成命题公式 设 P：全部人今日都去参与活动，Q：明天的会议取消，PQ欢迎下载精品学习资源12. 将语句“今日没有人来” 翻译成命题公式设P：今日有人来，P13. 将语句“有人去上课” 翻译成谓词公式设Px： x 是人， Qx： x 去上课， xPx Qx1 1. 将语句 假如小李学习努力，那么他就会取得好成果. 翻译成命题公式 . 设 P：小李学习努力， Q:小李会取得好成果， PQ12. 将语句 小张学习努力 ,小王取得好成果 . 翻译成命题公式 .设 P：小张学习努力， Q:小王取得好成果，P Q

15、四、判定说明题1 设集合 A=1 ， 2 ， B=3 ，4 ，从 A 到 B 的关系为 f= ，就 f 是 A 到 B 的函数 错误由于 A 中元素 2 没有 B 中元素与之对应，故f 不是 A 到 B 的函数2. 设 G 是一个有 4 个结点 10 条边的连通图，就G 为平面图错误不满意“设G 是一个有 v 个结点 e 条边的连通简洁平面图，如v3 ，就 e 3v-6 ”3. 设 N、R 分别为自然数集与实数集，f： NR ，f x= x+6 ，就 f 是单射正确设 x1 ， x2 为自然数且 x1 x2 ，就有 fx1= x1 +6x2 +6= fx2 ，故 f 为单射4. 下面的推理是否

16、正确，试予以说明(1) （ x） F（x）G（x）前提引入2F（ y） G（ y）US （ 1） 错误（ 2 ）应为 F（y）G （x），换名时，约束变元与自由变元不能混淆5. 如图二所示的图G 存在一条欧拉回路图二错误 由于图 G 为中包含度数为奇数的结点6. 设 G 是一个有 6 个结点 14 条边的连通图，就G 为平面图欢迎下载精品学习资源错误不满意“设G 是一个有 v 个结点 e 条边的连通简洁平面图，如v3，就 e3 v-6 ”7. 假如 R1 和 R 2 是 A 上的自反关系，就R 1R2 是自反的正确R 1 和 R2 是自反的，xA， R1， R 2，就 R 1R2 ，所以 R

17、1R 2 是自反的8. 如图二所示的图G 存在一条欧拉回路v5dv4 egcv1fhn av2bv3图二正确由于图 G 为连通的，且其中每个顶点的度数为偶数9. P（PQ）P 为永真式正确P（PQ）P 是由P（PQ）与 P 组成的析取式，假如 P 的值为真，就 P（PQ）P 为真，假如 P 的值为假，就 P 与 PQ 为真，即 P（PQ）为真，也即P（PQ）P 为真，所以P（PQ）P 是永真式另种说明：P（PQ）P 是由P（PQ）与 P 组成的析取式，只要其中一项为真，就整个公式为真可以看到，不论P 的值为真或为假， P（PQ）与 P 总有一个为真，所以P（PQ）P 是永真式 或用等价演算 P

18、（PQ）PT10. 如偏序集 的哈斯图如图一所示，就集合A 的最大元为 a，最小元不存在欢迎下载精品学习资源图一正确对于集合 A 的任意元素x，均有 R（或 xRa），所以 a 是集合 A 中的最大元依据最小元的定义，在集合A 中不存在最小元11. 假如 R1 和 R 2 是 A 上的自反关系， 就 R1 R2 是自反的；正确， R1 和 R2，是自反的，xA, R1, R2,就 R1 R2 ，所以 R1R 2 是自反的 .12. 如图二所示的图中存在一条欧拉回路.图二正确，由于图G 为连通的，且其中每个顶点的度数为偶数；五运算题（每道题12 分，此题共 36 分）1. 试求出（ PQ）（RQ

19、）的析取范式（ PQ）（R Q）PQ（R Q ）PQ（R Q） PQRQ（析取范式）2 设 A=1, 1, 2 ， B=1, 2 ，试运算（ 1 ）（ AB）（ 2）（ AB）（ 3 ） A（AB）（ 1）（ AB） =1（2 ）（ AB）=1, 2, 1, 2（ 3 ） A （ AB） =1, 1, 2欢迎下载精品学习资源3 图 G=，其中 V= a, b, c, d ， E= a, b, a, c , a, d, b, c, b, d, c, d，对应边的权值依次为1、2 、3、 1、4及 5，试（ 1）画出 G 的图形；（ 2）写出 G 的邻接矩阵；（ 3）求出 G 权最小的生成树及其权

20、值a 3d2415（ 1） G 的图形表示如图一所示：b 1c图一0111101111011110a1（ 2）邻接矩阵：3d245（ 3）最小的生成树如图二中的粗线所示：b1c图二权为： 1+1+3=54. 画一棵带权为 1, 2, 2, 3, 4的最优二叉树 ,运算它们的权最优二叉树如图三所示1275342312欢迎下载精品学习资源图三权为 13+23+22+32+42=275. 求（ PQ）R 的析取范式与合取范式（ PQ）R（ PQ）RP QR（析取范式）PR Q R（合取范式）6 设 A=0 ，1 ， 2， 3， R=|xA，yA 且 x+y0 ，S=|xA， yA 且 x+y 2，试

21、求 R， S， R S， S -1 ，rRR=, S=,R S=，S -1= S，rR= IA=,7 试求出（ PQ）R 的析取范式，合取范式，主合取范式（ PQ）RPQR PQ R （析取范式） PR Q R （合取范式） PR QQ QR PP PRQ PR Q QR PQRP PQR PQR PQR8 设 A=a, b, 1, 2 ， B= a, b, 1, 1 ，试运算（ 1）（ A B）（ 2 ）（ AB）（ 3 ）（ AB） （ AB）（ 1）（ A B） =a, b, 2欢迎下载精品学习资源（ 3）（ AB） （ AB） = a, b, 2, a, b, 19 图 G=，其中 V

22、= a, b, c, d, e， E= a, b, a, c,2 、1、 2、3 、6 、1、4 及 5 ，试（ 1 ）画出 G 的图形；（ 2 ）写出 G 的邻接矩阵；（ 3 ）求出 G 权最小的生成树及其权值（ 1 ） G 的图形表示为：（ 2 ）邻接矩阵：（ 3 ）粗线表示最小的生成树，权为 7 ：10设谓词公式xP x, yzQ y, x, zyR y, z变元和约束变元（ 1） x 量词的辖域为 Px, yzQ y, x, z ，z 量词的辖域为 Q y, x, z ,（ 2）（ AB） = a, b, 1, 2,a, b, 1 a, e, b, d, b, e, c, e, c,

23、d, d, e ，对应边的权值依次为0110110011100110110111110F y ，试（ 1 ）写出量词的辖域；（ 2 ）指出该公式的自由欢迎下载精品学习资源y 量词的辖域为R y, z 欢迎下载精品学习资源（ 2 ）自由变元为 P x, yzQ y, x, z 与F y 中的 y，以及R y, z 中的 z欢迎下载精品学习资源约束变元为 x 与 Q y, x, z 中的 z，以及 R y, z 中的 y11设 A=1,2,1,2 ， B=1,2,1,2 ，试运算（ 1）（ A B）；（ 2 ）（ AB）；（ 3 ）AB（ 1） A B =1,2（ 2 ） AB =1,2（ 3 ）

24、 AB= ， ， ， ， ， ， ， ， ， ， ,12设 G=， V= v1 ， v2 ，v3， v4，v5， E= v1, v3， v2 ,v3 ， v2 ,v4 ，v3,v4 ，v3, v5 ， v4 ,v5 ，试（ 1 ）给出 G 的图形表示；（ 2）写出其邻接矩阵；（ 3 ）求出每个结点的度数；（ 4 ）画出其补图的图形（ 1） G 的图形表示为：（ 2 ）邻接矩阵：0010000110110110110100110（ 3 ） v1， v2， v3， v4 ，v5 结点的度数依次为1 ，2 ， 4， 3， 2（ 4 ）补图如下：欢迎下载精品学习资源13设集合 A=1 ， 2， 3，

25、4 ， R=|x, yA；| x y|=1 或 x y=0 ，试（ 1 ）写出 R 的有序对表示；（ 2 ）画出 R 的关系图；（ 3 ）说明 R 满意自反性，不满意传递性（ 1 ） R=,（ 2 ）关系图为21343 ）由于 ,均属于 R，即 A 的每个元素构成的有序对均在R 中，故 R 在 A 上是自反的；因有 与 属于 R，但 不属于 R，所以 R 在 A 上不是传递的；14. 求 PQ R 的析取范式，合取范式、主析取范式，主合取范式P（R Q）欢迎下载精品学习资源PR QPQR（析取、合取、主合取范式） PQRPQ R PQ R PQ RPQR PQ R PQR （主析取范式）15设

26、图 G=， V= v1 ， v2， v3， v4， v5， E= v1, v2 ， v1, v3 ， v2 , v3 ，v2, v4 ， v3 , v4， v3, v5 ， v4 , v5 ，试(1) 画出 G 的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出图 G 的补图的图形v1v2v5欢迎下载精品学习资源（ 1 ）关系图（ 2 ）邻接矩阵（ 3 ） deg v1 =2deg v2=3deg v3=4deg v4=3v3v40110010110110110110100110欢迎下载精品学习资源deg v5=2v1（ 4）补图 v2v513 / 35v3v4欢迎下

27、载精品学习资源16. 设谓词公式xAx,y zBx,y, z yCy,z 试(1) 写出量词的辖域；x 量词的辖域为 Ax,y zBx,y, z,z 量词的辖域为Bx,y,z,y 量词的辖域为Cy,z(2) 指出该公式的自由变元和约束变元.自由变元为 Ax,y zBx,y, z 中的 y, 以及 Cy,z 中的 z.约束变元为 Ax,y zBx,y, z 中的 x 与 Bx,y,z 中的 z, 以及 Cy,z 中的 y；六、证明题1. 试证明：如 R 与 S 是集合 A 上的自反关系，就R S 也是集合 A 上的自反关系证明：设xA，由于 R 自反，所以 x R x，即 R；又由于 S 自反，

28、所以 x R x，即 S 即RS故 R S 自反2. 试证明集合等式ABC =AB AC 证明：设 S= ABC，T= ABAC，如 xS，就 xA 或 xBC，即 xA 或 xB 且 xA 或 xC也即 xAB 且 xAC ，即 xT，所以 ST反之，如 xT，就 xAB 且 xAC， 即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS，所以 TS 因此 T=S3. 试证明集合等式ABC =AB AC欢迎下载精品学习资源证明：设 S=ABC，T=AB AC， 如 xS，就 xA 且 xBC ，即 xA 且 xB 或 xA 且 xC，也即 xAB 或 xAC ，即 xT

29、，所以 ST反之，如 xT，就 xAB 或 xAC，即 xA 且 xB 或 xA 且 xC也即 xA 且 xBC ，即 xS，所以 TS因此 T=S4. 试证明集合等式ABC =AB AC 证明：设 S= ABC，T= ABAC，如 xS，就 xA 或 xBC，即 xA 或 xB 且 xA 或 xC也即 xAB 且 xAC ，即 xT，所以 ST反之，如 xT，就 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS，所以 TS 因此 T=S5 试证明（ x）（ P（ x）R （x）（ x） P（ x）（ x）R（ x）证明：（ 1）（ x）（ P（

30、x）R （x）P（ 2） P（ a）R （ a）ES1（ 3） P（ a）T2I（ 4）（ x） P（ x）EG3（ 5） R（ a）T2I（ 6）（ x） R（ x）EG5（ 7）（ x） P（x）（ x） R（ x）T56I6. 设 m 是一个取定的正整数，证明：在任取m 1 个整数中，至少有两个整数，它们的差是m 的整数倍证明设 a1 ， a2 ， am 1 为任取的 m 1 个整数，用m 去除它们所得余数只能是0 ， 1， m 1 ，由抽屉原理可知，欢迎下载精品学习资源a1 ，a2 ，am 1 这 m 1 个整数中至少存在两个数as 和 at ，它们被 m 除所得余数相同，因此as 和

31、 at的差是 m 的整数欢迎下载精品学习资源倍；欢迎下载精品学习资源7. 已知 A、B 、C 是三个集合，证明A-B C=A-B A-C证明 xA- （B C）xAx（ B C ）xA（xBxC ）（ xA xB）（xAxC）x（A-B ）x（ A-C ）x（ A-B ）（A-C ）A-（ B C ）=（A-B ）（A-C ）8 （ 15 分）设 是半群，对 A 中任意元 a 和 b，如 a b 必有 a*b b*a ，证明：(1) 对 A 中每个元 a，有 a*a a；2 对 A 中任意元 a 和 b，有 a*b*a a；3 对 A 中任意元 a、 b 和 c，有 a*b*c a*c ；证明

32、 由题意可知，如 a*b b*a ，就必有 a b；1 由 a*a*a a*a*a ，所以 a*a a；2 由 a*a*b*a a*a*b*a a*b*a*a a*b*a*a ，所以有 a*b*a a；3 由 a*c*a*b*c a*c*a*b*c a*b*c a*b*c a*b*c*a*c a*b*c*a*c，所以有 a*b*c a*c；13. 设 A,B 为任意集合，证明： A-B-C = A-BC. 证明： A-B-C = A B C= A B C= A B C= A-B C9. 求命题公式 PQP Q 的主析取范式和主合取范式解： PQP QPQ P QP Q P QP Q P QPP

33、 Q Q P QP QM1m0 m2 m310. 例 5 在边长为 1 的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过 1/8 ；证明：把边长为1 的正方形分成四个全等的小正方形，就至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8 ；11. 试证明集合等式 AU B C=AUBAUC.证明：设 S=AUB C,T=AUBAUC, 如 xS, 就 x A 或 xB C，即 xA 或 x B 且 xA 或 x C, 也即 x AUB 且 xAUC,即 xT, 所以 sT.欢迎下载精品学习资源反之，如 xT, 就 xAUB 且 xAUC,即 xA 或 x B 且 xA 或 x C,也即 xA 或 x B C，即 xS, 所以 TS.因此 T=S.12. 利用形式演绎法证明：P