《(完整版)《离散数学》期末试题及答案,推荐文档》由会员分享，可在线阅读，更多相关《(完整版)《离散数学》期末试题及答案,推荐文档（5页珍藏版）》请在金锄头文库上搜索。
1、326离散数学期末考试题 (B) 一、填空题 (每小题 3分，共 15分)1设 A a,b,a,b, ，则 A = (), A = (), P(A)中的元素个数 |P(A)| ().2设集合A中有3个元素，则A上的二元关系有()个，其中有()个是A到A 的函数 .3. 谓 词 公 式 x(P(x) Q(x) y(Q(y) P(y) 中 量 词 x 的 辖 域 为(), 量词 y 的辖域为 ().4. 设 D241,2,3,4,6,8,12,24 ，对于其上的整除关系 “|”，元素()不存在补元 .5当n()时，n阶完全无向图Kn是平面图，当当n为()时，Kn是欧拉图二. 1.若| A| m,|
2、B| n,则| A B | ()，A到B的2元关系共有()个，A上的2元关系共有()个2. 设 A = 1,2, 3, f = (1,1), (2,1), (3, 1), g = (1, 1), (2, 3), (3, 2)和 h = (1,3), (2, 1), (3,1) ,则 ()是单射, ()是满射, ()是双射 3. 下列5个命题公式中，是永真式的有()(选择正确答案的番号).(1) p(pq) q ；(2) p(pq) ；(3) p(pq) ；(4) p(pq)q ；(5)(pq)q.4. 设D24是24的所有正因数组成的集合，是其上的整除关系，则3的补元()，4 的补元 (),
3、6 的补元 ().5. 设G是亿15)简单平面图，则 G 一定是()图，且其每个面恰由()条边围成, G 的面数为 ().三 1. 设 A a,b,c, B a,b,c,c, 则 A B () ,A B ()， P(A) ().2.集合 A a,b, c ，其上可定义 ()个封闭的 1 元运算， ()个封闭的 2元运算， ()个封闭的 3元运算 .3. 命题公式 (p q) 1的对偶式为 ( ).4. 所有 6 的因数组成的集合为 ( ).5. 不同构的 5 阶根树有 ()棵 .四、(10分)设f : A B且g : B C，若g 是单射， 证明 f 是单射， 并举例说明 g不一定是单射五、(
4、15分)设A a,b,c,d,A上的关系R (a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,b),(d,c) ,1画出R的关系图Gr.2判断R所具有的性质.3求出R的关系矩阵M r.六、(10分)利用真值表求命题公式 A (p (q r) (r (qp)的主析取范式和主合取范式 .七、(10分)边数m 30的简单平面图G，必存在节点v使得deg(v) 4.八、(10 分) 有六个数字，其中三个 1，两个 2，一个 3，求能组成四位数的个数 .离散数学期末考试题(B)参考答案一、1. a, b, a, b, ， a, b, a, b ， 16.92.29
5、 , 27.3. P(x)Q(x), Q(y) P(y).4. 2, 4, 6, 12.5. 4 ，奇数 .mn m2二、1.mn,2 ,2.2.g, g, g.3.1,2,4.4.8, 不存在，不存在.5连通，3, 10.三、1. A B a,a,b,b,c,c , A B c , P(A) , a, b, c, a, b, c.39 小272.3 ,3 ,3 .3. (p q) 0.4. -1 , -2, -3, -6, 1 , 2 , 3 , 6.5.9.四、证对于任意x, y A ，若f (x)f(y)，则 g(f(x)g(f(y)，即(f g)(x)(fg)(y).由于 fg是单射，
6、因此x y，于是f是单射.例如取A a,b, B(1,2,3, C ,，令 f (a,1),(b,2)，g (1, ),(2,),(3, ),这时 f g ( a, ), (b,)是单射，而 g 不是单射.五、解1. R的关系图Gr如下：2.(1)由于(b,b) R，所以R不是自反的.由于(a,a) R，所以R不是反自反的.因为(d,b) R，而(b,d) R，因此R不是对称的(4)因(a,c),(c,a) R，于是R不是反对称的.(5)经计算知 R R (a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,c) R，进而 R 是E(x)2 x2!3!2!传
7、递的.综上所述，所给R是传递的.11 1000 003.R的关系矩阵Mr11 10 .11 10六、解命题公式A(P(qr)(r(qp)的真值表如下p, q, rp (qr)r(q p)A1, 1,1 :1111, 1,0 10101,0, 11111,0, 01110, 1, 11000, 1,01110, 0, 11110, 0, 0111由表可知，A(p(qr)(r(qp)的主析取范式为A(pqr) (pqr)(pqr) ( p qr)(pqr)(pqr).A的主合取范式为A(p qr)(pqr).七、证不妨设G的阶数n 3，否则结论是显然的.根据推论1知，m 3n 6.若G的任意节点v的度数均有deg(v) 5，由握手定理知2mdeg(v)v5n .2于是nm ,进而m3n 632m 6.因此m 30,与已知矛盾.所以必存在55节点v使得deg(v) 4 .八、解设满足要求的r位数的个数有ar种，r = 0,1, 2,则排列计数生成函数1219 319 41 51 6xx_xx61221221 3x 4x因而a4194!38.
