离散数学复习题（5.30日更新）

复习说明：该复习题库仅供大家练习用，考试时，将从中抽取部分题目并对其进行修改，然后组成试卷。所以大家务必掌握每道题的解法，而不要对题目或答案死记硬背。

一、选择题：

1. 下列句子是命题的是( )。

A. 你喜欢我吗? C. 2x = 9。

B. 这里的景色真美啊! D. 明年国庆节是晴天。

2. 下列语句不是命题的是( )。 ．．

A.黄金是非金属。

B.要是他不上场，我们就不会输。

C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 3. 下列句子不是命题的是( )。 ．．

A. 做人真难啊! B. 后天是阴天。

A.数学方法 A. 真值 A. P??Q

B.逻辑方法 B. 陈述句

C. 2是偶数。 C.实践方法 C. 命题

D. 地球是方的。 D.抽象方法 D. 谓词 D. ?P?Q D．P??Q D. ?(?P∨?Q) D.P∨?Q

4. 数理逻辑是采用( )研究抽象思维规律的一门科学。 5. 在命题演算中，语句为真为假的一种性质称为( )。

6. 设P：明天天晴；Q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( )

B. ?P??Q B．?P?Q

C. ?P??Q C．?P??Q C. ?(P?Q) C.P→?Q

7. 设P：我很累，Q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是( )

A．?P∧Q A. ?P∧?Q A.P∨Q

8. 设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。

B. ?(P∧Q) B.P∧?Q

9. 若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 10. 命题公式?(P∧Q)→R的成真指派是( )。

A. 000，001，110 C. 全体指派

B. 001，011，101，110，111 D. 无 C.所有指派 C. (P?Q)∨?Q

D.无

D. (P∨P)∧(P??P) D．P??Q D. P?Q? ?Q∨?P D. ??{?,{?}}

11. 命题公式P∧(Q∨? R)的成真指派是( )。

A.110，111，100 B.110，101，011 12. 下列命题公式是永真式的是( )

A. (P∧?P)? Q A．P?(P∨Q)

B. ?(P?Q)∧Q B．Q∧?Q

13. 下列命题公式为重言式的是( )

C．(P∨?P)?Q C. P?Q? ?Q∨P C.{?}?{?,{?}}

14. 下列式子正确的是( )

A. P?Q?Q?P A.{?}∈{?,{?}}

B. P?Q? ?P∨Q B.{?}∈{?,{{?}}}

15. 下列命题中，不正确的是( )。

16. 设P, Q, R是命题公式,则P?R，Q?R，P∨Q?( )。

A. P

B. Q

C. R

D. ?R D．?P∨P∨Q

17. 下列是两个命题变元P，Q的小项是( )

A．P∧?P∧Q A.?P∧Q

B．?P∨Q B.?P∨Q

C．?P∧Q

18. 关于命题变元P和Q的大项M01表示( )。

C. P∨?Q

D. P∧?Q

19. 下列含有命题P，Q，R的公式中，是主析取范式的是( )

A. (P∧Q∧R)∨(?P∧Q)

B. (P∨Q∨R)∧(?P∧Q) D. (P∧Q∧R)∨(?P∧?Q∧R)

C. (P∨Q∨R)∧(?P∨?Q∨R) 确的表达式是( )。 A. M(x)∨F(x)

B. M(x)∧F(x)

C. (?x)(M(x)?F(x))

D. (?x)(M(x)∧F(x))

21. 设A(x): x是鸟，B(x): x会飞，命题“有的鸟不会飞”符号化为( )。

A. ?(?x)(A(x)∧B(x)) B. ?(?x)(A(x)∧B(x)) C. ?(?x)(A(x)?B(x)) D. ?(?x)(A(x)?B(x)) 22. 设R(x)：x是实数；S(x,y)：x小于y。用谓词表达下述命题：不存在最小的实数。其中错

误的表达式是：( )。 A. (?x)(R(x)?(?y)(R(y)∧S(y, x)))

B. ?(?x)(R(x)?(?y)(R(y)∧S(x, y))) D. (?x)(R(x)?(?y)(R(y)?S(y, x))) C. A(a) C. A(1)

D. A(b)?A(a) D. A(2)? A(1) D. A(b)?A(a)

C. (?x)(R(x)∧(?y)(?R(y)∨?S(x, y))) A. A(a)∨A(b) A. A(1)∨A(2) A. A(a)∧A(b)

B. A(a)∧A(b) B. A(1)∧A(2) B. A(a)∨A(b)

20. 设M(x)：x是人；F(x)：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中正

23. 设论域为{a, b}，与公式(?x)A(x)等价的是( )。 24. 设论域为{l，2}，与公式(?x)A(x)等价的是( )。

25. 在论域D={a,b}中与公式(?x)A(x)等价的不含存在量词的公式是( )。

C. A(a)?A(b)

26. 设论域为整数集，下列真值为真的公式是( )。

A．(?x)(?y)(x – y = 0) C．(?x)(?y)(x – y = 0)

B．(?y)(?x)(x – y = 0) D．?(?x)?(?y)(x – y = 0) C. (?x)(x·y=x)

D. (?x)(?y)(x+y=2y)

27. 设个体域为整数集,则下列公式中值为真的是( )。

A. (?y)(?x)(x·y=2) B. (?x)(?y)(x·y=2) 28. 下列等值式不正确的是( )

A．?(?x)A?(?x)?A

B．(?x)(B?A(x))?B?(?x)A(x) C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D．(?x)(?y)(A(x)?B(y))?(?x)A(x)?(?y)B(y) 29. 下列哪个式子不是谓词演算的合式公式( )

A. (?x)(A(x,2)∧B(y))

B. (?x)(A(x)∧B(x,y)) D. (?x)(A(x) ?B(y))

C. ((?x)∧(?y))?(A(x,y)∧B(x,y))

30. 谓词公式(?x)P(x,y)∧(?x)(Q(x,z)?(?x)(?y)R(x,y,z)中量词?x的辖域是( )

A．(?x)Q(x,z)?(?x)(?y)R(x,y,z)) C．Q(x,z)?(?x)(?y)R(x,y,z)

B．Q(x,z)?(?y)R(x,y,z) D．Q(x,z)

31. 利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：

(?x)(p(x,y)?(?z)Q(x,z))∧(?y)R(x,y)改写成( ) A. (?z)(p(z,y)?(?y)Q(z,y))∧(?s)R(z,s) B. (?z)(p(z,y)?(?s)Q(x,s))∧(?y)R(z,y) C. (?x)(p(x,m)?(?y)Q(x,y))∧(?m)R(m,m) D. (?x)(p(y,y)?(?y)Q(x,y))∧(?s)R(y,s)

32. 对于公式(?x)(?y)P(x,y)∨Q(x,z)∧(?x)P(x,y)，下列说法正确的是( )

A.x是自由变元

B.x是约束变元 D.(?x)的辖域是P(x,y) C. A?B=B?A C.{?}??

D. A - B=B – A D.{?}?? D. A ? B

C.(?x)的辖域是P(x,y)∨Q(x,z)

33. 集合的以下运算律不成立的是( )。 ．．．

A. A∩B=B∩A B. A∪B=B∪A 34. 下列式子正确的是( )

A. ???

B. ???

35. 设A∩B=B,则有( )

A. A∪B=A

B. A – B = ?

C. A∪B=B

36. 设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是( )

A．(X-Y)-Z=X-(Y∩Z)

B．(X-Y)-Z=(X-Z)-Y D．(X-Y)-Z=X-(Y∪Z) C.{{a}}?P(A) C.8个 C.8个 C. 81

D.{a,{a}}?P(A) D.9个 D.9个 D. 64

D. 以上答案都正确

C．(X-Y)-Z=(X-Z)-(Y-Z) A.{a}∈P(A) A.3个

37. 设A={a,{a}}，P(A)为A的幂集，则下列各式正确的是( )。

B.{a}?P(A) B.6个

38. 设S={a,b,c},则S的幂集的元素的个数有( )。 39. 设A={a,b,c},则A×A中的元素有( )。

A.3个 B.6个 A. 7

B. 12

40. 设集合A={a, b, c}，集合B={a, b, c, d}，则│A?B│等于( )。

41. 设有A={a,b,c}上的关系R={, , }，则R具有( )的性质。

A. 自反性

B. 反对称性

C. 传递性

42. 设集合A={a, b, c}上的关系如下，具有传递性的是( )。

A.R={,,,} C.R={,,,} A.自反性

B.对称性

B.R={,} D.R={}

D.反自反性

图1

43. 设A={1,2,3}，A上二元关系R的关系图如图1，R具有的性质是( )。

C.传递性

44. 下列关系矩阵所对应的关系具有反对称性的是( )。

?101??011A．???

??100???100??011B．???

??101??

?001??001C．???

??100??

?101??010D．???

??100??45. 设A={a,b,c}，A上二元关系R={, , }，则关系R的对称闭包s(R)是( )。

A. R∪IA

B. R

C. R∪{}

D. R∩IA

46. 设A={1，2，3，4 }，A上二元关系R={<1,2>, <3,4>, <2,2>}，S={<2,4>, <3,1>, <4,2>}，则

S?R-1的运算结果是( )。 A．{<4,1>, <2,3>, <4,2>} C．{<4,1>, <2,3>, <2,4>}

B．{<2,3>, <3,2>, <4,1>, <4,2>} D．{<1,1>, <2,2>, <3,3>, <4,4>}

47. 设A={1，2，3，4，5}，A上二元关系R={<1,2>, <3,4>, <2,2>}，S={<2,4>, <3,1>, <4,2>}，

则S-1?R-1的运算结果是( )。 A．{<4,1>，<2,3>，<2,4>} C．{<4,1>，<2,3>，<4,2>} A.{{b,c},{c}} A. 8

B．{<2,4>，<2,3>，<4,2>} D．{<2,2>，<3,1>，<4,4>} C.{{a,b},c} C. 6

D.{{a},{b,c}} D. 5

48. 设A={a,b,c}，则下列是集合A的划分的是( )。

B.{{a,b},{a,c}} B. 7

49. 集合{1, 2, 3}上共有( )个不同的等价关系。

50. 设X={a, b, c},IX是X上恒等关系，要使IX∪{，，，}∪R为X上的等

价关系，R应取( )。 A. {，} C. {，} 分是( ) A．{{a},{b,c},{d}}

B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}}

D．{{a,b},{c,d}}

52. 集合{1, 2, 3, 4}上的偏序关系如下列四个关系图所示，其中属于全序关系的是( )。

B.{，} D.{，}

51. 设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划

1 3 A

2 4

1 3 B

2 4 1 3

C

2 4

1 3 D 2 4

53. 设A={1, 2, 3}，B={a, b}，下列二元关系R为A到B的函数的是( )。

A. R={<1, a>, <2, a>, <3, a>} C. R={<1, a>, <2, b>} A．满射函数

B. R={<1, a>, <1, b>, <2, a>, <3, a>} D. R={<1, b>, <2, a>, <3, b>, <1, a>} C．双射函数 C.双射

D．非入射非满射 D.既非入射也非满射

54. 设R为实数集，函数f：R?R，f(x)=2x，则f是( )

B．入射函数

55. 设N为自然数集(含0)，函数f：N→N×N, f(n)=是( )。

A.满射但非入射

B.入射但非满射