《离散数学》考试题库及答案一

《离散数学》考试题库及答案

一、选择题（2*10）

[■令P：今天下雨了,

Q：我没带伞，则命题“虽然今天下雨了，但是我没

带伞”可符号化为（）。

(A)P-「Q(B)PV^Q

(C)PAQ(D)PA^Q

2.下列命题公式为永真蕴含式的是（）。

(A)Q—(PAQ)(B)P—(PAQ)

(C)(PAQ)-P(D)(PVQ)-Q

3、命题“存在一些人是大学生”的否定是（A）,而命题“所有的人都是要死

的”的否定是（）。

（A）所有人都不是大学生，有些人不会死

（B）所有人不都是大学生，所有人都不会死

（C）存在一些人不是大学生，有些人不会死

（D）所有人都不是大学生，所有人都不会死

■永真式的否定是（）。

（A）永真式（B）永假式（C）可满足式（D）以上均有可能

5、以下选项中正确的是（）o

（A）0=0（B）070（C）OG0（D）0庄0

6、以下哪个不是集合A上的等价关系的性质？（）

（A）自反性（B）有限性（C）对称性（D）传递性

■集合A={l,2,...,10}上的关系R={<x,y>|x+y=10,x,y£A},则R的性质为（）。

（A）自反的（B）对称的

（C）传递的，对称的（D）传递的

■设D=<V,E>为有向图，V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}

是（）。

（A）强连通图（B）单向连通图

（C）弱连通图（D）不连通图

9、具有6个顶点，12条边的连通简单平面图中，每个面都是由（）条边

围成?

(A)2(B)4(C)3(D)5

10.连通图G是一棵树，当且仅当G中()o

(A)有些边不是割边(B)每条边都是割边

(C)无割边集(D)每条边都不是割边

二'填空题(2*10)

1、命题“2是偶数或-3是负数”的否定是。

■设全体域D是正整数集合，则命题VxR(xy=y)的真值是。

3、令R(x):x是实数，Q(x):x是有理数。则命题”并非每个实数都是有理数”的符

号化表示为o

4、公式(「PAQ)v(「PArQ)化简为o

5、设AAB=Anc,NnB=Anc,则BCo

A={2,4,6},A上的二元运算*定义为:a*b=max{a,b},则在独异点＜A,*＞中,

单位元是，零元是0

7、任一有向图中，度数为奇数的结点有(奇数/偶数)个。

8.如下无向图割点是，割边是。

三、(10分)设A、8和C是三个集合，贝”AuBnTBE)。

o四、（15分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面

3个条件，有几种派法？如何派？

⑴若A去，则C和D中要去1个人；

（2）B和C不能都去;

⑶若C去，则D留下

五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质:

六、（20分）画一个图使它分别满足：

（1）有欧拉回路和哈密尔顿回路；

（2）有欧拉回路，但无条哈密尔顿回路;

（3）无欧拉回路，但有哈密尔顿回路；

（4）既无欧拉回路，又无哈密尔顿回路。

答案：

一、选择题：

1、D2、C3、A4、B5、D

6、B7、B8、C9、C10、B

二、填空：

1、2不是偶数且-3不是负数

2、F

3、「Vx(R(x)-Q(x))

4、

5、等于

6、2,6

7、偶数

8、d,e5

三、证明：

Vx(x€4fxeB)AB/\x史4)=Vx(x史4Vx£B)A3^r(x€B/\x^A)

<=>—i3x(x€AAB)A—iVKxgSVxC4)n—imKxCAAx^,B)V—i\/x(xEAVx^B)

=—i(3x(xCA/\x年B)NVx(x€AVx七功igMxCAAB)AVA(X€B~^X£4))

—l(-Sty4)o

四、解设4:4去工作；B-.8去工作；O.C去工作；D;“去工作。则根据

题意应有：A-^C®D,TB/\Q,八「。必须同时成立。因此

A」(8入QA

=(「4V(CA「。V(「。八。)A(「8V」0A(「CV

V(CA「。V(「。入。)八((「8人」0V(「8AV「CV(「CN」0

<=>(—iAA—18A—\C)V(~A—18A—\D)V(~i/A—।C)V(~i^4A—।C/\—\D)

V(CA—।Dl\―\BN―।C)V(CA—।D!\―18A―iZT)V(CA―।Dt\―\C)V(CA—।D/\

—।C/\—\D)

NrCNDJBJQNCCNDJBJD)NJCNDJQNCCNDJC

入「o

=FVFVJ4A「QVFVFV(CA「。八」乃)VFVFV(「CA。入」歹)VFV

(「CA。VF

=(-4人「QV八C"D)N(「CADN「B)V(」CA。

入VJBNCA「。V(」CAD)

oT

故有三种派法：BND,ANC,AND。

五、

"000、

(1)R={<2,1>,<3,1>,<2,3>};M=101;它是反自反的、反对称的、传递的;

R[100J

/011、

(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};M=101;它是反自反的、

RLioj

对称的；

‘011、

(3)R={<1,2>,<2,1>,<1,3>,<3,3>};MR=100;它既不是自反的、反自反的、

〔。oJ

也不是对称的、反对称的、传递的。

~7\、

《离散数学》考试题库及答案

一、单项选择题：本大题共15小题，每小题1分，共15分，在每小题列出

的备选项中只有一项是最符合题目要求的，请将其选出。

1.令P：他怕困难,q：他战胜困难,命题〃他战胜困难是因为他不怕困难〃的符

号化形式为

A.p—♦qB.q—►pC.pAqD.pVq

2.令F(x)：x为苹果，H(x,y)：x与y完全相同，L(x,y):x=y,则命

题“没有完全相同的苹果”的符号化形式为

Ar3x3y(F(x)AF(y)AL(x,y)-H(x,y))

B.r3x3y(F(x)AF(y)A-L(x,y)AH(x,y))

Cr3x3y(F(x)AF(y)ArL-H(x,y))

D.VxVy(F(x)AF(y)ArL(x,y)ArH(x,y))

3.一颗树有2个4度结点，3个3度结点，其余为树叶，则该树中树叶个数是

A.7B.8C.9D.10

4.设集合A={a,b,c,d},现有A上的二元关系R={<a,b>,<b,c>,<c,b>,

<b,a>},则A是

A.自反的B.对称的

C.反对称的D.传递的

5.下图中为欧拉图的是

6.下列谓词公式中，不是前束范式的为

A.VxVy(A(x)4B(y))

B.Vx3y(A(x)AB(y))

CVx3y(A(x)AB(y)-C(z))

D.Vx3y(A(x)AB(y)—>3zC(z))

7.表示集合之间关系的图是

A.文氏图B.哈斯图C.欧拉图D.树

8.无向完全图A的边的条数为

A.10B.15C.20D.30

9.设T是n阶树(nN2),则T下耳净的性质是

A.连通图•••B.哈密顿图

C.有n-1条边D.至少有两片树叶

10.设R、S均为集合A上的二元关系，下面命题正确的是

A.若R与S是自反的，则R・S也是自反的

B.若R与S是反自反的，则R・S也是反自反的

C若R与S是对称的，则R。S也是对称的

D.若R与S是传递的，则R。S也是传递的

11.以下关于图的矩阵的描述，正确的是

A.邻接矩阵即关系矩阵B.可达矩阵是针对无向图的

C•无向图有邻接矩阵D.可达矩阵是针对有向图的

12.一个6阶连通图的边数至少为

A.4B.5C.6D.7

13.下列关于反函数的命题，正确的是

A.单射函数有反函数B.任意函数均有反函数

C.满射函数有反函数D.双射函数有反函数

14.一个6阶图,其各结点度数之和不可整为

A.10B.12a15D.20

15.在整数集合Z上定义*运算如下：江也€2述*卜=&+1)-10,则代数系统<2,*>是

A.格B.环C.域D.群

非选择题部分

注意事项：

用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题：本大题共10小题，每小题2分，共20分。

16.设E={a,b]是字母表，£•表示由工上的字符构成的有限长度的申的集合(包含长

度为0的串，即空串在内)，A=|a,bvaa,bb,aaa,bbb|,B={colcoG£'A,

C=|(i)l(De£*AI<i)l^2],贝ijA-(BCC)=o

浙02324#离散数学试题第2页(共4页)

17.在整数域中，命题公式Vxmy(x•y=0)的真值为，命题公式

3xVy(x-y=D的真值为。

18.设A为非空有限集合,P(A)为A的再集，U为集合的并运算，群<P(A),U>中，单

位元是零元是O

19.一个手锡等距离地镶嵌着5颗彩珠，每颗彩珠可以从红、白、蓝、绿、黄5种颜色中挑

选。如果要求手银匕的彩珠颜色都不相同,则可以构成种不同颜色

彩珠分布的手镯。

20.某连通平面图有6个顶点，其平面表示中共有8个面，则其边有条。

21.设布"集合A=[a,b,c,d}上的二元关系R={<a,b>,<b,a>,<c,c>,<d,d>|,

则R2=,R3=e

22.为了从无向完全图5中得到其生成树,至少需要删除条边。

23.设有集合A=|a,b,c|上的二元关系RI=|<a,b>,<a,c>,<c,b>},则R1的

自反闭包r(RI)=R1的对称闭包s(Rl)=o

24.一个无向图有21条边，有3个4度结点，其余结点均为3度，则其结点共有

__________个。

25.设集合A=[1,2,3|,集合8=|a,，<;,<1,“，则1人*81=而

IP(A)xBI=o

三、计算题：本大题共5小题，每小题6分，共30分。

26.用列真值表的方法说明下列逻辑等价式成立

(P-(Q-P))o(rP-(Q-rP))o

27.用等值演算法推导命题公式(PTQAR)八5P-(rQArR))的主析