【正文】 4. 當為 數(shù)時，必為歐拉圖。12. 設(shè)是分配格，若對任意的，都有，則 。20. 在有理數(shù)集合上定義二元運算*：，則的幺元是（ ）。(寫出一般表示形式即可)28．設(shè)集合，是上的二元關(guān)系，且，則的傳遞閉包 。 (1) (2) (8分)，是格中的偏序關(guān)系，若，則有。13. 設(shè)是獨異點，并且對于中的每一個元素，都有，其中是幺元，證明：是一個阿貝爾群。21．證明等價式：。(20分)29．設(shè)是一個格，且，令其中是格中的偏序關(guān)系，證明：是的子格。(15分)38．(10分)設(shè)是從群到群的同態(tài)映射，分別是群與的幺元，令證明：是群的子群。2．集合上可以定義的二元運算的個數(shù)是 。9. 設(shè)、是集合，若，則到的單射函數(shù)有 個。17. 設(shè)、是集合，若，則到的單射函數(shù)有 個。25. 若連通簡單平面圖有6個頂點，3個面，則有 條邊。，且，則從到有 個二元關(guān)系，從到有 個映射。A．　　 　B． C．　　　　 D．8．下列公式中， 是析取范式。 B．3個面 C．4個面A． B． C． D．15．下列公式中， 是關(guān)于兩個命題變元，的極小項。D．16. 下列語句中不是命題的是 。A． B． C． D．24. 數(shù)的加法在下列集合中 上是封閉的。A. B. C. D. 31. 設(shè)是整數(shù)集，且設(shè)，對每一個，有， 元素0的原象的集合為 。( )7．一個不是自反的關(guān)系，一定是反自反的。( )15. 具有兩個或多個元素的格中不存在以自身為補元的元素。9．設(shè)是非空集合上的二元關(guān)系，若是自反的，證明：是自反的。17. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。1234567146232523137224415162723．(5分) Gladbrook飼料公司有7個谷物箱，要通過谷物管道將它們連接起來，以使谷物能從任意一個箱子轉(zhuǎn)移到其它箱子，為了使建造費用最少，希望建造盡可能少的管道，在兩個箱子之間建造管道的費用(以10萬美元計)由下表給出，其中“”表示不能建造管道，應(yīng)該怎樣建造管道才能使費用最少?！峨x散數(shù)學》練習題一答案 一、單項選擇題（每小題2分，共8分） 1—5 . D C B C C 6—10 ． A B D C A11—15 C B C D A 16—20 C C B D C 21—25 C C B D C 26—30. D C B A D 31. C 二、填空題（每空1分，共11分）1． 2． 、 的真值同時為13. *4. 奇 5. 12 6. 7. 9 8． 9． , 的真值都為010. 11. 0 12. 13. 14 14. 15. 或 16. 17. 假 18. 219. 17 20. 0 21. 有余(補)分配格 22. 假 23. 2 24. 17 25. 0 26. 有余(補)分配格 27. 28. 29. 30. 731. 三、解答題（共81分）3.(10分)設(shè)是平面圖，有個頂點，條邊，個面，個連通分支，證明：。證明：從運算表可知，是幺元，與互為逆元，以自身為逆元，所以是群。10.(6分) 證明等價式：。14. 證明：循環(huán)群是交換群。(2) ，不在同一個連通分支中，與在中是不相鄰的，因而與在中是相鄰的，從而在中找到一條從到的路。24. (10分) 設(shè)為實數(shù)集，對任意的，定義：證明：是雙射。(2) 對任意的，由書上習題結(jié)論，有從而有即，運算+和證明：因為是自反的，所以，則，故也是自反的。29. (15分) 設(shè)是一個格，且，令其中是格中的偏序關(guān)系，證明：是的子格。證明：由題設(shè)，運算*在上是封閉的。36. 證明在格中，是格中的偏序關(guān)系，若，則有。 對任意的，則有，因為是的子群，所以有，所以是對稱的。證明：對任意的，則，因為是奇數(shù)，所以若在中是奇數(shù)度頂點，則在中也是奇數(shù)度頂點；若在中是偶數(shù)度頂點，則在中也是偶數(shù)度頂點，因此，如果中有個奇數(shù)度的頂點，那么的補圖中奇數(shù)度的頂點也是個。(2) 因為每個元素都存在余元素，所以是有余格。證明：設(shè)的最大元和最小元分別為1與0，往證和是的最大元和最小元。(2) 因為3與15不存在余元素，所以不是有余格。證明：對任意的，存在，使得，所以是滿射。12. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。證明：對任意的，存在，使得，所以是滿射。17. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。 ” 在上滿足交換性、結(jié)合性；運算“證明： (1) (附加前提) (2) (1) (3) (4) (2)(3) (5) (4) (6) (5) (7) (8) (6)(7) (9) 21. (20分) 設(shè)是含幺環(huán),且*滿足等冪律,在上定義運算+,另外即所以運算+對(2) ，(3) ，，25. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。(2) 由運算的定義，顯然運算具有交換性和結(jié)合性。59。(4) 對任意的，有所以運算*具有交換性。工aaaaaaaaaaa解：關(guān)系矩陣為關(guān)系圖為：27. (15分)給定群，其中，是上的模15加法運算，試求： (1) 的所有生成元； (2) 的所有子群； (3) 每個子群的所有右陪集。(4) 對任意的，有 (5) 對任意的，有綜上，由亨廷頓公理，是布爾代數(shù)。證明：(1) 由題設(shè)條件可知，運算+和 ” 滿足消去律。證明：因為是自反的，則，而，所以，故是自反的。15．設(shè)、是命題公式，試用兩種方法分別證明等價式：。證明：必要性。11. 證明：任一序集都是格。蘭2紅3 白4白 5蘭6紅7紅 17．洛杉磯地區(qū)有7家汽車旅游公司，在一天中每家公司最多參觀下列景點中的三個不同景點，這些景點是好萊塢、貝弗利山、迪斯尼樂園和通用電影制片廠，同一天中，參觀一個景點的旅游公司不能超過一個，第一家旅游公司只參觀好萊塢，第二家公司只參觀好萊塢和迪斯尼樂園，第三家公司只參觀通用電影制片廠，第四家只參觀迪斯尼樂園和通用電影制片廠，第五家只參觀好萊塢和貝弗利山，第六家只參觀貝弗利山和通用電影制片廠，第七家只參觀迪斯尼樂園和貝弗利山。4. (10分) 試用推理規(guī)則證明： ① ② ①③ ④ ③⑤ ②④⑥ ⑦ ⑥⑧ ③⑦⑩ ⑤⑧⒒ ⑩5. (10分) 設(shè)是連通簡單圖，其中每個頂點的度數(shù)都是偶數(shù)，則對于任一頂點，圖的連通分支數(shù)小于等于的度數(shù)的一半。《離散數(shù)學》練習題二答案一、填空題（每空2分，共12分）1. 2. 3. 4. 75. 6. 7. 148. 9. 6 10. 0 11. 12. 2 13. 奇14. 15. 1416. 17. 6 18. 0 19. 20. 偶數(shù) 22. 23. 24. 、 25. 7 26. 不存在 27. 6 28. 29. 30. 5 31. 、 32. 不存在 33. 、二、單項選擇題（每小題2分，共12分）1. B 2. D 3. A 4. B 5. D 6. D 7. C 8. D 9. A 10. C11. D 12. B 13. A 14. D 15. C 16. B 17. C 18. B 19. B 20. A21. B 22. C 23. A 24. C 27. B 28. D 29. C 30. B 31. A 32. C三、判斷題1．T 2．F 3. F 4．T 5. T 6．T 7．F 8. F 9．T 10. T11．F 12．T 13. F 14．F 15．T 16. F三、解答題1．(10分) 設(shè)，上的二元運算為矩陣的乘法運算，求 (1) 的運算表； (2) 的所有子群；解：為方便起見，令，則(1) *(2) 、2.