月离散数学期末考试题及答案.docVIP

上 海 海 事 大 学 试 卷 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) 求。 (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对应的关系图，并计算该关系图的可达性矩阵。简要说明有向图可达性矩阵和对应的传递闭包之间的关系。 8.(7’)下表给出格关于”∨”运算的部分结果，例如，b∨d=d. ∨ a b c d e f a e a e e a b d d e b c d e c d e d e e f 将表中剩余部分填满。 找出L的最大元素和最小元素。 证明。 画出L的哈斯图。 9.(6’)设f和g是Z到Z的映射，其中，g是集合的特征函数。 (a)计算 (b)计算。 (c)确定函数. (d)证明： 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且满足，则 (b)证明保持序关系≤；即，如果在B1中c≤d,则在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) 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路，如果有的话，计算相应的权重；如果没有的话，说明原因。 17(5’)假设要用字母C, E, L, S, U, Y的二进制码字编写信息，它们的使用频率分别为7, 31, 20, 24, 12, 6. 画一颗使这些字母编码效率最高的树。 用(a)中确定的编码方法对信息CLUE进行编码。 参考答案 注：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∨s P ③ ﹃d∨h∨s T②E ④ ﹃d∨s T①③I ⑤