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

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

2、A B| ()，A 到 B 的 2 元關(guān)系共有() 個(gè),A上的2元關(guān)系共有() 個(gè).2.設(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)，則()是單射，()是滿射，() 是雙射.3.下列5個(gè)命題公式弋中，是永真式的有 ()(選擇正確答案的番號)(1)P(Pq)q ；(2)P(Pq)；(3)P(Pq)；(4)P(Pq)q ；(5)(Pq)q.4. 設(shè)D24是24的所有正因數(shù)組成的集合，“| ”是其上的整除關(guān)系，則3的補(bǔ)元()，4的補(bǔ)元()，6的補(bǔ)元().5. 設(shè)

3、G是億15)簡單平面圖，則 G -定是()圖，且其每個(gè)面恰由()條邊圍成，G的面數(shù)為().三.1.設(shè) A a,b,c, B a,b,c,c，則 A B (),AB ()，P(A)().2.集合A a,b,c,其上可定義()個(gè)封閉的1元運(yùn)算，()個(gè)封閉的2元運(yùn)算，() 個(gè)封閉的3元運(yùn)算.3.命題公式(p q) 1的對偶式為().4.所有6的因數(shù)組成的集合為().5.不同構(gòu)的5階根樹有()棵.四、(10 分)設(shè) f : A B 且 g : BC ,若f g是單射，證明f是單射，并舉例說明g不疋疋單射.五、(15分)設(shè)A a,b, c, d, A上的關(guān)系R ( a,a), (a, b),(a, c)

4、,(c,a),(c, b), (c,c), (d,a), (d, b),(d, c),1. 畫出R的關(guān)系圖Gr.2. 判斷R所具有的性質(zhì).3. 求出R的關(guān)系矩陣M r.六、(10分)利用真值表求命題公式 A (p (q r) (r (q p)的主析取范式 和主合取范式.七、(10分)邊數(shù)m 30的簡單平面圖G，必存在節(jié)點(diǎn)v使得deg(v) 4.丿八、(10分)有六個(gè)數(shù)字，其中三個(gè) 1,兩個(gè)2, 個(gè)3，求能組成四位數(shù)的個(gè)數(shù).離散數(shù)學(xué)期末考試題(B)參考答案一、1. a,b,a,b,，a,b,a,b，16.2. 29,27.3. P(x) Q(x), Q(y) P(y).4. 2, 4, 6, 1

5、2.5. 4，奇數(shù).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. (pq) 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),即(fg)(x)(fg)(y).由于 fg是單射，因此xy，于是f是單射.(1, ),(2, ),(3,五、解1. R的關(guān)系圖a,b, B(1,2,3, C

6、,)，這時(shí) f g ( a, ), (b,，令 f (a,1),(b,2)是單射，而g不是單射.2.(1)由于(b,b) R，所以R不是自反的由于(a,a) R，所以R不是反自反的 因?yàn)?d,b) R，而(b,d) R，因此R不是對稱的(4)因(a, c), (c,a) R，于是R不是反對稱的經(jīng)計(jì)算知R R( a,a), (a,b), (a, c), (c, a), (c, b), (c, c), (d, a), (d,c)R，進(jìn)而R是傳遞的.綜上所述，所給R是傳遞的.11103. R的關(guān)系矩陣Mr00oo111o .1110六、解命題公式A(P(qr)(r(qp)的真值表如下p, q, rA1, 1, 11111, 1,00101,0, 11111,0, 01110, 1, 11000, 1,01 110, 0, 11110, 0, 0111由表可知，A (p(qr)(r(qp)的主析取范式為A的主合取范式為 A ( pq r)(pqr).七、證不妨設(shè)G的階數(shù)n 3，否則結(jié)論是顯然的.根據(jù)推論1 知，m 3n 6 若 G 的任意節(jié)點(diǎn)v的度數(shù)均有deg(v)5，由握手定理知2mdeg(v)v5n .2于是n -m，進(jìn)而m3n 6c23 m6.因此m30 ,與已知矛盾.所以