离散数学复习题

一、单项选择题

1．对任意集合A、B、C，下述论断正确的是 【 A 】 （A）若A?B，B?C，则 A?C （B）若A?B，B?C，则 A?C （C）若A?B，B?C，则 A?C （D）若A?B，B?C，则 A?C

2．设A??a,?a??，则下列选项错误的是 【 B 】 （A）?a??P(A) （B）?a??P(A) （C）??A???P(A) （D）??A???P(A) 3．设A??a,b,c?上的关系如下，有传递关系的有 【 D 】 （A）R1???a,c?,?c,a?,?a,b?,?b,a?? （B）R2???a,c?,?c,a?? （C）R3???a,b?,?c,c?,?b,a?,?b,c?? （D）R4???a,a?,? 4．R是A上的自反关系，则 【 B 】 （A）R?R?R （B）R?R?R （C）R?R?IA （D）R?R?IA 5．K4中含3条边的不同构生成子图有 【 C 】 （A）1个 （B）2个 （C）3个 （D）4个

6．设G?V,E为无向图，u,v?V,若u,v连通，则 【 D 】 （A）d(u,v)?0 （B）d(u,v)?0 （C）d(u,v)?0 （D）d(u,v)?0 7．欧拉回路是 【 B 】 （A）路径 （B）简单回路

（C）既是基本回路也是简单回路 （D）既非基本回路也非简单回路 8．5阶无向完全图的边数是 【 B 】： （A）5 （B）10 （C）15 （D）20

9．设A＝?a,b,c? ，B＝?b,c,d,e? ，C＝?b,c?，则（A∪B）? C为 【 C 】 （A）?a,b? （B）?b,c? （C）?a,d,e? （D）?a,b,c?

??，B?P(P(A))则下列选项错误的是 【 D 】 10．设A?????B （C）??????B （D）??,?????P(A) （A）??B （B）?1,2,?,10?上的关系R???x,y?|x?y?10,x?A,y?A?, 则R的性质为 11．集合A?? 【 B 】 （A）自反的 （B）对称的 （C）传递的、对称的 （D）反自反的、传递的 12．设R是非空集A上的二元关系，则R的对称闭包s(R)＝ 【 B 】 （A）R?IA （B）R?R （C）R?IA （D）R?R

13．若简单图G与其补图G同构，称G为自补图，则含有5个结点不同构的无向自补图的个数为 【 C 】 （A）0 （B）1 （C）2 （D）3

14．设G?V,E为无向图，u,v?V,若u,v连通，则 【 D 】 （A）d(u,v)?0 （B）d(u,v)?0 （C）d(u,v)?0 （D）d(u,v)?0 15．欧拉回路是 【 B 】 （A）路径 （B）简单回路

（C）既是基本回路也是简单回路 （D）既非基本回路也非简单回路 16．n个结点的无向完全图的边数是 【 D 】： （A）n(n?1) （B）n （C）2n （D）n(n?1)/2

17．设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为【 A 】 (A) P?Q, (B) Q?P , (C) Q?P , (D) ?Q∨?P

18．下面哪个命题是命题“2是偶数或－3是负数”的否定？ 【 C 】 (A) 2是偶数或－3不是负数, (B) 2是奇数或－3不是负数, (C) 2不是偶数且－3不是负数, (D) 2是奇数且－3是不负数,

19．下面哪个联结词运算不可交换 : 【 B 】 (A) ∧, (B)

2~~? , (C) ∨ , (D) ?

20． 命题公式(P∧(P?Q))?Q 是 ; 【 C 】 (A) 矛盾式, (B) 蕴含式, (C) 重言式 , (D) 等值式

21．下列命题联结词集合中,哪个是最小联结词组; 【 C 】 (A) ??,??, (B) ??,?,?? (C) ? (D) ??,??

22．下面那一个命题是假命题; 【 A 】 (A) 如果2是偶数,那么一个公式的析取范式唯一, (B) 如果2是偶数,那么一个公式的析取范式不唯一, (C) 如果2是奇数,那么一个公式的析取范式唯一,

??(D) 如果2是奇数,那么一个公式的析取范式不唯一

23．谓词公式?x(P(x)??yR(y))?Q(x)中变元x是; 【 D 】 （A）自由变元, (B) 约束变元, (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元

24．设A(x):x是人, B(x):x犯错误,命题“没有不犯错误的人”符号化为; 【 D 】(A)?x(A(x)?B(x)), (B)??x(A(x)??B(x)), (C) ??x(A(x)?B(x)), (D) ??x(A(x)??B(x))

25．命题公式? (P∧Q)?R的成真赋值为; 【 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) ?P∧?Q, (B) ?P∨?Q , (C) ?（P?Q）, (D) P??Q 28．下面哪个命题是命题“2是偶数或－3是负数”的否定？【 C 】。 (B) 2是偶数或－3不是负数, (B) 2是奇数或－3不是负数, (C) 2不是偶数且－3不是负数, (D) 2是奇数且－3是不负数, 29．下面哪个联结词运算不可交换【 C 】。 (A) ∧, (B) ∨, (C)

?, (D) ?

30． 下面哪个命题公式是重言式 【 B 】。 (A) (P?Q)∧(Q?P), (B) (P∧Q)?P, (C) (?P∨Q)∧?(?P∧?Q) , (D) ?（P∨Q）

31．下列命题联结词集合中,哪个不是最小联结词组【 C 】。 (A) ??,??, (B) ??,?? (C) ??,?,?? (D) ? 32．命题公式P?Q∧R的对偶式是【 D 】。

(C) P?（Q∨R）, （B）P∧（Q∨R）， （C）?P∨（Q∧R）， （D）?P∧（Q∨R） 33．谓词公式?x(P(x)??yR(y))?Q(x)中变元x是【 D 】。

??（A）自由变元, (B) 约束变元,

(C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元

34．设C(x):x是运动员, G(x):x是强壮的,命题“没有一个运动员不是强壮的”符号化为【 C 】。

(A)??x(C(x)??G(x)), (B)??x(C(x)??G(x)), (C) ??x(C(x)??G(x)), (D) ??x(C(x)??G(x)) 35．?x?yP(x,y)的否定是【 B 】。

(A) ?x?y?P(x,y)， (B) ?x?y?P(x,y) ，(C) ?x?y?P(x,y)， (D) ?x?y?P(x,y) 36．在谓词演算中，下列各式正确的是【 A 】：

(A) ?x?yA(x,y)??y?xA(x,y), (B) ?x?yA(x,y)??y?xA(x,y), (C) ?x?yA(x,y)??y?xB(x,y), (D) ?x?yA(x,y)??x?yA(x,y)

二、填空题

1.若集合A的基数A?10，则其幂集的基数p(A)? 1024 。 2.设A??x|100?x?200,x?7n?3,n?Z,x?Z?，则|A|? 15 。

3.设N表示非负整数集，，R：N→N，xRy定义为x+2y＝10，则Dom(R)＝{0,2,4,6,8,10} Ran(R)＝{5,4,3,2,1,0}

4.A=?2,3,4,5,6,8,10,12,24?,R是A上的整除关系，那么A的极大元是 10，24 ,极小元是 2，3，5 ,。

5.设A=?1,2,3?上的关系R???1,1?,?1,2?,?1,3?,?3,3??，则R具备 反对称性 、传递性，R不具备 自反性、反自反性和对称性。

6.设G=（n,m）是简单图,v是G中度数为k的结点，e是G中的一条边，则G－e中有n个结点，m－1 条边。

7. 3个结点可构成 4 个不同构的简单无向图。 8.具有p个顶点的完全图Kp有pp?2个生成树，p≥2。

9.设G是一个有k个支的图，如果S是G的割集，则G-S恰有 k+1 个支。

10.设A=?1,2? ，则A?A=? ，A? 2 。 11.集合A???a??的幂集P(A)??，??,???,??a??,??,?a??? 。

12.设R是集合?1,2,?,10?上的模7同余关系，则. ?2?R? ?2,9? 。

13. A=?2,3,4,5,6,8,10,12,24?,R是A上的整除关系，那么A的极大元是 10，24 ,极小元是 2，3，5 ,。

14.整数集上的小于关系“＜”具有 反自反 、 反对称 和 传递 性。

15.设G=（n,m）是简单图,v是G中度数为k的结点，e是G中的一条边，则G－v中有n－1个结点，m－k 条边。

16.3个结点可构成 4 个不同构的简单无向图。 17.具有p个顶点的完全图Kp有pp?2个生成树，p≥2。 18.设S是连通图G=（V，E）的割集，则G-S恰有 2 个支。 19.设P:我生病,Q:我去学校看电影

(1) 命题“我虽然生病但我仍去学校”符号化为 P∧Q 。 (2) 命题“只有在生病的时候，我才不去学校”符号化为P??Q 。 20. 设P、Q为两个命题，德摩根律可表示为?(P?Q)??P??Q，（或

， 吸收律可表示为p?(P?Q)?P （或p?(P?Q)?P）。 ?(P?Q)??P??Q）

21.公式?(P?Q)的主析取范式为P??Q, 主合取范式的编码表示为M0?M1?M3。 22.?x?y(F(x,y)?G(y,z))??xP(x,y)中,?x的作用域为?y(F(x,y)?G(y,z)), ?y的作用域为

(F(x,y)?G(y,z)), ?x的作用域为P(x,y)。

23.谓词公式?xF(x)??xG(x)的前束范式为?x?y(F(x)?G(y)。

24.设P:我有钱,Q:我去看电影

(1) 命题“如果我有钱, 那么我就去看电影”符号化为P?Q。 (2) 命题“虽然我有钱, 但我不去看电影”符号化为P??Q。

25.命题公式P?(Q??S)的成真赋值为 010， 100， 101， 110，111 , 成假赋值为 000，001，011。

本文来源：https://www.bwwdw.com/article/ltrh.html