《离散数学》考试试卷（试卷库14卷）及答案

《离散数学》考试试卷（试卷库14卷）

试题总分： 100 分 考试时限：120 分钟

题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分）

1. 下述命题公式中，是重言式的为( )

（A）(p?q)?(p?q) （B）p?q?((p?q)?(q?p))

（C）?(p?q)?q

（D）(p??q)?q

2. 对任意集合A,B,C,下列结论正确的是（ ）

（A）若A?B,B?C,则A?C； （B）若A?B,B?C,则A?C； （C）若A?B,B?C,则A?C； （D）若A?B,B?C,则A?C； 3. 设S?{ 1, 2, 3 }，定义S?S上的等价关系,

S?S上一个划分共有( )个分块。

（A）4

（B）5

（C）6

（D）9

,则由R产生的

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

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

（A）有些边是割边 （B）每条边都是割边

（C）所有边都不是割边 （D）图中存在一条欧拉路径

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

（A） m?3n?6

（B）n?3m?6 （C）m?3n?6 （D） n?3m?6

7. 设P,Q的真值为0,R,S的真值为1,则下面命题公式中真值为1的是（ ）

（A）R?P （B）Q?S （C）P?S （D）Q?R 8. 在图G=中,结点总度数与边数的关系是（ ）

（A）deg(vi)?2|E|

（B）deg(vi)?|E|

（C）

?deg(v)?2|E|

iv?V（D）

?deg(v)?|E|

iv?V9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ）

（A）７ （B）８ （C）９ （D）１４ 10. 设集合A上有四个元素,则A上的不同的等价关系的个数为（ ）

（A）11 （B）14 （C）17 （D）15

二、填空题（每题2分，共20分）

1. 设A={a，b，c，d}，其上偏序关系R的哈斯图为

则R= 。

2. 设A?{x|x?2,n?N}，定义A上的二元运算*为普通乘法、除法和加法，则代数系统中运算*关于 运算具有封闭性。

3. A，B，C表示三个集合，文氏图中阴影部分的集合表达式为

。

A B C n。 4. 矛盾式又叫 式，其定义为 。 5. 的图称为无向图。

第 1 页/共 4 页

6. 设是一个偏序集合，在A的一个子集中，如果 ，则称这个子集为链。 7. 在真值表中，一个公式的真值为Ｆ的指派所对应的大项的合取，即为此公式的 范式。

8. 设R是非空集合A上的等价关系，对任意的a?A，定义 为a关于R的等价类。 9. 设是一个群，A，B∈P(G)且A≠?，B≠?，则A和B的积AB= 。 10. 的无向图称为树。

三、判断题（每题1分，共10分）

1. 公式?xP(x)??yQ(x,y)的前束范式为?x?y(P(x)?Q(x,y))。（ ） 2. (A?B)?C=(A?C) ?(B?C)。（ ） 3. 不存在既对称又反对称的关系。（ ）

4. 若无向连通图G中存在桥，则G的点连通度和边连通度都是1。（ ） 5. {{?}}?{ ?，{{?}}}。（ ）

6. 任意图结点度数的总和等于边数的两倍。（ ）

7. 设?A,?,??是布尔代数，则?A,?,??一定为有补分配格。（ ） 8. 群中有零元。（ ）

9. 质数阶群没有非平凡子群。（ ）

10. (?x)A(x)∨(?x)B(x) ?(?x)(A(x)∨B(x))（ ）

四、解答题（3小题，共20分）

1. （5分）考虑在七天内安排七们功课的考试，使得同一位教师所任的两们课程考试不安排在接连的两天里，试说明如果没有教

师担任多于四门课程，则符合上述要求的考试安排总是可能的。 2.

3. （8分）求公式(Q?P) ∧P∧R的主析取范式和主合取范式。

4. （7分）已知无向图G有11条边,2度与3度顶点各2个,其余都是4度顶点,求G中共有几个顶点，写出过程。

第 2 页/共 4 页

五、证明（5小题，共30分）

1. （10分）用推理P,T规则证明：P→(Q→R)，R→(Q→S) ? P→(Q→S)。

2. 对于正整数k,Nk＝{0,1,2,…,k-1},设*k是Nk上的一个二元运算,使得a*kb=a*b(mod k),这里a,b∈Nk。当k＝4时构造出的*k

运算表。（4分）

3. （6分）设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。

4. （4分）设Ａ，Ｂ，Ｃ是三个集合，证明：A－(B?C)＝(A－B)－C。

5. （6分）设G是连通简单平面图，结点数为n（n?3），边数为m，面数为r，则r?2n?4。

试题参考答案及评分标准

一、选择题（每题2分，共20分） ADBCB ADCBD 二、填空题（每题2分，共20分）

1.{,,,,}?IA

2. 乘法

3. B?C?A?B?C

4.永假公式 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式。 5. 所有边都是无向边

6. 每两个元素都是有关系的 7. 主合取

8. [a]R = {x?A | aRx} 9. {a*b|a∈A,b∈B} 10. 连通且无回路

三、判断题（每题1分，共10分）×√×√× √√×√× 四、解答题（3小题，共20分） 1．（5分）设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故G总包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当安排。 2．（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。 解：主析取范式:(P∧Q∧R)

主合取范式: (P∨Q∨R)∧(P∨┐Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R) 3.（7分）解：设图G中有4度的顶点的个数为X，总的顶点的个数为V，则有V=2+2+X 根据顶点度数之和与边的数目的关系，则有2*2+3*2+4*X=2*11 （5分） 由此式得X=3 （3分）

总的顶点个数V=2+2+3=7 （2分）

五、证明（4小题，共30分）

1. （10分）每步约2分，没有P,T标识扣3分,没有序号扣3分。证明过程： （1）P→(Q→R) P （2）R→(Q→S) P （3）(Q→R)→S T(2)E （4）(Q→R)→(Q→S) T(3)E （5）P→(Q→S) T(1)(4)I 2. （4分） *4 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 3. （6分） 证明：设R不是反对称的，即存在?R??R时有x?y，则由R是可传递的得,?R,与R是反自反的矛盾，所以R不是反对称的不成立，即R一定是反对称的。（10分） 4. （4分）证明过程：

A－(B?C)＝A?~(B?C) = A?(~B?~C)= (A?~B)?~C＝(A－B)－C（4分）

第 3 页/共 4 页

5. （6分）证明过程：设G是连通简单平面图，结点数为n（n?3），边数为m，面数为r，则r?2n?4。

当n=3,m=2时，r=1, r?2n?4成立。（1分）

当m?3时，则每一个面的次数不小于3,由于各面的次数之和为2m,因此 2m?3r,（3分）

代入欧拉公式得n+r-m=2，消去m得r?2n?4（2分）

第 4 页/共 4 页

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