《離散數(shù)學(xué)》期末練習(xí)題考試卷和答案.pdf

1 離散數(shù)學(xué)練習(xí)題離散數(shù)學(xué)練習(xí)題一一 一、單項選擇題一、單項選擇題 1設(shè)集合3 , 2 , 1 , 0E，則下面集合與E相等的是 。 A03 xRx B9 2 xRx C065 2 xxRx D30 xNx 2設(shè)6 , 5 , 4 , 3 , 2 , 1A，R是集合A上的整除關(guān)系，下列敘述中錯誤的是 。 A4，5，6 全是A的極大元 BA沒有最大元 C6 是A的上界 D1 是A的最大下界 3. 設(shè) 4 , 3 , 2 , 1X，dcbaY , , , ，則下列關(guān)系中為從X到Y(jié)的映射是 。 Acba , 3 , , 2 , , 1 Bbcba , 4 , , 3 , , 2 , , 1 Cbaa , 3 , , 2 , , 1 Dcbbba , 3, , 4 , , 2 , , 1 , , 1 4. 設(shè)G是 4 階群，則其子群的階不能是下面的 。 A. 1 B. 2 C. 3 D. 4 5設(shè)5 , 4 , 3 , 2 , 1S，則下列集合中等于S的是 。 A 4 , 3 , 2 , 1 B25, 2 xxx 是有理數(shù) C5,xxx 是正整數(shù) D5,xxx 是有理數(shù) 6下面有關(guān)集合之間的包含和屬于關(guān)系的說法，正確的是 。 , bababa, cbababa, A和 B和 C和 D、和 7. 設(shè)A為n個元素的集合，則A上有 個二元關(guān)系。 A n 2 B nn 2 C2n Dn 8. 數(shù)的加法在下列集合中 上是封閉的。 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 9. 下列圖形中為歐拉圖的是 。 10設(shè),L是格，Lcba,，且abac ,，則cba caba。 2 A. = B. C. D. 沒關(guān)系 11設(shè)BA，則有 。 AB BB CBA DAB 12. QP 。 A QPP B PQQP C PQQP D PQQP 13. 對于一個只有 4 個不同元素的集合A來說，A上的不同的二元關(guān)系的總數(shù)為 。 A4 B16 C 16 2 D 4 2 14. 下列代數(shù)系統(tǒng)* , G中， 不構(gòu)成群。 A01 , 1G，*是模 11 乘法 B9 , 5 , 4 , 3 , 1G，*是模 11 乘法 CG為有理數(shù)集，*是普通加法 DG為有理數(shù)集，*是普通乘法 15. 設(shè)G為有n個頂點的簡單圖，則有 。 A nG B nG C nG D nG 16設(shè)5 , 4 , 3 , 2 , 1S，則下列集合中等于S的是（ ）。 A 4 , 3 , 2 , 1 B25, 2 xxx 是有理數(shù) C5,xxx 是正整數(shù) D5,xxx 是有理數(shù) 17設(shè)8 , 7 , 6,5 , 4,3 , 2 , 1A，下列選項正確的是（ ） 。 AA1 BA3 , 2 , 1 CA5 , 4 DA 18設(shè)A為n個元素的集合，則A上有（ ）個二元關(guān)系。 A n 2 B nn 2 C2n Dn 19數(shù)的加法在下列集合中（ ）上是封閉的。 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 20下列圖形中為歐拉圖的是（ ）。 3 21設(shè)5 , 4 , 3 , 2 , 1S，則下列集合中等于S的是（ ）。 A 4 , 3 , 2 , 1 B25, 2 xxx 是有理數(shù) C5,xxx 是正整數(shù) D5,xxx 是有理數(shù) 22設(shè)8 , 7 , 6,5 , 4,3 , 2 , 1A，下列選項正確的是（ ） 。 AA1 BA3 , 2 , 1 CA5 , 4 DA 23設(shè)A為n個元素的集合，則A上有（ ）個二元關(guān)系。 A n 2 B nn 2 C2n Dn 24數(shù)的加法在下列集合中（ ）上是封閉的。 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 25下列圖形中為歐拉圖的是（ ）。 2626下列命題中， 是錯誤的。 A. xxx B. xxx C. 若 xxA，則Ax且Ax D. 若BA，則BA 2 27 7冪集)(PPP是 。 A , , B , , , 4 C , , , , D , , 2828. . 下列命題公式中 為重言式。 rqpp rpqprqp rprpqp rqqp A. B.和 C.和 D.、和 2929任意一個具有多個等冪元的半群 (若元素a滿足aaa*，則稱a為等冪元)，該半 群 。 A不能構(gòu)成群 B不一定能構(gòu)成群 C必能構(gòu)成群 D能構(gòu)成交換群 3030設(shè)I是整數(shù)集合，下列集合中 關(guān)于數(shù)的加法和乘法構(gòu)成整環(huán)。 AInn 2 BInn 12 CInnn , 0 DI 3131設(shè)集合3 , 2 , 1A，5 , 4 , 3 , 2B，16 , 8 , 4 , 2C，4 , 3 , 2 , 1D，又規(guī)定偏序關(guān)系 “|”是集合上的“整除”關(guān)系，則下列偏序集中 能構(gòu)成格。 A , A B , B C , C D 二、填空題二、填空題 1設(shè)A為非空集合，且nA ，則A上不同的二元關(guān)系的個數(shù)為 ，A上不同的映射的個數(shù) 為 。 2設(shè)P、Q為兩個命題，當(dāng)且僅當(dāng) 時，QP 的真值為 1。 3. 在運算表中的空白處填入適當(dāng)符號，使* , , , cba成為群。 * a b c a a b a b c c c 4. 當(dāng)n為 數(shù)時，3nKn必為歐拉圖。 5. 某校有足球隊員 38 人，籃球隊員 15 人，排球隊員 20 人，三隊隊員總數(shù)為 58 人，且其中只有 3 人同 5 時參加 3 種球隊，那么僅僅參加兩種球隊的隊員人數(shù)是 。 6. 命題公式QP 的主析取范式為 。 7. 一棵無向樹有兩個 2 度頂點，一個 3 度頂點，三個 4 度頂點，則它的樹葉數(shù)為 。 8設(shè)P：我生病，Q：我去學(xué)校，命題“如果我生病，那么我不去學(xué)?！狈柣癁?。 9P ,Q為兩個命題，當(dāng)且僅當(dāng) 時，QP 的值為 0。 10. 設(shè)DCBA , , , 是四個非空集合，則DCBA的充分必要條件是 。 11. 在有理數(shù)集合Q上定義二元運算*：abbaba*，則 * , Q的幺元是 。 12. 設(shè) , L是 分 配 格 ， 若 對 任 意 的Lcba,， 都 有cabacaba , ， 則 。 13. 某班有學(xué)生 50 人，有 26 人在第一次考試中得優(yōu)，有 21 人在第二次考試中得優(yōu)，有 17 人兩次考試都 沒有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。 14. 將布爾表達式cbbcca化簡得 。 15. 設(shè)P：我有錢，Q：我去看電影，命題“當(dāng)且僅當(dāng)我有錢時，我才去看電影”符號化 為 。 16. 設(shè)* , ,ba是群，且baa*，則bb* 。 17命題公式rqqpp是永（ ）式。 18QP 的主析取范式中，含有（ ）個極小項。 19. 設(shè)集合gfedcbaA , , , , , , ，A上有一個劃分 gfedcba , , , , , , ，那么所對應(yīng)的 等價關(guān)系R應(yīng)有（ ）個序偶。 20. 在有理數(shù)集合Q上定義二元運算*：abbaba*，則 * , Q的幺元是（ ）。 21. 一個（ ）稱為布爾代數(shù)。 22命題公式rqqpp是永（ ）式。 23QP 的主析取范式中，含有（ ）個極小項。 24. 設(shè)集合gfedcbaA , , , , , , ，A上有一個劃分 gfedcba , , , , , , ，那么所對應(yīng)的 等價關(guān)系R應(yīng)有（ ）個序偶。 25. 在有理數(shù)集合Q上定義二元運算*：abbaba*，則 * , Q的幺元是（ ）。 26. 一個（ ）稱為布爾代數(shù)。 2727QPQP的主析取范式是 。(寫出一般 6 表示形式即可) 2828設(shè)集合 , , , dcbaA ，R是A上的二元關(guān)系，且cadccbabbaR , , , , , , , , , ， 則R的傳遞閉包 Rt 。 2929 設(shè) 集 合 12 , 8 , 6 , 4 , 3 , 2A，R是A上 的 整 除 關(guān) 系 ， 則R的 關(guān) 系 矩 陣 R M ， 哈斯圖為 。 3030. . 一個連通平面圖有 9 個頂點，它們的度數(shù)分別為：2，2，2，3，3，3，4，4，5，則該圖 共有 個面。 3131. . 集合cbaA , , 上可以定義的二元運算的個數(shù)是 。 三、解答題三、解答題 1.求帶權(quán)值為 1, 3, 5, 5, 8, 12, 14, 19 的最優(yōu)二叉樹。(只要最終結(jié)果，不要求中間過程)(8 分) 2求 的最小生成樹。(只要最終結(jié)果，不要求中間過程。) (8 分) 3.設(shè)G是平面圖，有n個頂點，m條邊，f個面，k個連通分支，證明：1kfmn (10 分) 7 4.化簡下列布爾表達式。 (1) cbcbaba (2) cbacba (8 分) 5. 證 明 在 格 , , L中 ，是 格L中 的 偏 序 關(guān) 系 ，Lcba , , ， 若cba， 則 有 cabacbba。 (8 分) 6. 設(shè)cbaA , , ， AP是A的冪集，是集合的對稱差運算， 已知 , AP是群， 在群 , AP 中，求：(1) 關(guān)于運算的幺元；(2) AP中每個元素的逆元；(3) 求元素x，使得 bxa。 (9 分) 7. 設(shè)* , , , , dcba是半群，其運算表如下 (8 分) 證明：* , , , , dcba是循環(huán)群。 * a b c d a a b c d b b c d a c c d a b d d a b c 8 8. 設(shè)R是集合A上的二元關(guān)系，若R是自反的和傳遞的，則RRR。 (8 分) 9. 設(shè)DS , 75 是格，其中 75 S是 75 的的所有正因數(shù)的集合，D是 75 S上的整除關(guān)系，求 75 S中每個元素的 余元素。 (8 分) 10. 證明等價式： QRPQRQP。 (6 分) 11.用推理規(guī)則證明： SRSRBABAPPDCDC , , , 。 12設(shè)R是非空集合A上的二元關(guān)系，令 1 RRIA，證明：具有自反性，對稱性。 13. 設(shè)* , G是獨異點，并且對于G中的每一個元素x，都有exx*，其中e是幺元，證明：* , G是 一個阿貝爾群。 9 14. 證明：循環(huán)群 aG 是交換群。 15. 設(shè) , , L是一個格，Lba , ，且ba ，令 bxaLxS 其中是格L中的偏序關(guān)系，證明： , , S是 , , L的子格。 16. 證明在格 , , L中，是格L中的偏序關(guān)系，Lcba , , ，若ab ，ac ，則有 cabacba。 17. 給定樹葉的權(quán)為 1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。 18. 證明：若無向圖G是不連通的，則其補圖G是連通的。 10 19(10 分)求帶權(quán) 1、2、3、4、5、6、7、8、9、10 的最優(yōu)二叉樹。 20. (10 分) 設(shè)集合cbaA , , ，R是A上的二元關(guān)系，bccabaaaR , , , , , , , ， 試求：(1) AP； (2) R的關(guān)系圖與關(guān)系矩陣 R M； (3) Rr、 Rs、 Rt。 21證明等價式： CQPACQPACAQP。 22. 證明：樹是一個偶圖。 11 23. 設(shè)* , G是群，對任意的Ga，令xaaxGxH* ，證明：H是G的子群。 24. 設(shè)R為實數(shù)集，RRRRf:，對任意的RRyx , ，定義：yxyxyxf, , 證明：f是雙射。 25. 設(shè),*,B是含幺環(huán),且*滿足等冪律,在B上定義運算+,如下: bababa*, baba*, 1 aa 證明:1 , 0 , , , , B是一個布爾代數(shù)，其中 0 和 1 分別是關(guān)于運算和*的幺元。 26用推理規(guī)則證明： CBEDAEDCBA , , (10 分) 27設(shè)R是非空集合A上自反的二元關(guān)系，證明： 1 R也是自反的。(10 分) 28設(shè)G是整數(shù)加群，在G上定義：2*baba，證明：* , G是交換群。(20 分) 12 29設(shè) , , L是一個格，Lba , ，且ba ，令bxaLxS 其中是格L中的偏序關(guān)系，證明： , , S是 , , L的子格。(15 分) 30給定樹葉的權(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)品， 1 P不能與 2 P、 3 P或 4 P在同節(jié)車廂里運輸， 2 P不能與 3 P或 5 P一起運輸， 3 P不能與 4 P一起運輸， 5 P不能 與 6 P一起運輸。(15 分) 13 32用推理規(guī)則證明： CBEDAEDCBA , , (10 分) 33設(shè)R是非空集合A上自反的二元關(guān)系，證明： 1 R也是自反的。(10 分) 34設(shè)G是整數(shù)加群，在G上定義：2*baba，證明：* , G是交換群。(20 分) 35設(shè) , , L是一個格，Lba , ，且ba ，令bxaLxS 其中是格L中的偏序關(guān)系，證明： , , S是 , , L的子格。(15 分) 36給定樹葉的權(quán)為 1，4，9，16，25，36，49，64，81，100，試構(gòu)造一棵最優(yōu)二叉榪。(10 分) 37 假設(shè)一家化工廠要將多種化學(xué)產(chǎn)品利用鐵路從精煉廠運到煉油廠， 但是根據(jù) EPA(美國環(huán)保署)的規(guī)定， 這些化學(xué)產(chǎn)品不能全部都裝在同一節(jié)車廂里運輸，因為如果它們混和起來，就會產(chǎn)生劇烈反應(yīng)，從而引發(fā) 14 事故，為了使費用最低，廠長希望使用盡可能少的車廂，問最少使用多少車廂？其中共有六種化學(xué)產(chǎn)品， 1 P不能與 2 P、 3 P或 4 P在同節(jié)車廂里運輸， 2 P不能與 3 P或 5 P一起運輸， 3 P不能與 4 P一起運輸， 5 P不能 與 6 P一起運輸。(15 分) 3838(10 分)設(shè)是從群* , 1 G到群 , 2 G的同態(tài)映射， 1 e， 2 e分別是群* , 1 G與 , 2 G的 幺元，令 21 exGxH 證明：* , H是群* , 1 G的子群。 3939. . (14 分)設(shè),*G是群，H是G的子群，在G上定義二元關(guān)系R如下： 對任意的Gba,，Rba,當(dāng)且僅當(dāng)Hba * 1 證明：(1) R是G上的等價關(guān)系； (2) 對任意的Ga， aHa R 。 4040(10 分)用推理規(guī)則證明：SQSRQPP , 。 4 41 1. . (10 分)設(shè)EVG , 是n階簡單無向圖，n是大于 2 的奇數(shù)，如果G中有k個奇數(shù)度的頂 點，那么G的補圖G中奇數(shù)度的頂點也是k個。 4242. . (12 分)設(shè)f是從格 11 , L到格 22 , L的滿同態(tài)映射，證明：若 11 , L是有界格，則 格 22 , L也是有界格。 4343設(shè)在一次國際會議上有 7 個人，各懂的語言如下： a：英語 b：英語和西班牙語 c：英語、漢語和俄語 d：日語和西班牙語 e：德語和漢語 f：法語、日語和俄語 g：法語和德語 15 (1) 用無向簡單圖描述以上事實； (2) 他們中間是否任何兩個人可對話(必要時通過別人作翻譯)。 4444設(shè)DS , 30 是格，其中 30 S是 30 的所有正因數(shù)的集合，D是 30 S上的整除關(guān)系，則 (1) 求每個元素的余元素； (2) DS , 30 是否為有余格，是否為分配格？并說明理由。 離散數(shù)學(xué)練習(xí)題二離散數(shù)學(xué)練習(xí)題二 一、一、填空填空題題 1 1冪集)(PPP是 。 2 2集合baA , 上可以定義的二元運算的個數(shù)是 。 3 3 集合cbaA , , 上的關(guān)系 , , , , , cbccbaR 的傳遞閉包 Rt 。 4 4一個連通平面圖有 8 個頂點，它們的度數(shù)分別為：2，2，3，3，3，4，4，5，則該圖共有 個面。 5 5 設(shè)集合36 , 12 , 8 , 6 , 4 , 3A，R是A上的整除關(guān)系， 則R的關(guān)系矩陣 R M ， 16 哈斯圖為 。 6 6設(shè)p：我們勤奮，q：我們好學(xué)，r：我們?nèi)〉煤贸煽?。命題“只要勤奮好學(xué)，我們就能 取得好成績”符號化為 。 7 7某班有學(xué)生 50 人，有 26 人在第一次考試中得優(yōu)，有 21 人在第二次考試中得優(yōu)，有 17 人 兩次考試都沒有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。 8 8. . 設(shè)集合 , , cbaA ，R是A上的二元關(guān)系，且accbbaR , , , , , ，則R的對稱閉包 Rs= 。 9 9. . 設(shè)A、B是集合，若2A，3B，則A到B的單射函數(shù)有 個。 1010. . 整數(shù)加法群的幺元是 。 1111. . 設(shè) , L是 分 配 格 ， 若 對 任 意 的Lcba,， 都 有cabacaba , ， 則 。 1212. . 任何簡單圖中頂點的度數(shù)之和等于邊數(shù)的 倍。 1313. . 當(dāng)n為 數(shù)時， n K必為歐拉圖2n。 1 14 4設(shè)P：我有錢，Q：我去看電影，命題“如果我有錢，那么我就去看電影”符號化 為 。 1515某班有學(xué)生 50 人，有 26 人在第一次考試中得優(yōu)，有 21 人在第二次考試中得優(yōu)，有 17 人兩次考試都沒有得優(yōu)，那么兩次考試都得優(yōu)的學(xué)生人數(shù)是 。 第 頁（共 59 頁） 17 1616. . 設(shè)集合 , , , dcbaA ，R是A上的二元關(guān)系， 且cadccbabbaR , , , , , , , , , ， 則R的傳遞閉包 Rt= 。 1717. . 設(shè)A、B是集合，若2A，3B，則A到B的單射函數(shù)有 個。 1818. . 整數(shù)加法群的幺元是 。 1919. . 設(shè) , L是 分 配 格 ， 若 對 任 意 的Lcba,， 都 有cabacaba , ， 則 。 2020. . 無向圖G中具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有頂點的度數(shù)都 是 。 2121. . 若連通簡單平面圖G有 4 個頂點，3 個面，則G有 條邊。 2222 設(shè)A、B是集合， 其中4 , 1A，4 , 2B， 則 BPAP 。 23集合cbaA , , 上的關(guān)系 , , , , , cbccbaR 的傳遞閉包 Rt 。 18 2424. . 設(shè)A是非空集合，則),(AP中的幺元是 ，零元是 。 2525. . 若連通簡單平面圖G有 6 個頂點，3 個面，則G有 條邊。 2626. . 設(shè) , L是格，其中24 , 12 , 8 , 6 , 4 , 3 , 2 , 1L，是整除關(guān)系，則 3 的補元是 ，6 的補元 是 。 2727. . 設(shè)A、B是集合，若2A，3B，則A到B的單射函數(shù)有 個。 28設(shè)集合 aA ，則 APP 。 29設(shè)集合 , , , dcbaA ，R是A上的二元關(guān)系，且cadccbabbaR , , , , , , , , , ，則R的 傳遞閉包 Rt= 。 30. 若連通平面簡單圖G有 4 個頂點，3 個面，則G有 條邊。 31. 設(shè)A是非空集合，則),(AP中的幺元是 ，零元是 。 32. 設(shè) , L是格，其中24 , 12 , 8 , 6 , 4 , 3 , 2 , 1L，是整除關(guān)系，則 8 的補元是 ，4 的補元 是 。 33.已知集合A和B，且nA ，mB ，則從A到B有 個二元關(guān)系，從A到B有 個映射。 二、單項選擇題二、單項選擇題 1 1下列集合運算中 是正確的。 A. B. , C. , D. , 2 2下面 是重言式。 A. RQP B. QPRP C. RQQP D. RPQPRQP 19 3.3. QPQP的主析取范式是 A 。 A. QPQP B. QPQP C. QPQP D. QPQP 4 4. 若* , G是一個群，則運算“*”一定滿足 。 A. 交換律 B. 消去律 C. 冪等律 D. 分配律 5 5設(shè)I是整數(shù)集合，下列集合中 關(guān)于數(shù)的加法和乘法構(gòu)成整環(huán)。 AInn 2 BInn 12 CInnn , 0 DI 6 6如下的哈斯圖所示偏序集為格的是 。 7 7設(shè)5 , 4 , 3 , 2 , 1S，則下列集合中等于S的是 。 A 4 , 3 , 2 , 1 B25, 2 xxx 是有理數(shù) C5,xxx 是正整數(shù) D5,xxx 是有理數(shù) 8 8下列公式中， 是析取范式。 A. qp B. qp C. pqp D. qp 9 9. . 下列語句中為命題的是 。 A. 今天是陰天； B. 你身體好嗎？ C. 我真快樂； D. 請不要走。 1010. . 設(shè)G是連通簡單平面圖，G中有 6 個頂點 8 條邊，則 G 的面的數(shù)目是 。 A2 個面 B3 個面 C4 個面 D5 個面 1111. . 設(shè)R，S是集合A上的二元關(guān)系，稱關(guān)系RyxxyS, ,為R的 關(guān)系。 A. 交 B. 并 C. 補 D.逆 20 1212. . 下面集合中, 關(guān)于數(shù)的減法是封閉的。 A全體自然數(shù)N B 2 Zxx C 12 Zxx D 是質(zhì)數(shù)xx 1313. . 設(shè) A 是有界格，若它也是有余格，只要 。 A. 每一個元素有一個余元 B. 每一個元素至少有兩個余元 C. 每一個元素?zé)o余元 D. 每一個元素僅有一個余元 1 14 4設(shè)集合3 , 2 , 1 , 0E，則下面集合與E相等的是 。 A03 xRx B9 2 xRx C065 2 xxRx D30 xNx 1515下列公式中， 是關(guān)于兩個命題變元p，q的極小項。 Aqpp Bqp Cqp Dqpp 1616. . 下列語句中不是命題的是 。 A. 3 是奇數(shù) B. 請勿吸煙 C. 我是中學(xué)生 D. 4+35 1717. . 數(shù)的加法在下列 集合上是封閉的。 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 1818. . 給定下列序列，可構(gòu)成無向簡單圖的頂點度數(shù)序列的是 。 A. 3 , 2 , 2 , 1 , 1 B. 2 , 2 , 2 , 1 , 1 C. 3 , 3 , 3 , 1 , 0 D. 5 , 4 , 4 , 3 , 1 1919. . 若* , G是一個群，則運算“*”一定滿足 。 A. 交換律 B. 消去律 C. 冪等律 D. 分配律 2020. . 設(shè)R是非空集合A上的關(guān)系，則R的對稱閉包 Rs= 。 A. 1 RR B. RIA C. A IR D. 1 RR 2121下列集合運算中 是正確的。 A. B. , 21 C. , D. , 2 22 2下面的二元關(guān)系中， 具有傳遞性。 A. 父子關(guān)系 B. 朋友關(guān)系 C. 集合的包含關(guān)系 D. 實數(shù)的不相等關(guān)系 2323. . 設(shè)Z是整數(shù)集，且設(shè)ZZZf:，對每一個ZZba,，有babaf 2 ,， 元素 0 的原象的 集合為 。 A 00ZZ B 0Z C Z0 D 00ZZ 2424. . 數(shù)的加法在下列集合中 上是封閉的。 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 2525. . 設(shè)無向樹T由 3 個 3 度頂點， 2 個 2 度頂點。 其余頂點都是樹葉， 則T有 片樹葉。 A. 3 B. 4 C. 5 D. 6 2626. . 設(shè)命題P，Q的真值是 0，命題R，S的真值是 1，則下列公式中真值為 1 的是 。 A. PR B. SQ C. SP D. RQ 2727設(shè)0)( 1 xfxM，0)( 2 xfxN，則方程0)()( 21 xfxf的解集是 。 ANM BNM CNM DNM 2 28 8設(shè)R是非空集合A上的關(guān)系，則R的對稱閉包 Rs= 。 A. RIA B. A IR C. 1 RR D. 1 RR 2929. . 數(shù)的加法在下列集合中 上是封閉的。 22 A1 , 0 B1 1， CZbaba , D是奇數(shù)xx 3030. . 給定下列序列，可構(gòu)成無向簡單圖的頂點度數(shù)序列的是 。 A. 3 , 2 , 2 , 1 , 1 B. 2 , 2 , 2 , 1 , 1 C. 3 , 3 , 3 , 1 , 0 D. 5 , 4 , 4 , 3 , 1 3131. . 設(shè)Z是整數(shù)集，且設(shè)ZZZf:，對每一個ZZba,，有babaf 2 ,， 元素 0 的原象的 集合為 。 A 00ZZ B 0Z C Z0 D 00ZZ 3232. . 命題公式PQP為 。 A.重言式 B.可滿足式 C.矛盾式 D.等價式 三、判斷題三、判斷題 1若BA ，則必有BBA。( ) 2一個不是自反的關(guān)系，一定是反自反的。( ) 3. 凡陳述句都是命題。( ) 4有限半群必存在等冪元。( ) 5. 任何非平凡無向圖中的奇數(shù)度頂點的個數(shù)是偶數(shù)。( ) 6 6設(shè)A，B，C，D均為非空的集合，已知BA 且DC ，則一定有DBCA。( ) 7 7一個不是自反的關(guān)系，一定是反自反的。( ) 8 8. . “王蘭和王英是姐妹”是復(fù)合命題。( ) 9 9. . 設(shè) , , L是代數(shù)格，它所誘導(dǎo)的偏序格為 , L，則對任意的Lba,，bba當(dāng)且僅當(dāng) aba。( ) 1010任何非平凡樹T都至少有兩片樹葉。( ) 1 11 1設(shè),A是偏序集，B是A的非空子集，若B有上界，則B必有最小上界。( ) 1 12.2. 在有界分配格中，一個元素若有補元，則補元一定是唯一的。( ) 23 1 13.3. “王蘭和王英是姐妹”是復(fù)合命題。( ) 1 14 4若半群存在左幺元，則左幺元是唯一的。( ) 1515. . 具有兩個或多個元素的格中不存在以自身為補元的元素。( ) 1616. . 兩個無向圖同構(gòu)的充分必要條件是它們的頂點個數(shù)與邊的個數(shù)分別相等。( ) 四四、解答題解答題 1 1(10 分) 設(shè) 10 01 , 10 01 , 10 01 , 10 01 G，G上的二元運算為矩陣的乘法運算，求 (1) * , G的運算表； (2) * , G的所有子群； 2. 2. (14 分) 設(shè)* , G是一個群，定義集合G上的一個關(guān)系R如下： 1 * , , , , axayGaGyxyxR 證明：R是集合G上的一個等價關(guān)系。 3. 3. (12 分)設(shè)f是從格 11 , L到格 22 , L的滿同態(tài)映射，證明：若 11 , L是有界格，則格 22 , L 也是有界格。 4. 4. (10 分) 試用推理規(guī)則證明： QPRRPQSRQP， 5. 5. (10 分) 設(shè)G是連通簡單圖，其中每個頂點的度數(shù)都是偶數(shù)，則對于任一頂點v，圖 vG 的連通 分支數(shù)小于等于v的度數(shù)的一半。 6 6設(shè)DS , 45 是格，其中 45 S是 45 的所有正因數(shù)的集合，D是 45 S上的整除關(guān)系，則 (1) 求每個元素的余元素； (2) DS , 45 是否為有余格，是否為分配格？并說明理由。 24 7洛杉磯地區(qū)有 7 家汽車旅游公司，在一天中每家公司最多參觀下列景點中的三個不同景點，這些景 點是好萊塢、貝弗利山、迪斯尼樂園和通用電影制片廠，同一天中，參觀一個景點的旅游公司不能超 過一個，第一家旅游公司只參觀好萊塢，第二家公司只參觀好萊塢和迪斯尼樂園，第三家公司只參觀 通用電影制片廠，第四家只參觀迪斯尼樂園和通用電影制片廠，第五家只參觀好萊塢和貝弗利山，第 六家只參觀貝弗利山和通用電影制片廠，第七家只參觀迪斯尼樂園和貝弗利山。請問這些游覽可以只 安排在星期一、星期三和星期五嗎？ 8 8設(shè)A、B是命題公式，試用兩種方法分別證明等價式：BABA。 9 9設(shè)R是非空集合A上的二元關(guān)系，若R是自反的，證明： Rt是自反的。 1010. . 設(shè)R為實數(shù)集，：RRR，對任意的RRyx,，令yxyx,，證明：是滿射， 并說明不是單射。 1111. . 證明：任一序集都是格。 1212. . 求帶權(quán) 1，2，3，4，5，6，7，8，9，10 的最優(yōu)二叉樹。 1313. . 設(shè)* , H和* , K都是群* , G的子群，令 KkHhkhHK , *，HhKkhkKH , * 證明* , HK是* , G的子群的充要條件是KHHK 。 1 14 4. . 設(shè)R為實數(shù)集，：RRR，對任意的RRyx,，令yxyx,，證明是滿射，并 說明不是單射。 25 1515設(shè)A、B是命題公式，試用兩種方法分別證明等價式：BABA。 1616. . 證明：三個元素以上的鏈不是有余格。 1717. . 求帶權(quán) 1，2，3，4，5，6，7，8，9，10 的最優(yōu)二叉樹。 1818設(shè)R是非空集合A上的二元關(guān)系，若R是自反的，證明： Rs是自反的。 1919. . 設(shè) , 2InmnmA，其中I是整數(shù)集合，證明： , , A是整環(huán)，其中運算“+”和“ ” 是關(guān)于數(shù)的普通加法和乘法。 2020(10 分)用推理規(guī)則證明：DCBA，F(xiàn)AFED。 2 21 1. . (20 分) 設(shè),*,B是含幺環(huán),且*滿足等冪律,在B上定義運算+,如下: bababa*, baba*, 1 aa 證明:1 , 0 , , , , B是一個布爾代數(shù)，其中 0 和 1 分別是關(guān)于運算和*的幺元。 2222. . (15 分)證明：在5nKn中任意刪去3n條邊后所得到的圖是哈密爾頓圖。 1 2 3 4 5 6 7 1 - 4 - 6 2 - 3 2 - 5 2 - 3 1 3 - 7 - 2 2 4 - 4 1 - 26 2323(5 分) Gladbrook 飼料公司有 7 個谷物箱，要通過谷物管 道將它們連接起來， 以使谷物能從任意一個箱子轉(zhuǎn)移到其它箱 子，為了使建造費用最少，希望建造盡可能少的管道，在兩個 箱子之間建造管道的費用(以 10 萬美元計)由下表給出，其中 “-”表示不能建造管道，應(yīng)該怎樣建造管道才能使費用最少。 2 24 4(15 分)給定群 66 , I，其中5 , 4 , 3 , 2 , 1 , 0 6 I， 6 是 6 I上的模 6 加法運算，試求： (1) 6 I的所有生成元； (2) 6 I的所有子群； (3) 每個子群的所有右陪集。 2525. . (5 分)設(shè)集合cbaA , , ，R是A上的二元關(guān)系，bccabaaaR , , , , , , , ，試求R的關(guān) 系圖與關(guān)系矩陣 R M。 2626. . (5 分)設(shè)集合cbaA , , ，R是A上的二元關(guān)系，bccabaaaR , , , , , , , ，試求R的關(guān) 系圖與關(guān)系矩陣 R M。 2 27 7. . (15 分)給定群 1515 , I，其中41 , , 2 , 1 , 0 15 I， 15 是 15 I上的模 15 加法運算，試求： (1) 15 I的所有生成元； (2) 15 I的所有子群； (3) 每個子群的所有右陪集。 2828(5 分)試用克魯斯卡爾算法求下列表格所確定的權(quán)圖的最小支撐樹。 1 v 2 v 3 v 4 v 5 v 6 v 1 v / 479 1463 2007 695 283 2 v 479 / 966 1567 666 301 3 v 1463 966 / 837 998 1267 5 - 1 - 6 - 2 7 - 27 4 v 2007 1567 837 / 1213 1724 5 v 695 666 998 1213 / 412 6 v 283 301 1267 1724 412 / 2929(15 分)證明：如果G是一個具有奇數(shù)個頂點的偶圖，則G不是哈密爾頓圖。 3030(10 分)用推理規(guī)則證明：BA，CABC 3 31 1(20 分) 設(shè)1 , 0 , , , , B是一個布爾代數(shù)，在B上定義運算*，如下： bababa*，baba 證明: , * , B 是含幺交換環(huán)。 離散數(shù)學(xué)離散數(shù)學(xué)練習(xí)題一答案練習(xí)題一答案 一、單項選擇題（一、單項選擇題（每小題 2 分，共 8 分） 1 15 . 5 . D D C C B B C C C C 6 61010 A A B D CB D C A A 1 11 11 15 5 C C B B C C D D A A 161620 20 C C B D C C B D C C 21212525 C C C C B B D D C C 26263030. . D D C C B B A A D D 3131. . C C 二、填空題二、填空題（每空 1 分，共 11 分） 1 1 n n 2 2 P、Q 的真值同時為 1 3. 3. * a b c a c a b 28 b a b c c b c a 4.4. 奇奇 5.5. 1212 6.6. QP 7.7. 9 9 8 8QP 9 9P ,Q 的真值都為