離散數(shù)學期末練習題 (帶答案)

1、離散數(shù)學復習注意事項：1、 第一遍復習一定要認真按考試大綱要求將本學期所學習內容系統(tǒng)復習一遍。2、 第二遍復習按照考試大綱的要求對第一遍復習進行總結。把大綱中指定的例題及書后習題認真做一做。檢驗一下主要內容的掌握情況。3、第三遍復習把隨后發(fā)去的練習題認真做一做，檢驗一下第一遍與第二遍復習情況，要認真理解,注意做題思路與方法。離散數(shù)學綜合練習題一、選擇題1下列句子中，（ ）是命題。A2是常數(shù)。 B這朵花多好看呀！ C請把門關上！D下午有會嗎？2令: 今天下雪了，:路滑，r:他遲到了。則命題“下雪路滑，他遲到了” 可符號化為（ ）。A. B. C. D. 3令今天下雪了，路滑，則命題“雖然今天下雪

2、了，但是路不滑”可符號化為（ ）。 A. B. C. D. 4設:是鳥，:會飛，命題“有的鳥不會飛”可符號化為（ ）。A. B. C. D. 5.設:是整數(shù)，:的絕對值，：大于等于；命題“所有整數(shù)的絕對值大于等于0”可符號化為（ ）。A. B. C. D. 6.設:是人，:犯錯誤，命題“沒有不犯錯誤的人”符號化為（）。AB CD 7.下列命題公式不是永真式的是（ ）。A. B. C. D. 8設:x為有理數(shù)；:x為實數(shù)。命題“任何有理數(shù)都是實數(shù)”的符號化為（ ）AB CD9.設個體域，與公式等價的命題公式是( )AB CD10.下列等價式不正確的是（ ）。ABCD11. 設個體域，與公式等價的

3、命題公式是( )AB CD12.設X=，則下列陳述正確的是（ ）。A.B.C.D.13.有向圖D是連通圖，當且僅當（ ）。A. 圖D中至少有一條通路 B. 圖D中有通過每個頂點至少一次的通路C. 圖D的連通分支數(shù)為一D. 圖D中有通過每個頂點至少一次的回路 14.設A=a,b,c，則下列是集合A的劃分的是( )A.B. C.D. 15.下列謂詞公式中是前束范式的是（ ）。A B CD16.設，則方程的解為（）。AMNBM N CMN CM-N17.設是群，則下列陳述不正確的是（ ）。A. B. C. D. 18.在整數(shù)集合上，下列定義的運算滿足結合律的是（ ）。A. B. C. D. 19.

4、設簡單圖G所有結點的度數(shù)之和為50，則G的邊數(shù)為（ ）。( )A. 50B. 25C. 10D. 520.設簡單無向圖是一個有5個頂點的4正則圖，則有（ ）條邊。A. 4B. 5C. 10D. 2021.設集合,上的等價關系 ，則對應于的劃分是（ ）。A. B. C. D. 22.設集合,上的等價關系 ，則對應于的劃分是（ ）。A. B. C. D. 23.設是群，則下列陳述不正確的是（ ）。A. B. C. D. 24.，下列定義的運算關于集合是不封閉的是（ ）。A. ，即的較大數(shù)B. ，即的較小數(shù)C. ，即的最大公約數(shù)D. ，即的最小公倍數(shù)25. 設，則是( )。A從X到Y的雙射B從X到Y

5、的滿射，但不是單射C從X到Y的單射，但不是滿射D從X到Y的二元關系，但不是從X到Y的映射26.設簡單無向圖是一個有6個頂點的5正則圖，則有( )條邊。A. 5B. 6C. 15D. 3027.圖G如下圖所示，以下說法正確的是( )。Aa是割點Bb,c是點割集Cb,d是點割集Dc是割點28.格L是分配格的充要條件是L不含與下面哪一個選項同構的子格（ ）。A鏈B鉆石格C五角格D. 五角格與鉆石格29.下列圖是歐拉圖的是（ D ）。30.給定一個有n個結點的無向樹，下列陳述不正確的是（ ）。A所有結點的度數(shù)2B無回路但若增加一條新邊就會變成回路C連通且，其中e是邊數(shù)，v是結點數(shù)D無回路的連通圖31.

6、 設有5個元素，則其冪集的元素總個數(shù)為（ ）。A. 32B.25C. 50D. 532若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是（ ）。A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6)33. 設則其冪集的元素總個數(shù)為（ ）。A. 3B. 4C. 8D. 1634. 在實數(shù)集合R上，下列定義的運算中不可結合的是（ ）。A. B. C. D. 35. 無向圖G是歐拉圖，當且僅當（ ）。A. G的所有結點的度數(shù)全為偶數(shù)B. G中所有結點的度數(shù)全為奇數(shù) C. G連通且所有結點度數(shù)全為奇數(shù) D. G連通

7、且所有結點度數(shù)全為偶數(shù)36.下列不一定是樹的是（ ）A. 無回路的連通圖D B. 有n個結點，n-1條邊的連通圖 C. 每對結點之間都有通路的圖 D. 連通但刪去一條邊則不連通的圖37. 設簡單圖G所有結點的度數(shù)之和為48，則G的邊數(shù)為( )A. 48B. 24C. 16D. 1238下面既是哈密頓圖又是歐拉圖的圖形是（ B ）。39.下列必為歐拉圖的是（ ）A.有回路的連通圖B.不可以一筆畫的圖C.有1個奇數(shù)度結點的連通圖D.無奇數(shù)度結點的連通圖40.二部圖 是（ ）。A.歐拉圖 B. 哈密頓圖 C.平面圖 D. 完全圖41下列所示的哈斯圖所對應的偏序集中能構成格的是（ C ）。A.B.C.

8、D.42.設簡單無向圖是一個有6個頂點的3正則圖，則有( )條邊。A. 3B. 6C. 9D. 1843下列式子為矛盾式的是（ ）。AB CD 44.設集合，A上的關系，則R是（ ）A自反的B對稱的C傳遞的D反對稱的45設是集合上的兩個關系，其中，則 是的（ ）閉包。A自反B對稱 C傳遞D自反、對稱且傳遞閉包46. 下列公式是前束范式的是（ ）。ABC D47. 設R為實數(shù)集，函數(shù)，則是（ ）。A單射而非滿射B滿射而非單射 C雙射D既不是單射，也不是滿射48下列各圖中既是歐拉圖，又是漢密爾頓圖的是（ C ）。A B C D49下列四個格，是分配格的是（ C ）。50設集合A=a,b, c上的關

9、系如下，具有傳遞性的是（ ）。A R=,B R=,C R=,D R=參考答案：（若有問題，可以到1#402或打電話問）一、選擇題AAAAB DACAA CCDBD BCDBC ABBDC CBDDA ACCDD BBBDB CCCBB ADCCD二、填空題1命題公式的成真指派為 10 ，成假指派為_00，01，11_。2. 命題公式的成真指派為00 10 11，成假指派為_01_。3命題公式的成真指派為00 01 11 , 成假指派為_ 10_。4公式約束變元為 x,y ，自由變元為 x,z 。5公式約束變元為_x,y_，自由變元為_x,z_ 。6設，則， a,b 。7設，上的關系，則對稱閉包

10、 , ，傳遞閉包 ,。8.設*是集合上的二元運算，若運算*滿足_結合律_，并且存在_單位元_，則稱為獨異點。9 設，則， a,b,c 。10.一棵無向樹的頂點數(shù)與邊數(shù)的關系是 m=n-1 。6階無向連通圖至多有 6 棵不同構的生成樹。11設，則復合函數(shù)=, =。12. 是一個群，其中，則當=6時，在中，2的階為_3_, 3的階為_ 2 。13設是格，其中A=1, 3,4，6，8，12，24，為整除關系，則1的補元是_24 _，3的補元是_8_。14設A=，B=,那么=1,3,4,5 ran= 3,5 。 15. 設A=l,2,3,4,A上的二元關系R=,，S=,，則 , , , 。16設和是集

11、合上的兩個關系，則= , ， = , 。 17設A=2, 4, 6，A上的二元運算*定義為：a*b=maxa,b，則在獨異點中，單位元是 2 ，零元是 6 。18一棵無向樹的頂點數(shù)n與邊數(shù)m關系是 m= n-1 。設G是具有8個頂點的樹，則G中增加_21 _條邊才能把G變成完全圖。19設復合函數(shù)gf是從A到C的函數(shù)，如果gf是滿射，那么_ g_必是滿射，如果gf是單射，那么_f _必是單射。20設是格，其中A=1, 3, 5, 9, 45，為整除關系，則1的補元是_45_，3的補元是_ 5 _。21給出A=l，2上的一個等價關系_,_，并給出其對應的劃分_1,2_。22設，上的二元關系，則的自

12、反閉包，傳遞閉包 R 23命題公式的成真賦值為 01 10 11 ，成假賦值為 00 。24公式的成真賦值是 00,11 。成假賦值 01 10 25公式的成真賦值是 01 11 。成假賦值 00 10 26公式的成假賦值是 01 10 。成假賦值 00 11 27設個體域是實數(shù)集，命題的真值為 1 ；命題的真值為 0 。28.設fRR,f(x)=x+3,gRR,g(x)=2x+1,則復合函數(shù) 2x+4 , 2x+7 。29.給定集合A=1,2,3,4,5，在集合A上定義兩種關系：R=,S=,，則 , 。30設A=0，1，2，3，6，則domR= 0， 3，6_ ，ranR=_0， 3，6 ，

13、31 設為模6加群，其中，則2-3= 0 ，4-2= 4 。32一個結點為n的無向完全圖，其邊的數(shù)目為n(n-1)/2 ，頂點的度為 n-1 。33. 已知階無向簡單圖有條邊，則的補圖中有 m- n(n-1)/2 條邊。 參考答案：1_10_，00，01，11 2. 00 10 11， 01_ 3. _00 01 11, 104. _x,y ，x,z_ 5. _x,y ，x,z_ 6., a,b 7.， 8. 結合律 ， 單位元9, a,b，c 10.n-1, 6 11. ,12. 3 , 2 13. _24_,_8_ 14. 1,3,4,5，_315. , 16. ， 17. 2 , 6 1

14、8. m= n-1, _21 19. _g , _f_ 20. 45 , _5_ 21. , 22. , 23. 01 10 11，0024. 00，11 ,01，10 25. 01，11 ,00，10 26. 01 10 , 00 11 27. 1 , 0 28. , 29. , 30. 0， 3，6, 0， 3，6 31. 0 , 4 32. n(n-1)/2, n-1 33. m- n(n-1)/2 三、計算題（僅給出部分題目的解題思路，未給出答案自己完成）1. 已知命題公式（1）構造真值表（2）求出公式的主析取范式解題思路：（1）真值表p q r0 0 010010 0 110010

15、1 011000 1 111001 0 001001 0 101111 1 001001 1 10111（2）2.已知命題公式（1）構造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表p q r0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 11100（2）主析取范式 3求公式 的主合取范式及主析取范式。4構造命題公式的真值表。5. 一棵（無向）樹有2結點的度為2， 1個結點的度為3，3個結點的度為4, 其余都是葉結點，問該樹有幾個葉結點？解：在一個有限圖中，各結點的度數(shù)總和是邊數(shù)的2倍；而樹中

16、的邊數(shù)為結點數(shù)減1。根據(jù)這兩點，可知樹中各結點的度數(shù)總和=2*（樹中點數(shù)-1），設樹葉有x個，于是，2*2+3+3*4+x=2*（2+1+3+x-1）得x=9。6.一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點？提示：類似上題求解。7.設，,，其中表示實數(shù)集。（1）求函數(shù)，；（2）哪些函數(shù)有反函數(shù)？如果有，求出這些反函數(shù)。解：（1） （2）和有反函數(shù)，； 8.設Aa，b，c，R是A上的二元關系，且R，求r(R)、s(R)和t(R)。解：r(R)=RIA=,s(R)=RR-1=,t(R)= RR2R3=，9.設，為整除關系。（1）畫出偏序集的哈斯圖；（2）求A中

17、的極大元；（3）求子集B=3, 6, 9的上確界與下確界。1623424954解：（1）哈斯圖（2）A中的極大元為 24，54；極小元為1；最大元：無；最小元：1（3）求子集B=3, 6, 9的上確界為54，下確界為3。10.設有向圖如圖所示，用鄰接矩陣完成以下計算。（1）到長度小于或等于4的通路數(shù)；（2）到自身長度小于或等于4的回路數(shù)；（3）求出的可達矩陣，并說明的連通性。有向圖的鄰接矩陣為， ，（1）v1到v4長度小于或等于4的通路數(shù)為（2）v1到自身長度小于或等于4的回路數(shù)為（3）由可達矩陣可知D是單向連通的。 11設，給出冪集合對稱差運算的運算表。12設，給出模6加運算的運算的運算表。

18、參看教材P167例9.4 與9.514. 設A1，2，3，4，5，R是A上的二元關系，且R，求r(R)、s(R)和t(R)。解：r(R)=RIAs(R)=RR-1t(R)= ，,（2,2,15.下圖為一連通賦權圖，計算該圖的最小生成樹和權值。四、簡答題1.設集合上的關系（1）畫出的關系圖，并寫出的關系矩陣；（2）是否為等價關系？若是，寫出的所有等價類。解：（1）R的關系圖為132 564（2）R的關系矩陣 由關系圖可以看出是等價關系。等價類為： 或寫為：A/R=1,3,6,2,5,42. 設是A=上的二元關系。（1）畫出R的關系圖；（2）寫出R的關系矩陣；（3）討論R的性質。1解：（1）R的關

19、系圖 234（2）R的關系矩陣 （3）R非自反、非反自傳、對稱、非反對稱 、非傳遞的 （4）R不是函數(shù)，不滿足函數(shù)單值性的要求。3設A=1,2,3,4,5,6,7,8,9,10，R是A上的二元關系，R=|x,yA x+y=10 說明R具有哪些性質。解：R=, , , , , , , 易知 R既不是自反也不是反自反的R是對稱的 R不是反對稱的 R不是傳遞的。4判斷下圖是否為二部圖？若是，找出它的互補結點子集。它是否為哈密頓圖？若是，找出一條哈密頓回路。 5.判斷下圖G是否是二部圖？若是，找出它的互補結點子集。它是否為哈密頓圖？若是，找出一條哈密頓回路。 6.設，為A上的整除關系。（1）是否為偏序

20、集，若是，畫出其哈斯圖；（2）是否為格？說明理由；135945解：（1）是偏序集。哈斯圖為：（2）是格。因為偏序集中的任意兩個元素均有上、下確界。 四、證明題1用一階邏輯的推理理論證明： 前提：， 結論： 證明：（1） 前提引入 （2） （1） （3） 前提引入 （4） （3） （5） （2）（4）析取三段論 （4分）（6） 前提引入 （7） （6） （8） （5）（7）假言推理 （9） （8） （3分）2設是非空集合,是所有從到的雙射函數(shù)的集合, 是函數(shù)的復合運算。證明：是群。證明：由于集合是非空的，,因此非空 。(1) ,因為和都是到的雙射函數(shù)，故也是到的雙射函數(shù)，從而集合關于運算 是封閉

21、的。 (2) ,由函數(shù)復合運算的結合律有，故運算 是可結合的。 (3) 上的恒等函數(shù)也是到的雙射函數(shù)即,且有, 故 是中的幺元。 (4) ,因為是雙射函數(shù)，故其逆函數(shù)是存在的，也是到的雙射函數(shù)，且有,因此是的逆元 由此上知是群 3設代數(shù)系統(tǒng)，為模6加法。證明：關于運算構成群。證明：集合顯然非空。 (1) ,從而集合關于運算是封閉的。 (2) ,有，故運算 是可結合的。 (3) , ,故0是中的幺元。 (4) ,因為,因此是的逆元 由此上知是群4設A是集合，P(A)是A的冪集合，是對稱差運算， 證明構成群。 提示：參考2、3證明題完成。5設為正整數(shù)，在上定義二元關系如下：當且僅當。證明：是一個等

22、價關系。證明： 任取所以R自反的。任取所以R是對稱的。任取 所以R是傳遞的。因此，R是等價關系。6.設R是A上的關系，如果R滿足以下兩條件：（1）對于任意的aR， 都有aRa，（2）若aRb, aRc, 則有bRc， 證明：R是等價關系 證明： 任取（1）由已知條件（1）得,所以是自反的。 （2）由已知條件（1）、（2）得所以是對稱的。 （3）由已知條件（1）、（2）得 所以是傳遞的。五、應用題（僅給出第7題的參考答案,未給出參考答案的自己完成）1. 構造下列推理的證明。 如果今天是星期一，則要進行英語或離散數(shù)學考試。如果英語老師有會，則不考英語。今天是星期一，英語老師有會，所以進行離散數(shù)學考試。2. 構造下列推理的證明。小王是理科學生，則他的數(shù)學成績很好。如果小王不是文科學生，則他一定是理科學生。小王的數(shù)學成績不好, 所以小王是文科學生。3如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍； 如果丁得亞軍，丙不能得亞軍；事實是甲已得冠軍。因此丁不能得亞軍。參照作業(yè)：P54 17