2023年7月19日发(作者：)

《离散数学》模拟题

一.单选题

1.下述式子错误的是()

A.{}

B.{}

C.{}

D.{,{}}

[答案]:C

2.若是A上的等价关系,则不是()

A.自反的

B.对称的

C.反自反的

D.传递的

[答案]:C

3.已知f:RR,f(x)3x21,试问f为:()

A.内射

B.满射

C.双射

D.非内射,非满射

[答案]:D

4.A;为一个代数系统,下列说法不正确的是().

A.若*有左单位元el且有右单元er那么*有单位元,eeler

B.若*有左零元zl和右零元zr,那么*有零元zzlzr.

C.若*有元数a对*有左逆元a1l和右逆元ar,则a有逆元aalar.

D.若A;为群,则*只有单位元而没有零元.

1页(共14页)第 [答案]:C

5.下列能构成独异点的是()

A.(N;+)

B.(N;-)

C.(N;·)

D.(N;|)

[答案]:C

6.如果()为一个格,那么二元运算不一定满足()

A.交换律

B.结合律

C.吸收律

D.分配律

[答案]:D

7.K3是3个结点的完全图,则()

A.K3有6个边

B.K3有5个边

C.K3是欧拉图

D.K3不是哈蜜顿图

[答案]:C

8.下述语句是命题的是()

A.2x-3=0

B.你喜欢春天吗?

C.天气好暖和呀!

D.我不喜欢春天.

[答案]:D

2页(共14页)第 9.下述公式正确的是()

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(x))xP(x)xQ(x)

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

[答案]:A

10.若T是一个(n,m)树,则()

A.m=n-1

B.n=m-1

C.n-m+k=2

D.m=2n-1

[答案]:A

11.下述说法错误的是().

A.若aA则aAB

B.若aA则aAB

C.若aAB,则aA

D.若A⊂B,则ABA

[答案]:B

12.设G是连通平面图,G中有11个结点,5个面,则G中边的条数是().

A.10

B.12

C.16

D.14

[答案]:C

13.设S{,{1},{1,2}},则有()S.

A,{{1,2}};

3页(共14页)第 B,{1,2};

C,{1};

D,{2}.

[答案]:A

14.设A={1,2,3},则A上有()个二元关系.

A,23;

B,32;

C,223;

D,232

[答案]:D

15.全体小项合取式为().

A,可满足式;

B,矛盾式;

C,永真式;

D,A,B,C都有可能.

[答案]:C

16.关于有补格的描述不正确的是().

A.有补格必有界

B.有补格中每个元素的补元一定存在

C.有补格满足德摩根定律

D.有补格的元素不一定有限

[答案]:C

17.若图G的所有回路均为偶数长,则G().

A.G是欧拉图

B.G是哈图

C.G是平面图

D.G是二部图

4页(共14页)第 [答案]:D

18.下述公式正确的是().

A.PQQP

B.PQQP

C.PQQP

D.PQPQ

[答案]:C

19.设A=｛a,b,c,d｝,A上的关系ρ=｛(a,b),(b,a),(c,a),(c,b),(a,a),(b,b)｝,则ρ是().

A.自反的

B.对称的

C.反对称的

D.传递的

[答案]:D

20.复合语句”他工作很努力;但是思想僵化”中的逻辑联结词为().

A.∨

B.∧

C.→

D.↔

[答案]:B

21.下面四组数能构成无向图的度数列的有().

A,2,3,4,5,6,7;

B,1,2,2,3,4;

C,2,1,1,1,2;

D,3,3,5,6,0.

[答案]:B

5页(共14页)

第 22.图的邻接矩阵为()

100001011101A,1000

111111111111B,1111

010000111101C,1000

010001011101D,1000

[答案]:C

23.设S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},

S5={3,5},在条件XS1且XS3下X与()集合相等.

A,X=S2或S5;

B,X=S4或S5;

C,X=S1,S2或S4;

D,X与S1,…,S5中任何集合都不等.

[答案]:B

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

6页(共14页)第 A,

B,

C,

D,[答案]:B

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

A、

{2,3};

B,{1,2,3};

C,{1,3};

D,.

[答案]:B

26.下述命题公式中,是重言式的为().

A,(pq)(pq);

B,(pq)((pq))(qp));

C,(pq)q;

S第7页(共14页)

D,(pp)q.

[答案]:C

(pq)r的主析取范式中含极小项的个数为().

A,2;

B,3;

C,5;

D,0

[答案]:C

28.给定推理

①x(F(x)G(x)) P

②F(y)G(y) US①

③xF(x) P

④F(y) ES③

⑤G(y) T②④I

⑥xG(x) UG⑤

x(F(x)G(x))xG(x)

推理过程中错在().

A,①->②;

B,②->③;

C,③->④;

D,④->⑤

[答案]:C

29.设S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},

8页(共14页)第 S5={3,5},在条件XS1且XS3下X与()集合相等.

A,X=S2或S5;

B,X=S4或S5;

C,X=S1,S2或S4;

D,X与S1,…,S5中任何集合都不等.

[答案]:C

30.设R和S是P上的关系,P是所有人的集合,R{x,y|x,yPx是y的父亲},S{x,y|x,yPx是y的母亲}则S1R表示关系().

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的祖父或祖母}.

[答案]:A

31.下面函数()是单射而非满射.

A,f:RR,f:ZR,B,f(x)x22x1;

f(x)lnx;

C,f:RZ,D,f:RR,[答案]:B

f(x)[x],[x]表示不大于x的最大整数;

f(x)2x1.

32.其中R为实数集,Z为整数集,R+,Z+分别表示正实数与正整数集.设S={1,2,3},R为S上的关第9页(共14页)

系,其关系图为则R具有()的性质.

A,自反,对称,传递;

B,什么性质也没有;

C,反自反,反对称,传递;

D,自反,对称,反对称,传递.

[答案]:D

二.不定项

1.下列语句是命题的有().

A,明年中秋节的晚上是晴天;

B,xy0;

C,xy0当且仅当x和y都大于0;

D,我正在说谎.

[答案]:AC

2.下列各命题中真值为真的命题有().

A,2+2=4当且仅当3是奇数;

B,2+2=4当且仅当3不是奇数;

C,2+2≠4当且仅当3是奇数;

D,2+2≠4当且仅当3不是奇数;

[答案]:AD

3.下列符号串是合式公式的有()

A,PQ;

B,PPQ;

10页(共14页)第 C,(PQ)(PQ);

D,(PQ).

[答案]:CD

4.下列等价式成立的有().

A,PQQP;

B,P(PR)R;

C,P(PQ)Q;

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

[答案]:AD

5.若A1,A2An和B为wff,且A1A2AnB则().

A,称A1A2An为B的前件;

B,称B为A1,A2An的有效结论

C,当且仅当A1A2AnBF;

D,当且仅当A1A2AnBF.

[答案]:BC

6.以下关系中能构成函数的是()

A.(1.2),(2.1),(3.4),(4.3)

B.(1.2),(1.1),(2.2),(3.2)

C.(1.2),(2.3),(3.4),(4.1)

D.(1.4),(3.1),(2.3),(4.1),(3.2)

[答案]:AC

7.图G如下图所示,则G是()

A.欧拉图,非哈密顿图

11页(共14页)第 B.哈密顿图,非欧拉图

C.非欧拉图,非哈密图

D.欧拉图且哈密顿图

图G

[答案]:ACD

8.下列代数系统能够构成群的是().

A.(Q;+)

B.(Q,-)

C.(R;-)

D.(I,+)

[答案]:AD

三.判断题

1.()设S={1,2},则S在普通加法和乘法运算下都不封闭.

[答案]:T

2.()在布尔格中,对A中任意原子a,和另一非零元b,在ab或ab中有且仅有一个成立.

[答案]:T

3.()设S{x|xZx0}N,+,·为普通加法和乘法,则是域.

[答案]:F

4.()一条回路和任何一棵生成树至少有一条公共边.

[答案]:F

5.()没T是一棵m叉树,它有t片树叶,i个分枝点,则(m-1)i=t-1

[答案]:F

四.问答题

第12页(共14页)

1.说明:A(BC)(AB)(AC)

[答案]:A(BC)A(BC)AABCABAC

2.#A1n1,#A2n2,试问有多少个由A1到A2的不同关系?为什么?

[答案]:共有2n1•n2个A1到A2上的二元关系,因为:依据二元关系的定义,A1到A2上的二元关系是A1与A2的笛卡尔积的任意一个子集,而A1与A2的笛卡尔积共有#(A1A2)n1•n2个元素,再依据幂集的定义,知共有#(2

3.F=Q∨¬((¬P∨Q)∧P)是什么类型的公式?说明理由.

[答案]:Q((PQ)P)Q((PP)(QP))

A1A2)2#A1#A22n1n2个关系.

Q(QP)QQP1P1所以为重言式.

4.证明设h:A→B是(A;)到(B;)的满同态,则如果*是可交换的,则也是可交换的.

[答案]:b1,b2B,由于h为A到B上的满射,故a1,a2A,使得b1h(a1),b2h(a2),则

b1b2h(a1)h(a2)h(a1a2)h(a2a1)h(a2)h(a1)b2b1

故满足交换率.

5.试证明链;　也是一个分配格.

[答案]:(1)设L;是一个链,则L;是一个偏序集,且对l1,l2L有l1l2或l2l1,于是若l1l2,则glb(l1,l2)l1,lub(l1,l2)l2,

若l2l1,则glb(l1,l2)l2,lub(l1,l2)l1

所以L;是格.

设任取l1,l2,l3L,由于L为一个链,故有l1l2l3或l1l3l2或l2l1l3或l3l2l1或l3l1l2,不妨取l1l2l3,那么l1l2l1,l1l3l1,l2l3l3,由定理7-3得

l1(l2l3)l1(l3)l1,而(l1l2)(l1l3)l1l1l1,

第13页(共14页)

所以l1(l2l3)(l1l2)(l1l3)满足分配律,所以链是一个分配格.

6.若图G的所有节点的度为2,则G的每个分图含环.

[答案]:证法一:由于G中所有结点的度均为2,那么对G中任一连通分图来讲,它必然是一个欧拉图,并且每个结点在欧拉回路中只出现一次,换句话说G的每个分图均是环,所以G是由环构成的.

证法二:设G有r个分图G1,......,Gr,不妨设Gi为(ni,mi)图,假设Gi不含环,则Gi是树,于是mini1,又Gi每个结点度为2,所以由握手定理2ni2mi,nimi矛盾,因此必是Gi含环.

第14页(共14页)