《离散数学复习题--修订编选》由会员分享，可在线阅读，更多相关《离散数学复习题--修订编选（14页珍藏版）》请在金锄头文库上搜索。
1、v1.0 可编辑可修改 1 一、单项选择题 1对任意集合A、B 、C，下述论断正确的是【 A 】 （ A）若 AB，BC，则 AC （B）若 AB，BC ，则 AC （ C）若 AB，BC，则 AC （D）若 AB，BC ，则 AC 2设aaA,，则下列选项错误的是【 B 】 （ A）)(APa（ B ）)(APa（C）)(APA（D）)(APA 3设cbaA,上的关系如下，有传递关系的有【 D 】 （ A）abbaaccaR, 1 （ B）accaR, 2 （ C）cbabccbaR, 3 （D）, 4 aaR 4R是 A上的自反关系，则【 B 】 （ A）RRR（ B）RRR（C） A I
2、RR（D） A IRR 5 4 K中含 3 条边的不同构生成子图有【 C 】 （A）1 个（B）2 个（C）3个（D）4 个 6设EVG,为无向图，Vvu, 若vu,连通，则【 D 】 （A）0),(vud（B）0),(vud（C）0),(vud（D）0),(vud 7欧拉回路是【 B 】 （A）路径（B ）简单回路 （C）既是基本回路也是简单回路（D ）既非基本回路也非简单回路 85 阶无向完全图的边数是【 B 】 ： （A）5 （B）10 （C） 15 （D）20 9设 Acba,，B edcb,，Ccb,，则（ AB） C 为【 C 】 （ A）ba,（B）cb,（C ）eda,（D）c
3、ba, 10 设A，)(APPB则下列选项错误的是【 D 】 v1.0 可编辑可修改 2 （ A）B（B）B（C）B（D）)(,AP 11集合10,2, 1A上的关系AyAxyxyxR,10|, 则 R的性质为 【 B 】 （ A）自反的（B ）对称的（C）传递的、对称的（D）反自反的、传递的 12 设 R是非空集A上的二元关系，则R的对称闭包s(R) 【 B 】 （ A） A IR（B）RR （C） A IR（D）RR 13 若简单图G与其补图G同构，称G为自补图，则含有5 个结点不同构的无向自补图的 个数为【 C 】 （A）0 （B） 1 （C）2 （D ） 3 14设EVG,为无向图，V
4、vu, 若vu,连通，则【 D 】 （A）0),(vud（B）0),(vud（C）0),(vud（D）0),(vud 15欧拉回路是【 B 】 （A）路径（B ）简单回路 （C）既是基本回路也是简单回路（D ）既非基本回路也非简单回路 16n个结点的无向完全图的边数是【 D 】 ： （A）)1(nn（B） 2 n（ C ）n2（D）2/)1(nn 17设 P:我将去镇上 ,Q: 我有时间。命题“我将去镇上, 仅当我有时间时”符号化为【 A 】 (A) PQ, (B) QP , (C) QP , (D) Q P 18下面哪个命题是命题“2 是偶数或 3 是负数”的否定【 C 】 (A) 2 是偶
5、数或 3 不是负数 , (B) 2是奇数或 3 不是负数 , (C) 2不是偶数且 3 不是负数 , (D) 2是奇数且 3 是不负数 , 19下面哪个联结词运算不可交换 : 【 B 】 (A) , (B) , (C) , (D) 20 命题公式 (P(PQ)Q 是 ; 【 C 】 (A) 矛盾式 , (B) 蕴含式 , (C) 重言式 , (D) 等值式 v1.0 可编辑可修改 3 21 下列命题联结词集合中, 哪个是最小联结词组; 【 C 】 (A) , (B) , (C) (D) , 22下面那一个命题是假命题; 【 A 】 (A) 如果 2 是偶数 , 那么一个公式的析取范式唯一, (
6、B) 如果 2 是偶数 , 那么一个公式的析取范式不唯一, (C) 如果 2 是奇数 ,那么一个公式的析取范式唯一, (D) 如果 2 是奇数 ,那么一个公式的析取范式不唯一 23谓词公式)()()(xQyyRxPx中变元x是; 【 D 】 （ A）自由变元 , (B) 约束变元 , (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元 24设)(xA:x是人 , )(xB:x犯错误 , 命题“没有不犯错误的人”符号化为; 【 D 】 (A)()(xBxAx, (B)()(xBxAx, (C) )()(xBxAx, (D) )()(xBxAx 25命题公式 (P Q)R的成
7、真赋值为 ; 【 B 】 (A)000, 001,110 (B) 001, 011, 101,110,111 (C) 全体赋值 (D) 无 26下面语句中哪个是真命题；【 D 】 (A) 我在说谎 , (B) 严禁吸烟 , (C) 如果 1+2=3, 那么雪是黑的 , (D) 如果 1+2=5, 那么雪是黑的 27设 P:我们划船 ,Q: 我们跑步。命题“我们不能既划船又跑步”符号化为【 B 】 (A) PQ, (B) PQ , (C) （PQ ） , (D) PQ 28下面哪个命题是命题“2 是偶数或 3 是负数”的否定【 C 】 。 (B) 2 是偶数或 3 不是负数 , (B) 2是奇数
8、或 3 不是负数 , (C) 2不是偶数且 3 不是负数 , (D) 2是奇数且 3 是不负数 , 29下面哪个联结词运算不可交换【 C】 。 (A) , (B) , (C) , (D) v1.0 可编辑可修改 4 30 下面哪个命题公式是重言式【 B】 。 (A) (PQ) (QP), (B) (PQ)P, (C) (PQ)(PQ) , (D) （PQ ） 31下列命题联结词集合中, 哪个不是最小联结词组【C 】 。 (A) , (B) , (C) , (D) 32命题公式PQR的对偶式是【D 】 。 (C) P（ Q R）, （B）P（ Q R） ， （ C ）P（ Q R） ， （D）P
9、（ Q R） 33谓词公式)()()(xQyyRxPx中变元x是【D】 。 （A）自由变元 , (B) 约束变元 , (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元 34设)(xC:x 是运动员 , )(xG:x是强壮的 , 命题“没有一个运动员不是强壮的”符号化为 【 C 】 。 (A)()(xGxCx, (B)()(xGxCx, (C) )()(xGxCx, (D) )()(xGxCx 35),(yxyPx的否定是【 B 】 。 (A) ),(yxPyx， (B) ),(yxPyx，(C) ),(yxPyx， (D) ),(yxPyx 36在谓词演算中，下列各式正
10、确的是【 A 】 ： (A) ),(),(yxxAyyxyAx, (B) ),(),(yxxAyyxyAx, (C) ),(),(yxxByyxyAx, (D) ),(),(yxyAxyxyAx 二、填空题 1. 若 集合 A的基数10A，则其幂集的基数)(Ap 1024 。 2. 设ZxZnnxxxA,37,200100|，则| A 15 。 3. 设 N表示非负整数集， ， R：NN，xRy 定义为 x+2y10，则 Dom(R)0,2,4,6,8,10 v1.0 可编辑可修改 5 Ran(R) 5,4,3,2,1,0 =24,12,10,8 ,6 ,5,4,3,2,R 是 A上的整除关系
11、，那么A的极大元是 10 ，24 , 极小元是 2 ，3， 5 , 。 5. 设 A=3 ,2, 1上的关系3 ,3,3 , 1,2 , 1,1 , 1R，则 R 具备反对称性、传递 性， R不具备自反性、反自反性和对称性。 6. 设 G= （n,m）是简单图 ,v 是 G中度数为k 的结点， e 是 G中的一条边，则Ge 中有 n 个 结点， m 1 条边。 7. 3个结点可构成 4 个不同构的简单无向图。 8. 具有 p 个顶点的完全图K p 有 2p p个生成树， p2。 9. 设 G是一个有k 个支的图，如果S是 G的割集，则G-S 恰有 k+1 个支。 10. 设 A=2, 1，则
12、AA=，A 2 。 11. 集合aA，的幂集)(APaa,。 12. 设 R是集合10,2 ,1上的模 7 同余关系，则 . R 29, 2。 13. A=24,12,10,8 ,6, 5 ,4,3 ,2,R 是 A上的整除关系， 那么 A的极大元是 10 ， 24 , 极小元是 2 ， 3，5 , 。 14. 整数集上的小于关系“”具有反自反、 反对称和传递性。 15. 设 G= （ n,m）是简单图 ,v 是 G中度数为k 的结点， e 是 G中的一条边， 则 Gv 中有 n1 个结点， m k 条边。 个结点可构成 4 个不同构的简单无向图。 17. 具有 p个顶点的完全图K p 有 2
13、p p个生成树， p2。 18. 设 S是连通图G= （V，E）的割集，则G-S 恰有 2 个支。 19. 设 P: 我生病 ,Q: 我去学校看电影 (1) 命题“我虽然生病但我仍去学校”符号化为 P Q 。 (2) 命题“只有在生病的时候，我才不去学校”符号化为PQ 。 20. 设 P、Q为两个命题，德摩根律可表示为QPQP)(， （或 v1.0 可编辑可修改 6 QPQP)(） ， 吸收律可表示为PQPp)(（或PQPp)(） 。 21. 公式)(QP的主析取范式为QP, 主合取范式的编码表示为 310 MMM。 22.),(),(),(yxxPzyGyxFyx中,x的作用域为),(),(
14、zyGyxFy, y的作用域为 ),(),(zyGyxF, x的作用域为),(yxP。 23. 谓词公式)()(xxGxxF的前束范式为)()(yGxFyx。 24. 设 P:我有钱 ,Q: 我去看电影 (1) 命题“如果我有钱, 那么我就去看电影”符号化为QP。 (2) 命题“虽然我有钱, 但我不去看电影”符号化为QP。 25. 命题公式 )(SQP 的成真赋值为 010 ， 100 ， 101 ， 110 ，111 , 成假赋值为 000 ， 001，011。 26. 公式)(QP的主析取范式为QP, 主合取范式的编码表示为 310 MMM。 27. ),(),(),(yxxPzyQyxP
15、yx中,x的作用域为),(),(zyQyxPy, y的作用域为 ),(),(zyQyxP, x的作用域为),(yxP。 28. 谓词公式)()()(yyRxxQxxP的前束范式为)()()(yRzQxPyzx。 三、计算题 1、用等值演算法化简并判断下列公式的类型(P(QR) (QR)(P Q) 解：原式(P(Q R) (Q P)R) (PQ)R) (Q P)R) (PQ)R) (Q P)R) (PQ)(QP) R) (PQ)(PQ) R) T R R 故原式为可满足式 v1.0 可编辑可修改 7 2、求命题公式(pq)（pq）的合取范式、析取范式、主合取范式和主析取范 式。 解：合取范式： (pq)（pq）=(pq)（ （pq）（qp） ） =(pq) （pq）（ pq） = (pq) （pq）（ pq） = pq 析取范式： (pq)（pq）=(pq)（ （pq）（pq） ） =
