《離散數(shù)學》期末試題及答案

1、326散數(shù)學期 末考 試題 (B )一、填空題 ( 每小題 3 分，共 15 分 ).設(shè) A a,b, a,b, , M A =(), A ) = (), P(A)中的 TOC o 1-5 h z 元素個數(shù)|P(A) | (). 設(shè)集合 A 中有 3 個元素，則 A 上的二元關(guān)系有() 個，其中有() 個是 A到 A 的函數(shù) .謂詞公式 x(P(x) Q(x) y(Q(y) P(y)中量詞x的轄域為(),量詞 y 的轄域為 ().設(shè) D24 1,2,3,4,6,8,12,24 ， 對于其上的整除關(guān)系 “| ”， 元素 () 不存在補元.當n() 時，n階完全無向圖Kn是平面圖，當當門為() 時

2、，Kn是歐拉圖.二.1.若| A|m,|B|n,則 | AB| (), A1J B的 2 元關(guān)系共有() 個，A上的2 元關(guān)系共有() 個 .設(shè) 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.設(shè)D24是24的所有正因數(shù)組成的集合，“|”是其上的整除關(guān)系，則3的補元(),

3、4 的補元 ( )， 6 的補元 ( ).設(shè)G是(7, 15)簡單平面圖，則G一定是() 圖，且其每個面恰由()條邊圍成， G 的面數(shù)為 ().1.設(shè) 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 的因數(shù)組成的集合為 (). 不同構(gòu)的 5 階根樹有 ( ) 棵 .、 (10 分) 設(shè) f : A B 且 g : B C ，若 f g 是單射，證明 f 是單射，并舉例說明

4、g 不一定是單射 .五、(15分)設(shè)A a,b,c,d , A上的關(guān)系R ( a,a),(a,b), (a,c), (c, a),(c,b),(c, c), (d,a), (d,b), (d,c) ,.畫出R的關(guān)系圖Gr.判斷R所具有的性質(zhì).求出R的關(guān)系矩陣MR.六、 (10 分)利用真值表求命題公式 A (p (q r) (r (q p) 的主析取范式和主合取范式 .七、(10分)邊數(shù)m 30的簡單平面圖G,必存在節(jié)點v使得deg(v) 4.八、 (10 分) 有六個數(shù)字，其中三個1，兩個2，一個3，求能組成四位數(shù)的個數(shù).離散數(shù)學期末考試題 (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 ，奇數(shù) .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的關(guān)系圖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)經(jīng)計算知 R R (a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,c) R,進而 R是傳遞的.綜上所述，所給R是傳遞的.3. R的關(guān)系矩陣M綜上所述，所給R是傳遞的.3. R的關(guān)系矩陣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).七、證不妨設(shè)G的階數(shù)n3,否則結(jié)論是顯然的.根據(jù)推論1知，六、解命題公式AA的主合取范式為A ( pq r) (p q r).七、證不妨設(shè)G的階數(shù)n3,否則結(jié)論是顯然的.根據(jù)推論1知，m 3n 6.若G的任意節(jié)點v的度數(shù)均有deg(v)5,由握手定理知2.于是n -m ,進而m53n2m deg(v) 5n.v26 3