326《離散數(shù)學(xué)》期末考試題(B) 一、填空題(每小題3分，共15分) 1.設(shè)}，則 = ( )，{} = ( )，中的元素個數(shù)( ). 2.設(shè)集合A中有3個元素，則A上的二元關(guān)系有( )個，其中有( )個是A到A的函數(shù). 3.謂詞公式中量詞的轄域?yàn)? ), 量詞的轄域?yàn)? ). 4.設(shè)，對于其上的整除關(guān)系“|”，元素( )不存在補(bǔ)元. 5.當(dāng)( )時，階完全無向圖是平面圖，當(dāng)當(dāng)為( )時，是歐拉圖. 二．1. 若，則( )，A到B的2元關(guān)系共有( )個，A上的2元關(guān)系共有( )個. 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個命題公式中，是永真式的有( )(選擇正確答案的番號). (1)； (2)； (3)； (4)； (5). 4. 設(shè)D24是24的所有正因數(shù)組成的集合，“|”是其上的整除關(guān)系，則3的補(bǔ)元( )，4的補(bǔ)元( )，6的補(bǔ)元( ). 5. 設(shè)G是(7, 15)簡單平面圖，則G一定是( )圖，且其每個面恰由( )條邊圍成，G的面數(shù)為( ). 三．1.設(shè)，，則，，. 2.集合，其上可定義( )個封閉的1元運(yùn)算，( )個封閉的2元運(yùn)算，( )個封閉的3元運(yùn)算. 3.命題公式的對偶式為( ). 4.所有6的因數(shù)組成的集合為( ). 5.不同構(gòu)的5階根樹有( )棵. 四、(10分)設(shè)且，若是單射，證明是單射，并舉例說明不一定是單射. 五、(15分)設(shè),上的關(guān)系 , 1.畫出的關(guān)系圖. 2.判斷所具有的性質(zhì). 3.求出的關(guān)系矩陣. 六、(10分)利用真值表求命題公式的主析取范式和主合取范式. 七、(10分) 邊數(shù)的簡單平面圖，必存在節(jié)點(diǎn)使得. 八、(10分) 有六個數(shù)字，其中三個1，兩個2，一個3，求能組成四位數(shù)的個數(shù). 《離散數(shù)學(xué)》期末考試題(B)參考答案 一、1. {{a, b}, a, b, }， {{a, b}, a, b}，16. 2., 27. 3., . 4. 2, 4, 6, 12. 5.，奇數(shù). 二、1.. 2.g, g, g. 3.1,2,4. 4.8，不存在，不存在. 5.連通，3，10. 三、1. ，，, {{a, b}}, {{c}}, {{a, b}, {c}}}. 2.. 3.. 4.{-1，-2，-3，-6，1，2，3，6}. 5.9. 四、證 對于任意，若，則，即. 由于是單射，因此，于是是單射. 例如取，令，，這時是單射，而不是單射. 五、解 1. 的關(guān)系圖如下： a b c d 2.(1)由于，所以不是自反的. (2)由于，所以不是反自反的. (3)因?yàn)?，而，因此不是對稱的. (4)因，于是不是反對稱的. (5)經(jīng)計算知，進(jìn)而是傳遞的. 綜上所述，所給是傳遞的. 3.的關(guān)系矩陣. 六、解 命題公式的真值表如下: p, q, r A 1, 1, 1 1 1 1 1, 1, 0 0 1 0 1, 0, 1 1 1 1 1, 0, 0 1 1 1 0, 1, 1 1 0 0 0, 1, 0 1 1 1 0, 0, 1 1 1 1 0, 0, 0 1 1 1 由表可知，的主析取范式為 A的主合取范式為. 七、證 不妨設(shè)的階數(shù)，否則結(jié)論是顯然的. 根據(jù)推論1知，. 若的任意節(jié)點(diǎn)的度數(shù)均有，由握手定理知 . 于是，進(jìn)而. 因此，與已知矛盾. 所以必存在節(jié)點(diǎn)使得. 八、解 設(shè)滿足要求的r位數(shù)的個數(shù)有ar種，r = 0，1，2，…，則排列計數(shù)生成函數(shù) , 因而.