离散数学单项选择题习题（有答案）集

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)

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

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))xP(x)xQ(x) B.x(P(x)Q(x))xP(x)xQ(x) C.x(P(x)Q)xP(x)Q D.x(P(x)Q)xP(x)Q 6. 下列推导错在( ) ①xy(xy) ②y(zy) ③zz ④x(xx)

P US① ES② UG③

A.② B. ④ C. ③ D.无

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) 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))xP(x)xQ(x)

1

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))) C.x(M(x)P(x))(x(M(x)P(x))) D.x(M(x)P(x))(x(M(x)P(x))) 11.下述命题公式中，是重言式的为( )

A.(pq)(pq) B.pq((pq)(qp)) C.(pq)q 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)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.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y0 C.xy0当且仅当x和y都大于0 D.我正在说谎

18.下列公式是重言式的有( )

A.(PQ) 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)A(x,y)) 21.下列各命题中真值为真的命题有( )

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

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domf 都有 f(x)g(x) B. f与g的表达式相同 C. domgdomf 且 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上的等价关系,

则由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

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

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,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的丈夫} B.{x,y|x,yPx是y的孙子或孙女} C. D.{x,y|x,yPx是y的祖父或祖母40.在自然数集N上，（对任意a,bN）下列( B)运算是可结合的

a,b) C.aba5b A.abab B.abmax( 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)Mortal(x) B.M(x)Mortal(x) C. x(M(x)Mortal(x)) D.x(M(x)Mortal(x)) 54.设S{,{1},{1,2}}，则有( A )S

A.{{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.{}

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

A. 乘法 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.NQ,QS 则NS C.NQ,QR 则NR D.N,S 则NS 65.设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(2S,)，其中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},，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> D.<1，1>

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

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

则bc D.a,bA,有a(ab)b且 a(ab)b C.a,b,cA,若abac a a b c b b a c c c c c 77.设s{1,2,2,3,3,4,4}，*为普通乘法，则是( ) A.代数系统 B.半群 C.群 D.都不是

8

11178.设s{1,111,2,,3,,4}，*为普通乘法，则是( ) 234A.代数系统 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.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的函数，则( )

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. 给定无向图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条边的连通图 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) 2C.n(n1) D.

n(n1)2

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

111. 下列图中( )是根树

A.G1{a,b,c,d},{a,a,a,b,c,d} B.G2{a,b,c,d},{a,b,b,d,c,d} C.G3{a,b,c,d},{a,b,a,d,c,a} D.G4{a,b,c,d},{a,b,a,c,d,d} 112. 下面给出的集合中，哪一个是前缀码？( )

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

45

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