【正文】 ，則(1) *(2) 、2. (14分) 設(shè)是一個群，定義集合上的一個關(guān)系如下：證明：是集合上的一個等價關(guān)系。44．設(shè)是格，其中是30的所有正因數(shù)的集合，是上的整除關(guān)系，則 (1) 求每個元素的余元素； (2) 是否為有余格，是否為分配格？并說明理由。證明：設(shè)的最大元和最小元分別為1與0，往證和是的最大元和最小元。40．(10分)用推理規(guī)則證明：。 綜上，是等價關(guān)系。39. (14分)設(shè)是群，是的子群，在上定義二元關(guān)系如下：對任意的，當(dāng)且僅當(dāng)證明：(1) 是上的等價關(guān)系；(2) 對任意的。蘭6蘭6666666蘭66666666666紅5蘭2紅1白3蘭4解：在平面上畫六個頂點分別表示六種化學(xué)產(chǎn)品，如果兩種化學(xué)產(chǎn)品不能在一節(jié)車廂中運輸，則在這兩種產(chǎn)品所對應(yīng)的頂點之間連一條邊，從而得到一個無向圖，現(xiàn)對該圖的頂點著色，如圖所示，用了三種顏色，所以最少用三節(jié)車廂，第一節(jié)車廂裝、和，第二節(jié)車廂裝，第三節(jié)車廂裝和。35. (15分) 設(shè)是一個格，且，令其中是格中的偏序關(guān)系，證明：是的子格。對任意的，有所以運算*是可交換的。證明：因為是自反的，所以，則，故也是自反的。30. 證明在格中，是格中的偏序關(guān)系，若，則有。對任意的，有所以關(guān)于運算*，元素的逆元是。證明：由題設(shè)，運算*在上是封閉的。(4) 對任意的，有(5) 對任意的，有綜上，由亨廷頓公理，是布爾代數(shù)。(3) 對任意的，有即所以運算證明：(1) 由題設(shè)條件可知，運算+和(2) 對任意的，若，即所以，有解得：即因此是單射。23.(10分)設(shè)是群，對任意的，令，證明：是的子群。20.(10分) 設(shè)集合，是上的二元關(guān)系，試求：(1) ； (2) 的關(guān)系圖與關(guān)系矩陣； (3)、。18. 證明：若無向圖是不連通的，則其補圖是連通的。15. 設(shè)是一個格，且，令其中是格中的偏序關(guān)系，證明：是的子格。證明：由可知，中的每一個元素都以自身為逆元，所以是群。證明：(1) (2) (3) (1)(2) (4) (5) (3)(4) (6) (7) (5)(6)12．設(shè)是非空集合上的二元關(guān)系，令，證明：具有自反性，對稱性。9.(8分)設(shè)是格，其中是75的的所有正因數(shù)的集合，是上的整除關(guān)系，求中每個元素的余元素。8. (8分) 設(shè)是集合上的二元關(guān)系，若是自反的和傳遞的，則。(3) ，使得。(1) (2) 解：(1) (2) 5. (8分)證明在格中，若，則有。/47914632007695283479/96615676663011463966/837998126720071567837/121317246956669981213/41228330112671724412/29．(15分)證明：如果是一個具有奇數(shù)個頂點的偶圖，則不是哈密爾頓圖。25. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。,ˉ如下:, , 證明:是一個布爾代數(shù)，其中0和1分別是關(guān)于運算和*的幺元。19. 設(shè)，其中是整數(shù)集合，證明：是整環(huán)，其中運算“+”和“15．設(shè)、是命題公式，試用兩種方法分別證明等價式：。11. 證明：任一序集都是格。7．洛杉磯地區(qū)有7家汽車旅游公司，在一天中每家公司最多參觀下列景點中的三個不同景點，這些景點是好萊塢、貝弗利山、迪斯尼樂園和通用電影制片廠，同一天中，參觀一個景點的旅游公司不能超過一個，第一家旅游公司只參觀好萊塢，第二家公司只參觀好萊塢和迪斯尼樂園，第三家公司只參觀通用電影制片廠，第四家只參觀迪斯尼樂園和通用電影制片廠，第五家只參觀好萊塢和貝弗利山，第六家只參觀貝弗利山和通用電影制片廠，第七家只參觀迪斯尼樂園和貝弗利山。( )四、解答題1．(10分) 設(shè)，上的二元運算為矩陣的乘法運算，求 (1) 的運算表； (2) 的所有子群；2. (14分) 設(shè)是一個群，定義集合上的一個關(guān)系如下：證明：是集合上的一個等價關(guān)系。( )13. “王蘭和王英是姐妹”是復(fù)合命題。( )9. 設(shè)是代數(shù)格，它所誘導(dǎo)的偏序格為，則對任意的，當(dāng)且僅當(dāng)。( )5. 任何非平凡無向圖中的奇數(shù)度頂點的個數(shù)是偶數(shù)。 三、判斷題1．若，則必有。A. B. C. D. 29. 數(shù)的加法在下列集合中 上是封閉的。其余頂點都是樹葉，則有 片樹葉。A. B. C. D. 22．下面的二元關(guān)系中， 具有傳遞性。　A．　　 B． 　C．　 D．18. 給定下列序列，可構(gòu)成無向簡單圖的頂點度數(shù)序列的是 。A． B． C． D．13. 設(shè)A是有界格，若它也是有余格，只要 ?！?A. 今天是陰天；　 B. 你身體好嗎？ C. 我真快樂；　 D. 請不要走。A． B． C． D．6．如下的哈斯圖所示偏序集為格的是 。A. B. C. D. 2．下面 是重言式。31. 設(shè)是非空集合，則中的幺元是 ，零元是 。 27. 設(shè)、是集合，若，則到的單射函數(shù)有 個。23．集合上的關(guān)系的傳遞閉包 。19. 設(shè)是分配格，若對任意的，都有，則 。15．某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。11. 設(shè)是分配格，若對任意的，都有，則 。7．某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。 4．一個連通平面圖有8個頂點，它們的度數(shù)分別為：2，2，3，3，3，4，4，5，則該圖共有 個面。44．設(shè)是格，其中是30的所有正因數(shù)的集合，是上的整除關(guān)系，則 (1) 求每個元素的余元素； (2) 是否為有余格，是否為分配格？并說明理由。40．(10分)用推理規(guī)則證明：。(15分)36．給定樹葉的權(quán)為1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。(10分)31．假設(shè)一家化工廠要將多種化學(xué)產(chǎn)品利用鐵路從精煉廠運到煉油廠，但是根據(jù)EPA(美國環(huán)保署)的規(guī)定，這些化學(xué)產(chǎn)品不能全部都裝在同一節(jié)車廂里運輸，因為如果它們混和起來，就會產(chǎn)生劇烈反應(yīng)，從而引發(fā)事故，為了使費用最低，廠長希望使用盡可能少的車廂，問最少使用多少車廂？其中共有六種化學(xué)產(chǎn)品，不能與、或在同節(jié)車廂里運輸，不能與或一起運輸，不能與一起運輸，不能與一起運輸。26．用推理規(guī)則證明： (10分)27．設(shè)是非空集合上自反的二元關(guān)系，證明：也是自反的。23. 設(shè)是群，對任意的，令，證明：是的子群。19．(10分)求帶權(quán)10的最優(yōu)二叉樹。15. 設(shè)是一個格，且，令 其中是格中的偏序關(guān)系，證明：是的子格。 (6分)：。 (9分)7. 設(shè)是半群，其運算表如下 (8分)證明：是循環(huán)群。(只要最終結(jié)果，不要求中間過程。30. 一個連通平面圖有9個頂點，它們的度數(shù)分別為：2，2，2，3，3，3，4，4，5，則該圖共有 個面。26. 一個（ ）稱為布爾代數(shù)。22．命題公式是永（ ）式。18．的主析取范式中，含有（ ）個極小項。14. 將布爾表達式化簡得 。10. 設(shè)是四個非空集合，則的充分必要條件是 。6. 命題公式的主析取范式為 。2．設(shè)、為兩個命題，當(dāng)且僅當(dāng) 時，的真值為1。Ⅰ． Ⅱ． Ⅲ． Ⅳ． A.Ⅲ B.Ⅰ和Ⅲ C.Ⅰ和Ⅱ D.Ⅰ、Ⅱ、Ⅲ和Ⅳ29．任意一個具有多個等冪元的半群 (若元素滿足，則稱為等冪元)，該半群 ?！．　　 B．　 C．　　 D．25．下列圖形中為歐拉圖的是（ ）。21．設(shè)，則下列集合中等于的是（ ）。　A．　　　 　 B． 　C．　　　　 　　　 D．17．設(shè)，下列選項正確的是（ ）。A． B． C． D． 13. 對于一個只有4個不同元素的集合來說，上的不同的二元關(guān)系的總數(shù)為 ?！．　　 B．　 C．　　 D．9. 下列圖形中為歐拉圖的是 。A. 1 B. 2 C. 3 D. 45．設(shè)，則下列集合中等于的是 ?！峨x散數(shù)學(xué)》練習(xí)題一一、單項選擇題1．設(shè)集合，則下面集合與相等的是 。A． B．C． D．4. 設(shè)是4階群，則其子群的階不能是下面的 。A． B． C．2 D．8. 數(shù)的加法在下列集合中 上是封閉的。A． B． C． D．12. 。A． B． C． D． 16．設(shè)，則下列集合中等于的是（ ）?！．　　 B．　 C．　　 D．20．下列圖形中為歐拉圖的是（ ）。A． B．