离散数学单项选择题习题集

离散数学单项选择题习题集(共13页)

有答案)

(单项选择题 第一章第二章

1. 下列表达式正确的有( ) A.  ( P  Q )  Q

B.PQP C.(PQ)(PQ)P D.P(PQ)T

2. 下列推理步骤错在( ) ①x(F(x)G(x)) ②F(y)G(y) ③xF(x) ④F(y) ⑤G(y) ⑥xG(x)

A.②

P US① P ES③ T②④I EG⑤ B.④

C.⑤

D.⑥

3. 设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。 A.PQR

B.RPS C.SQR D.(PR)(QS)

4. 下列公式中哪些是永真式？( ) A.(┐PQ)→(Q→R)

→(Q→Q) C.(PQ)→P

→(PQ)

5. 下列等价关系正确的是( ) A.x(P(x)Q(x))xP(x)xQ(x) C.x(P(x)Q)xP(x)Q 6. 下列推导错在( ) ①xy(xy) ②y(zy) ③zz ④x(xx) A.②

B. ④

P US① ES② UG③ C. ③

D.无

B.x(P(x)Q(x))xP(x)xQ(x)

D.x(P(x)Q)xP(x)Q

7. 若公式(PQ)(PR)的主析取范式为m001m011m110m111则它的主合取范式为( ) A.m001m011m110m111

B.M000M010M100M101 ；

C.M001M011M110M111 D.m000m010m100m101 。

8. 在下述公式中不是重言式为( ) A．(PQ)(PQ) C．(PQ)Q

B．(PQ)((PQ)(QP))

D．P(PQ)

9. 下列各式中哪个不成立( ) A.x(P(x)Q(x))xP(x)xQ(x)

B.x(P(x)Q(x))xP(x)xQ(x)

2

C.x(P(x)Q(x))xP(x)xQ(x) D.x(P(x)Q)xP(x)Q

10. 命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）( )

A.x(M(x)P(x))(x(M(x)P(x))) C.x(M(x)P(x))(x(M(x)P(x))) 11. 下述命题公式中，是重言式的为( ) A.(pq)(pq) C.(pq)q

B.pq((pq)(qp)) D.(pq)q

B.x(M(x)P(x))(x(M(x)P(x)))

D.x(M(x)P(x))(x(M(x)P(x)))

12. 谓词公式x(P(x)yR(y))Q(x)中的x是( ) A.自由变元

B.约束变元

C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元

13. 命题“有的人喜欢所有的花”的逻辑符号化为( )

设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y A. x(M(x)y(F(y)H(x,y))) B.x(M(x)y(F(y)H(x,y))) C. x(M(x)y(F(y)H(x,y))) D.x(M(x)y(F(y)H(x,y))) 14. 下列等价式成立的有( )

A.PQPQ B.P(PR)R

C.P(PQ)Q D.P(QR)(PQ)R

15. 给定公式xP(x)xP(x)，当D={a,b}时，解释( )使该公式真值为0。 (a)=0、P(b)=0

(a)=0、P(b)=1

(a)=1、P(b)=1

x是人，P(x)：x犯错误,命题“没有不犯错误的人”符号化为( ) 16. 设M(x)：A.x(M(x)P(x)) B.(x(M(x)P(x))) C.(x(M(x)P(x))) D.(x(M(x)P(x))) 17. 下列语句是命题的有( ) A.明年中秋节的晚上是晴天 大于0

D.我正在说谎

B.xy0

C.xy0当且仅当x和y都

18. 下列公式是重言式的有( ) A.(PQ)

B.(PQ)Q

C.(QP)P D.(PQ)P

19. 下列集合中哪个是最小联结词集( ) A.{,}

B.{,}

C. {,}

D.{,,}

3

20. 设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为( ) A.x(L(x)A(x,y))

B.x(L(x)y(J(y)A(x,y)))

C.xy(L(x)J(y)A(x,y)) D.xy(L(x)J(y)A(x,y))

21. 下列各命题中真值为真的命题有( ) +2=4当且仅当3是奇数 +2=4当且仅当3不是奇数 +2≠4当且仅当3是奇数

+2=4仅当3不是奇数

22. 命题逻辑演绎的CP规则为( ) A.在推演过程中可随便使用前提

B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C.如果要演绎出的公式为BC形式，那么将B作为前提，演绎出C D.设(A)是含公式A的命题公式，BA，则可用B替换(A)中的A 第三章

23. 设A={1，2，3，4}，P（A）（A的幂集）上规定二元系R{s,t|s,tp(A)(|s||t|}则P（A）R=( ) A．A

B．P(A)

C．{[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，

[{1，2，3，4}]R }

D．{[]R，[2]R，[2，3]R，[2，3，4]R，[A]R }

24. 集合A={1,2,…,10}上的关系R={|x+y=10,x,yA}，则R 的性质为( ) A.自反的 B.对称的 C.传递的，对称的 D.传递的

25. 集合A={1，2，3，4}上的偏序关系为，则它的Hass图为( C )

26. 设R，S是集合A上的关系，则下列说法正确的是( )

4

/ A．若R，S 是自反的， 则RS是自反的 的

C．若R，S 是对称的， 则RS是对称的

B．若R，S 是反自反的， 则RS是反自反

D．若R，S 是传递的， 则RS是传递的

27. Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确 ( )

，BC则AC

，BC则 A∈B

∈B，B∈C则 A∈C

28. 设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为( C )

29. 设f，g是函数，当( C )时，f=g A.xdomf 都有 f(x)g(x) C. domgdomf 且 fg

B. f与g的表达式相同 D.domgdomf,rangefrangef

30. 设A,B{,{}}，则B－A是( ) A.{{}}

B.{}

C.{,{}}

D.

31. 集合A={1，2，3，4}上的偏序关系图如下左，则它的哈斯图为( C )

32. 设S{ 1, 2, 3 }，定义SS上的等价关系,

有( B )个分块。 A．4

B．5

C．6

D．9

,则由R产生的SS上一个划分共

33. 下列是真命题的有( ) A． {a}{{a}}

B．{{}}{{},}

C．{{},}

D．{{}}

34. 设SAB，下列各式中( B )是正确的 domSB





 ranS = S

5

35. 设S{ 1, 2, 3 }，S上关系R的关系图如下 ，则R具有( D )性质

A．自反性、对称性、传递性 性 D．自反性

B．反自反性、反对称性 C．反自反性、反对称性、传递

},B{x| y(yIx2y)},C{x| y(yIx2y1)}, 36. 设A{x|x是偶数或奇数

D{x|0,1,1,2,2,3,3,4,4,}下列相等的集合是( D )

的B

和C

和D

和D

37. 设Aa,b，则P（A）×A = ( C)

（A）

C.,a,,b,{a},a,{a},b,{b},a,{b},b,A,a,A,b D.a,,b,,a,{a},b,{a},a,{b},b,{b},a,A,b,A 38. A是素数集合，B是奇数集合，则A-B=( D ) A.素数集合

B.奇数集合

C.

D.{2}

39. 设R和S是P上的关系，P是所有人的集合，R{x,y|x,yPx是y的父亲}，

S{x,y|x,yPx是y的母亲}则RS1表示关系 ( A )

A.{x,y|x,yPx是y的丈夫} C.

} B.{x,y|x,yPx是y的孙子或孙女 } D.{x,y|x,yPx是y的祖父或祖母40. 在自然数集N上，（对任意a,bN）下列( B)运算是可结合的 A.abab B.abmax(a,b)

C.aba5b

D.abab

41. Q为有理数集N，Q上定义运算*为a*b = a + b – ab ，则的幺元为( 0 )

42. 公式xy(P(x,y)Q(y,z))xP(x,y)换名( A ) A.xu(P(x,u)Q(u,z))xP(x,y) C.xy(P(x,y)Q(y,z))xP(x,u) 43. 下面蕴涵关系不成立的是( C ) A.xP(x)xQ(x)x(P(x)Q(x)) C.xP(x)xQ(x)x(P(x)Q(x))

B.xP(x)xQ(x)x(P(x)Q(x)) D.xyA(x,y)yxA(x,y)

6

B.xy(P(x,u)Q(u,z))xP(x,u)； D.uy(P(u,y)Q(y,z))uP(u,y)。

44. N是自然数集，定义f:NN, f(x)(x) mod3（即x除以3的余数）,则f是(D) A.满射不是单射

B.单射不是满射

C.双射

D.不是单射也不是满射

45. 集合A={2，3，6，12，24，36}上偏序关系R的Hass图为 则集合B={2，3，6，12}的上确界( ) B={2，3，6，12}的下界( ) C={6，12，24，36}的下确界( ) D={6，12，24，36}的上界( ) A. 12,无,6,36

B. 12,2,6,36

C. 12,2,12,36

,无,6,无

46. 下列哪个偏序集构成有界格( ) A.（N，） B.（Z，） （A），)

47. 六阶群的子群的阶数可以是( D) ，2，5 ，4

，6，7

，3

C.（{2，3，4，6，12}，|（整除关系））

D.(P

48. 对右图，则k(G),(G),(G)分别为( C )

、2、1

、1、2

、1、1

、2、2

49. 一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有( A )个4度结点

50. 具有6 个顶点，12条边的连通简单平面图中，每个面都是由( C )条边围成

51. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A) +2

+m-2

+n+2

52. 下列哪个公式为永真式？( C )

=>Q→P

=>P→Q =>P→Q (PQ)=>P

53. “人总是要死的”谓词公式表示为( )（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的

A.M(x)Mortal(x) B.M(x)Mortal(x) 54. 设S{,{1},{1,2}}，则有( A )S A.{{1,2}}

B.{1,2 }

C.{1}

7

C. x(M(x)Mortal(x)) D.x(M(x)Mortal(x))

D.{2}

55. 判断下列命题哪个正确？( B ) A.若A∪B＝A∪C，则B＝C

B.{a,b}={b,a}

(A∩B)P(A)∩P(B)（P(S)表示S的幂集） 56. 下列结果正确的是( ) A.(AB)AB

B.(AB)A

D.若A为非空集，则AA∪A成立

C.(AB)BA D.{}

n57. 集合A{xx2,nN}对( )运算封闭

A. 乘法 B.减法

C. 加法

D.xy

58. 设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义运算[i][j][(ij)modm]，则代数系统Zm,m最确切的性质是( ) A.封闭的代数系统

B.半群

C.独异点 D.群

59. 设N,是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则

a,bN有ab( )

(a，b) D. max(a，b)

60. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶

61. 有向图D= ，则v1到v4长度为2的通路有( )条

62. 设V{a,b,c,d,e,f}，E{a,b,b,c,c,a,a,d,d,e,f,e}，则有向图

GV,E是( )

A.强连通的 B.单侧连通的 C.弱连通的 D.不连通的

63. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点

64. 下列命题正确的是( C ) A.2N,NS 则2S C.NQ,QR 则NR

B.NQ,QS 则NS

D.N,S 则NS

65. 设A={a,{a}}，下列命题错误的是( B ) A.{a}P(A) B.{a}P(A)

C.{{a}}P(A)

8

D.{{a}}P(A)

66. 设A={} ，B=Р(Р(A)) 下列( )表达式不成立 A.B

B.B

C. B

D. B

67. 设R，S是集合A上的关系，则下列( )断言是正确的 A.R,S自反的，则RS是自反的 C.若R,S传递的，则RS是传递的

B.若R,S对称的，则RS是对称的 D.若R,S反对称的，则RS是反对称的

68. 设P={x|(x+1)24且xR},Q={x|5x2+16且xR},则下列命题哪个正确( )    代数系统

69. G(2S,)，其中S{1,2,3}，为集合对称差运算，则方程{1,2}x{1,3}的解为( ) A. 

B.{1,2,3}

C.{1,3}

D. {2,3}

=Q

70. 在有理数集Q上定义的二元运算*，x,yQ有x*yxyxy， A. xQ,x1时有逆元x1 B.只有唯一逆元 无逆元

71. 设S={0，1}，*为普通乘法，则< S ， * >是( ) A.半群，但不是独异点 但不是群

72. 设A={1，2，…，10 }，则下面定义的运算*关于A封闭的有( ) *y=max(x ，y) *y=gcd(x ， y)

B.只是独异点，但不是群

则Q中满足( )

D.所有元素都

C. 所有元素都有逆元

C.群 D.环，

*y=质数p的个数使得xpy

(gcd (x ，y)表示x和y的最大公约数)

*y=lcm(x ，y) （lcm(x ，y) 表示x和y的最小公倍数） 73. 设[{a ， b ， c}，*]为代数系统，*运算如下：

* a b c 则零元为( C)

D.没有 a a b c b b a c c c c c 74. 设G1{0,1,2},，G2{0,1},*，其中表示模3加法，*表示模2乘法，在集合G1G2上定义如下运算：a,b,c,dG1G2,有a,b•c,dac,bd,称G1G2,•为G1G2的积代数，则G1G2的积代数幺元是( B ) A.<0，0>

B.<0，1>

C.<1，0>

9

D.<1，1>

75. 设R是实数集合，“”为普通乘法，则代数系统 不是( A ) A．群 B．独异点 C．半群

76. 设是一个格，由格诱导的代数系统为A , ,，则( )成立 A.A,,满足对的分配律

B.a,bA,ababb

C.a,b,cA,若abac 则bc

D.a,bA,有a(ab)b且 a(ab)b

77. 设s{1,1,2,1,3,1234,4}，*为普通乘法，则是( ) A.代数系统 B.半群

C.群 D.都不是

78. 设s{1,1,2,1,3,1234,4}，*为普通乘法，则是( ) A.代数系统 B.半群

C.群 D.都不是

79. 在自然数集N上，下列哪种运算是可结合的( ) *b=a-b *b=max{a，b} *b=a+2b *b=|a-b|

80. 设A,是一个有界格，如果它也是有补格，只要满足( )

A. 每个元素都至少有一个补元 B. 每个元素都有多个补元 C.每个元素都无补元 D. 元素都有一个补元

81. 具有如下定义的代数系统G,，( )不构成群 A.G{1,10}，*是模11乘

B.G{1,3,4,5,9}，*是模11乘 C.GQ（有理数集），*是普通加法 D.GQ（有理数集），*是普通乘法

82. 在( )中，补元是唯一的 A.有界格

B.有补格 C.分配格 D.有补分配格

83. 在布尔代数A , ,,中，bc0当且仅当( ) A.bc

B.cb

C.bc

D.cb

84. 设是偏序集，“”定义为：a,bA,aba|b，则当A=( )时，是格 A.{1，2，3，4，6，12} B.{1，2，3，4，6，8，12，14} C.{1，2，3，…，12} D.{1，2，3，4}

85. 设A , ,,是布尔代数，f是从An到A的函数，则( ) 是布尔代数

能表示成析取范式，也能表示成合取范式

C.若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式 D.若f是布尔函数，它一定能表示成析（合）取范式 图论

10

每个86. 连通非平凡的无向图G有一条欧拉回路当且仅当图G ( ) A.只有一个奇度结点 点

87. 设GV,E为无向图，V7,E23，则G一定是( ) A.完全图

B.树

C.简单图

D.多重图

B.只有两个奇度结点

C.只有三个奇度结点 D.没有奇度结

88. 若一棵完全二元（叉）树有2n-1个顶点，则它( )片树叶

89. 图 给出一个格L，则L是( )

A.分配格

B.有补格 C.布尔格 ，B，C都不对

90. 在Peterson图 中，至少填加( )条边才能构成Euler图

91. 在有n个顶点的连通图中，其边数( ) A.最多有n-1条 B.至少有n-1 条

C.最多有n条 D.至少有n 条

92. 图 中 从v1到v3长度为2的通路有( )条

A． 0 B． 3 C． 2 D． 1

93. 下面那一个图可一笔画出( A )

94. 一个割边集与任何生成树之间( ) A.没有关系 B.割边集诱导子图是生成树 95. 在任何图中必定有偶数个( ) A.度数为偶数的结点

B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点

11

C.有一条公共边 D.至少有一条公共边

96. 一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( )

97. 下列偏序集( C )能构成格

98. 连通图G是一棵树当且仅当G中( ) A.有些边是割边 B.每条边都是割边 条欧拉路径

99. 有n个结点(n3)，m条边的连通简单图是平面图的必要条件( ) A.n3m6

B.n3m6 C.m3n6 D.m3n6

C.所有边都不是割边

D.图中存在一

100. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点

101. 在有n个顶点的连通图中，其边数( ) A.最多有n-1条 B.至少有n-1条

C.最多有n条 D.至少有n条

102. 给定无向图GV,E，如下图所示，下面哪个边集不是其边割集( ) A.{v1,v4,v3,v4} B.{v4,v5,v4,v6} C.{v4,v7,v4,v8} D.{v1,v2,v2,v3}

103. 如右图 相对于完全图K5的补图为( A )

104. 下列哪一种图不一定是树( ) A.无回路的简单连通图

B.每对顶点间都有通路的图

C.有n个顶点n-1条边的连通图 105. 下面偏序集( B )能构成格

D.连通但删去任何一条边便不连通的图

12

106. 6阶有限群的任何子群一定不是( ) 阶 阶

阶

阶

107. 在如下的有向图中，从V1到V4长度为3 的道路有( )条

A．1

B．2

C．3

D．4

108. n个结点的无向完全图Kn的边数为( ) A.n(n1)

B.

n(n1) 2C.n(n1) D.n(n1) 2109. 设G是一个哈密尔顿图，则G一定是( ) A.欧拉图

B.树

C.平面图 D.连通图

110. 在如下各图中( B)是欧拉图

111. 下列图中( )是根树

A.G1{a,b,c,d},{a,a,a,b,c,d} C.G3{a,b,c,d},{a,b,a,d,c,a}

B.G2{a,b,c,d},{a,b,b,d,c,d} D.G4{a,b,c,d},{a,b,a,c,d,d}

112. 下面给出的集合中，哪一个是前缀码( )

A.{0，10，110，101111} B.{1，11，101，001，0011} D.{01，001，000，1}

113. 左图[0]相对于完全图的补图为( A )

C.{b，c，aa，ab，aba}

13

114. 下列图中是欧拉图的有( A )

115. 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=( ) ×k ×(k+1)

×(k+1)-m

×(k+1)-2m

116. 设G是简单有向图，可达矩阵P(G)刻画下列 ( C )关系 A.点与边

B.边与点

C.点与点

D.边与边

117. 设G是一棵树，n,m分别表示顶点数和边数，则( ) =m

B. n=m+1

C. m=n+1

D.不能确定 .

14