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

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

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

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

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

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

6、 設(shè)有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è)則其冪集的元素總個數(shù)為（ ）。A. 3B. 4C. 8D. 1634. 在實數(shù)集合R上，下列定義的運算中不可結(jié)合的是（ ）。A. B. C. D. 35. 無向圖G是歐拉圖，當(dāng)且僅當(dāng)（ ）。A. G的所有結(jié)點的度數(shù)全為偶數(shù)B. G中所有結(jié)點的度數(shù)全為奇數(shù) C. G連通且所有結(jié)點度數(shù)全為奇數(shù) D. G連通

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

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

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設(shè)，則， a,b 。7設(shè)，上的關(guān)系，則對稱閉包

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

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

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

13、31 設(shè)為模6加群，其中，則2-3= 0 ，4-2= 4 。32一個結(jié)點為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. 結(jié)合律 ， 單位元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）構(gòu)造真值表（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）構(gòu)造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表p q r0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 11100（2）主析取范式 3求公式 的主合取范式及主析取范式。4構(gòu)造命題公式的真值表。5. 一棵（無向）樹有2結(jié)點的度為2， 1個結(jié)點的度為3，3個結(jié)點的度為4, 其余都是葉結(jié)點，問該樹有幾個葉結(jié)點？解：在一個有限圖中，各結(jié)點的度數(shù)總和是邊數(shù)的2倍；而樹中

16、的邊數(shù)為結(jié)點數(shù)減1。根據(jù)這兩點，可知樹中各結(jié)點的度數(shù)總和=2*（樹中點數(shù)-1），設(shè)樹葉有x個，于是，2*2+3+3*4+x=2*（2+1+3+x-1）得x=9。6.一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點？提示：類似上題求解。7.設(shè)，,，其中表示實數(shù)集。（1）求函數(shù)，；（2）哪些函數(shù)有反函數(shù)？如果有，求出這些反函數(shù)。解：（1） （2）和有反函數(shù)，； 8.設(shè)Aa，b，c，R是A上的二元關(guān)系，且R，求r(R)、s(R)和t(R)。解：r(R)=RIA=,s(R)=RR-1=,t(R)= RR2R3=，9.設(shè)，為整除關(guān)系。（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.設(shè)有向圖如圖所示，用鄰接矩陣完成以下計算。（1）到長度小于或等于4的通路數(shù)；（2）到自身長度小于或等于4的回路數(shù)；（3）求出的可達矩陣，并說明的連通性。有向圖的鄰接矩陣為， ，（1）v1到v4長度小于或等于4的通路數(shù)為（2）v1到自身長度小于或等于4的回路數(shù)為（3）由可達矩陣可知D是單向連通的。 11設(shè)，給出冪集合對稱差運算的運算表。12設(shè)，給出模6加運算的運算的運算表。

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

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

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

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

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