离散数学期末考试及答案-6

厦门大学《离散数学》课程试卷

软件学院2008年级

主考教师：金贤安 试卷类型：（A卷）

一、 选择题（共10题，每题3分，共30分）CDDAC DCADD

1、下列语句为命题的是（ ）。

A．勿踏草地；。

B．你去图书馆吗？； C．月球上有水； D．本命题为假。

2．下列推理中，（ ）是错误的。

A. 如果x是有理数，则它为整数。1/2是有理数。所以1/2是整数。

B. 若周末气温超过30度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。 C. 下午小明或者去看电影，或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。 D. 若a能被4整除，则a能被2整除。a能被2整除。因此a能被4整除。 3．谓词公式?x(P(x)??yR(y))?Q(x)中的x( )。 A．只是约束变元 B．只是自由变元

C．既非约束变元又非自由变元 D．既是约束变元又是自由变元

4. 下列关系中，（ ）不是等价关系。 A. 非空集合的幂集的元素间包含关系； B. 集合之间的等势关系； C. 公式之间的等值关系； D. 图之间的同构关系。

5. 下面等值式中，（ ）是不正确的。 A. ?x(A(x)?B(x))??xA(x)??xB(x) B. ?x(A(x)?B(x))??xA(x)??xB(x) C. ?x(A(x)?B)??xA(x)?B D. ?x(A?B(x))?A??xB(x)

1

6．下列关于集合的势的叙述中，（ ）是错误的。 A. 实数集比自然数集优势；

B. 任一无限集合都存在与自己等势的真子集； C. 集合之间的优势关系是偏序关系； D. 有理数集比整数集优势。

7．设A,B,C是集合，F是关系，G:A?B,D?A，则下列式子中不正确的是（ ）。A．A?B???A?B?B B. G?1(G(D))?D

C. F[A?B]?F[A]?F[B] D. (A?B)?C?A?(B?C) 8. 以下序列中，（ ）是简单可图的。

A. (4,4,3,3,2,2)； B. (3,3,3,1)； C. (5,4,3,2,2)； D. (6,6,3,2,2,2,1)。 9. 下列叙述中错误的是( )。

A．n(n≥2)阶竞赛图都具有哈密顿通路； B．非平凡树不是欧拉图，也不是哈密顿图；

C．n(n≥3且为奇数)阶的二部图一定不是哈密顿图；

D．欧拉回路包含图的所有顶点，哈密顿回路包含图的所有边。 10．下列关于图的连通性的叙述中正确的是( )。

A. 有向图是连通的是指它是强连通的；

B. 任一无向图的点连通度都不超过它的边连通度；

C. 在一n阶圈Cn(n≥4)上任意去掉两个顶点得到得图都有2个连通分支； D. n阶无向完全图的点连通度为n； 二、填空题（共8题，每题3分，共24分）

1．令F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快。则命题“不存在比所有火车都快的汽车”符号化形式为___??x(F(x)?(?y(G(y)?H(x,y)))______________。 2．公式(p?q)?r的主析取范式为_______m1?m3?m7_______。

3．集合A={a,b,c,d}上的等价关系共有___15___个。

4．自对偶图的顶点数n和边数m之间满足关系式为m =_______ m=2n-2________。 5．设T是有t片树叶的2叉正则树，则T应该有_______个顶点。 6．P({Φ,{Φ}}) = _{Φ,{Φ},{Φ,{Φ}},{{Φ}}}____。

2

7．在1到100之间（包含1和100）即不能被2，也不能被3，还不能被5整除的自然数有___26____个。 8．“p仅当q”，“只有q才p”，“除非q才p”这三个命题的符号化分别为___

p?q,p?q,p?q__ , ____ 和 _____ 。（请按顺序填写）

三、应用、计算和证明题（共6题，46分）

1．(6分) 在命题逻辑的自然推理系统中构造下面推理的证明。

前提：┒(P∧┒Q)，┒Q∨R，┒R 结论：┒P

1 （1）?Q?R 前提引入 （2） ?R 前提引入

（3） ?Q （1）（2）析取三段论 （4） ?(P??Q) 前提引入 （5） ?P?Q 置换

(6) ?P (3)(5)析取三段论

2．（8分）设集合A={a，b，c，d}，A上的关系R={,,,,} 求：（1）画出R的关系图。(2分)

（2）R的自反闭包、对称闭包和传递闭包的关系图。（2分，2分和2分）

（1） 如图1

0

（2）r(R)?R?R?R?IA?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?}?IA

s(R)?R?R?1?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?,?d,c?,?c,b?}

t(R)?R?R2???{?a,a?,?a,b?,?a,c?,?a,d?,?b,b?,?b,d??b,a?,?c,d?,?b,c?} 3．（8分）设为一偏序集，其中A={1，2，?，12}，R是A上的整除关系。 （1）画出的哈斯图；（4分）

（2）求A的所有极大元和极小元（2分）

（3）求B={2,3,6}的最小上界和最大下界（2分）。

3

(1)如图2

（2）A的极大元有：7，8，9，10，11，12 A的极小元有：1

（3）B的上界是{6,12},最小上界是6 B的下界是1，最小下界是1

4.（8分）

判断左图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4分）

判断右图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4分）；

5．（8分） 设G是无向简单图且δ(G)≥k≥2，试证明G中存在长度大于等于k+1的初级回路（圈）。

6．（8分）在一棵有3个2度顶点，2个4度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2分）

4

请画出所有这样的非同构的无向树。（6分）

答案及评分标准

一 选择题

CDDAC DCADD 二

1. ??x(F(x)??y(G(y)?H(x,y))) 或者?x(F(x)??y(G(y)??H(x,y))) 2. m1?m3?m7 3. 15

4. m=2n-2 5. 2t-1

6. {?,{?},{{?}},{?,{?}}}

7. 26

8. p?q,p?q,p?q (该小题每空1分) 三

1 （1）?Q?R 前提引入 （2） ?R 前提引入

（3） ?Q （1）（2）析取三段论 （4） ?(P??Q) 前提引入 （5） ?P?Q 置换

(6) ?P (3)(5)析取三段论

若未注明推理规则,或标注有错,扣1分.

2 （1） 如图1

5

（2）r(R)?R?R0?R?IA?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?}?IA

s(R)?R?R?1?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?,?d,c?,?c,b?}

t(R)?R?R2???{?a,a?,?a,b?,?a,c?,?a,d?,?b,b?,?b,d??b,a?,?c,d?,?b,c?} 该题要求画出三个闭包的关系图. 每个关系图2分,共6分. 边少画或多画一律判错. 3 (1)如图2

（2）A的极大元有：7，8，9，10，11，12 A的极小元有：1

（3）B的上界是{6,12},最小上界是6 B的下界是1，最小下界是1

哈斯图中若出现水平的边,扣1分. 4．（８分）

（１）判断下图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4分）

答：因为该图是连通图且图中没有奇度顶点，所以该图是欧拉图(只要判断正确给2分)。欧拉回路标序如下图：

6

１ ９ ８ ２ 14 11 1312 ７

10 ３

６

找的欧拉回路正确再2分

４

５

（2）判断下图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4分）

答：该图不是哈密顿图(2分)。取Ｖ＝｛４，６，８｝，从图中删除Ｖ，得五个连通分支，如下图所示，所以该图不是哈密顿图。(2分)

另一证明:反证若有哈密顿圈,由于点5,7,9都是二度点,因此该哈密顿圈必包含边(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),这6条边构成一个圈,矛盾.

１ １ ６ ５ 10 ４ ９ ７ ５ 10 ８ ９ ７ ２

２

３ ３

５．（8分）设G是无向简单图且δ(G)≥k≥2，试证明G中存在长度大于等于k+1的初级回路（圈）。 证明：不妨设Ｇ是连通图，若G不连通，因为Ｇ的各连通分支的最小度也都大等于k，因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点，由G是连通图，因而u,v之间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为Γt=v0v1?vt,则t≥k，事实上若存在“极大路径” Γs=v0v1?vs

7

且s

在Γt上构造圈，由于δ(v0)≥δ(G)≥k≥2，因而v0除与Γt上的v1相邻外，还存在Γt上的k-1个顶点vi1,vi2,?,vik?1(1?i1?i2???ik?1?t)与v0相邻，则v0v1...vi1...vi2?vik?1v0为一个圈且长度大等于k+1。

注意:也可直接设Γ是G的最长路径.

６．（8分）在一棵有3个2度顶点，2个4度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2分）

请画出所有这样的非同构的无向树。（6分）

答：设树叶有x片，则边数m=3+2+x-1=4+x，由握手定理知，2m=2*(4+x)=∑d(vi)=3*2+2*4+x 解得x=6，所以应该有６片树叶。共有十个非同构的无向树，如下： (1) 两个４度点相邻的情况：

(2) 两个４度点中间有一个２度点的情况：

8

(3) 两个４度点中间有两个２度点的情况：

(4) 两个４度点中间有三个２度点的情况：

(请酌情扣分)

9

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