苏州大学2012年离散数学期末考试题及答案

1、-装 订 线-苏 州 大 学 试 卷2011 2012 学年第二学期期末考试 离散数学 （A卷）班级 学号 姓名 总分 题 目得 分阅卷人注：P=1,2,3,.1.(6)用题中所提供的变元将下面一段论述转化成命题公式，然后给出形式化证明。如果天气干燥，那么我将去远足或游泳。我去游泳当且仅当天气暖和。所以，如果我没去远足，则天气是潮湿的或暖和的。(d, h, s, w)2.(5)判断下列两个谓词蕴含式的逻辑值。如果逻辑值为F，须举例予以说明【或者通过定义一个恰当的谓词说明，或者在一个小的论域上（如U=a,b）通过给变元赋真值验证】。(a)。(b) 。3.(6)设A=1, 2, 3，.(a) 求。

2、(b) 列出A的所有子集。(c) 中哪些是无穷集合？4.(6)从集合1,2,3,1000中随机取一个整数，该整数至少能被4,5或6中的一个整除的概率是多少。5.(5)整数集合Z上的关系R定义如下：(m,n)R当且仅当.判断R是否满足自反，反自反，对称，反对称和传递属性。R是否为等价关系？6.(5) 设R1和R2是集合S到T上的关系，R3是集合T到U上的关系。证明：7.(8 ) 集合S=1,2,3,4,5上关系R的关系矩阵是：，写出下列闭包运算的布尔矩阵：(a)r(R)；(b)s(R)；(c)rs(R)；(d)sr(R)；(e)tsr(R)；(f)列出tsr(R)的等价类；(g)画出与关系R对应

3、的关系图，并计算该关系图的可达性矩阵。简要说明有向图可达性矩阵和对应的传递闭包之间的关系。8.(7)下表给出格关于”运算的部分结果，例如，bd=d.abcdefaeaeeabddebcdecdedeef(a) 将表中剩余部分填满。(b) 找出L的最大元素和最小元素。(c) 证明。(d) 画出L的哈斯图。9.(6)设f和g是Z到Z的映射，其中，g是集合的特征函数。(a)计算(b)计算。(c)确定函数.(d)证明：10.(5)(a)证明若S和T是可数的，则ST也是可数的；(b)证明若f是S到T的满射并且S是可数的，则T也是可数的；(c)用(a)和(b)的结论证明有理数集合Q是可数的。11.(8)

4、设是布尔代数B1和B2之间的一一对应，且已知保持或运算。(a)证明也保持或运算；即，如果x,yB2和a,bB1且满足，则(b)证明保持序关系；即，如果在B1中cd,则在B2中有。(c)证明如果01和02分别是B1和B2的全下界，则。(c)证明如果11和12分别是B1和B2的全上界，则。12.(8)设两个变元的布尔函数的集合用BOOL(2)表示，B=0,1.(a)用列表形式写出布尔代数BOOL(2)的全部原子。(b)将定义在上的函数用BOOL(2)中的原子”表示出来。(c)写出布尔表达式的析取范式，并用BOOL(2)中的原子”表示出来。13.(5) 设完全图K6的顶点为v1,v2,v6.(a)

5、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路，如果有的话，计算相应的权重；如果没有的话，说明原因

6、。4354421344222217(5)假设要用字母C, E, L, S, U, Y的二进制码字编写信息，它们的使用频率分别为7, 31, 20, 24, 12, 6.(a) 画一颗使这些字母编码效率最高的树。(b) 用(a)中确定的编码方法对信息CLUE进行编码。参考答案注：P=1,2,3,.1.(6)设：d:=天气干燥; h:=我去远足; s:=我去游泳; w:=天气暖和。(d, h ,s, w)条件：dhs, sw.结论：hdw证明： h附加前提 dhsP dhsTE dsTI swP swTI swTE dwTI2.(5)(a)真值F。例如，假设U=a,b,令p(x,y)表示命题“x=

7、y”,则逻辑蕴含不成立。(b)真值T。3.(6)(a) (b) (c) 。4.(6)0.4665.(5)满足自反，对称，传递。是等价关系。6.(5) ,同理可得，所以，反之，设，则。若，若，总之，故。证毕。7.(8) (a) ; (b) ; (c) ;(d) ; (e) ; (f)1=1,5; 2=2,3,4.（g）与关系R对应的关系图如下和该关系图的可达性矩阵如下： 513452一个有向图可达性矩阵就是其对应关系的传递闭包。8.(7)(a)表中红色部分为填入元素。abcdefaaeaeeabebddebcadcdecdedddedeeeeeeefabcdef(b)L的最大元素和最小元素分别为

8、：e,f(c)证明,同理可证，(d)画出L的哈斯图如下：dfcbae9.(6)(e) 1,0,-1,0(f) 9,10,1,0(c)是E的特征函数，(d)证明：同理可证：10.(5)(a)，每个St是可数的，所以ST也是可数的。(b)对每个tT,设g(t)是S的元素且f(g(t)=t,则g是单射函数。所以T是S的子集，已知S是可数的，所以S的子集T也是可数的。(c)由(a)可知，ZP是可数的。又因为从ZP到Q存在满射函数f,根据(b)的结论，Q是可数的。11.(8)(a) ， (b)若cd，则d=cd,所以(c)因为是B2上的满射，所以在B1中存在e，使得(e)=02.故(d) 与(c)类似，设(e)=12.则12.(8)(a)xyabcd001000010100100010110001(b)根据(a)中的记号，g=cd(c)根据(a)中的记号，= abd13.(5) (a)(b) 1+4+43=17(c) 65+654+6544=63014.(5)(a)d10010001101100011(b)两个序列如下：111111110000000015.(5)是度