院（系） 班级 学号（9位） 姓名 ———————————阅————卷————密————封————装————订————线——————————
常熟理工学院20 ～20 学年第 学期
《离散数学》考试试卷（试卷库17卷）
试题总分： 100 分 考试时限：120 分钟
题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题（每题2分，共20分）
1. 下列各命题中真值为真的命题有( )
（A）2+2=4当且仅当3是奇数 （B）2+2=4当且仅当3不是奇数 （C）2+2≠4当且仅当3是奇数 （D）2+2=4仅当3不是奇数
2. G=
（A）{2,3}
（B）{1,2,3}
（C）{1,3}
（D）?
3. 设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
4. 具有如下定义的代数系统?G,??，( )不构成群
（A）G?{1,10}，*是模11乘 （B）G?{1,3,4,5,9}，*是模11乘
（C）G?Q（有理数集），*是普通加法 5. 在如下各图中( )是欧拉图
（D）G?Q（有理数集），*是普通乘法
6. 下面给出的集合中，( )是前缀码
（A）{0，10，110，101111} （B）{1，11，101，001，0011} （C）{b，c，aa，ab，aba} （D）{01，001，000，1} 7. 下面联结词不具有交换律的是（ ）。
（A）? （B）? （C）? （D）?
8. G=
（A） G中至少有一条通路 （B） G中至少有一条回路
（C） G中有通过每个结点至少一次的回路 （D） G中有通过每个结点至少一次的通路。 9. 命题公式A与B是等价的,是指（ ）
（A） A和B有相同的原子变元。 （B）A和B具有相同的真值
（C）A和B是可满足的 （D）当A的真值为真时,B的真值也为真。 10. Z是整数集合,对于下列*运算,哪个
（A）a*b?ab
（B）a*b?a
（C）a*b?a?ab
（D）a*b?a?b
二、填空题（每题2分，共20分）
1. 设A?{2,a,{3},4}，B?{{a},3,4,1}，请在下列每对集合中填入适当的符号：
（1）{a} B (2) {a,4,{3}} A 。
2. 设R为集合A上的等价关系，对?a?A，集合[a]R= ，
[a]R称为元素a形成的R等价类，则[a]R??，因为 。
3. 由n个命题变元组成的不等价的命题公式共有 种。
4. 设
第 1 页/共 3 页
———————————阅————卷————密————封————装————订————线——————————
* a b c a b c a b c b b c c c b 则幺元是 ；是否有等幂性 。
7. A和B的笛卡尔积或直积的定义为:A?B={ }。
8. 设r是集合A上的相容关系，若C?A ，如果 ，称C是由相容关系r产生的相容类。 9. 设
三、判断题（每题1分，共10分）
1. (?x)(F(y) →G(x))???F(y) →(?x)G(x)。（ ） 2. A,B,C是集合，若A?B?A?C，则必须B?C（ ） 3. 自然数集合与有理数集合都是可数集合。（ ） 4. 图G中的每条边都是割边，则G必是树。（ ） 5. 循环群的生成元唯一。 （ ） 6. 命题公式是没有真假值的。（ ） 7. (A?B)?C = A?(B?C) （ ）
8. 对于集合A，一个从A到B的映射，称为集合A上的一个n元运算。如果B?A，则称该n元运算是封闭的。（ ） 9. 有最大元和最小元的偏序集不一定是格。（ ） 10. K3,3是平面图。（ ）
n
四、解答题（4小题，共30分）
1. （5分）什么是“最小联结词组”，目前常用的最小联结词组有哪几个？
2. （8分）求公式 (P?Q)∧P∧R 的主析取范式和主合取范式。
3. （7分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，
有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？
第 2 页/共 3 页
———————————阅————卷————密————封————装————订————线——————————
4. （10分）设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{
方法求出Ｒ的传递闭包。
五、证明（3小题，共20分）
1. （10分）用推理P,T规则证明：A，A→B， A→C， B→(D→?C)??D。
2. （5分）证明：若T是有n个结点的完全二叉树，则T有
3. （5分）在R上定义运算：a?b?a?b?ab。证明
n?1片叶子。 2
第 3 页/共 3 页
离散数学17
