离散数学单项选择题习题(有答案)集

单项选择题 第一章第二章

1. 下列表达式正确的有( )

A. ? ( P ? Q ) ? Q B.P?Q?P C.(P?Q)?(P??Q)?2. 下列推理步骤错在( ) ①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)

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

P D.P?(P?Q)?T

A.② 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) B.P→(Q→Q) C.(P?Q)→P D.P→(P?Q) 5. 下列等价关系正确的是( ) A.?x(P(x)?Q(x))?C.?x(P(x)?Q)??xP(x)??xQ(x)

B.?x(P(x)?Q(x))??xP(x)??xQ(x)

?xP(x)?Q D.?x(P(x)?Q)??xP(x)?Q

6. 下列推导错在( ) ①?x?y(x?②?y(z?③z?z ④?x(x?x) y)

P US① ES② UG③

y)

A.② B. ④ C. ③ D.无 7. 若公式(P?Q)?(?P?R)的主析取范式为m001A.m001C.M001?m011?m110?m111?M?m011?m110?m111则它的主合取范式为( )

B.M000 D.m000?M010?M100?M101 ；

011?M110?M111?m010?m100?m101 。

8. 在下述公式中不是重言式为( ) A．(P?Q)?(P?Q) B．(P?Q)?((P?Q)?(Q?P))

C．?(P?Q)?Q D．P?(P?Q) 9. 下列各式中哪个不成立( ) A.?x(P(x)?Q(x))?

?xP(x)??xQ(x) B.?x(P(x)?Q(x))?1

?xP(x)??xQ(x)

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)))

B.?x(M(x)?P(x))??(?x(M(x)?P(x)))

P(x)))C.?x(M(x)?P(x))??(?x(M(x)?P(x))) D.?x(M(x)?P(x))??(?x(M(x)?11.下述命题公式中，是重言式的为( ) A.(p?q)?(p?q) B.p?qC.?(p?q)?q

?((p?q)?(q?p))

D.(p??q)?q

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)?C. ?x(M(x)??y(F(y)?H(x,y)))H(x,y))) B.?x(M(x)??y(F(y)? D.?x(M(x)??y(F(y)?H(x,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.P(a)=0、P(b)=0 B.P(a)=0、P(b)=1 C.P(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.明年中秋节的晚上是晴天 B.x?我正在说谎

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

y?0

C.xy?0当且仅当x和y都大于0 D.

B.(P?Q)?Q C.?(Q?P)?P D.(P?Q)?P

19.下列集合中哪个是最小联结词集( )

A.{?,?} B.{?,?} C. {?,?} D.{?,?,?}

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)))

2

C.?x?y(L(x)?J(y)?A(x,y)) D.?x?y(L(x)?J(y)?21.下列各命题中真值为真的命题有( )

A(x,y))

A.2+2=4当且仅当3是奇数 B.2+2=4当且仅当3不是奇数 C.2+2≠4当且仅当3是奇数 D.2+2=4仅当3不是奇数 22.命题逻辑演绎的CP规则为( ) A.在推演过程中可随便使用前提

B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C.如果要演绎出的公式为B?C形式，那么将B作为前提，演绎出C

?AD.设?(A)是含公式A的命题公式，B第三章

，则可用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上的关系，则下列说法正确的是( )

A．若R，S 是自反的， 则R?S是自反的 B．若R，S 是反自反的， 则R?S是反自反的 C．若R，S 是对称的， 则R?S是对称的 D．若R，S 是传递的， 则R?S是传递的 27.Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确 ( )

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

3

29.设f，g是函数，当( C )时，f=g A.?x?domfC. domg 都有 f(x)?g(x)

B. f与g的表达式相同

?domf,rangef?rangef?domf 且 f?gB?{?,{?}} D.domg

30.设A??,，则B－A是( )

A.{{?}} B.{?} C.{?,{?}} D.?

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

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

则由R产生的S?S上一个划分共有( B )个分块。 A．4 B．5 C．6 D．9 33.下列是真命题的有( )

A． {a}?{{a}} B．{{?}}?{{?},?} C．??{{?},?} D．??{{?}} 34.设S?A?B，下列各式中( B )是正确的

domS?B B.domS?A C.ranS?A D.domS ? ranS = S 35.设S?{ 1, 2, 3 }，S

上关系R的关系图如下 ，则R具有( D )性质

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

4

36.设A?{x|x是偶数或奇数

},B?{x|? y(y?I?x?2y)},C?{x|? y(y?I?x?2y?1)},

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

A.A的B B.B和C C.C和D D.A和D 37.设A??a,b?，则P（A）×A = ( C) A.A B.P（A）

C.???,a?,??,b?,?{a},a?,?{a},b?,?{b},a?,?{b},b?,?D.

A,a?,?A,b??

?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是所有人的集合，

S?{?x,y?|x,y?P?x是y的母亲}则R?S?1表示关系 ( A )

R?{?x,y?|x,y?P?x是y的父亲}，

A.{?x,y?|x,y?P?x是y的丈夫} B.{?x,y?|x,y?P?x是y的孙子或孙女x,y?|x,y?P?x是y的祖父或祖母} }

C.? D.{?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 ) A.a B.b C.1 D.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) B.?x?y(P(x,u)?Q(u,z))??xP(x,u)； C.?x?y(P(x,y)?Q(y,z))??xP(x,u) D.?u?y(P(u,y)?Q(y,z))??uP(u,y)。 43.下面蕴涵关系不成立的是( C )

A.?xP(x)??xQ(x)??x(P(x)?Q(x)) B.?xP(x)??xQ(x)??x(P(x)?Q(x)) C.?xP(x)??xQ(x)??x(P(x)?Q(x)) D.?x?yA(x,y)??y?xA(x,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}的上界( )

5

A. 12,无,6,36 B. 12,2,6,36 C. 12,2,12,36 D.12,无,6,无 46.下列哪个偏序集构成有界格( )

A.（N，?） B.（Z，?） C.（{2，3，4，6，12}，|（整除关系）） D.(P（A），?) 47.六阶群的子群的阶数可以是( D)

A.1，2，5 B.2，4 C.3，6，7 D.2，3

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

A.2、2、1 B.1、1、2 C.1、1、1 D.1、2、2

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

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

51.设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A) A.m-n+2 B.n-m-2 C.n+m-2 D.m+n+2 52.下列哪个公式为永真式？( C )

A.?Q=>Q→P B.?Q=>P→Q C.P=>P→Q D.?P?(P?Q)=>P

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

B.M(x)?Mortal

(x) C. ?x(M(x)?Mortal(x)) D.?x(M(x)?Mortal(x))

?{?,{1},{1,2}}，则有( A )?SA.{{1,2}} B.{1,2 } C.{1} D.{2} 55.判断下列命题哪个正确？( B )

A.若A∪B＝A∪C，则B＝C B.{a,b}={b,a}

C.P(A∩B)?P(A)∩P(B)（P(S)表示S的幂集） D.若A为非空集，则A?A∪A成立 56.下列结果正确的是( )

A.(A?B)?A?B B.(A?B)?A?? C.(A?B)?B?A D.??{?}?? 57.集合A?{xx?2,n?N}对( )运算封闭

nA. 乘法 B.减法 C. 加法 D.x?y

58.设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义运算

6

[i]?[j]?[(i?j)modm]，则代数系统?Zm,?m?最确切的性质是( )

A.封闭的代数系统 B.半群 C.独异点 D.群 59.设?N,??是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则 ?a,b?N有a?b?( )

A.a B.b C.min(a，b) D. max(a，b)

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

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

A.0 B.1 C.2 D.3 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有( )个顶点 A.10 B.4 C.8 D.12

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

?Q,Q?S 则N?S

D.??N,??S 则??N?S65.设A={a,{a}}，下列命题错误的是( B )

A.{a}?P(A) B.{a}?P(A) C.{{a}}?P(A) 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是自反的 B.若R,S对称的，则R?S是对称的 C.若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},则下列命题哪个正确( ) A.Q?P B.Q?P C.P?Q D.P=Q 代数系统

7

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

A. ? B.{1,2,3} C.{1,3} D. {2,3} 70.在有理数集Q上定义的二元运算*，?x,y?Q有x*y?x?y?xy， 则Q中满足( )

A. ?x?Q,x?1时有逆元x?1 B.只有唯一逆元 C. 所有元素都有逆元 D.所有元素都无逆元

71.设S={0，1}，*为普通乘法，则< S ， * >是( )

A.半群，但不是独异点 B.只是独异点，但不是群 C.群 D.环，但不是群 72.设A={1，2，?，10 }，则下面定义的运算*关于A封闭的有( ) A.x*y=max(x ，y) B.x*y=质数p的个数使得x?p?y

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

* a b c 则零元为( C)

A.a B.b C.c D.没有 74.设G1??{0,1,2},??a a b c b b a c c c c c ，G2??{0,1},*?，其中?表示模3加法，*表示模2乘法，在集合G1?G2上定义如

称?G1?G2,??为G1?G2的积代数，

下运算：??a,b?,?c,d??G1?G2,有?a,b???c,d???a?c,b?d?,则G1?G2的积代数幺元是( B )

A.<0，0> B.<0，1> C.<1，0> D.<1，1>

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

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

a?b?b

B.?a,b?A,a?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,12,2,13,3,14,4}，*为普通乘法，则是( )

A.代数系统 B.半群 C.群 D.都不是

8

78.设s?{1,12,2,13,3,14,4}，*为普通乘法，则是( )

A.代数系统 B.半群 C.群 D.都不是 79.在自然数集N上，下列哪种运算是可结合的？( )

A.a*b=a-b B.a*b=max{a，b} C.a*b=a+2b D.a*b=|a-b| 80.设?A,??是一个有界格，如果它也是有补格，只要满足( )

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

81.具有如下定义的代数系统?G,??，( )不构成群 A.GC.G?{1,10}，*是模?Q11乘 B.G?{1,3,4,5,9}，*是模?Q11乘

（有理数集），*是普通加法 D.G（有理数集），*是普通乘法

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的函数，则( )

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

86.连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )

A.只有一个奇度结点 B.只有两个奇度结点 C.只有三个奇度结点 D.没有奇度结点 87.设G??V,E?为无向图，V?7,E?23，则G一定是( )

A.完全图 B.树 C.简单图 D.多重图

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

9

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

A.分配格 B.有补格 C.布尔格 D.A，B，C都不对

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

A.1 B.2 C.4 D.5 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.割边集诱导子图是生成树 C.有一条公共边 D.至少有一条公共边 95.在任何图中必定有偶数个( )

A.度数为偶数的结点 B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点 96.一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( ) A.5 B.7 C.8 D.9

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

10

98.连通图G是一棵树当且仅当G中( )

A.有些边是割边 B.每条边都是割边 C.所有边都不是割边 D.图中存在一条欧拉路径

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

100. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点 A.10 B.4 C.8 D.12 101. 在有n个顶点的连通图中，其边数( )

A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条 102. 给定无向图GA.{?v1,v4C.{?v4,v7??V,E?，如下图所示，下面哪个边集不是其边割集( )

?,?v3,v4?} B.{?v4,v5?,?v4,v6?}

?,?v4,v8?} D.{?v1,v2?,?v2,v3?}

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

104. 下列哪一种图不一定是树( )

A.无回路的简单连通图 B.每对顶点间都有通路的图

C.有n个顶点n-1条边的连通图 D.连通但删去任何一条边便不连通的图 105. 下面偏序集( B )能构成格

11

106. 6阶有限群的任何子群一定不是( ) A.2阶 B.3 阶 C.4 阶 D.6 阶

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

A．1 B．2 C．3 D．4 108. n个结点的无向完全图Kn的边数为( ) A.n(n?1) B.

n(n?1)2 C.n(n?1) D.

n(n?1)2

109. 设G是一个哈密尔顿图，则G一定是( ) A.欧拉图 B.树 C.平面图 D.连通图 110. 在如下各图中( B)是欧拉图

111. 下列图中( )是根树 A.G1C.G3??{a,b,c,d},{?a,a?,?a,b?,?c,d?}?

??{a,b,c,d},{?a,b?,?a,d?,?c,a?}? B.G2??{a,b,c,d},{?a,b?,?b,d?,?c,d?}???{a,b,c,d},{?a,b?,?a,c?,?d,d?}?

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

A.{0，10，110，101111} B.{1，11，101，001，0011} C.{b，c，aa，ab，aba} D.{01，001，000，1}

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

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

12

115. 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=( ) A.n×k B.n×(k+1) C.n×(k+1)-m D.n×(k+1)-2m 116. 设G是简单有向图，可达矩阵P(G)刻画下列 ( C )关系 A.点与边 B.边与点 C.点与点 D.边与边 117. 设G是一棵树，n,m分别表示顶点数和边数，则( ) A.n=m

B. n=m+1 C. m=n+1 D.不能确定 . 13

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