離散數(shù)學期末復習題套

1、離散數(shù)學期末考試題(A)一、填空題(每小題3分，共15分)1.設(shè)，則，.2.集合，其上可定義( )個封閉的1元運算，( )個封閉的2元運算，( )個封閉的3元運算.3.命題公式的對偶式為( ).4.所有6的因數(shù)組成的集合為( ).5.不同構(gòu)的5階根樹有( )棵.二、單選題(每小題3分，共15分)1.設(shè)A, B是集合，若，則(A)B = Æ (B) A = Æ (C)Æ (D)2.謂詞公式中量詞的轄域為(A) (B)(C) (D)和3.任意6階群的子群的階一定不為(A)4 (B)6 (C)2 (D)34.設(shè)是正整數(shù)，則有限布爾代數(shù)的元素個數(shù)為(A)2n (B)4n

2、(C) (D)5.對于下列序列，可構(gòu)成簡單無向圖的度數(shù)序列為(A)3, 3, 4, 4, 5 (B)0, 1, 3, 3, 3 (C)1, 1, 2, 2, 3 (D)1, 1, 2, 2, 2三、判斷題(每小題3分，共15分): 正確打“”，錯誤打“×”.1. 設(shè)，則是滿射. ( )2. 5男5女圓桌交替就座的方式有2880種. ( )3. 設(shè)是格，對于，若且，則. ( )4. 任何樹都至少2片樹葉. ( )5. 無向圖有生成樹的充要條件是為連通圖. ( )四、(10分)設(shè)和是集合，證明，并舉例說明上式中不能將改為 = .五、(15分)設(shè)N是自然數(shù)集合，定義N上的關(guān)系如下：是偶數(shù)，

3、1.證明是N上的等價關(guān)系.2.求出N關(guān)于等價關(guān)系的所有等價類.3.試求出一個N到N的函數(shù)，使得.六、(10分)在實數(shù)集合R中證明下列推理的有效性:因為R中存在自然數(shù)，而所有自然數(shù)是整數(shù)，所以R中存在整數(shù).七、(10分)設(shè)R是實數(shù)集合，令，定義上的運算如下:對于任意，證明是非Abel群.八、(10分)若簡單平面圖的節(jié)點數(shù)且邊數(shù)，則是連通圖，試證明之.離散數(shù)學期末考試題(B)一、填空題(每小題3分，共15分)1.設(shè)Æ，則Æ = ( )，Æ = ( )，中的元素個數(shù)( ).2.設(shè)集合A中有3個元素，則A上的二元關(guān)系有( )個，其中有( )個是A到A的函數(shù).3.謂詞公式中

4、量詞的轄域為( ), 量詞的轄域為( ).4.設(shè)，對于其上的整除關(guān)系“|”，元素( )不存在補元.5.當( )時，階完全無向圖是平面圖，當為( )時，是歐拉圖.二、單選題(每小題3分，共15分)1.設(shè)是集合A上的偏序關(guān)系，是的逆關(guān)系，則是A上的(A)偏序關(guān)系 (B)等價關(guān)系 (C)相容關(guān)系 (D)以上結(jié)論都不成立2.由2個命題變元和組成的不等值的命題公式的個數(shù)有(A)2 (B)4 (C)8 (D)163.設(shè)是素數(shù)且是正整數(shù)，則任意有限域的元素個數(shù)為(A) (B) (C) (D)4.設(shè)R是實數(shù)集合，是其上的小于等于關(guān)系，則(R, )是(A)有界格 (B)分配格 (C)有補格 (D)布爾格5.3階

5、完全無向圖的不同構(gòu)的生成子圖有(A)2 (B)3 (C)4 (D)5三、判斷題(每小題3分，共15分): 正確打“”，錯誤打“×”.1.若一個元素既存在左逆元，又存在右逆元，則. ( )2.命題聯(lián)結(jié)詞不滿足結(jié)合律. ( )3.在Z8 = 0，1，2，3，4，5，6，7中，2關(guān)于“×8”的逆元為4. ( )4.整環(huán)不一定是域. ( )5.任何平面圖的面數(shù). ( )四、(10分)設(shè)且，若是單射，證明是單射，并舉例說明不一定是單射.五、(15分)設(shè),上的關(guān)系,1.畫出的關(guān)系圖.2.判斷所具有的性質(zhì).3.求出的關(guān)系矩陣.六、(10分)利用真值表求命題公式的主析取范式和主合取范式.七

6、、(10分) 邊數(shù)的簡單平面圖，必存在節(jié)點使得.八、(10分) 有六個數(shù)字，其中三個1，兩個2，一個3，求能組成四位數(shù)的個數(shù).離散數(shù)學期末考試題(C)一、填空題(每小題3分，共15分)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)；

7、(5).4. 設(shè)D24是24的所有正因數(shù)組成的集合，“|”是其上的整除關(guān)系，則3的補元( )，4的補元( )，6的補元( ).5. 設(shè)G是(7, 15)簡單平面圖，則G一定是( )圖，且其每個面恰由( )條邊圍成，G的面數(shù)為( ).二、單選題(每小題3分，共15分)1. 設(shè)A, B, C是集合，則下述論斷正確的是( ).(A)若A Í B， B Î C，則A Î C. (B)若A Í B， B Î C，則A Í C.(C)若A Î B， B Í C，則A Î C. (D)若A Î B， B &#

8、205; C，則A Í C. 2. 設(shè)R Í A ´ A，S Í A ´ A，則下述結(jié)論正確的是( ).(A)若R和S是自反的，則R Ç S是自反的.(B)若R和S是對稱的，則是對稱的.(C)若R和S是反對稱的，則是反對稱的.(D)若R和S是傳遞的，則R È S是傳遞的.3.在謂詞邏輯中，下列各式中不正確的是( ).(A) (B)(C)(D)4. 域與整環(huán)的關(guān)系為( ).(A)整環(huán)是域 (B)域是整環(huán) (C)整環(huán)不是域 (D) 域不是整環(huán)5.設(shè)G是(n, m)圖，且G中每個節(jié)點的度數(shù)不是k就是k + 1，則G中度數(shù)為k的節(jié)點

9、個數(shù)為( ).(A). (B)n(n + 1). (C)nk. (D).三、判斷題(每小題3分，共15分): 正確打“”，錯誤打“×”.1.設(shè)f: Z ® Z，則是單射. ( )2.設(shè)是群G1到群G2的同態(tài)映射，若G1是Abel群，則G2是Abel群. ( )3.設(shè)是格，對于，若且，則. ( )4.元素個數(shù)相同的有限布爾代數(shù)都是同構(gòu)的. ( )5.設(shè)G是n (n ³ 11)階簡單圖，則G或是非平面圖. ( )四、(15分)設(shè)A和B是集合，使下列各式(1)； (2)；(3)成立的充要條件是什么，并給出理由.五、(10分) 設(shè)S是實數(shù)集合R上的關(guān)系，其定義如下R且是是

10、整數(shù)，證明: S是R上的等價關(guān)系.六、(10分) 求謂詞公式的前束范式.七、(10分) 若n個人，每個人恰有3個朋友，則n必為偶數(shù)，試證明之.八、(10分) 利用生成函數(shù)求解遞歸關(guān)系.離散數(shù)學期末考試題(D)一、填空題(每小題3分，共15分)1. 設(shè)|A| = 5, |B| = 2, 則可定義A到B的函數(shù)( )個，其中有( )單射，( )個滿射.2. 令G(x): x是金子，F(xiàn)(x): x是閃光的，則命題“金子都是閃光的，但閃光的未必是金子”符號化為( ).3. 設(shè)X是非空集合，則X的冪集P(X)關(guān)于集合的È運算的單位元是( )，零元是( )，P(X)關(guān)于集合的Ç運算的單位

11、元是( ).4. 不同構(gòu)的5階無向樹有( )棵.5. 對于n階完全無向圖Kn, 當n為( )時是Euler圖，當n ³ ( )時是Hamilton圖，當n ( )時是平面圖.二、單選題(每小題3分，共15分)1. 冪集P(P(P(Æ) 為( )(A)Æ, Æ, Æ. (B)Æ, Æ, Æ, Æ. (C) Æ, Æ, Æ, Æ, Æ (D) Æ, Æ, Æ.2. 設(shè)R是集合A上的偏序關(guān)系，則是( ).(A)偏序關(guān)系 (B)等價關(guān)

12、系 (C)相容關(guān)系 (D)以上答案都不對3. 下列( )組命題公式是不等值的.(A)與. (B) 與.(C)與. (D)與.4.下列代數(shù)結(jié)構(gòu)(G, *)中，( )是群.(A)G = 0, 1, 3, 5, “*”是模7加法. (B) G = Q, “*”是數(shù)的乘法.(C)G = Z, “*”是數(shù)的減法. (D) G = 1, 3, 4, 5, 9, “*”是模11乘法.5.4階完全無向圖中含3條邊的不同構(gòu)的生成子圖有(A)3 (B)4 (C)5 (D)2三、判斷題(每小題3分，共15分): 正確打“”，錯誤打“×”.1.函數(shù)的復合運算“”滿足結(jié)合律. ( )2. 是最小功能完備聯(lián)結(jié)詞

13、集合. ( )3. 實數(shù)集R關(guān)于數(shù)的乘法運算“×”阿貝爾群. ( )4. 任意有限域的元素個數(shù)為2n. ( )5. 設(shè)G是n(n為奇數(shù))簡單圖，則G與中度數(shù)為奇數(shù)的節(jié)點個數(shù)相同. ( )四、(10分)設(shè)A和B是集合，使成立的充要條件是什么，并給出理由.五、(10分) 設(shè)R和S是集合A上的對稱關(guān)系，證明對稱的充要條件是.六、(15分)分別利用(1)等值演算法和(2)真值表求命題公式的主析取范式和主合取范式.七、(10分) 設(shè)G是(n, m)無向圖，若，證明G中必存在圈.八、(10分) 在初始條件f(1) = c下，求解遞歸關(guān)系，其中b，c為常數(shù)且，k為正整數(shù).離散數(shù)學期末考試題(E)一

14、、填空題(每小題3分，共15分)1.設(shè)A = 2, 3, 4, a, B = 1, 3, 4, a, 則3( )A，a( )B，a( )B.2. 設(shè)A = 1, 2, 3, 4, 5上的關(guān)系R = (1, 2), (3, 4), (2, 2), S = (4, 2), (2, 5), (3, 1), (1, 3), 則 , , .3. gcd(36, 48) = ( )，lcm(36, 48) = ( ).4.任意有限布爾代數(shù)均與集合代數(shù)( )同構(gòu)，其元素個數(shù)為( ).5. 不同構(gòu)的5階無向樹有( )棵，不同構(gòu)的5階根樹有( )棵.二、單選題(每小題3分，共15分)1. 在有理數(shù)集合Q上定義運

15、算“*”如下：對于任意x, y Î Q， = x + y xy，則Q關(guān)于*的單位元是( ).(A)x. (B)y. (C)1. (D)0. 2. 設(shè)A = 1, 2, 3, 下圖分別給出了A上的兩個關(guān)系R和S，則 是( )關(guān)系.GR112233GS(A)自反. (B)對稱. (C)傳遞. (D)等價.3.令T(x): x是火車，B(x): x是汽車，F(xiàn)(x, y): x比y快，則“某些汽車比所有的火車慢”符號化為( ).(A).(B).(C).(D).4. 整數(shù)集合Z關(guān)于數(shù)的加法“+”和數(shù)的乘法“×”構(gòu)成的代數(shù)結(jié)構(gòu)(Z, +, ×)是( ).(A)域 (B)域和整

16、環(huán) (C)整環(huán) (D) 有零因子環(huán)5.設(shè)G是簡單圖，是G的補圖，若，則稱G為自補圖. 5階不同構(gòu)的自補圖個數(shù)為( ).(A)0. (B)1. (C)2. (D)3.三、判斷題(每小題3分，共15分): 正確打“”，錯誤打“×”.1. Æ, Æ Ï P(P(Æ). ( )2. 非空1元及2元聯(lián)結(jié)詞集合的個數(shù)為29-1. ( )3. 群可分為Abel群和非Abel群. ( )4. 元素個數(shù)相同的有限域都是同構(gòu)的. ( )5. 設(shè)G是簡單圖，則G或是連通圖. ( )四、(15分) 設(shè), 若是單射，證明f是單射，并舉例說明g不一定是單射.五、(10分)

17、 設(shè)A = a, b, c, d上的關(guān)系R = (a, b), (b, d), (c, c), (a, c), 畫出R的關(guān)系圖，并求出R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R).六、(10分)用CP規(guī)則證明下列推理.七、(10分) 求謂詞公式的前束范式. 八、(10分)任意6個人中，一定有3個人彼此認識或有3個人彼此不認識.離散數(shù)學期末考試題(F)一、填空題(每小題3分，共15分)1. 設(shè)A = 1, 2, 3, 1, 2, 3, B = 2, 2,3, 1 , 則A B = , B A = , A Å B = .2. 實數(shù)集合R關(guān)于加法運算“+”的單位元為( ), 關(guān)

18、于乘法運算“×”的單位元為( ), 關(guān)于乘法運算“×”的零元為( ).3. 令Z(x): x是整數(shù)，O(x): x是奇數(shù)，則“不是所有整數(shù)都是奇數(shù)”符號化為( ).4. 有限域的元素個數(shù)為( ), 其中( )且( ). 5. 設(shè)G是(7, 15)簡單平面圖，則G一定 ( )連通圖，其每個面恰由( )條邊圍成，G的面數(shù)為( ).二、單選題(每小題3分，共15分)1. 函數(shù)的復合運算“”滿足( )(A)交換律. (B)結(jié)合律. (C)冪等律. (D)消去律.2. 設(shè)集合A中有4個元素，則A上的等價關(guān)系共有( )個.(A)13 (B)14 (C)15 (D)163.下列代數(shù)結(jié)構(gòu)(G, *)中，( )是群.(A