-------------------------------------------------------------------------------------- 苏 州 大 学 试 卷
2011 — 2012 学年第二学期期末考试
《 离散数学 》（A卷）
班级 学号 姓名 总分 题 目 得 分 阅卷人 注：P={1,2,3,….}
1.(6’)用题中所提供的变元将下面一段论述转化成命题公式，然后给出形式化证明。
如果天气干燥，那么我将去远足或游泳。我去游泳当且仅当天气暖和。所以，如果我没去远足，则天气是潮湿的或暖和的。(d, h, s, w)
2.(5’)判断下列两个谓词蕴含式的逻辑值。如果逻辑值为F，须举例予以说明【或者通过定
义一个恰当的谓词说明，或者在一个小的论域上（如U={a,b}）通过给变元赋真值验证】。
(a)?y?xp(x,y)??x?yp(x,y)。 (b) ?x?yp(x,y)??y?xp(x,y)。
3.(6’)设A={1, 2, 3}，B?{nn?P,n是偶数}，C?{nn?P,n是奇数}.
(a) 求确定A?B,B?C,B?C,B?C的值。 (b) 列出A的所有子集。
(c) A?B,A?C,A?C,C?A中哪些是无穷集合？
4.(6’)从集合{1,2,3,…,1000}中随机取一个整数，该整数至少能被4,5或6中的一个整除的概率是多少。 5.(5’)整数集合Z上的关系R定义如下：(m,n)∈R当且仅当m3?n3?0(mod5).判断R是否满足自反，反自反，对称，反对称和传递属性。R是否为等价关系？
6.(5’) 设R1和R2是集合S到T上的关系，R3是集合T到U上的关系。证明：
装订 线------------------------------------------------------------------------------------ (R1?R2)?R3?R1?R3?R2?R3
7.(8 ’) 集合S={1,2,3,4,5}上关系R的关系矩阵是：
1
0000101110A?00000，写出下列闭包运算的布尔矩阵：
0100000000(a)r(R)；(b)s(R)；(c)rs(R)；(d)sr(R)；(e)tsr(R)；(f)列出tsr(R)的等价类；
(g)画出与关系R对应的关系图，并计算该关系图的可达性矩阵。简要说明有向图可达性矩阵和对应的传递闭包之间的关系。 8.(7’)下表给出格(L,?)关于”∨”运算的部分结果，例如，b∨d=d.
∨ a b c d e f a b e c a d d e d d e e e e e f a b c d e (a) 将表中剩余部分填满。
(b) 找出L的最大元素和最小元素。 (c) 证明f?c?d?e。 (d) 画出L的哈斯图。
9.(6’)设f和g是Z到Z的映射，其中f(n)?n?1,n?Z，g是集合E?{nn?Z,n是偶数}的特征函数。
(a)计算(g?f)(5),(g?f)(4),(f?g)(7),(f?g)(8), (b)计算(f?f)(11),(f?f)(12),(g?g)(11),(g?g)(12)。 (c)确定函数g?f和f?f.
(d)证明：g?g?g?f,f?g??(g?f)
10.(5’)(a)证明若S和T是可数的，则S×T也是可数的；
(b)证明若f是S到T的满射并且S是可数的，则T也是可数的； (c)用(a)和(b)的结论证明有理数集合Q是可数的。
11.(8’) 设?是布尔代数B1和B2之间的一一对应，且已知?保持或运算∨。
(a)证明?也保持或运算∨；即，如果x,y∈B2和a,b∈B1且满足x??(a),y??(b)，则
-1?-1(x?y)?a?b??-1(x)??-1(b)
(b)证明?保持序关系≤；即，如果在B1中c≤d,则在B2中有?(c)??(d)。
2
(c)证明如果01和02分别是B1和B2的全下界，则?(01)?02。 (c)证明如果11和12分别是B1和B2的全上界，则?(11)?12。 12.(8’)设两个变元的布尔函数的集合用BOOL(2)表示，B={0,1}.
(a)用列表形式写出布尔代数BOOL(2)的全部原子。
(b)将定义在g:B2?B上的函数g(x,y)?x用BOOL(2)中的原子”∨”表示出来。 (c)写出布尔表达式x??y的析取范式，并用BOOL(2)中的原子”∨”表示出来。 13.(5’) 设完全图K6的顶点为v1,v2,…,v6.
(a) K6中有多少个与K4同构子图？
(b)从v1到v2所有长度小于等于3的迹有几条？ (c) K6中所有长度小于等于3的迹总共有几条？ 14.(5’) (a)画一个能构造3阶de Bruijn序列的有向图。
(b)根据你所画出的有向图，写出两个3阶de Bruijn序列。
15.(5’)(a)一棵树有n2个节点度数是2，n3个节点的度数是3，…，nk个节点的度数是k，问
它有几个度数为1的节点。
16.(5’) (a)找出下图的最小生成树。
(b)最小生成树的总权重是多少？
(c)此图中Hamilton回路的最小权重是多少？
(e)判断此图中有没有Euler回路或Euler路，如果有的话，计算相应的权重；如果没有的话，说明原因。
4 2 4 2 2 1 2 4 3 5 4 3 2 4
17(5’)假设要用字母C, E, L, S, U, Y的二进制码字编写信息，它们的使用频率分别为7, 31, 20,
24, 12, 6. (a) 画一颗使这些字母编码效率最高的树。 (b) 用(a)中确定的编码方法对信息CLUE进行编码。
3