離散數(shù)學(xué)總結(jié)

1、離散數(shù)學(xué)q 離散數(shù)學(xué)離散數(shù)學(xué)(Discrete Mathematics)q 離散數(shù)學(xué)是以離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目為主要目標(biāo)，其標(biāo)，其研究對象一般地是有限個或可數(shù)個元素研究對象一般地是有限個或可數(shù)個元素，因此它充，因此它充分分描述了計算機科學(xué)離散性的特點描述了計算機科學(xué)離散性的特點。集合論集合論數(shù)理邏輯數(shù)理邏輯圖論圖論代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu)離散數(shù)學(xué)的應(yīng)用舉例q 關(guān)系型數(shù)據(jù)庫的設(shè)計關(guān)系型數(shù)據(jù)庫的設(shè)計(關(guān)系代數(shù)關(guān)系代數(shù))q 表達(dá)式解析表達(dá)式解析(樹樹)q 優(yōu)化編譯器的構(gòu)造優(yōu)化編譯器的構(gòu)造(閉包閉包)q 編譯技術(shù)、程序設(shè)計語言編譯技術(shù)、程序設(shè)計語言(代

2、數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu))q Lisp和和Prolog、人工智能、自動推理、機器證明、人工智能、自動推理、機器證明(數(shù)理邏輯數(shù)理邏輯)q 網(wǎng)絡(luò)路由算法網(wǎng)絡(luò)路由算法(圖論圖論)q 游戲中的人工智能算法游戲中的人工智能算法(圖論、樹、博弈論圖論、樹、博弈論)q 專家系統(tǒng)專家系統(tǒng)(集合論、數(shù)理邏輯集合論、數(shù)理邏輯知識和推理規(guī)則的計算機表達(dá)知識和推理規(guī)則的計算機表達(dá))q 軟件工程軟件工程團隊開發(fā)團隊開發(fā)時間和分工的優(yōu)化時間和分工的優(yōu)化(圖論圖論網(wǎng)絡(luò)、劃分網(wǎng)絡(luò)、劃分)q (各種各種)算法的構(gòu)造、正確性的證明和效率的評估算法的構(gòu)造、正確性的證明和效率的評估(離散數(shù)學(xué)的離散數(shù)學(xué)的各分支各分支)離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)q概念

3、概念（正確）（正確）必須掌握好離散數(shù)學(xué)中大量的概念必須掌握好離散數(shù)學(xué)中大量的概念q判斷判斷（準(zhǔn)確）（準(zhǔn)確）根據(jù)概念對事物的屬性進行判斷根據(jù)概念對事物的屬性進行判斷q推理推理（可靠）（可靠）根據(jù)多個判斷推出一個新的判斷根據(jù)多個判斷推出一個新的判斷數(shù)理邏輯命題邏輯q 命題、真值、簡單命題與復(fù)合命題、命題符號化。命題、真值、簡單命題與復(fù)合命題、命題符號化。q 聯(lián)結(jié)詞：聯(lián)結(jié)詞：，。q 命題公式、求公式的賦值。命題公式、求公式的賦值。 q 真值表、公式的成真賦值和成假賦值。真值表、公式的成真賦值和成假賦值。 q 公式的類型：重言式、矛盾式、可滿足式。公式的類型：重言式、矛盾式、可滿足式。q 等值式與等值

4、演算。等值式與等值演算。q 基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德合律、分配律、德摩根律、吸收律、零律、同一律、排中摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊含等值式、等價等值式、假言易位、等價否律、矛盾律、蘊含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。定等值式、歸謬論。q 與范式有關(guān)的概念：簡單合取式、簡單析取式、析取范式、與范式有關(guān)的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項、極大項、主析取范式、主合取范式。合取范式、極小項、極大項、主析取范式、主合取范式。求給定公式范式的步驟

5、求給定公式范式的步驟(1)消去聯(lián)結(jié)詞消去聯(lián)結(jié)詞、(若存在若存在)。AB ABAB (AB)(AB)(2)否定號的消去否定號的消去(利用雙重否定律利用雙重否定律)或內(nèi)移或內(nèi)移(利用德摩根律利用德摩根律)。A A(AB) AB(AB) AB(3)利用分配律：利用利用分配律：利用對對的分配律求析取范式，的分配律求析取范式， 對對的分配律求合取范式。的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)求公式A的主析取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為析取范式?；瘹w為析取范式。 (2)除去析取范式中所有永假的析取項。除去析取范式中所有永假的析取項。(

6、3)將析取式中重復(fù)出現(xiàn)的合取項和相同的變元合并。將析取式中重復(fù)出現(xiàn)的合取項和相同的變元合并。(4)對合取項補入沒有出現(xiàn)的命題變元，即添加如對合取項補入沒有出現(xiàn)的命題變元，即添加如(pp)式，式，然后應(yīng)用分配律展開公式。然后應(yīng)用分配律展開公式。方法二、真值表法方法二、真值表法(1)寫出寫出 A 的真值表。的真值表。(2)找出找出 A 的成真賦值。的成真賦值。(3)求出每個成真賦值對應(yīng)的極小項（用名稱表示），按角標(biāo)求出每個成真賦值對應(yīng)的極小項（用名稱表示），按角標(biāo)從小到大順序析取。從小到大順序析取。求公式A的主合取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為合取范式。化歸為合取

7、范式。 (2)除去合取范式中所有永真的合取項。除去合取范式中所有永真的合取項。(3)將合取式中重復(fù)出現(xiàn)的析取項和相同的變元合并。將合取式中重復(fù)出現(xiàn)的析取項和相同的變元合并。(4)對析取項補入沒有出現(xiàn)的命題變元，即添加如對析取項補入沒有出現(xiàn)的命題變元，即添加如(pp)式，式，然后應(yīng)用分配律展開公式。然后應(yīng)用分配律展開公式。方法二、真值表法方法二、真值表法(1)寫出寫出 A 的真值表。的真值表。(2)找出找出 A 的成假賦值。的成假賦值。(3)求出每個成假賦值對應(yīng)的極大項（用名稱表示），按角標(biāo)求出每個成假賦值對應(yīng)的極大項（用名稱表示），按角標(biāo)從小到大順序析取。從小到大順序析取。數(shù)理邏輯命題邏輯q

8、推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)推理的前提推理的前提推理的結(jié)論推理的結(jié)論推理正確推理正確q 判斷推理是否正確的方法判斷推理是否正確的方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q 對于正確的推理，在自然推理系統(tǒng)對于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明中構(gòu)造證明 自然推理系統(tǒng)自然推理系統(tǒng)P的定義的定義自然推理系統(tǒng)自然推理系統(tǒng)P的推理規(guī)則的推理規(guī)則附加前提證明法附加前提證明法歸謬法歸謬法數(shù)理邏輯 一階邏輯q 個體詞（個體域、全總個體域），謂詞個體詞（個體域、全總個體域），謂詞(特性謂詞特性謂詞)，量詞，量詞（全稱量詞、存在量詞）（全稱量詞、存在量詞）q 命題符號化：命題符號化：

9、v當(dāng)給定個體域時，在給定個體域內(nèi)將命題符號化。當(dāng)給定個體域時，在給定個體域內(nèi)將命題符號化。v當(dāng)沒給定個體域時，應(yīng)在全總個體域內(nèi)符號化。當(dāng)沒給定個體域時，應(yīng)在全總個體域內(nèi)符號化。v在符號化時，當(dāng)引入特性謂詞時，注意全稱量詞與蘊含在符號化時，當(dāng)引入特性謂詞時，注意全稱量詞與蘊含聯(lián)結(jié)詞的搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。聯(lián)結(jié)詞的搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。 q 邏輯有效式、矛盾式、可滿足式邏輯有效式、矛盾式、可滿足式 q 閉式的性質(zhì)：在任何解釋下均為命題。閉式的性質(zhì)：在任何解釋下均為命題。 q 對給定的解釋，會判別公式的真值或不能確定真值。對給定的解釋，會判別公式的真值或不能確定真值。數(shù)理邏輯

10、一階邏輯q 深刻理解重要的等值式，并能熟練地使用它們。深刻理解重要的等值式，并能熟練地使用它們。 q 熟練地使用置換規(guī)則、換名規(guī)則和代替規(guī)則。熟練地使用置換規(guī)則、換名規(guī)則和代替規(guī)則。 q 準(zhǔn)確地求出給定公式的前束范式（形式可以不唯一）。準(zhǔn)確地求出給定公式的前束范式（形式可以不唯一）。 q 正確地使用正確地使用UI、UG、EI、EG規(guī)則，特別地要注意它們之間規(guī)則，特別地要注意它們之間的關(guān)系。的關(guān)系。 v一定對前束范式才能使用一定對前束范式才能使用UI、UG、EI、EG規(guī)則，對不是規(guī)則，對不是前束范式的公式要使用它們，一定先求出公式的前束范式。前束范式的公式要使用它們，一定先求出公式的前束范式。v

11、記住記住UI、UG、EI、EG規(guī)則的各自使用條件。規(guī)則的各自使用條件。v在同一推理的證明中，如果既要使用在同一推理的證明中，如果既要使用UI規(guī)則，又要使用規(guī)則，又要使用EI規(guī)則，規(guī)則，一定要先使用一定要先使用EI規(guī)則，后使用規(guī)則，后使用UI規(guī)則，而且規(guī)則，而且UI規(guī)規(guī)則使用的個體常項一定是則使用的個體常項一定是EI規(guī)則中使用過的。規(guī)則中使用過的。q 對于給定的推理，正確地構(gòu)造出它的證明。對于給定的推理，正確地構(gòu)造出它的證明。集合論集合代數(shù)q 掌握集合的子集、相等、空集、全集、冪集等概念及其符掌握集合的子集、相等、空集、全集、冪集等概念及其符號化表示。號化表示。vB A x (xB xA) vB

12、 A x (x B x A)vq 掌握集合的交、并、（相對和絕對）補、對稱差、廣義交、掌握集合的交、并、（相對和絕對）補、對稱差、廣義交、廣義并的定義及其性質(zhì)。廣義并的定義及其性質(zhì)。 vAB x | xA xB vAB x | xA x B vq 掌握基本的集合恒等式（等冪律、交換律、結(jié)合律、分配掌握基本的集合恒等式（等冪律、交換律、結(jié)合律、分配律、德律、德摩根律、收律、零律、同一律、排中律、矛盾律、摩根律、收律、零律、同一律、排中律、矛盾律、余補律、雙重否定律、補交轉(zhuǎn)換律）。余補律、雙重否定律、補交轉(zhuǎn)換律）。q 運用邏輯演算或利用已知的集合恒等式或包含式證明新的運用邏輯演算或利用已知的集合恒

13、等式或包含式證明新的等式或包含式等式或包含式 。集合恒等式的證明方法q 邏輯演算法邏輯演算法利用利用邏輯等值式邏輯等值式和和推理規(guī)則推理規(guī)則q 集合演算法集合演算法利用利用集合恒等式集合恒等式和和已知結(jié)論已知結(jié)論邏輯演算法的格式題目：題目：AB證明：證明： x， xA xB所以所以 AB或證或證 A B A B 題目：題目：A B證明：證明： x， xA xB所以所以 A B集合演算法的格式題目：題目：AB證明：證明： A B所以所以 AB題目：題目：A B證明：證明：A B所以所以 A B集合論二元關(guān)系q 有序?qū)?、笛卡爾積、笛卡爾積的性質(zhì)有序?qū)?、笛卡爾積、笛卡爾積的性質(zhì) q 二元關(guān)系，二元關(guān)

14、系，A到到B的二元關(guān)系，的二元關(guān)系，A上的二元關(guān)系，關(guān)系的定義上的二元關(guān)系，關(guān)系的定義域和值域，關(guān)系的逆，關(guān)系的合成，關(guān)系的定義域、值域、域和值域，關(guān)系的逆，關(guān)系的合成，關(guān)系的定義域、值域、逆等的主要性質(zhì)逆等的主要性質(zhì) q 集合集合A上的二元關(guān)系的主要性質(zhì)（自反性，反自反性，對稱上的二元關(guān)系的主要性質(zhì)（自反性，反自反性，對稱性，反對稱性，傳遞性）的定義及判別法，對某些關(guān)系證明性，反對稱性，傳遞性）的定義及判別法，對某些關(guān)系證明它們有或沒有中的性質(zhì)。它們有或沒有中的性質(zhì)。q A上二元關(guān)系的上二元關(guān)系的n次冪的定義及主要性質(zhì)次冪的定義及主要性質(zhì) q 等價關(guān)系、等價類、商集、劃分等概念，以及等價關(guān)系

15、與劃等價關(guān)系、等價類、商集、劃分等概念，以及等價關(guān)系與劃分之間的對應(yīng)分之間的對應(yīng) q 偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、下確界等概念小元、上界、下界、上確界、下確界等概念關(guān)系性質(zhì)的特點自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性定義定義xA RxA RR RRR x=yRR集合表達(dá)式集合表達(dá)式IA RRIARR-1RR-1 IAR R R關(guān)系矩陣關(guān)系矩陣主對角線主對角線元素全是元素全是1主對角線主對角線元素全是元素全是0 矩陣是對稱矩矩陣是對稱矩陣陣 若若 rij1，且且 i

16、j，則，則rji0 對對M2中中1所所在位置，在位置，M中相應(yīng)的位中相應(yīng)的位置都是置都是1 關(guān)系圖關(guān)系圖每個頂點每個頂點都有環(huán)都有環(huán)每個頂點每個頂點都沒有環(huán)都沒有環(huán) 如果兩個頂點如果兩個頂點之間有邊，一之間有邊，一定是一對方向定是一對方向相反的邊相反的邊(無單無單邊邊) 如果兩點之間如果兩點之間有邊，一定是有邊，一定是一條有向邊一條有向邊(無雙向邊無雙向邊) 如果頂點如果頂點 xi到到 xj 有邊，有邊，xj 到到 xk 有邊，有邊，則從則從 xi到到 xk 也有邊也有邊 關(guān)系性質(zhì)的證明通常的證明方法是利用定義證明。通常的證明方法是利用定義證明。R 在在 A 上自反上自反任取任取 x，有，有x

17、A RR 在在 A 上對稱上對稱任取任取 ，有，有R RR 在在 A 上反對稱上反對稱任取任取 ，有，有R R xyR 在在 A 上傳遞上傳遞任取任取 , ，有，有R R R集合論函數(shù)q 掌握函數(shù)、掌握函數(shù)、A到到B的函數(shù)、集合在函數(shù)下的像、集合在函的函數(shù)、集合在函數(shù)下的像、集合在函數(shù)下的完全原像的概念及表示法；當(dāng)數(shù)下的完全原像的概念及表示法；當(dāng)A與與B都是有窮集時，都是有窮集時，會求會求A到到B的函數(shù)的個數(shù)。的函數(shù)的個數(shù)。 q 掌握掌握A到到B的函數(shù)是單射、滿射、和雙射的定義及證明方的函數(shù)是單射、滿射、和雙射的定義及證明方法。法。 q 掌握常函數(shù)、恒等函數(shù)、單調(diào)函數(shù)、特征函數(shù)、自然映射掌握常

18、函數(shù)、恒等函數(shù)、單調(diào)函數(shù)、特征函數(shù)、自然映射等概念。等概念。 q 掌握復(fù)合函數(shù)的主要性質(zhì)和求復(fù)合函數(shù)的方法。掌握復(fù)合函數(shù)的主要性質(zhì)和求復(fù)合函數(shù)的方法。 q 掌握反函數(shù)的概念及主要性質(zhì)。掌握反函數(shù)的概念及主要性質(zhì)。單射和滿射的證明方法q 證明函數(shù)證明函數(shù) f : AB是滿射是滿射的，基本方法是：的，基本方法是：任取任取 yB，找到找到 xA ( x 與與 y 相關(guān)，可能是一個關(guān)于相關(guān)，可能是一個關(guān)于 y 的的表達(dá)式表達(dá)式)或者證明或者證明存在存在xA，使得，使得 f (x)y。q 證明函數(shù)證明函數(shù) f : AB是單射是單射的，基本方法是：的，基本方法是：假設(shè)假設(shè) A 中中存在存在 x1 和和 x

19、2，使得，使得 f (x1)f (x2)，利用已知條件，利用已知條件或者相關(guān)的定理最終或者相關(guān)的定理最終證明證明 x1x2。集合論基數(shù)q 掌握基數(shù)的基本概念掌握基數(shù)的基本概念q 掌握可數(shù)集合和不可數(shù)集合的概念，以及相關(guān)結(jié)論掌握可數(shù)集合和不可數(shù)集合的概念，以及相關(guān)結(jié)論圖論解決實際問題(1) 很多離散問題可以用圖模型求解。很多離散問題可以用圖模型求解。(2) 為了建立一個圖模型，需要決定頂點和邊分別代表什么。為了建立一個圖模型，需要決定頂點和邊分別代表什么。(3) 在一個圖模型中，邊經(jīng)常代表兩個頂點之間的關(guān)系。在一個圖模型中，邊經(jīng)常代表兩個頂點之間的關(guān)系。圖論基本概念q 理解與圖的定義有關(guān)的諸多概

20、念，以及它們之間的相互關(guān)理解與圖的定義有關(guān)的諸多概念，以及它們之間的相互關(guān)系。系。q 深刻理解握手定理及其推論的內(nèi)容，并能熟練地應(yīng)用它們。深刻理解握手定理及其推論的內(nèi)容，并能熟練地應(yīng)用它們。q 深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、二部圖等概念及其它們的性質(zhì)和相互關(guān)系，并能熟練地應(yīng)二部圖等概念及其它們的性質(zhì)和相互關(guān)系，并能熟練地應(yīng)用這些性質(zhì)和關(guān)系。用這些性質(zhì)和關(guān)系。q 深刻理解通路與回路的定義、相互關(guān)系及其分類，掌握通深刻理解通路與回路的定義、相互關(guān)系及其分類，掌握通路與回路的各種不同的表示方法。路與回路的各種不同的表示方法。q 理解無向圖的點連通度、邊連通度等概念及其之間的關(guān)系，理解無向圖的點連通度、邊連通度等概念及其之間的關(guān)系，并能熟練地求出給定的較為簡單的圖的點連通度與邊連通并能熟練地求出給定的較為簡單的圖的點連通度與邊連通度。度。q 理解有向圖連通性的概念及其分類，掌握判斷有向連通圖理解有向圖連通性的概念及其分類，掌握判斷