2022年《離散數(shù)學(第三版)》方世昌的期末復習知識點總結(jié)

1、精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考離散數(shù)學期末復習提要離散數(shù)學是中心電大“數(shù)學與數(shù)學應(yīng)用專業(yè)”（本科）的一門選修課；該課程使用新的教學大綱，在原有離散數(shù)學課程的基礎(chǔ)上削減了教學內(nèi)容（主要是群與環(huán)、格與布爾代數(shù)這兩章及圖論的后三節(jié)內(nèi)容），使用的教材為中心電大出版的離散數(shù)學（劉敘華等編）和離散數(shù)學學習指導書（虞恩蔚等編） ；離散數(shù)學主要討論離散量結(jié)構(gòu)及相互關(guān)系，使同學得到良好的數(shù)學訓練，提高同學抽象思維和規(guī)律推理才能，為從事運算機的應(yīng)用供應(yīng)必要的描述工具和理論基礎(chǔ)；其先修課 程為：高等數(shù)學、線性代數(shù)；后續(xù)課程為：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、

2、操作系統(tǒng)、運算機網(wǎng)絡(luò)等；課程的主要內(nèi)容1、 集合論部分（集合的基本概念和運算、關(guān)系及其性質(zhì)）；2、 數(shù)理規(guī)律部分（命題規(guī)律、謂詞規(guī)律）；3、 圖論部分（圖的基本概念、樹及其性質(zhì)）；學習建議離散數(shù)學是理論性較強的學科，學習離散數(shù)學的關(guān)鍵是對離散數(shù)學（集合論、數(shù)理規(guī)律和圖論）有關(guān)基本概念的精確把握，對基本原理及基本運算的運用，并要多做練習；教學要求的層次各章教學要求的層次為明白、懂得和把握；明白即能正確判別有關(guān)概念和方法；懂得是能正確表達有關(guān)概念和方法的含義；把握是在懂得的基礎(chǔ)上加以敏捷應(yīng)用；一、各章復習要求與重點第一章集合 復習學問點 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含

3、、相等、冪集2、集合的交、 并、差、補等運算及其運算律（交換律、 結(jié)合律、 安排律、 吸取律、 De Morgan律等），文氏（ Venn）圖3、序偶與迪卡爾積本章重點內(nèi)容：集合的概念、集合的運算性質(zhì)、集合恒等式的證明復習要求 學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 1 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考1、懂得集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念；2、把握集合的表示法和集合的交、并、差、補等基本運算；3、把握集合運

4、算基本規(guī)律，證明集合等式的方法；4、明白序偶與迪卡爾積的概念，把握迪卡爾積的運算； 本章重點習題 P56， 4、6； P1415，3、6、7； P20，5、7； 疑難解析 1、集合的概念由于集合的概念同學在中學階段已經(jīng)學過，這里只多了一個冪集概念，重點對冪集加以把握，一是把握冪集的構(gòu)成，一是把握冪集元數(shù)為2n；2、集合恒等式的證明通過對集合恒等式證明的練習，既可以加深對集合性質(zhì)的懂得與把握；又可以為第三章命題規(guī)律中公式的基本等價式的應(yīng)用打下良好的基礎(chǔ)；實際上，本章做題是一種基本功訓練，特別要求同學重視吸取律和重要等價式在ABA B 證明中的特別作用； 例題分析 例 1 設(shè) A ，B 是兩個集合

5、， A=1 ，2，3 ，B=1 ，2 ，就 A(B) ；解 A,1, 2, 3, 1,2, 1,3, 2,3, 1,2,3B ,1, 2, 1,2于是 A B 3, 1,3, 2,3, 1,2,3例 2設(shè) Aa, b,a, b ,，試求：(1) Aa, b；2 A；3 A；4a,bA ；5A ； 6A ；解1 Aa, ba ,b ,(2) AA3 Aa,b,a, b4a, bA5A6A例 3試證明A B ABAB A B證明學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 2 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - -

6、 - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考A B ABA BA A AA B A BB AB BB A BABAB A B其次章二元關(guān)系 復習學問點 1、關(guān)系、關(guān)系矩陣與關(guān)系圖2、復合關(guān)系與逆關(guān)系3、關(guān)系的性質(zhì)（自反性、對稱性、反對稱性、傳遞性）4、關(guān)系的閉包（自反閉包、對稱閉包、傳遞閉包）5、等價關(guān)系與等價類6、偏序關(guān)系與哈斯圖（Hasse）、極大 /小元、最大 /小元、上 /下界、最小上界、最大下界7、函數(shù)及其性質(zhì)（單射、滿射、雙射）8、復合函數(shù)與反函數(shù)本章重點內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價關(guān)系、半序關(guān)系、映射的概念 復習要求 1、懂得關(guān)系的概念：二元

7、關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系；把握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運算；2、把握求復合關(guān)系與逆關(guān)系的方法；3、懂得關(guān)系的性質(zhì)（自反性、對稱性、反對稱性、傳遞性），把握其判別方法（定義、矩陣、圖）；4、把握求關(guān)系的閉包（自反閉包、對稱閉包、傳遞閉包）的方法；5、懂得等價關(guān)系和偏序關(guān)系的概念，把握等價類的求法和偏序關(guān)系做哈斯圖的方法，極大/ 小元、最大 /小元、上 /下界、最小上界、最大下界的求法；6、懂得函數(shù)概念：函數(shù)、函數(shù)相等、復合函數(shù)和反函數(shù)；7、懂得單射、滿射、雙射等概念，把握其判別方法； 本章重點習題 P25，1； P3233，4， 8， 10； P43，2， 3， 5； P5

8、152， 5，6； P59， 1， 2； P64，學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 3 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考3； P7475， 2， 4，6， 7； P81， 5， 7； P86， 1， 2； 疑難解析 1、關(guān)系的概念關(guān)系的概念是其次章全章的基礎(chǔ)，又是第一章集合概念的應(yīng)用；因此，同學應(yīng)當真正懂得并嫻熟把握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示；2、關(guān)系的性質(zhì)及其判定關(guān)系的性質(zhì)既是對關(guān)系概念的加深懂得與把握，又是關(guān)系的閉包、等

9、價關(guān)系、半序關(guān)系的基礎(chǔ)；對于四種性質(zhì)的判定，可以依據(jù)教材中P49 上總結(jié)的規(guī)律；這其中對傳遞性的判定，難度稍大一點，這里要提及兩點：一是不破壞傳遞性定義，可認為具有傳遞性；如空關(guān)系具有傳遞性，同時空關(guān)系具有對稱性與反對稱性，但是不具有自反性；另一點是介紹一種判定傳遞性的“跟蹤法”，即如a1 , a 2R,a2 , a3R,ai1 , aiR ，就 a1 , aiR ；如如a, bR,b, aR ，就有a , aR ，且b,bR ；、關(guān)系的閉包在懂得把握關(guān)系閉包概念的基礎(chǔ)上，主要把握閉包的求法；關(guān)鍵是熟記三個定理的結(jié)論：定理2，r RRI A ；定理 3，s R1RR；定理 4，推論t RnRi

10、 ；i 1、半序關(guān)系及半序集中特別元素的確定懂得與把握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖；哈斯圖畫法把握了，對于確定任一子集的最大 （小） 元，極大（小） 元也就簡潔了； 這里要留意， 最大（?。?元與極大 （?。?元只能在子集內(nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為全部上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣；、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射；判定的方法除定義外，可借助于關(guān)系圖，而實數(shù)集的子集上的映射也可以利用直角坐標系表示進行，特別是對各種初等函數(shù)； 例題分析 例 1 設(shè)集合 Aa ,b,

11、c ,d，判定以下關(guān)系，哪些是自反的，對稱的，反對稱的和傳遞的：學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 4 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考R1a, a , b, aR2a, a , b,c , d ,aR3c, dR4a, a, , b,b , c,cR5a,c , b, d解：均不是自反的； R4 是對稱的； R1 ,R2 ,R3 , R4 ,R5 是反對稱的； R1 ,R2 ,R 3 , R 4 ,R5 是傳遞的；例 2 設(shè)集合 A1

12、,2,3,4,5， A 上的二元關(guān)系R 為R1,1 ,2,2 ,3,3 ,3,4 ,4,4 ,5,3 ,5,4 ,5,5（）寫出R 的關(guān)系矩陣，畫出R 的關(guān)系圖；（）證明R 是 A 上的半序關(guān)系，畫出其哈斯圖；（） 如 BA，且 B2,3,4,5，求 B 的最大元，最小元，極大元，微小元，最小上界和最大下界；解 （ 1）R 的關(guān)系矩陣為100000100000110R 的關(guān)系圖略0001000111M R（ 2）由于 R 是自反的， 反對稱的和傳遞的，所以 R 是 A 上的半序關(guān)系； A,R 為半序集，A,R 的哈斯圖如下；4。 1。 3。 2。 5(3) 當 B2,3,4,5， B 的極大元

13、為2，4；微小元為2，5； B 無最大元與最小元；B也無上界與下界，更無最小上界與最大下界；第三章命題規(guī)律 復習學問點 、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊涵、等價），復合命題、命題公式與說明，真值表，公式分類（恒真、恒假、可滿意），公式的等價學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 5 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考、析取范式、合取范式，微小（大）項，主析取范式、主合取范式、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）、

14、公式的蘊涵與規(guī)律結(jié)果、形式演繹本章重點內(nèi)容： 命題與聯(lián)結(jié)詞、 公式與說明、 析取范式與合取范式、公式恒真性的判定、形式演繹 復習要求 、懂得命題的概念；明白命題聯(lián)結(jié)詞的概念；懂得用聯(lián)結(jié)詞產(chǎn)生復合命題的方法；、懂得公式與說明的概念；把握求給定公式真值表的方法，用基本等價式化簡其他公式，公式在說明下的真值； 、明白析取（合?。┓妒降母拍?；懂得極大（?。╉椀母拍詈椭魑鋈。ê先。┓妒降母拍睿话盐沼没镜葍r式或真值表將公式化為主析?。ê先。┓妒降姆椒?；、把握利用真值表、等值演算法和主析取/合取范式的唯獨性判別公式類型和公式等價的方法；、懂得公式蘊涵與規(guī)律結(jié)果的概念，把握基本蘊涵式；6、把握形式演繹的證明

15、方法； 本章重點習題 P93，1； P98， 2， 3； P104，2， 3； P107， 1， 3； P112， 5； P115， 1， 2， 3； 疑難解析 1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的；詳細方法有兩種，一是真值表法，對于任給一個公式，主要列出該公式的真值表，觀看真值表的最終一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），如不全為0，就為可滿意的；二是推導法，即利用基本等價式推導出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）當且僅當?shù)葍r于它的合取范式（析取范式）中，每個子句（短語）均至少包含一個原子及其否定；這里

16、要求的析取范式中所含有的每個短語不是微小項，肯定要與求主析取范式相區(qū)分，對于合取范式也同樣；2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式；關(guān)鍵有兩點：一是學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 6 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考精確懂得把握定義；另一是奇妙使用基本等價式中的安排律、同一律和互補律，結(jié)果的前一步適當使用等冪律，使相同的短語（或子句）只保留一個；另外，由已經(jīng)得到的主析?。ê先。┓妒?，依據(jù)GG1,GG 原理，

17、參閱離散數(shù)學學習指導書P71 例 15，可以求得主合?。ㄎ鋈。┓妒?；3、形式演繹法把握形式演繹進行規(guī)律推理時，一是要懂得并把握14 個基本蘊涵式，二是會使用三個規(guī)章：規(guī)章P、規(guī)章 Q 和規(guī)章 D ，需要進行肯定的練習； 例題分析 例 1 求 GPQRP 的主析取范式與主合取范式；解 （ 1）求主析取范式， 方法 1：利用真值表求解PQRPQPQRG000010001001010010011001100011101001110111111111因此GP PQQR RPQRPQRPQRPQR方法 2：推導法學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 7 頁，共 26 頁

18、- - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考GPQ RRPPQRP PRQQPQRPPRQRP QRPPPQQRPQRP PQRPQ PQRPPQRPRQRPQRPQR RPQRPQRQRPQRPQR QR（ 2）求主合取范式方法 1：利用上面的真值表PQRP 為 0 的有兩行， 它們對應(yīng)的極大項分別為PQR,PQR因此，PQRPPQRPQR方法 2：利用已求出的主析取范式求主合取范式已用去 6 個微小項，尚有2 個微小項，即PQR 與PQR于是GPQRGGP PQRPPQRQRPQR QR例 2

19、試證明公式GPQQRPR 為恒真公式；證法一：見離散數(shù)學學習指導書P60 例 6（ 4）的解答；（真值表法）證法二：G=（P Q）（QR）（P R）=（ PQ）（ QR）P R=（ （ P Q） （ PR）（QQ ） （QR）P）R=（ P QP）（ PRP）（QRP）R=（ 1 （QRP）R=QRP R=1故 G 為恒真公式；例 3 利用形式演繹法證明 P（ QR），S P， Q 蘊涵 SR；學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 8 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - -

20、-學習資料收集于網(wǎng)絡(luò)，僅供參考證明：（ 1）SP規(guī)章 P（ 2） S規(guī)章 D（ 3） P規(guī)章 Q，依據(jù)（ 1），（ 2）（ 4） P（ QR）規(guī)章 P（ 5） QR規(guī)章 Q，依據(jù)（ 3），（ 4）（ 6） Q規(guī)章 P（ 7） R規(guī)章 Q ，依據(jù)（ 5），（6）（ 8） SR規(guī)章 D，依據(jù)（ 2），（ 7）第四章謂詞規(guī)律 復習學問點 1、謂詞、量詞、個體詞、個體域、變元（約束變元與自由變元）2、謂詞公式與說明，謂詞公式的類型（恒真、恒假、可滿意）3、謂詞公式的等價和蘊涵4、前束范式本章重點內(nèi)容：謂詞與量詞、公式與說明、前束范式 復習要求 1、懂得謂詞、量詞、個體詞、個體域、變元的概念；懂得用謂詞

21、、量詞、規(guī)律聯(lián)結(jié)詞描述一個簡潔命題；明白命題符號化；2、懂得公式與說明的概念；把握在有限個體域下消去公式量詞，求公式在給定說明下真值的方法；明白謂詞公式的類型；3、懂得用說明的方法證明等價式和蘊涵式；4、把握求公式前束范式的方法； 本章重點習題 P120， 1， 2； P125126，1， 3； P137， 1； 疑難解析 1、謂詞與量詞反復懂得謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)章；學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 9 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - -

22、 - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考2、公式與說明能將一階規(guī)律公式表達式中的量詞排除，寫成與之等價的公式，然后將說明I 中的數(shù)值代入公式，求出真值；3、前束范式在充分懂得把握前束范式概念的基礎(chǔ)上，利用改名規(guī)章、基本等價式與蘊涵式（一階規(guī)律中），將給定公式中量詞提到母式之前稱為首標； 典型例題 例 1 設(shè) I 是如下一個說明：D2,3F2F3P2P3Q2,2Q2,3Q3,2Q3,332011101求xy P xQ F x , y的真值；解xy P xQ F x , yxP xQ F x ,2P xQF x ,3P 2Q F2 ,2P 2QF 2 ,3P 3QF 3 ,

23、2P 3Q F3 ,300010111111例 2 試將一階規(guī)律公式化成前束范式；解GxyP xyPx, yx, yyQ yR xyQ yR xxyPx, yzQ zR xxyz Px, yQ zR x第五章圖論 復習學問點 1、圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)2、關(guān)聯(lián)矩陣、相鄰矩陣3、權(quán)圖、路、最短路徑，迪克斯特拉算法（Dijkstra ）4、樹、支撐樹、二叉樹5、權(quán)圖中的最小樹，克魯斯卡爾算法（Kruskal ）學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 10 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - -

24、 - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考6、有向圖、有向樹本章重點內(nèi)容：權(quán)圖的最短路、二叉樹的遍歷、權(quán)圖中的最優(yōu)支撐樹 復習要求 1、懂得圖的有關(guān)概念：圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)；2、把握圖的矩陣表示（關(guān)聯(lián)矩陣、相鄰矩陣）；3、懂得權(quán)圖、路的概念，把握用Dijkstra 算法求權(quán)圖中最短路的方法；4、懂得樹、二叉樹與支撐樹的有關(guān)概念；把握二叉樹的三種遍歷方法，用Kruskal 算法求權(quán)圖中最小樹的方法；5、懂得有向圖與有向樹的概念； 本章重點習題 P221， 2； P225， 1；P231， 2，3； P239， 5； P242， 1，2； 疑難解析 1

25、.本章的概念較多，學習時需要認真比較各概念的含義，如：圖、子圖、有向圖、權(quán)圖；樹、支撐樹、二叉樹、有向樹；路、簡潔路、回路等，這些都是圖的基本概念，今后將在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、運算機網(wǎng)絡(luò)等課程中用到；2、權(quán)圖中的最短路嚴格執(zhí)行迪克斯特拉（Dijkstra ）算法步驟，從起點起，到每一點求出最短路，然后進行認真比較，最終到達終點，算出最小權(quán)和；3、權(quán)圖中的最優(yōu)支撐樹權(quán)圖中的最優(yōu)支撐樹是圖中所帶權(quán)和最小的支撐樹，使用克魯斯卡爾 （ Kruskal ）算法； 典型例題 例1在具有 n 個頂點的完全圖K n 中刪去多少條邊才能得到樹？解： n 個頂點的完全圖K n 中共有 n （ n-1）/2 條邊，n

26、 個頂點的樹應(yīng)有n-1 條邊，于是，刪去的邊有：n （ n-1） /2-（ n-1） =（ n-1）（ n-2） /2例2求下面有限圖中點u 到各點間的最短路； （圖上數(shù)字見教材P231，第 3 題；）學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 11 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考解uu1 ，du, u 1=1,路u, u1uu2 ,du, u 2=9,路 u, u4, u3, u7, u2uu3 ,du, u3 =5,路 u, u4, u3

27、 ,uu4 ,du, u4 =3,路 u, u4 uu5 ,du, u5 =11,路 u, u1, u5 或路u, u4, u3 , u7 , u2 , u5uu6 ,du, u6 =13,路 u, u1, u5, u6uu7 ,du, u7 =8,路 u, u4 , u3 , u7uu8 ,du, u8 =11,路 u, u4, u8 uv,du, v=15,路u, u1, u5 , u6 ,v或路 u, u4 , u3 , u7 , u6 ,v二、考核說明本課程的考核實行形成性考核和終結(jié)性考核的形式；形成性考核占總成果的20%，以課程作業(yè)的形式進行（共三次， 由中心電大統(tǒng)一布置）的 80%

28、；總成果為100 分， 60 分及格；終結(jié)性考核即期末考試，占總成果期末考試實行全國統(tǒng)一閉卷考核，試卷滿分為100；由中心電大統(tǒng)一命題，統(tǒng)一評分標準，統(tǒng)一考試時間（考試時間為120 分鐘）；1、試題類型試題類型有填空題（分數(shù)約占20%）、單項挑選題（分數(shù)約占14%）、運算題（分數(shù)約占 50%）和證明題（分數(shù)約占16%）；填空題和單項挑選題主要涉及基本概念、基本理論，重要性質(zhì)和結(jié)論、公式及其簡潔運算；運算題主要考核同學的基本運算技能，要求書寫運算、推論過程或理由；證明題主要考查應(yīng)用概念、性質(zhì)、定理及主要結(jié)論進行規(guī)律推理的才能，要求寫出推理過程；2、考核試卷題量安排試卷題量在各部分的安排是：集合論

29、約占40%，數(shù)理規(guī)律約占40%，圖論約占20%；詳細課程考核情形見課程考核說明；附錄：試題類型及規(guī)范解答舉例 填空題 學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 12 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考1. 設(shè) R是集合 A 上的二元關(guān)系，假如關(guān)系R 同時具有性、對稱性和性，就稱 R 是等價關(guān)系；2. 命題公式G=（ P Q）R， 就 G 共有個不同的說明；把G 在其全部說明 下所取真值列成一個表，稱為G 的；說明（P，Q，R）或（ 0， 1，

30、0）使 G 的真值為；3. 設(shè) G=（ P，L ）是圖，假如G 是連通的，并且，就 G 是樹；假如根樹T的每個點 v 最多有兩棵子樹，就稱T 為； 單項挑選題 （挑選一個正確答案的代號，填入括號中）1. 由集合運算定義，以下各式正確的有（）；A XXYB.XXYC.XXYD.YXY2. 設(shè) R1，R2 是集合 A=a ，b，c，d 上的兩個關(guān)系，其中R1= （ a，a），（ b，b），（ b，c），（ d，d） ，R2 =（ a，a），（b，b），（ b，c），（ c，b），（ d，d） ，就 R2 是 R1 的（）閉包；A 自反B對稱C傳遞D以上都不是3. 設(shè) G 是由 5 個頂點組成的完全

31、圖，就從G 中刪去（）條邊可以得到樹；A 4B 5C 6D 10 運算題 1. 化簡下式：（ ABC）（ AB）C）（ AB C）（ABC）2. 通過求主析取范式判定以下命題公式是否等值；（ 1）（ P Q）（P QR）；（ 2）（ P （ Q R）（ Q（P R） ；3. 求圖中 A 到其余各頂點的最短路徑，并寫出它們的權(quán)；B7C12A253D46E1F學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 13 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考 證明題

32、 1. 利用基本等價式證明下面命題公式為恒真公式；（ PQ ）（QR）（ PR）2. 用形式演繹法證明：PQ， RS，PR 蘊涵 QS；試題答案及評分標準 填空題 1、自反；傳遞2、8；真值表； 13、無回路；二叉樹 單項挑選題 （挑選一個正確答案的代號，填入括號中） 1、 A2、 B3、C 運算題 1. 解：（ ABC）（ AB）C）（ AB C）（ABC）=（ ABC）（ ABC）（ ABC ）（ ABC）=（ AB）（ CC）（ AB ）（CC）=（ AB）E）（ AB）E）E 為全集=（ AB）（ AB）=A（ BB）=AE=A2. 解：（P Q）（P QR）（ P Q（RR）（P Q

33、R）（ P QR）（ P QR）（P QR） m6m7m3m3m6m7（P （QR）（ Q（P R）（ P Q）（ Q R）（ PP R）（PQR）（安排律）學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 14 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考（ P Q（RR）（P P）QR） （PQR）（ P QR）（ P QR）（P QR）（P QR）（PQR）m6m7m3m7m3m3m6由此可見m7（PQ） （PQR）（ P （ QR）（ Q（PR）3. 解

34、：A 到 B 的最短路徑為AB ，權(quán)為 1； A 到 E 的最短路徑為ABE ，權(quán)為 3；A 到 F 的最短路徑為ABEF ，權(quán)為 4； A 到 C 的最短路徑為ABEFC ，權(quán)為 7；A 到 D 的最短路徑為ABEFCD ，權(quán)為 9； 證明題 1. 證明：（ PQ）（ QR）（PR）（P Q）（QR）（P R）（P Q）（QR）（P R）（ PQ）（ QR）P R（ PQ）P ）（ QR）R）（ 1（QP ）（ QR）1） QP QR（QQ）PR1PR 12. 證明：（ 1）P R規(guī)章 P（ 2）RP規(guī)章 Q ，依據(jù)（ 1）（ 3）PQ規(guī)章 P（ 4）RQ規(guī)章 Q，依據(jù)（ 2）（3）（ 5）

35、QR規(guī)章 Q，依據(jù)（ 4）（ 6）RS規(guī)章 P學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 15 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考（ 7）QS規(guī)章 Q，依據(jù)（ 5）（ 6）（ 8）QS規(guī)章 Q ，依據(jù)（ 7）三、綜合練習及解答（一）填空題1、集合的表示方法有兩種：法和法；請把“大于3而 小 于 或 等 于7的 整 數(shù) 集 合 ” 用 任 一 種 集 合 的 表 示 方 法 表 示 出 來A= ；2、 A ，B 是兩個集合， A=1 ，2，3， 4

36、 ，B=2 ，3，5 ，就 B-A=， （ B）（ A ） =， （ B）的元素個數(shù)為；3、 設(shè) A a ,b,B1,2，就從 A 到 B 的全部映射是；4、 設(shè)命題公式GPQR ，就使公式G 為假的說明是、和；5、設(shè) G 是完全二叉樹，G 有 15 個點，其中8 個葉結(jié)點，就G 的總度數(shù)為，分枝點數(shù)為；6、全集 E=1 ， 2， 3，4， 5 ，A=1 ， 5 ， B=1 ， 2， 3， 4 ， C=2 ， 5 ， 求 AB=， （A ）（ C）=，C=；7、設(shè) A 和 B 是任意兩個集合，如序偶的第一個元素是A 的一個元素，其次個元素是B 的一個元素，就全部這樣的序偶集合稱為集合A 和 B

37、 的，記作 AB，即 AB=；AB 的子集 R 稱為 A ， B 上的；8、將幾個命題聯(lián)結(jié)起來，形成一個復合命題的規(guī)律聯(lián)結(jié)詞主要有否定、和等值；9、表達式xyL （ x ， y）中謂詞的定義域是a ， b， c ，將其中的量詞排除，寫成與之等價的命題公式為；10、一個無向圖表示為G= （ P， L ），其中 P 是的集合， L 是學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 16 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考的集合，并且要求；（二）單項挑選題

38、（挑選一個正確答案的代號，填入括號中）1.設(shè)命題公式 GPPQR) P ，就 G 是（）；A. 恒真的B. 恒假的C.可滿意的D. 析取范式2、設(shè)集合A a,b , c， A 上的關(guān)系 R a ,a , a,b , b, c ，就R2 =（）； A a, a , a,b , a,c;C a, b , a,c, b,b ; B a, b, a, c, b, c; D a, a , a, b, c, c .3、一個公式在等價意義下，下面哪個寫法是唯獨的（）；A 析取范式B合取范式C主析取范式D以上答案都不對4、設(shè)命題公式G=（ PQ ）， H=P（ QP），就 G 與 H 的關(guān)系是（）；A GHB

39、 HGCG=HD以上都不是01011100015、已知圖G 的相鄰矩陣為00011，就 G 有（）；1010111110A.5 點， 8 邊B. 6 點， 7 邊C. 5 點， 7 邊D. 6 點， 8 邊6、以下命題正確選項（）；A =B=C aa ， b， cD a ， b， c7、設(shè)集合A=a ，b，c ，A 上的關(guān)系R= （a，b），（ a，c），（ b， a），（b，c），（ c，a），（ c， b），（ c， c） ，就 R 具有關(guān)系的（）性質(zhì)；A 自反B對稱C傳遞D反對稱8、設(shè) R 為實數(shù)集，映射=RR，（x ） = -x 2+2x-1 ，就是（）；A 單射而非滿射B滿射而非單射

40、C雙射D 既不是單射，也不是滿射 9、以下語句中， （）是命題；A 下午有會嗎？B 這朵花多好看呀！C 2 是常數(shù)；D 請把門關(guān)上； 10、下面給出的一階規(guī)律等價式中，（）是錯的；A x（A （x ）B（ x） =xA （x ）xB （ x） B AxB （ x ）=x （ AB（ x ）學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 17 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考Cx （ A （ x ）B（ x） = xA （x）xB （ x ） DxA

41、 （ x ） = x （A（ x）（三）運算題1、設(shè) R 和 S 是集合 A1,2,3,4R上的關(guān)系，其中S 1,1, 1,3, 2,3, 3,4 1,2, 2,3, 2,4, 4,4，試求：（ 1）寫出 R 和 S 的關(guān)系矩陣；（ 2）運算R S,RS,R 1 ,S 1R 1 ；2、 設(shè) A=a ，b，c，d ，R1，R2 是 A 上的關(guān)系，其中 R1= （ a，a），（ a，b），（b， a），（ b， b），（ c，c），（ c，d），（d，c），（ d，d） ，R2= （ a，b），（b， a），（ a，c），（ c，a），（ b， c），（ c， b），（ a， a），（b， b），

42、（c， c） ；（ 1）畫出 R1 和 R2 的關(guān)系圖；（ 2）判定它們是否為等價關(guān)系，是等價關(guān)系的求A 中各元素的等價類；3、 用真值表判定以下公式是恒真？恒假？可滿意？（ 1）（ PP）Q（ 2）（ PQ）Q（ 3）（ PQ）（ QR）（PR）4、 設(shè)說明 I 為：（ 1）定義域D=-2 ， 3，6 ；（ 2） F（ x ）： x 3； G（ x ）：x5；在說明 I 下求公式x （ F（ x）G（x ）的真值；5、 求下圖所示權(quán)圖中從u 到 v 的最短路，畫出最短路并運算它們的權(quán)值；學習資料精選名師 優(yōu)秀名師 - - - - - - - - - -第 18 頁，共 26 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -學習資料收集于網(wǎng)絡(luò)，僅供參考V 17V 312U253V46V 21V 46、 化簡下式：（ ABC）（ AB）（ A（ B C）A ）7、 已知 A=1 ， 2， 3， 4，5 ，B=1 ， 2， 3 ， R 是 A 到 B 的二元關(guān)系，并且R= （ x， y）|xA 且 yB 且 2x+y4 ，畫出 R 的關(guān)系圖，并寫出關(guān)系矩陣；8、 畫出下面偏序集（A ， ）的哈斯圖，并指出集合A 的最小元、最大元、極大元和微小 元