《离散数学》期末试题及答案

1、326散数学期 末考 试题 (B )一、填空题 ( 每小题 3 分，共 15 分 ).设 A a,b, a,b, , M A =(), A ) = (), P(A)中的 TOC o 1-5 h z 元素个数|P(A) | (). 设集合 A 中有 3 个元素，则 A 上的二元关系有() 个，其中有() 个是 A到 A 的函数 .谓词公式 x(P(x) Q(x) y(Q(y) P(y)中量词x的辖域为(),量词 y 的辖域为 ().设 D24 1,2,3,4,6,8,12,24 ， 对于其上的整除关系 “| ”， 元素 () 不存在补元.当n() 时，n阶完全无向图Kn是平面图，当当门为() 时

2、，Kn是欧拉图.二.1.若| A|m,|B|n,则 | AB| (), A1J B的 2 元关系共有() 个，A上的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) ，则 () 是单射， () 是满射， () 是双射. 下列 5 个命题公式中，是永真式的有()( 选择正确答案的番号).p(pq)q；p(pq)；p(pq)；p( pq)q；(p q) q.设D24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元(),

3、4 的补元 ( )， 6 的补元 ( ).设G是(7, 15)简单平面图，则G一定是() 图，且其每个面恰由()条边围成， G 的面数为 ().1.设 A a,b,c , B a,b,c,c,则 A B (), A B (),P(A) () .集合 A a, b,c ，其上可定义() 个封闭的 1 元运算， () 个封闭的 2元运算， ( ) 个封闭的 3 元运算 .命题公式 (p q) 1的对偶式为 (). 所有 6 的因数组成的集合为 (). 不同构的 5 阶根树有 ( ) 棵 .、 (10 分) 设 f : A B 且 g : B C ，若 f g 是单射，证明 f 是单射，并举例说明

4、g 不一定是单射 .五、(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) ,.画出R的关系图Gr.判断R所具有的性质.求出R的关系矩阵MR.六、 (10 分)利用真值表求命题公式 A (p (q r) (r (q p) 的主析取范式和主合取范式 .七、(10分)边数m 30的简单平面图G,必存在节点v使得deg(v) 4.八、 (10 分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.离散数学期末考试题 (B) 参考答案一、 1. a, b, a, b,

5、 ， a, b, a, b ， 16.929, 27.P(x) Q(x), Q(y) P(y) .2, 4, 6, 12.4 ，奇数 .2mn小m、1. mn,2 ,2 .2.g, g, g.3.1,2,4.4.8 ,不存在，不存在.5.连通，3, 10.、1. A B a,a,b,、1. A B a,a,b,b,c, c , A B c , P(A) ,a, b, c,a，ba，b， c.33,39,327.(p q) 0.4.-1 ,-2,-3,-6,1,2, 3, 6.4.-1 ,-2,-3,-6,1,2, 3, 6.5.9.5.9.四、证对于任意x,yA,f(x) f(y),则g(f(

6、x) g(f(y),即(fg)(x) (f g)(y).由于f g是单射，因此x四、证对于任意x,yA,f(x) f(y),则g(f(x) g(f(y),即(fg)(x) (f g)(y).由于f g是单射，因此xy ,于是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不是反自反的.(3)因为(d,b) R,而(b,d) R ,因此R不是对称的

7、. 因(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是传递的.综上所述，所给R是传递的.3. R的关系矩阵M综上所述，所给R是传递的.3. R的关系矩阵Mr1011101110110000p, q, rA1, 1, 111P 111, 1,00101,0, 11111,0, 01110, 1, 11000, 1,01110, 0, 11110, 0, 0111(P(qr) (r (q p)的真值表如下：由表可知，A (p (q r) (r (q p)的主析取范式为六、解命题公式AA的主合取范式为A ( pq r) (p q r).七、证不妨设G的阶数n3,否则结论是显然的.根据推论1知，六、解命题公式AA的主合取范式为A ( pq r) (p q r).七、证不妨设G的阶数n3,否则结论是显然的.根据推论1知，m 3n 6.若G的任意节点v的度数均有deg(v)5,由握手定理知2.于是n -m ,进而m53n2m deg(v) 5n.v26 3