離散數(shù)學復(fù)習提綱(完整版)

1、離散數(shù)學期末復(fù)習大綱（完整版）（含例題和考試說明）一、命題邏輯復(fù)習知識點1、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊涵、等價），復(fù)合命題2、命題公式與賦值（成真、成假），真值表，公式類型（重言、矛盾、可滿足），公式的基本等值式3、范式：析取范式、合取范式，極大（?。╉?，主析取范式、主合取范式 4、公式類型的判別方法（真值表法、等值演算法、主析取/合取范式法）5、命題邏輯的推理理論本章重點內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、（主）析取范式與（主）合取范式、公式類型的判定、命題邏輯的推理復(fù)習要求1、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。2、理解公式與賦值的概念；掌握求給定公式

2、真值表的方法，用基本等值式化簡其它公式，公式在解釋下的真值。3、了解析取（合?。┓妒降母拍?；理解極大（小）項的概念和主析?。ê先。┓妒降母拍?；掌握用基本等值式或真值表將公式化為主析?。ê先。┓妒降姆椒?。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價方法。5、掌握命題邏輯的推理理論。疑難解析1、公式類型的判定判定公式的類型，包括判定公式是重言的、矛盾的或是可滿足的。具體方法有兩種，一是真值表法，二是等值演算法。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點：一是準確理解掌握定義；另一是巧妙使用基本等值式中的分配律、同一律和互補律（排中

3、律、矛盾律），結(jié)果的前一步適當使用冪等律，使相同的短語（或子句）只保留一個。3、邏輯推理掌握邏輯推理時，要理解并掌握12個（除第10，11）推理規(guī)則和3種證明法（直接證明法、附加前提證明法和歸謬法）。例1.試求下列公式的主析取范式：（1）；（2）（ ）2用真值表判斷下列公式是恒真？恒假？可滿足？（1）（PÙØP）«Q（2）Ø（P®Q）ÙQ（3）（P®Q）Ù（Q®R）®（P®R） 解： （1） 真值表P QØP PÙØP （PÙØP）&#

4、171;Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）為可滿足。 （2） 真值表P QP®Q Ø（P®Q） Ø（P®Q）ÙQ0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）為恒假。 （3） 真值表P Q RP®Q Q®R P®R （P®Q）Ù（Q®R）®（P®R）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0

5、11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1 因此公式（3）為恒真。3QÙ（PQ）蘊涵 P（an: 法1：真值表法2：若QÙ（PQ）為真，則 Q，PQ為真， 所以Q為假，P為假，所以P為真。 法3：若P為假，則P為真，再分二種情況： 若Q為真，則QÙ（PQ）為假 若Q為假，則PQ為假，則QÙ（PQ）為假根據(jù) ，所以 QÙ（PQ）蘊涵 P。）4利用基本等價式證明下列命題公式為恒真公式。（P®Q）Ù（Q®R）®（P®R）（PÚQ）ÙØ

6、（ØPÙ（ØQÚØR）Ú（ØPÙØQ）Ú（ØPÙØR）（1、證明： （P®Q）Ù（Q®R）®（P®R） =（ØPÚQ）Ù（ØQÚR）®（ØPÚR） =Ø（ØPÚQ）Ù（ØQÚR）Ú（ØPÚR）=（PÙØQ）Ú（Q

7、7;ØR）ÚØPÚR =（PÙØQ）ÚØP ）Ú（QÙØR）ÚR）=（1Ù（ØQÚØP ）Ú（QÚR）Ù1）= ØQÚØPÚQÚR =（ØQÚQ） ÚØP ÚR= 1 ÚØP ÚR= 1 （PÚQ）ÙØ（ØPÙ（ØQ&#

8、218;ØR）Ú（ØPÙØQ）Ú（ØPÙØR） =（PÚQ）Ù（PÚ（QÙR）Ú（ØPÙ（ØQÚØR） =（PÚ（QÙ QÙR）Ú（ØPÙ（ØQÚØR） =（PÚ（QÙR）ÚØ（PÚ（QÙR） =1）5用形式演繹法證明：蘊涵證明： （1） 規(guī)則P （2） 規(guī)則

9、Q （1） （3） 規(guī)則P （4） 規(guī)則Q（3） （5） 規(guī)則Q（2）（4） （6）R®S 規(guī)則P （7）P®S 規(guī)則Q（5）（6） )6用形式演繹法證明：（蘊涵A證明：(改()（1）A 規(guī)則D（2）AB 規(guī)則Q（1）（3） 規(guī)則P（4） 規(guī)則Q（2）（3）（5）D 規(guī)則Q（4）（6） 規(guī)則Q（5）（7） 規(guī)則P （8）E 規(guī)則Q（6）（7）（9） 規(guī)則Q（1）（8）7（PQ），QR，R 蘊涵 P（1）QR（2）R（3）Q（4）（PQ）（5）PQ（6）P）8某案涉及甲、乙、丙、丁四個，根據(jù)已有線索，已知：（1） 若甲、乙均未作案，則丙、丁也均未作案；（2） 若丙、丁均未作案

10、，則甲、乙也均未作案；（3） 若甲與乙同時作案，則丙與丁有一人且只有一人作案；（4） 若乙與丙同時作案，則甲與丁同時作案或同未作案。辦案人員由此得出結(jié)論：甲是作案者。這個結(jié)論是否正確？為什么？ 解：對問題中的四個簡單命題用P1，P2，P3，P4分別表示甲，乙，丙，丁作案，則辦案人員的推理如下：前提：1) ØP1ÙØP2®ØP3ÙØP42) ØP3ÙØP4®ØP1ÙØP23) P1ÙP2®(ØP3ÙP4)Ú(

11、P3ÙØP4)4) P3ÙP4®(ØP1ÙØP2)Ú(P1ÙP2)結(jié)論：P1。(ØP1ÙØP2®ØP3ÙØP4) Ù (ØP3ÙØP4®ØP1ÙØP2) Ù ( P1ÙP2®(ØP3ÙP4)Ú(P3ÙØP4) Ù ( P3ÙP4®(ØP1&

12、#217;ØP2)Ú(P1ÙP2) ® P1不是永真式，比如：P1取假，P2取真，P3取假，P4取真時，上式為假所以P1不是前提的有效結(jié)論，所以甲是作案者的結(jié)論是錯誤的)二、 謂詞邏輯復(fù)習知識點 1、謂詞、量詞、個體詞（一階邏輯3要素）、個體域、變元（約束出現(xiàn)與自由出現(xiàn)）2、謂詞公式與解釋，謂詞公式的類型（永真、永假、可滿足）3、謂詞公式的等值式（代換實例、消去量詞、量詞否定和量詞轄域收與擴）和置換規(guī)則（置換規(guī)則、換名規(guī)則和代替規(guī)則）本章重點內(nèi)容：謂詞與量詞、公式與解釋復(fù)習要求1、理解謂詞、量詞、個體詞、個體域、變元的概念；理解用謂詞、量詞、邏輯聯(lián)結(jié)詞描

13、述一個簡單命題；了解命題符號化。2、理解公式與解釋的概念；掌握在有限個體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類型。 疑難解析1、謂詞與量詞理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則（即換名規(guī)則和代替規(guī)則）。2、公式與解釋能將一階邏輯公式表達式中的量詞消除，寫成與之等價的公式，然后將解釋中的數(shù)值代入公式，求出真值。三、 集 合復(fù)習知識點1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補以及對稱差等運算及其運算律（交換律、結(jié)合律、分配律、吸收律、 德摩根律等），文氏（Venn）圖本章

14、重點內(nèi)容：集合的概念、集合的運算性質(zhì)、集合恒等式的證明。復(fù)習要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補、對稱差等基本運算。3、掌握集合運算基本規(guī)律，證明集合等式的方法。 疑難解析1、集合的概念重點對冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明對集合恒等式證明的練習，加深對集合性質(zhì)的理解與掌握。四、 二元關(guān)系復(fù)習知識點1、序偶、迪卡爾積，迪卡爾積的運算。2、關(guān)系表達式、關(guān)系矩陣與關(guān)系圖3、復(fù)合關(guān)系（右復(fù)合）與逆關(guān)系 3、關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性、傳遞性） 4、關(guān)系的

15、閉包（自反閉包、對稱閉包、傳遞閉包）5、等價關(guān)系與等價類6、偏序關(guān)系與哈斯圖、極大/小元、最大/小元7、函數(shù)及其性質(zhì)（單射、滿射、雙射）8、復(fù)合函數(shù)與反函數(shù)本章重點內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價關(guān)系、偏序關(guān)系和映射的概念復(fù)習要求1、了解序偶與迪卡爾積的概念，掌握迪卡爾積的運算。2、理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全域關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運算。3、掌握求復(fù)合關(guān)系與逆關(guān)系的方法。4、理解關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性、傳遞性），掌握其判別方法（定義、圖）。4、掌握求關(guān)系的閉包 （自反閉包、對稱閉包、傳遞閉包）的方法。5、

16、理解等價關(guān)系和偏序關(guān)系的概念，掌握等價類的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小元的求法。6、理解函數(shù)概念：函數(shù)、函數(shù)相等、A到B的函數(shù)、復(fù)合函數(shù)和反函數(shù)。7、理解單射、滿射、雙射等概念，掌握其判別方法。疑難解析1、關(guān)系的概念熟練掌握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示。2、關(guān)系的性質(zhì)及其判定關(guān)系的性質(zhì)既是對關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價關(guān)系、偏序關(guān)系的基礎(chǔ)。對于五種性質(zhì)的判定，可以依據(jù)教材上總結(jié)的規(guī)律。這其中對傳遞性的判定，難度稍大一點，這里要提及兩點：一是不破壞傳遞性定義，可認為具有傳遞性。如空關(guān)系具有傳遞性，同時空關(guān)系具有對稱性與反對稱性，但是不具有自反性。3

17、、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記定理7.10和7.114、偏序關(guān)系及偏序集中特殊元素的確定理解與掌握偏序關(guān)系與偏序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對于確定任一子集的最大（?。┰?，極大（?。┰簿腿菀琢?。這里要注意，最大（?。┰c極大（?。┰荒茉谧蛹瘍?nèi)確定。5、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實數(shù)集的子集上的映射也可以利用直角坐標系表示進行，尤其是對各種初等函數(shù)。五、 圖論復(fù)習知識點1、 圖的基本概念：無向圖與有向圖、頂點與邊的關(guān)聯(lián)關(guān)系、頂點（邊）與頂點（邊）之間鄰接

18、關(guān)系、簡單圖與多重圖、頂點度數(shù)（度）與握手定理、圖的同構(gòu)、完全圖、子（補）圖；2、 通路與回路、簡單通（回）路與初級通（回）路；連通圖與非連通圖、連通分支、強連通圖、單向連通圖與弱連通圖、二部圖；點割集、邊割集、點（邊）連通度；3、 圖的矩陣表示：鄰接矩陣、關(guān)聯(lián)矩陣、可達矩陣；4、 歐拉通（回）路、（半）歐拉圖；哈密爾頓通（回）路、（半）哈密爾頓圖；5、 無向樹、生成樹、帶權(quán)樹、最小生成樹，基本回路、基本回路系統(tǒng)、基本割集、基本割集系統(tǒng)、避圈法（Kruskal算法）；6、 有向樹、樹根、有序樹、二叉樹、前綴碼、最佳前綴碼、霍夫曼（Huffman）算法、帶權(quán)圖的最優(yōu)二分樹、二叉樹的周游；本章重點內(nèi)容： 握手定理、點（邊）割集、特殊圖（歐拉圖與哈密頓圖、無（有）向樹）復(fù)習要求1、理解圖的有關(guān)概念：圖、完全圖、子圖、母圖、生成子圖、圖的同構(gòu)等。2、深刻理解握手定理及其推論的內(nèi)容，并能熟練地應(yīng)用它們。3、理解圖的矩陣表示（關(guān)聯(lián)矩陣、相鄰矩陣）和性質(zhì)以及熟練掌握用有向圖的鄰接矩陣及各次冪求圖中通路與回路數(shù)的方法。4、深刻理解歐拉圖、哈密頓圖的定義及判別定理，對于給定的圖，應(yīng)用各定理準確判斷