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

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

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设S 1,S 2,S 3P ,S 4P 就命题为假的是（S 2S 4）；4设 G 是有 n 个结点的无向完全图,就G 的边数（ 1/2 n （ n-1 ）；5设 G 是连通平面图,有v 个结点, e 条边, r 个面,就 r=（ e-v+2 ）；6如

2、集合 A=1 ,2 ,1,2,就以下表述正确选项 1A 7已知一棵无向树T 中有 8 个顶点, 4 度、 3 度、 2 度的分支点各一个,T 的树叶数为 5 011118设无向图G 的邻接矩阵为10011就 G 的边数为 7 1000011001110109设集合 A=a,就 A 的幂集为 ,a 10以下公式中 AB A B 为永真式11如 G 是一个汉密尔顿图,就G 肯定是 连通图 12集合 A=1, 2, 3, 4 上的关系 R=|x=y 且 x, yA,就 R 的性质为（传递的）13设集合 A=1 ,2,3,4,5,偏序关系是 A 上的整除关系,就偏序集上的元素 5 是集合 A 的（极大

3、元14图 G 如图一所示,以下说法正确选项 a, d , b, d是边割集 图一15设 A（x）： x 是人, B（x）： x 是工人,就命题“ 有人是工人” 可符号化为（ xAxBx ）16如集合 A=1 ,2,B=1, 2,1,2 ,就以下表述正确选项 A B,且 A B 17设有向图（ a）、（ b）、（ c）与（ d）如图一所示,就以下结论成立的是 （ d）是强连通的 名师归纳总结 1 / 35 第 1 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - 011001 0 0 1 118设图 G 的邻接矩阵为 1 0 0 0 0 就 G 的边数为

4、 5 0 1 0 0 10 1 0 1 019无向简洁图 G 是棵树,当且仅当 G 连通且边数比结点数少 1 20以下公式 P Q P P P Q 为重言式21如集合 A a, a,1,2 ,就以下表述正确选项 a A22设图 G,v V,就以下结论成立的是 deg v 2 E v V23命题公式（ PQ）R 的析取范式是 （P Q ）R 24以下等价公式成立的为 P Q P P P Q 25设 A=a, b, B=1, 2,R1, R2,R3 是 A 到 B 的二元关系,且 1 ,R3=, ,就（ R2 ）不是从 A 到 B 的函数R1=, ,R2=, , b,26设 A=1, 2, 3,

5、4, 5, 6, 7, 8 ,R 是 A 上的整除关系,B=2, 4, 6,就集合B 的最大元、最小元、上界、下界依次为无、 2、无、 227如集合 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 为重言式,如A CBC,那么 AB 是重言式（重言式、冲突式或可满意式）；2命题公式（ PQ）P 的主

6、合取范式为PQPQ；3设集合 A=,a ,就 P（A）=,a ,a ；第 2 页,共 35 页名师归纳总结 2 / 35 - - - - - - -精选学习资料 - - - - - - - - - 4设图 G = V,E, G =V ,E ,如 V =V,E E , 就 G 是G 的生成子图；r假5在平面 G =V,E中,就deg ir=2|E| ,其中ir （i=1 ,2, , r）是 G 的面； 6命题公式PP的真值是i1（或 F,或 0）7如无向树T 有 5 个结点,就T 的边数为 4 8设正就 m 叉树的树叶数为t,分支数为i,就 m-1 i= t-1 9设集合 A=1 ,2上的关系

7、R, ,就在 R 中仅需加一个元素 ,就可使新得到的关系为对称的10xAxBx,zCy中的自由变元有 z, y ）,就复合函数g f =, 2, 11如集合 A=1,3,5,7, B=2 ,4,6,8,就 AB=空集（或12设集合 A=1 ,2,3上的函数分别为：f=,g=,3, , 13设 G 是一个图,结点集合为 V,边集合为 E,就 G 的结点度数之和为 2|E|（或“ 边数的两倍” ）14无向连通图 G 的结点数为 v,边数为 e,就 G 当 v 与 e 满意 e=v-1 关系时是树15设个体域 D1, 2, 3 , Px为“x 小于 2” ,就谓词公式 xPx 的真值为假（或 F,或

8、 0） 16命题公式 P Q P 的真值是 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 的树叶数为 5 20 xPxQxRx,y中的自由变元为 Rx,y 中的 y21设集合 A=0, 1, 2, 3,B=2, 3, 4, 5,R 是 A 到

9、B 的二元关系,R x , y x A 且 y B 且 x , y A B 就 R 的有序对集合为 , , , 22设 G 是连通平面图,v, e, r 分别表示G 的结点数,边数和面数,就v,e 和 r 满意的关系式v-e+r=2第 3 页,共 35 页23设 G是有 6 个结点, 8 条边的连通图,就从G 中删去 3 条边,可以确定图G 的一棵生成树24无向图 G 存在欧拉回路,当且仅当G 连通且全部结点的度数全为偶数25设个体域D1,2 ,就谓词公式xAx消去量词后的等值式为A1 A226设集合 Aa,b,那么集合A 的幂集是 ,a,b,a,b 27假如 R1 和 R2 是 A 上的自反

10、关系,就R1R2, R1R2,R1-R2 中自反关系有 2 个28设图 G 是有 6 个结点的连通图,结点的总度数为18 ,就可从 G 中删去 4 条边后使之变成树名师归纳总结 - - - - - - -3 / 35 精选学习资料 - - - - - - - - - 29设连通平面图 G 的结点数为 5,边数为 6,就面数为 3 30设个体域 Da, b,就谓词公式 xAx（ x）B（x）消去量词后的等值式为 A aA bB（ a）B（b） 31. 设集合 A=0 ,1 ,2 ,B=l ,2 , 3 , 剖, R 是 A 到 B 的二元关系, R= |x A 且 yB 且 x, y AB 就

11、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, A 上的二元关系R,R= 1, 1, 1,4, 2, 2, 2,3, 3,2,

12、 3,3, 4,1, 4,4,说明 R 是 A 上的等价关系；解从 R 的表达式知,xA ,x,xR,即 R 具有自反性；三、规律公式翻译1将语句“ 今日上课” 翻译成命题公式设P：今日上课,就命题公式为：PQ：他有时间,就命题公式为：P 2将语句“ 他去操场锤炼,仅当他有时间” 翻译成命题公式设P：他去操场锤炼,Q3将语句“ 他是同学” 翻译成命题公式设 P：他是同学,就命题公式为：P4将语句“ 假如明天不下雨,我们就去郊游” 翻译成命题公式设 P：明天下雨,Q：我们就去郊游,就命题公式为：P Q5将语句“ 他不去学校” 翻译成命题公式设 P：他去学校,P6将语句“ 他去旅行,仅当他有时间”

13、 翻译成命题公式设 P：他去旅行, Q：他有时间,P Q7将语句“ 全部的人都学习努力” 翻译成命题公式设 Px：x 是人, Qx：x 学习努力,（x） Px Qx8将语句“ 假如你去了,那么他就不去” 翻译成命题公式设 P：你去, Q：他去,P Q9将语句“ 小王去旅行,小李也去旅行” 翻译成命题公式设 P：小王去旅行,Q：小李去旅行,P Q10将语句“ 全部人都去工作” 翻译成谓词公式设 Px：x 是人, Qx：x 去工作, xPx Qx11将语句“ 假如全部人今日都去参与活动,就明天的会议取消” 翻译成命题公式设 P：全部人今日都去参与活动,Q：明天的会议取消,PQ第 4 页,共 35

14、页名师归纳总结 4 / 35 - - - - - - -精选学习资料 - - - - - - - - - 12将语句“ 今日没有人来”翻译成命题公式设 P：今日有人来,P13将语句“ 有人去上课”翻译成谓词公式设 Px：x 是人, Qx：x 去上课, xPx Qx1 1. 将语句 假如小李学习努力,那么他就会取得好成果 . 翻译成命题公式 . 设 P：小李学习努力,Q:小李会取得好成果,PQ 12. 将语句 小张学习努力 ,小王取得好成果. 翻译成命题公式.设 P：小张学习努力,Q:小王取得好成果,PQ 四、判定说明题1设集合 A=1 ,2,B=3 ,4,从 A 到 B 的关系为 f= ,就

15、f 是 A 到 B 的函数错误由于 A 中元素 2 没有 B 中元素与之对应,故 f 不是 A 到 B 的函数2设 G 是一个有 4 个结点 10 条边的连通图,就 G 为平面图错误不满意“ 设G 是一个有 v 个结点 e 条边的连通简洁平面图,如 v3,就 e3v-6 ”3设 N、R 分别为自然数集与实数集,f： NR,f x=x+6 ,就 f 是单射正确设 x1,x2 为自然数且x1 x2,就有 fx1= x1+6 x2+6= fx2,故 f 为单射4下面的推理是否正确,试予以说明 1 （x）F（x）G（x）前提引入 2 F（y）G（y） US （1）错误（2）应为 F（y）G（x）,换名

16、时,约束变元与自由变元不能混淆5如图二所示的图 G 存在一条欧拉回路图二错误 由于图 G 为中包含度数为奇数的结点6设 G 是一个有 6 个结点 14 条边的连通图,就G 为平面图第 5 页,共 35 页名师归纳总结 5 / 35 - - - - - - -精选学习资料 - - - - - - - - - 错误不满意“ 设G 是一个有 v 个结点 e 条边的连通简洁平面图,如 v3,就 e3v-6”7假如 R1 和 R2 是 A 上的自反关系,就 R1R2 是自反的正确R1 和 R2 是自反的,x A, R1, R2,就 R1 R2,所以 R1R2 是自反的8如图二所示的图 G 存在一条欧拉回

17、路v5 d v4e gv1 f h n cav2 b v3图二正确由于图 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（PQ）PT A 的最大元为a,最小元不

18、存在第 6 页,共 35 页10如偏序集 的哈斯图如图一所示,就集合名师归纳总结 6 / 35 - - - - - - -精选学习资料 - - - - - - - - - 图一正确对于集合A 的任意元素x,均有 R（或 xRa）,所以a 是集合 A 中的最大元依据最小元的定义,在集合A 中不存在最小元11. 假如 R1 和 R 2 是 A 上的自反关系,就 R1R2 是自反的；正确, R1 和 R2,是自反的,xA, R1, R2,就 R1R2,所以 R1R 2 是自反的 . 12. 如图二所示的图中存在一条欧拉回路 . 图二正确,由于图 G 为连通的,且其中每个顶点的度数为偶数；五运算题（每

19、道题12 分,此题共36 分）1试求出（ PQ）（RQ）的析取范式（PQ）（RQ）PQ（RQ） PQ（RQ） 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 名师归纳总结 7 / 35 第 7 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - 3图 G=,其中 V= a, b, c, d ,E= a, b, a, c , a, d, b, c, b, d, c, d,对应边的权值

20、依次为 1、2、3、 1、4及 5,试（1）画出 G 的图形；（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值a 3 4 d 1 2 1 5 （1）G 的图形表示如图一所示：c b 图一0111（2）邻接矩阵：1011a 2 3 4 d 110111101 5 （3）最小的生成树如图二中的粗线所示：b 1 c 图二权为： 1+1+3=5 4画一棵带权为1, 2, 2, 3, 4的最优二叉树 ,运算它们的权最优二叉树如图三所示7 12 5 3 名师归纳总结 1 2 4 2 3 8 / 35 第 8 页,共 35 页- - - - - - -精选学习资料 - - - - - -

21、- - - 图三权为 1 3+23+22+32+42=27 5求（ PQ）R 的析取范式与合取范式（PQ）R（PQ）R P QR （析取范式） PR QR （合取范式）6设 A=0 ,1,2, 3,R=|x A,y A 且 x+y0 ,S=|x A,y A 且 x+y 2,试求 R, S, R S,S -1,rRR= , S=, ,R S= S -1= S,rR=IA=,7试求出（ PQ）R 的析取范式,合取范式,主合取范式（PQ）RPQR PQR（析取范式） PR QR（合取范式） PRQQ QRPP PRQPRQ QRP QRP PQRPQR PQR 8设 A=a, b, 1, 2 ,B=

22、 a, b, 1, 1 ,试运算（ 1）（ A B）（2）（ AB）（3）（ AB） （AB）（ 1）（ A B）=a, b, 2 名师归纳总结 9 / 35 第 9 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - （ 2）（ AB）=a, b, 1, 2, a, b, 1 （ 3）（ AB） （AB）=a, b, 2, a, b, 1 9图 G=,其中 V= a, b, c, d, e, E= a, b, a, c, a, e, b, d, b, e, c, e, c, d, d, e ,对应边的权值依次为 2、1、 2、3、6、1、4 及 5,试

23、（1）画出 G 的图形；（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值（1）G 的图形表示为：（2）邻接矩阵：0110110011100110110111110（3）粗线表示最小的生成树,权为 7：10设谓词公式xPx,yzQy,x ,zyRy ,z Fy ,试（ 1）写出量词的辖域；（2）指出该公式的自由变元和约束变元（1） x 量词的辖域为,Px,yzQy ,x ,z ,10 / 35 第 10 页,共 35 页z 量词的辖域为Qyx,z , 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - y 量词的辖域为R y,z yzQy,

24、x,z 与F y中的 y,以及R y,z 中的 z（2）自由变元为P x,约束变元为x 与Qy,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）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 的图形表示为

25、：（2）邻接矩阵：0 0 1 0 00 0 1 1 01 1 0 1 10 1 1 0 10 0 1 1 0（3）v1,v2, v3,v4,v5 结点的度数依次为 1,2,4,3, 2 （4）补图如下：名师归纳总结 11 / 35 第 11 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - 13设集合 A=1 ,2,3,4, R=|x, y A；|x y|=1 或 x y=0 ,试（1）写出 R 的有序对表示；（2）画出 R 的关系图；（3）说明 R 满意自反性,不满意传递性（1）R=, （2）关系图为2 13 4 3）由于 ,均属于 R,即 A 的每

26、个元素构成的有序对均在R 中,故 R 在 A 上是自反的；因有 与 属于 R,但 不属于 R,所以 R 在 A 上不是传递的；14求 P Q R 的析取范式,合取范式、主析取范式,主合取范式P（RQ）名师归纳总结 12 / 35 第 12 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - PRQ PQR（析取、合取、主合取范式）PQRPQR PQR PQR PQR PQR PQR （主析取范式）15设图 G=,V= v1,v2,v3,v4,v5,E= v1, v2,v1, v3,v2, v3,v2, v4,v3, v4,v3, v5,v4, v5 ,试

27、 1 画出 G 的图形表示；2 写出其邻接矩阵；3 求出每个结点的度数；4 画出图 G 的补图的图形v1 （1）关系图v2 v3 11v4 v5 000（2）邻接矩阵10110110110110100110（3）deg v1=2 deg v2=3 deg v3=4 deg v4=3 deg v5=2 v1 v4 v5 13 / 35 第 13 页,共 35 页（4）补图v2 名师归纳总结 - - - - - - -v3 精选学习资料 - - - - - - - - - 16设谓词公式 xAx,y zBx,y, z yCy,z 试 1 写出量词的辖域；x 量词的辖域为 Ax,y zBx,y, z

28、, 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 上的自反关系,就 RS 也是集合 A 上的自反关系证明：设 x A,由于 R 自反,所以 x R x,即 R；又由于 S 自反,所以 x R x,即 S即 RS 故 RS 自反2试证明集合等式 A B C=A B A C 证明：设 S= A B C,T=A B A C

29、,如 xS,就 xA 或 xB C,即 xA 或 xB 且 xA 或 xC也即 xA B 且 xA C ,即 xT,所以 S T反之,如 xT,就 xA B 且 xA C, 即 xA 或 xB 且 xA 或 xC,也即 xA 或 xB C,即 xS,所以 T S因此 T=S3试证明集合等式A BC=AB AC14 / 35 第 14 页,共 35 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 证明：设 S=ABC,T=ABAC, 如 xS,就 xA 且 xBC,即 xA 且 xB 或 xA 且 xC,也即 xAB 或 xAC ,即 xT,所以 S

30、T反之,如 xT,就 xAB 或 xAC,即 xA 且 xB 或 xA 且 xC也即 xA 且 xBC,即 xS,所以 T S因此 T=S4试证明集合等式 A B C=A B A C 证明：设 S= A B C,T=A B A C,如 xS,就 xA 或 xB C,即 xA 或 xB 且 xA 或 xC也即 xA B 且 xA C ,即 xT,所以 S T反之,如 xT,就 xA B 且 xA C,即 xA 或 xB 且 xA 或 xC,也即 xA 或 xB C,即 xS,所以 T S因此 T=S5试证明（x）（ P（x）R（x）（ x）P（x）（ x）R（x）证明：（1）（x）（ P（x）R

31、（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） T56I 6设 m 是一个取定的正整数,证明：在任取 m1 个整数中,至少有两个整数,它们的差是 m 的整数倍证明 设 a ,a , ,a m 1 为任取的 m1 个整数,用 m 去除它们所得余数只能是 0,1, , m1,由抽屉原理可知,a ,a , ,a m 1 这 m1 个整数中至少存在两个数 sa和 ta,它们被 m 除所得余数相同,因此 a 和 ta的差是 m 的整数倍；名师归纳总结 15 /

32、 35 第 15 页,共 35 页- - - - - - -精选学习资料 - - - - - - - - - 7已知 A、B、C 是三个集合,证明 A-B C=A-B A-C 证明x A-（BC）x Ax（BC）x A（x Bx C）（ x Ax B）（x Ax C）x（A-B ）x（A-C ） x（A-B ）（A-C ）A-（BC）=（A-B ）（A-C ）8（ 15 分）设 是半群,对 A 中任意元 a 和 b,如 ab 必有 a*b b*a ,证明：1 对 A 中每个元 a,有 a*a a；2 对 A 中任意元 a 和 b,有 a*b*a a；3对 A 中任意元 a、 b 和 c,有 a

33、*b*c a*c ；证明由题意可知,如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 C 9求命题公式 P Q P Q 的主析取范式和主合取范式解： P Q P Q P Q P Q

34、PQ P Q P Q P Q PP Q Q P Q P Q M1 m0 m2 m3 10例 5 在边长为 1 的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形（可能是退化的）面积不超过 1/8 ；证明：把边长为 1 的正方形分成四个全等的小正方形,就至少有一个小正方形内有三个点,它们组成的三角形（可能是退化的）面积不超过小正方形的一半,即 1/8；11. 试证明集合等式 AU B C=AUB AUC. 证明：设 S=AUB C,T=AUB AUC, 如 xS,就 xA 或 xBC,即 xA 或 xB 且 xA 或 xC,也即 xAUB 且 xAUC, 即 xT,所以 sT. 16 / 35 第 16 页,共 35 页名师归纳总结 - - - - - - -精选学习资料 - - -