1、離散數(shù)學(xué)練習(xí)題一一、單項(xiàng)選擇題1設(shè)集合，則下面集合與相等的是 。A BC D2設(shè)，是集合上的整除關(guān)系，下列敘述中錯(cuò)誤的是 。A4，5，6全是的極大元 B沒(méi)有最大元 C6是的上界 D1是的最大下界3. 設(shè)，則下列關(guān)系中為從到的映射是 。A BC D4. 設(shè)是4階群，則其子群的階不能是下面的 。A. 1 B. 2 C. 3 D. 45設(shè)，則下列集合中等于的是 。A B C D6下面有關(guān)集合之間的包含和屬于關(guān)系的說(shuō)法，正確的是 。 A和 B和 C和 D、和7. 設(shè)為個(gè)元素的集合，則上有 個(gè)二元關(guān)系。A B C2 D8. 數(shù)的加法在下列集合中 上是封閉的。A B C D9. 下列圖形中為歐拉圖的是 。

2、 10設(shè)是格，且，則 。A. = B. C. D. 沒(méi)關(guān)系11設(shè)，則有 。A B C D12. 。A B C D 13. 對(duì)于一個(gè)只有4個(gè)不同元素的集合來(lái)說(shuō)，上的不同的二元關(guān)系的總數(shù)為 。A4 B16 C D14. 下列代數(shù)系統(tǒng)中， 不構(gòu)成群。A，*是模11乘法 B，*是模11乘法C為有理數(shù)集，*是普通加法 D為有理數(shù)集，*是普通乘法15. 設(shè)為有個(gè)頂點(diǎn)的簡(jiǎn)單圖，則有 。A B C D 16設(shè)，則下列集合中等于的是（ ）。A B C D17設(shè)，下列選項(xiàng)正確的是（ ）。A B C D18設(shè)為個(gè)元素的集合，則上有（ ）個(gè)二元關(guān)系。A B C2 D19數(shù)的加法在下列集合中（ ）上是封閉的。A B C

3、 D20下列圖形中為歐拉圖的是（ ）。21設(shè)，則下列集合中等于的是（ ）。A B C D22設(shè)，下列選項(xiàng)正確的是（ ）。A B C D23設(shè)為個(gè)元素的集合，則上有（ ）個(gè)二元關(guān)系。A B C2 D24數(shù)的加法在下列集合中（ ）上是封閉的。A B C D25下列圖形中為歐拉圖的是（ ）。26下列命題中， 是錯(cuò)誤的。A. B. C. 若，則且 D. 若，則27冪集是 。A BC D28. 下列命題公式中 為重言式。 A. B.和 C.和 D.、和29任意一個(gè)具有多個(gè)等冪元的半群 (若元素滿足，則稱為等冪元)，該半群 。A不能構(gòu)成群 B不一定能構(gòu)成群 C必能構(gòu)成群 D能構(gòu)成交換群30設(shè)是整數(shù)集合，下

4、列集合中 關(guān)于數(shù)的加法和乘法構(gòu)成整環(huán)。A B C D31設(shè)集合，又規(guī)定偏序關(guān)系“|”是集合上的“整除”關(guān)系，則下列偏序集中 能構(gòu)成格。A B C D二、填空題1設(shè)為非空集合，且，則上不同的二元關(guān)系的個(gè)數(shù)為 ，上不同的映射的個(gè)數(shù)為 。2設(shè)、為兩個(gè)命題，當(dāng)且僅當(dāng) 時(shí)，的真值為1。3. 在運(yùn)算表中的空白處填入適當(dāng)符號(hào)，使成為群。 *4. 當(dāng)為 數(shù)時(shí)，必為歐拉圖。5. 某校有足球隊(duì)員38人，籃球隊(duì)員15人，排球隊(duì)員20人，三隊(duì)隊(duì)員總數(shù)為58人，且其中只有3人同時(shí)參加3種球隊(duì)，那么僅僅參加兩種球隊(duì)的隊(duì)員人數(shù)是 。6. 命題公式的主析取范式為 。7. 一棵無(wú)向樹有兩個(gè)2度頂點(diǎn)，一個(gè)3度頂點(diǎn)，三個(gè)4度頂點(diǎn)，

5、則它的樹葉數(shù)為 。8設(shè)：我生病，：我去學(xué)校，命題“如果我生病，那么我不去學(xué)校”符號(hào)化為 。9 ,為兩個(gè)命題，當(dāng)且僅當(dāng) 時(shí)，的值為0。10. 設(shè)是四個(gè)非空集合，則的充分必要條件是 。11. 在有理數(shù)集合上定義二元運(yùn)算*：，則的幺元是 。12. 設(shè)是分配格，若對(duì)任意的，都有，則 。13. 某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒(méi)有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。14. 將布爾表達(dá)式化簡(jiǎn)得 。15. 設(shè)：我有錢，：我去看電影，命題“當(dāng)且僅當(dāng)我有錢時(shí)，我才去看電影”符號(hào)化為 。16. 設(shè)是群，且，則 。17命題公式是永（ ）式。18的主析取

6、范式中，含有（ ）個(gè)極小項(xiàng)。19. 設(shè)集合，上有一個(gè)劃分，那么所對(duì)應(yīng)的等價(jià)關(guān)系應(yīng)有（ ）個(gè)序偶。20. 在有理數(shù)集合上定義二元運(yùn)算*：，則的幺元是（ ）。21. 一個(gè)（ ）稱為布爾代數(shù)。22命題公式是永（ ）式。23的主析取范式中，含有（ ）個(gè)極小項(xiàng)。24. 設(shè)集合，上有一個(gè)劃分，那么所對(duì)應(yīng)的等價(jià)關(guān)系應(yīng)有（ ）個(gè)序偶。25. 在有理數(shù)集合上定義二元運(yùn)算*：，則的幺元是（ ）。26. 一個(gè)（ ）稱為布爾代數(shù)。27的主析取范式是 。(寫出一般表示形式即可)28設(shè)集合，是上的二元關(guān)系，且，則的傳遞閉包 。 29設(shè)集合，是上的整除關(guān)系，則的關(guān)系矩陣 ，哈斯圖為 。30. 一個(gè)連通平面圖有9個(gè)頂點(diǎn)，它們

7、的度數(shù)分別為：2，2，2，3，3，3，4，4，5，則該圖共有 個(gè)面。31. 集合上可以定義的二元運(yùn)算的個(gè)數(shù)是 。三、解答題1.求帶權(quán)值為 1, 3, 5, 5, 8, 12, 14, 19的最優(yōu)二叉樹。(只要最終結(jié)果，不要求中間過(guò)程)(8分)2求 的最小生成樹。(只要最終結(jié)果，不要求中間過(guò)程。) (8分)3.設(shè)是平面圖，有個(gè)頂點(diǎn)，條邊，個(gè)面，個(gè)連通分支，證明： (10分)4.化簡(jiǎn)下列布爾表達(dá)式。 (1) (2) (8分)5.證明在格中，是格中的偏序關(guān)系，若，則有。 (8分)6. 設(shè)，是的冪集，是集合的對(duì)稱差運(yùn)算，已知是群，在群中，求：(1) 關(guān)于運(yùn)算的幺元；(2) 中每個(gè)元素的逆元；(3) 求

8、元素，使得。 (9分)7. 設(shè)是半群，其運(yùn)算表如下 (8分)證明：是循環(huán)群。*8. 設(shè)是集合上的二元關(guān)系，若是自反的和傳遞的，則。 (8分)9. 設(shè)是格，其中是75的的所有正因數(shù)的集合，是上的整除關(guān)系，求中每個(gè)元素的余元素。 (8分)10. 證明等價(jià)式：。 (6分)11.用推理規(guī)則證明：。12設(shè)是非空集合上的二元關(guān)系，令，證明：具有自反性，對(duì)稱性。13. 設(shè)是獨(dú)異點(diǎn)，并且對(duì)于中的每一個(gè)元素，都有，其中是幺元，證明：是一個(gè)阿貝爾群。14. 證明：循環(huán)群是交換群。15. 設(shè)是一個(gè)格，且，令 其中是格中的偏序關(guān)系，證明：是的子格。16. 證明在格中，是格中的偏序關(guān)系，若，則有。17. 給定樹葉的權(quán)為

9、1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。18. 證明：若無(wú)向圖是不連通的，則其補(bǔ)圖是連通的。19(10分)求帶權(quán)1、2、3、4、5、6、7、8、9、10的最優(yōu)二叉樹。20. (10分) 設(shè)集合，是上的二元關(guān)系，試求：(1) ； (2) 的關(guān)系圖與關(guān)系矩陣； (3) 、。21證明等價(jià)式：。22. 證明：樹是一個(gè)偶圖。23. 設(shè)是群，對(duì)任意的，令，證明：是的子群。24. 設(shè)為實(shí)數(shù)集，對(duì)任意的，定義：證明：是雙射。25. 設(shè)是含幺環(huán),且*滿足等冪律,在上定義運(yùn)算+,如下:, , 證明:是一個(gè)布爾代數(shù)，其中0和1分別是關(guān)于運(yùn)算和*的幺元。26用推理規(guī)則證明： (1

10、0分)27設(shè)是非空集合上自反的二元關(guān)系，證明：也是自反的。(10分)28設(shè)是整數(shù)加群，在上定義：，證明：是交換群。(20分)29設(shè)是一個(gè)格，且，令其中是格中的偏序關(guān)系，證明：是的子格。(15分)30給定樹葉的權(quán)為1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。(10分)31假設(shè)一家化工廠要將多種化學(xué)產(chǎn)品利用鐵路從精煉廠運(yùn)到煉油廠，但是根據(jù)EPA(美國(guó)環(huán)保署)的規(guī)定，這些化學(xué)產(chǎn)品不能全部都裝在同一節(jié)車廂里運(yùn)輸，因?yàn)槿绻鼈兓旌推饋?lái)，就會(huì)產(chǎn)生劇烈反應(yīng)，從而引發(fā)事故，為了使費(fèi)用最低，廠長(zhǎng)希望使用盡可能少的車廂，問(wèn)最少使用多少車廂？其中共有六種化學(xué)產(chǎn)品，不能與、或在同節(jié)車

11、廂里運(yùn)輸，不能與或一起運(yùn)輸，不能與一起運(yùn)輸，不能與一起運(yùn)輸。(15分)32用推理規(guī)則證明： (10分)33設(shè)是非空集合上自反的二元關(guān)系，證明：也是自反的。(10分)34設(shè)是整數(shù)加群，在上定義：，證明：是交換群。(20分)35設(shè)是一個(gè)格，且，令其中是格中的偏序關(guān)系，證明：是的子格。(15分)36給定樹葉的權(quán)為1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。(10分)37假設(shè)一家化工廠要將多種化學(xué)產(chǎn)品利用鐵路從精煉廠運(yùn)到煉油廠，但是根據(jù)EPA(美國(guó)環(huán)保署)的規(guī)定，這些化學(xué)產(chǎn)品不能全部都裝在同一節(jié)車廂里運(yùn)輸，因?yàn)槿绻鼈兓旌推饋?lái)，就會(huì)產(chǎn)生劇烈反應(yīng)，從而引發(fā)事故，為了使費(fèi)

12、用最低，廠長(zhǎng)希望使用盡可能少的車廂，問(wèn)最少使用多少車廂？其中共有六種化學(xué)產(chǎn)品，不能與、或在同節(jié)車廂里運(yùn)輸，不能與或一起運(yùn)輸，不能與一起運(yùn)輸，不能與一起運(yùn)輸。(15分)38(10分)設(shè)是從群到群的同態(tài)映射，分別是群與的幺元，令證明：是群的子群。39. (14分)設(shè)是群，是的子群，在上定義二元關(guān)系如下：對(duì)任意的，當(dāng)且僅當(dāng)證明：(1) 是上的等價(jià)關(guān)系；(2) 對(duì)任意的，。40(10分)用推理規(guī)則證明：。41. (10分)設(shè)是階簡(jiǎn)單無(wú)向圖，是大于2的奇數(shù)，如果中有個(gè)奇數(shù)度的頂點(diǎn)，那么的補(bǔ)圖中奇數(shù)度的頂點(diǎn)也是個(gè)。42. (12分)設(shè)是從格到格的滿同態(tài)映射，證明：若是有界格，則格也是有界格。43設(shè)在一次國(guó)

13、際會(huì)議上有7個(gè)人，各懂的語(yǔ)言如下： a：英語(yǔ) b：英語(yǔ)和西班牙語(yǔ) c：英語(yǔ)、漢語(yǔ)和俄語(yǔ)d：日語(yǔ)和西班牙語(yǔ) e：德語(yǔ)和漢語(yǔ) f：法語(yǔ)、日語(yǔ)和俄語(yǔ) g：法語(yǔ)和德語(yǔ)(1) 用無(wú)向簡(jiǎn)單圖描述以上事實(shí)；(2) 他們中間是否任何兩個(gè)人可對(duì)話(必要時(shí)通過(guò)別人作翻譯)。44設(shè)是格，其中是30的所有正因數(shù)的集合，是上的整除關(guān)系，則 (1) 求每個(gè)元素的余元素； (2) 是否為有余格，是否為分配格？并說(shuō)明理由。離散數(shù)學(xué)練習(xí)題二 一、填空題1冪集是 。2集合上可以定義的二元運(yùn)算的個(gè)數(shù)是 。3集合上的關(guān)系的傳遞閉包 。 4一個(gè)連通平面圖有8個(gè)頂點(diǎn)，它們的度數(shù)分別為：2，2，3，3，3，4，4，5，則該圖共有 個(gè)面。5

14、設(shè)集合，是上的整除關(guān)系，則的關(guān)系矩陣 ，哈斯圖為 。6設(shè)：我們勤奮，：我們好學(xué)，：我們?nèi)〉煤贸煽?jī)。命題“只要勤奮好學(xué)，我們就能取得好成績(jī)”符號(hào)化為 。7某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒(méi)有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。8. 設(shè)集合，是上的二元關(guān)系，且，則的對(duì)稱閉包= 。9. 設(shè)、是集合，若，則到的單射函數(shù)有 個(gè)。10. 整數(shù)加法群的幺元是 。11. 設(shè)是分配格，若對(duì)任意的，都有，則 。12. 任何簡(jiǎn)單圖中頂點(diǎn)的度數(shù)之和等于邊數(shù)的 倍。13. 當(dāng)為 數(shù)時(shí)，必為歐拉圖。14設(shè)：我有錢，：我去看電影，命題“如果我有錢，那么我就去看

15、電影”符號(hào)化為 。15某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒(méi)有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。1616. 設(shè)集合，是上的二元關(guān)系，且，則的傳遞閉包= 。17. 設(shè)、是集合，若，則到的單射函數(shù)有 個(gè)。18. 整數(shù)加法群的幺元是 。19. 設(shè)是分配格，若對(duì)任意的，都有，則 。20. 無(wú)向圖中具有一條歐拉回路，當(dāng)且僅當(dāng)是連通的，并且所有頂點(diǎn)的度數(shù)都是 。21. 若連通簡(jiǎn)單平面圖有4個(gè)頂點(diǎn)，3個(gè)面，則有 條邊。22設(shè)、是集合，其中，則 。23集合上的關(guān)系的傳遞閉包 。17 第 頁(yè)（共59頁(yè)）24. 設(shè)是非空集合，則中的幺元是 ，零元是 。

16、25. 若連通簡(jiǎn)單平面圖有6個(gè)頂點(diǎn)，3個(gè)面，則有 條邊。26. 設(shè)是格，其中，是整除關(guān)系，則3的補(bǔ)元是 ，6的補(bǔ)元是 。 27. 設(shè)、是集合，若，則到的單射函數(shù)有 個(gè)。28設(shè)集合，則 。29設(shè)集合，是上的二元關(guān)系，且，則的傳遞閉包= 。30. 若連通平面簡(jiǎn)單圖有4個(gè)頂點(diǎn)，3個(gè)面，則有 條邊。31. 設(shè)是非空集合，則中的幺元是 ，零元是 。32. 設(shè)是格，其中，是整除關(guān)系，則8的補(bǔ)元是 ，4的補(bǔ)元是 。33.已知集合和，且，則從到有 個(gè)二元關(guān)系，從到有 個(gè)映射。二、單項(xiàng)選擇題1下列集合運(yùn)算中 是正確的。A. B. C. D. 2下面 是重言式。A. B. C. D. 3. 的主析取范式是 A 。

17、A. B. C. D. 4. 若是一個(gè)群，則運(yùn)算“*”一定滿足 。A. 交換律 B. 消去律 C. 冪等律 D. 分配律5設(shè)是整數(shù)集合，下列集合中 關(guān)于數(shù)的加法和乘法構(gòu)成整環(huán)。A B C D6如下的哈斯圖所示偏序集為格的是 。 7設(shè)，則下列集合中等于的是 。A B C D8下列公式中， 是析取范式。A. B. C. D. 9. 下列語(yǔ)句中為命題的是 。 A. 今天是陰天； B. 你身體好嗎？ C. 我真快樂(lè)； D. 請(qǐng)不要走。10. 設(shè)是連通簡(jiǎn)單平面圖，中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是 。A2個(gè)面 B3個(gè)面 C4個(gè)面 D5個(gè)面11. 設(shè)，是集合上的二元關(guān)系，稱關(guān)系為的 關(guān)系。 A. 交 B

18、. 并 C. 補(bǔ) D.逆12. 下面集合中, 關(guān)于數(shù)的減法是封閉的。A B C D13. 設(shè)A是有界格，若它也是有余格，只要 。A. 每一個(gè)元素有一個(gè)余元 B. 每一個(gè)元素至少有兩個(gè)余元C. 每一個(gè)元素?zé)o余元 D. 每一個(gè)元素僅有一個(gè)余元14設(shè)集合，則下面集合與相等的是 。A B C D15下列公式中， 是關(guān)于兩個(gè)命題變?cè)臉O小項(xiàng)。A B C D16. 下列語(yǔ)句中不是命題的是 。A. 3是奇數(shù) B. 請(qǐng)勿吸煙 C. 我是中學(xué)生 D. 4+3517. 數(shù)的加法在下列 集合上是封閉的。A B C D18. 給定下列序列，可構(gòu)成無(wú)向簡(jiǎn)單圖的頂點(diǎn)度數(shù)序列的是 。A. B. C. D. 19. 若是一

19、個(gè)群，則運(yùn)算“*”一定滿足 。A. 交換律 B. 消去律 C. 冪等律 D. 分配律20. 設(shè)是非空集合上的關(guān)系，則的對(duì)稱閉包= 。A. B. C. D. 21下列集合運(yùn)算中 是正確的。A. B. C. D. 22下面的二元關(guān)系中， 具有傳遞性。A. 父子關(guān)系 B. 朋友關(guān)系 C. 集合的包含關(guān)系 D. 實(shí)數(shù)的不相等關(guān)系23. 設(shè)是整數(shù)集，且設(shè)，對(duì)每一個(gè)，有， 元素0的原象的集合為 。A B C D24. 數(shù)的加法在下列集合中 上是封閉的。 A B C D25. 設(shè)無(wú)向樹由3個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)。其余頂點(diǎn)都是樹葉，則有 片樹葉。A. 3 B. 4 C. 5 D. 626. 設(shè)命題，的真值是

20、0，命題，的真值是1，則下列公式中真值為1的是 。A. B. C. D. 27設(shè)，則方程的解集是 。A B C D28設(shè)是非空集合上的關(guān)系，則的對(duì)稱閉包= 。A. B. C. D. 29. 數(shù)的加法在下列集合中 上是封閉的。A B C D30. 給定下列序列，可構(gòu)成無(wú)向簡(jiǎn)單圖的頂點(diǎn)度數(shù)序列的是 。A. B. C. D. 31. 設(shè)是整數(shù)集，且設(shè)，對(duì)每一個(gè)，有， 元素0的原象的集合為 。A B C D32. 命題公式為 。A.重言式 B.可滿足式 C.矛盾式 D.等價(jià)式三、判斷題1若，則必有。( )2一個(gè)不是自反的關(guān)系，一定是反自反的。( )3. 凡陳述句都是命題。( )4有限半群必存在等冪元。

21、( )5. 任何非平凡無(wú)向圖中的奇數(shù)度頂點(diǎn)的個(gè)數(shù)是偶數(shù)。( )6設(shè)，均為非空的集合，已知且，則一定有。( )7一個(gè)不是自反的關(guān)系，一定是反自反的。( )8. “王蘭和王英是姐妹”是復(fù)合命題。( )9. 設(shè)是代數(shù)格，它所誘導(dǎo)的偏序格為，則對(duì)任意的，當(dāng)且僅當(dāng)。( )10任何非平凡樹都至少有兩片樹葉。( )11設(shè)是偏序集，是的非空子集，若有上界，則必有最小上界。( )12. 在有界分配格中，一個(gè)元素若有補(bǔ)元，則補(bǔ)元一定是唯一的。( )13. “王蘭和王英是姐妹”是復(fù)合命題。( )14若半群存在左幺元，則左幺元是唯一的。( )15. 具有兩個(gè)或多個(gè)元素的格中不存在以自身為補(bǔ)元的元素。( )16. 兩個(gè)

22、無(wú)向圖同構(gòu)的充分必要條件是它們的頂點(diǎn)個(gè)數(shù)與邊的個(gè)數(shù)分別相等。( )四、解答題1(10分) 設(shè)，上的二元運(yùn)算為矩陣的乘法運(yùn)算，求 (1) 的運(yùn)算表； (2) 的所有子群；2. (14分) 設(shè)是一個(gè)群，定義集合上的一個(gè)關(guān)系如下：證明：是集合上的一個(gè)等價(jià)關(guān)系。3. (12分)設(shè)是從格到格的滿同態(tài)映射，證明：若是有界格，則格也是有界格。4. (10分) 試用推理規(guī)則證明： 5. (10分) 設(shè)是連通簡(jiǎn)單圖，其中每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)，則對(duì)于任一頂點(diǎn)，圖的連通分支數(shù)小于等于的度數(shù)的一半。6設(shè)是格，其中是45的所有正因數(shù)的集合，是上的整除關(guān)系，則 (1) 求每個(gè)元素的余元素； (2) 是否為有余格，是否為

23、分配格？并說(shuō)明理由。7洛杉磯地區(qū)有7家汽車旅游公司，在一天中每家公司最多參觀下列景點(diǎn)中的三個(gè)不同景點(diǎn)，這些景點(diǎn)是好萊塢、貝弗利山、迪斯尼樂(lè)園和通用電影制片廠，同一天中，參觀一個(gè)景點(diǎn)的旅游公司不能超過(guò)一個(gè)，第一家旅游公司只參觀好萊塢，第二家公司只參觀好萊塢和迪斯尼樂(lè)園，第三家公司只參觀通用電影制片廠，第四家只參觀迪斯尼樂(lè)園和通用電影制片廠，第五家只參觀好萊塢和貝弗利山，第六家只參觀貝弗利山和通用電影制片廠，第七家只參觀迪斯尼樂(lè)園和貝弗利山。請(qǐng)問(wèn)這些游覽可以只安排在星期一、星期三和星期五嗎？8設(shè)、是命題公式，試用兩種方法分別證明等價(jià)式：。9設(shè)是非空集合上的二元關(guān)系，若是自反的，證明：是自反的。10

24、. 設(shè)為實(shí)數(shù)集，：，對(duì)任意的，令，證明：是滿射，并說(shuō)明不是單射。11. 證明：任一序集都是格。12. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。13. 設(shè)和都是群的子群，令，證明是的子群的充要條件是。14. 設(shè)為實(shí)數(shù)集，：，對(duì)任意的，令，證明是滿射，并說(shuō)明不是單射。15設(shè)、是命題公式，試用兩種方法分別證明等價(jià)式：。16. 證明：三個(gè)元素以上的鏈不是有余格。17. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。18設(shè)是非空集合上的二元關(guān)系，若是自反的，證明：是自反的。19. 設(shè)，其中是整數(shù)集合，證明：是整環(huán)，其中運(yùn)算“+”和“ ”是關(guān)于數(shù)的普通加法和乘法。20(1

25、0分)用推理規(guī)則證明：，。21. (20分) 設(shè)是含幺環(huán),且*滿足等冪律,在上定義運(yùn)算+,如下:, , 證明:是一個(gè)布爾代數(shù)，其中0和1分別是關(guān)于運(yùn)算和*的幺元。22. (15分)證明：在中任意刪去條邊后所得到的圖是哈密爾頓圖。12345671-4-62-32-52-313-7-224-41-5-1-6-27-23(5分) Gladbrook飼料公司有7個(gè)谷物箱，要通過(guò)谷物管道將它們連接起來(lái)，以使谷物能從任意一個(gè)箱子轉(zhuǎn)移到其它箱子，為了使建造費(fèi)用最少，希望建造盡可能少的管道，在兩個(gè)箱子之間建造管道的費(fèi)用(以10萬(wàn)美元計(jì))由下表給出，其中“-”表示不能建造管道，應(yīng)該怎樣建造管道才能使費(fèi)用最少。2

26、4(15分)給定群，其中，是上的模6加法運(yùn)算，試求： (1) 的所有生成元； (2) 的所有子群； (3) 每個(gè)子群的所有右陪集。25. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。26. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。27. (15分)給定群，其中，是上的模15加法運(yùn)算，試求： (1) 的所有生成元； (2) 的所有子群； (3) 每個(gè)子群的所有右陪集。28(5分)試用克魯斯卡爾算法求下列表格所確定的權(quán)圖的最小支撐樹。/47914632007695283479/96615676663011463966/837998126720071567837/1213

27、17246956669981213/41228330112671724412/29(15分)證明：如果是一個(gè)具有奇數(shù)個(gè)頂點(diǎn)的偶圖，則不是哈密爾頓圖。30(10分)用推理規(guī)則證明：，31(20分) 設(shè)是一個(gè)布爾代數(shù)，在上定義運(yùn)算*，如下：，證明: 是含幺交換環(huán)。離散數(shù)學(xué)練習(xí)題一答案 一、單項(xiàng)選擇題（每小題2分，共8分） 15 . D C B C C 610 A B D C A1115 C B C D A 1620 C C B D C 2125 C C B D C 2630. D C B A D 31. C 二、填空題（每空1分，共11分）1 2 、 的真值同時(shí)為13. *4. 奇 5. 12 6

28、. 7. 9 8 9 , 的真值都為010. 11. 0 12. 13. 14 14. 15. 或 16. 17. 假 18. 219. 17 20. 0 21. 有余(補(bǔ))分配格 22. 假 23. 2 24. 17 25. 0 26. 有余(補(bǔ))分配格 27. 28. 29. 30. 731. 三、解答題（共81分）3.(10分)設(shè)是平面圖，有個(gè)頂點(diǎn)，條邊，個(gè)面，個(gè)連通分支，證明：。證明：對(duì)于圖的每個(gè)連通分支都是連通平面圖，因此由歐拉公式，有 其中分別是第個(gè)連通分支中的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則將上述個(gè)等式相加，有，即4.(8分)化簡(jiǎn)下列布爾表達(dá)式。(1) (2) 解：(1) (2) 5. (

29、8分)證明在格中，若，則有。證明： 因?yàn)椋裕?因此，故6.(9分) 設(shè)，是的冪集，是集合的對(duì)稱差運(yùn)算，已知是群，在群中，求：(1) 關(guān)于運(yùn)算的幺元； (2) 中每個(gè)元素的逆元； (3) 求元素，使得。解：(1) ，對(duì)于任意的，有，所以關(guān)于運(yùn)算的幺元是。(2) 對(duì)于任意的，有，所以的逆元是其自身。(3) ，使得。7.(8分) 設(shè)是半群，其運(yùn)算表如下*證明：是循環(huán)群。證明：從運(yùn)算表可知，是幺元，與互為逆元，以自身為逆元，所以是群。 因?yàn)椋允巧稍瑒t是循環(huán)群。8. (8分) 設(shè)是集合上的二元關(guān)系，若是自反的和傳遞的，則。證明：由于是傳遞的，必有。對(duì)任意的，因?yàn)槭亲苑吹模校瑥亩浴＞C上

30、知，。9.(8分)設(shè)是格，其中是75的的所有正因數(shù)的集合，是上的整除關(guān)系，求中每個(gè)元素的余元素。解：由格的哈斯圖可知：1與75互為余元素，3與25互為余元素，而5和15沒(méi)有余元素。10.(6分) 證明等價(jià)式：。證明： 11用推理規(guī)則證明：。證明：(1) (2) (3) (1)(2) (4) (5) (3)(4) (6) (7) (5)(6)12設(shè)是非空集合上的二元關(guān)系，令，證明：具有自反性，對(duì)稱性。證明：顯然，所以是自反性的。又所以是對(duì)稱的。13. 設(shè)是獨(dú)異點(diǎn)，并且對(duì)于中的每一個(gè)元素，都有，其中是幺元，證明：是一個(gè)阿貝爾群。證明：由可知，中的每一個(gè)元素都以自身為逆元，所以是群。對(duì)任意的，有所以

31、運(yùn)算*是可交換的，因此，是一個(gè)阿貝爾群。14. 證明：循環(huán)群是交換群。證明：對(duì)任意的，不妨令，其中，則因此循環(huán)群是交換群。15. 設(shè)是一個(gè)格，且，令其中是格中的偏序關(guān)系，證明：是的子格。證明：對(duì)任意的，則有，從而有即因此，故運(yùn)算在上是封閉的，所以是的子格。16. 證明在格中，是格中的偏序關(guān)系，若，則有。證明：因?yàn)椋裕虼擞疫叄省?8. 證明：若無(wú)向圖是不連通的，則其補(bǔ)圖是連通的。證明：因?yàn)槭遣贿B通的，則至少有兩個(gè)連通分支，對(duì)于其中任意兩個(gè)頂點(diǎn)，(1) ，在同一個(gè)連通分支中，則在另一個(gè)連通分支中任取一點(diǎn)，與以及與在中皆是不相鄰的，因而與以及與在中都是相鄰的，那么在中找到一條從到的路。(2)

32、 ，不在同一個(gè)連通分支中，與在中是不相鄰的，因而與在中是相鄰的，從而在中找到一條從到的路。 綜上，圖中任意兩點(diǎn)之間都存在路，所以是連通的。20.(10分) 設(shè)集合，是上的二元關(guān)系，試求：(1) ； (2) 的關(guān)系圖與關(guān)系矩陣； (3)、。解：(1) (2) 工aaaaaaaaaaa關(guān)系圖為：(3) 21(10分) 證明等價(jià)式：證明：22. (10分)證明：樹是一個(gè)偶圖。證明：設(shè)是一棵樹，對(duì)任意的，令(1) 因?yàn)槭沁B通的，所以對(duì)任意的，必有或，因此，(2) 因?yàn)槭菢洌c之間的基本通路有且只有一條，所以，(3) 因?yàn)槭菢洌袩o(wú)回路，所以或中的任意的兩個(gè)頂點(diǎn)不可能是相鄰的。綜上，是一個(gè)偶圖。23.(

33、10分)設(shè)是群，對(duì)任意的，令，證明：是的子群。證明：對(duì)任意的，有所以經(jīng)整理，得所以因此，由子群判定定理，是的子群。24. (10分) 設(shè)為實(shí)數(shù)集，對(duì)任意的，定義：證明：是雙射。證明：(1) 對(duì)任意的，存在，使得所以是滿射。(2) 對(duì)任意的，若，即所以，有解得：即因此是單射。綜上，是雙射。25.(10分) 設(shè)是含幺環(huán),且*滿足等冪律,在上定義運(yùn)算+,如下:, , 證明:是一個(gè)布爾代數(shù)，其中0和1分別是關(guān)于運(yùn)算和*的幺元。證明：(1) 由題設(shè)條件可知，運(yùn)算+和在上是封閉的。(2) 對(duì)任意的，由書上習(xí)題結(jié)論，有從而有即，運(yùn)算+和在上是可交換的。(3) 對(duì)任意的，有即所以運(yùn)算對(duì)+是可分配的。另外即所以

34、運(yùn)算+對(duì)是可分配的。(4) 對(duì)任意的，有(5) 對(duì)任意的，有綜上，由亨廷頓公理，是布爾代數(shù)。26(10分) 用推理規(guī)則證明：證明：(1) (2) (3) (1)(2) (4) (5) (3)(4)27(10分) 設(shè)是非空集合上自反的二元關(guān)系，證明：也是自反的。證明：因?yàn)槭亲苑吹模裕瑒t，故也是自反的。28. (20分) 設(shè)是整數(shù)加群，在上定義：，證明：是交換群。證明：由題設(shè)，運(yùn)算*在上是封閉的。對(duì)任意的，有則，即運(yùn)算*是可結(jié)合的。對(duì)任意的，有所以運(yùn)算*是可交換的。，對(duì)任意的，有所以2是關(guān)于運(yùn)算*的幺元。對(duì)任意的，有所以關(guān)于運(yùn)算*，元素的逆元是。 綜上，是交換群。29. (15分) 設(shè)是一個(gè)格

35、，且，令其中是格中的偏序關(guān)系，證明：是的子格。證明：對(duì)任意的，則有，從而有即因此，故運(yùn)算在上是封閉的，所以是的子格。30. 證明在格中，是格中的偏序關(guān)系，若，則有。證明：因?yàn)椋裕?因此，故31. (15分) 假設(shè)一家化工廠要將多種化學(xué)產(chǎn)品利用鐵路從精煉廠運(yùn)到煉油廠，但是根據(jù)EPA(美國(guó)環(huán)保署)的規(guī)定，這些化學(xué)產(chǎn)品不能全部都裝在同一節(jié)車廂里運(yùn)輸，因?yàn)槿绻鼈兓旌推饋?lái)，就會(huì)產(chǎn)生劇烈反應(yīng)，從而引發(fā)事故，為了使費(fèi)用最低，廠長(zhǎng)希望使用盡可能少的車廂，問(wèn)最少使用多少車廂？其中共有六種化學(xué)產(chǎn)品，不能與、或在同節(jié)車廂里運(yùn)輸，不能與或一起運(yùn)輸，不能與一起運(yùn)輸，不能與一起運(yùn)輸。蘭6蘭6666666蘭66666666666紅5蘭2紅1白3蘭4解：在平面上畫六個(gè)頂點(diǎn)分別表示六種化學(xué)產(chǎn)品，如果兩種化學(xué)產(chǎn)品不能在一節(jié)車廂中運(yùn)輸，則在這兩種產(chǎn)品所對(duì)應(yīng)的頂點(diǎn)之間連一條邊，從而得到一個(gè)無(wú)向圖，現(xiàn)對(duì)該圖的頂點(diǎn)著色，如圖所示，用了三種顏色，所以最少用三節(jié)車廂，第一節(jié)車廂裝、和，第二節(jié)車廂裝，第三節(jié)車廂裝和。32(10分) 用推理規(guī)則證明：證明：