2012年6月离散数学期末考试题及答案

1上海海事大学试卷2011—2012学年第二学期期末考试《离散数学》（A卷）班级学号姓名总分注：P={1,2,3,….}1.(6’)用题中所提供的变元将下面一段论述转化成命题公式，然后给出形式化证明。如果天气干燥，那么我将去远足或游泳。我去游泳当且仅当天气暖和。所以，如果我没去远足，则天气是潮湿的或暖和的。(d,h,s,w)2.(5’)判断下列两个谓词蕴含式的逻辑值。如果逻辑值为F，须举例予以说明【或者通过定义一个恰当的谓词说明，或者在一个小的论域上（如U={a,b}）通过给变元赋真值验证】。(a)),(),(yxpyxyxpxy。(b)),(),(yxpxyyxpyx。3.(6’)设A={1,2,3}，},{},{是奇数，是偶数nPnnCnPnnB.(a)求的值确定CBCBCBBA,,,。(b)列出A的所有子集。(c)ACCACABA,,,中哪些是无穷集合？4.(6’)从集合{1,2,3,…,1000}中随机取一个整数，该整数至少能被4,5或6中的一个整除的概率是多少。5.(5’)整数集合Z上的关系R定义如下：(m,n)∈R当且仅当)5(mod033nm.判断R是否满足自反，反自反，对称，反对称和传递属性。R是否为等价关系？6.(5’)设R1和R2是集合S到T上的关系，R3是集合T到U上的关系。证明：3231321)(RRRRRRR7.(8’)集合S={1,2,3,4,5}上关系R的关系矩阵是：题目得分阅卷人--------------------------------------------------------------------------------------装订线------------------------------------------------------------------------------------20000000010000000111010000A，写出下列闭包运算的布尔矩阵：(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.∨abcdefaeaeeabddebcdecdedeef(a)将表中剩余部分填满。(b)找出L的最大元素和最小元素。(c)证明edcf。(d)画出L的哈斯图。9.(6’)设f和g是Z到Z的映射，其中Znnnf,1)(，g是集合},{是偶数nZnnE的特征函数。(a)计算),8)((),7)((),4)((),5)((gfgffgfg(b)计算)12)((),11)((),12)((),11)((ggggffff。(c)确定函数fffg和.(d)证明：)(,fggffggg10.(5’)(a)证明若S和T是可数的，则S×T也是可数的；(b)证明若f是S到T的满射并且S是可数的，则T也是可数的；(c)用(a)和(b)的结论证明有理数集合Q是可数的。11.(8’)设是布尔代数B1和B2之间的一一对应，且已知保持或运算∨。(a)证明1-也保持或运算∨；即，如果x,y∈B2和a,b∈B1且满足)(),(byax，则)()()(1-1-1-bxbayx(b)证明保持序关系≤；即，如果在B1中c≤d,则在B2中有)()(dc。3(c)证明如果01和02分别是B1和B2的全下界，则210)0(。(c)证明如果11和12分别是B1和B2的全上界，则211)1(。12.(8’)设两个变元的布尔函数的集合用BOOL(2)表示，B={0,1}.(a)用列表形式写出布尔代数BOOL(2)的全部原子。(b)将定义在BBg2:上的函数xyxg),(用BOOL(2)中的原子”∨”表示出来。(c)写出布尔表达式yx的析取范式，并用BOOL(2)中的原子”∨”表示出来。13.(5’)设完全图K6的顶点为v1,v2,…,v6.(a)K6中有多少个与K4同构子图？(b)从v1到v2所有长度小于等于3的迹有几条？(c)K6中所有长度小于等于3的迹总共有几条？14.(5’)(a)画一个能构造3阶deBruijn序列的有向图。(b)根据你所画出的有向图，写出两个3阶deBruijn序列。15.(5’)(a)一棵树有n2个节点度数是2，n3个节点的度数是3，…，nk个节点的度数是k，问它有几个度数为1的节点。16.(5’)(a)找出下图的最小生成树。(b)最小生成树的总权重是多少？(c)此图中Hamilton回路的最小权重是多少？(e)判断此图中有没有Euler回路或Euler路，如果有的话，计算相应的权重；如果没有的话，说明原因。17(5’)假设要用字母C,E,L,S,U,Y的二进制码字编写信息，它们的使用频率分别为7,31,20,24,12,6.(a)画一颗使这些字母编码效率最高的树。(b)用(a)中确定的编码方法对信息CLUE进行编码。435442134422224参考答案注：P={1,2,3,….}1.(6’)设：d:=天气干燥;h:=我去远足;s:=我去游泳;w:=天气暖和。(d,h,s,w)条件：d→h∨s,s↔w.结论：﹃h→﹃d∨w证明：①﹃h附加前提②d→h∨sP③﹃d∨h∨sT②E④﹃d∨sT①③I⑤s↔wP⑥s→wT⑤I⑦﹃s∨wT⑥E⑧﹃d∨wT④⑦I2.(5’)(a)真值F。例如，假设U={a,b},令p(x,y)表示命题“x=y”,则逻辑蕴含不成立。(b)真值T。3.(6’)(a)P,P,,{2}CBCBCBBA(b){1,2,3}}{2,3}{1,3}{1,2}{3}{2}{1}{，，，，，，，(c)ACCA,BA，。4.(6’)0.4665.(5’)满足自反，对称，传递。是等价关系。6.(5’)32131211)(RRRRRRRR，,同理可得，32132)(RRRRR所以，3213231)(RRRRRRR反之，设321)(),(RRRus，则321),(),(,RutRRtsTt且使得。若311),(),(RRusRts，此时，若322),(),(RRusRts，此时，总之，3231),(RRRRus，故3231321)(RRRRRRR。证毕。7.(8’)(a)1000001010001000111010001)(Ar;(b)0000100010000100111010000)(As;5(c)1000101010001100111010001)(Ars;(d)1000101010001100111010001)(Asr;(e)1000101110011100111010001)(Atsr;(f)[1]={1,5};[2]={2,3,4}.（g）与关系R对应的关系图如下和该关系图的可达性矩阵如下：0000001110000000111010000)(At134526一个有向图可达性矩阵就是其对应关系的传递闭包。8.(7’)(a)表中红色部分为填入元素。∨abcdefaaeaeeabebddebcadcdecdedddedeeeeeeefabcdef(b)L的最大元素和最小元素分别为：e,f(c)证明cfccf,,同理可证，eddc,，edcf(d)画出L的哈斯图如下：9.(6’)(e)1,0,-1,0(f)9,10,1,0(c)fg是E的特征函数，Znnnff,2)((d)证明：fgggEZnEnfgEZnEngg,1,0,,1,0同理可证：)(fggf10.(5’)(a)TttSTS}){(:，每个S×{t}是可数的，所以S×T也是可数的。(b)对每个t∈T,设g(t)是S的元素且f(g(t))=t,则g是单射函数。所以T是S的子集，已知S是可数的，所以S的子集T也是可数的。(c)由(a)可知，Z×P是可数的。又因为从Z×P到Q存在满射函数f,根据(b)的结论，Q是可数的。11.(8’)(a))()())(())()(()(1-1-1-1-1-bxbababayx，(b)若c≤d，则d=c∨d,所以)()()()()()(dcdcdcd故，dfcbae7(c)因为φ是B2上的满射，所以在B1中存在e，使得φ(e)=02.故2112110)()0()()0(0)0()0(eee(d)与(c)类似，设φ(e)=12.则22111111)1()()1()1()1(ee12.(8’)(a)xyabcd001000010100100010110001(b)根据(a)中的记号，g=c∨d(c)根据(a)中的记号，yx=a∨b∨d13.(5’)(a)1546C(b)1+4+4×3=17(c)6×5+6×5×4+6×5×4×4=63014.(5’)(a)(b)两个序列如下：15.(5’)是度数为1的节点数为x个，则)1(2323232xnnnxknnnkk所以，2)2(243knknnxd100100011011000111111111100000000816.(6’)(a)(b)18。(c)28。(d)有欧拉路，其权重是42；没有欧拉回路，因为有奇度数的节点。17.(6’)(a)下图是符合要求的最优树之一：(b)使用(a)中的最优树可得其编码为：10110010011LSECYU4413222