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

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

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

3、必需掌握好離散數(shù)學(xué)中大量的概念必需掌握好離散數(shù)學(xué)中大量的概念q判別準(zhǔn)確判別準(zhǔn)確根據(jù)概念對(duì)事物的屬性進(jìn)展判別根據(jù)概念對(duì)事物的屬性進(jìn)展判別q推理可靠推理可靠根據(jù)多個(gè)判別推出一個(gè)新的判別根據(jù)多個(gè)判別推出一個(gè)新的判別4數(shù)理邏輯命題邏輯q命題、真值、簡(jiǎn)單命題與復(fù)合命題、命題符號(hào)化。命題、真值、簡(jiǎn)單命題與復(fù)合命題、命題符號(hào)化。q結(jié)合詞：結(jié)合詞：，。q命題公式、求公式的賦值。命題公式、求公式的賦值。 q真值表、公式的成真賦值和成假賦值。真值表、公式的成真賦值和成假賦值。 q公式的類型：重言式、矛盾式、可滿足式。公式的類型：重言式、矛盾式、可滿足式。q等值式與等值演算。等值式與等值演算。q根本的等值式，其中含

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

5、(假設(shè)存在假設(shè)存在)。AB ABAB (AB)(AB)(2)否認(rèn)號(hào)的消去否認(rèn)號(hào)的消去(利用雙重否認(rèn)律利用雙重否認(rèn)律)或內(nèi)移或內(nèi)移(利用德摩根律利用德摩根律)。A A(AB) AB(AB) AB(3)利用分配律：利用利用分配律：利用對(duì)對(duì)的分配律求析取范式，的分配律求析取范式， 對(duì)對(duì)的分配律求合取范式。的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)6求公式A的主析取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為析取范式?；瘹w為析取范式。 (2)除去析取范式中一切永假的析取項(xiàng)。除去析取范式中一切永假的析取項(xiàng)。(3)將析取式中反復(fù)出現(xiàn)的合取項(xiàng)和一樣的變?cè)?/p>

6、合并。將析取式中反復(fù)出現(xiàn)的合取項(xiàng)和一樣的變?cè)喜ⅰ?4)對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)刺砑尤鐚?duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加?pp)式，然后運(yùn)用分配律展開公式。式，然后運(yùn)用分配律展開公式。方法二、真值表法方法二、真值表法(1)寫出寫出 A 的真值表。的真值表。(2)找出找出 A 的成真賦值。的成真賦值。(3)求出每個(gè)成真賦值對(duì)應(yīng)的極小項(xiàng)用稱號(hào)表示，按角標(biāo)從小到大順序析取。求出每個(gè)成真賦值對(duì)應(yīng)的極小項(xiàng)用稱號(hào)表示，按角標(biāo)從小到大順序析取。7求公式A的主合取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為合取范式?；瘹w為合取范式。 (2)除去合取范式中一切永真的合取項(xiàng)。除

7、去合取范式中一切永真的合取項(xiàng)。(3)將合取式中反復(fù)出現(xiàn)的析取項(xiàng)和一樣的變?cè)喜?。將合取式中反?fù)出現(xiàn)的析取項(xiàng)和一樣的變?cè)喜ⅰ?4)對(duì)析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加如?duì)析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加?pp)式，然后運(yùn)用分配律展開公式。式，然后運(yùn)用分配律展開公式。方法二、真值表法方法二、真值表法(1)寫出寫出 A 的真值表。的真值表。(2)找出找出 A 的成假賦值。的成假賦值。(3)求出每個(gè)成假賦值對(duì)應(yīng)的極大項(xiàng)用稱號(hào)表示，按角標(biāo)從小到大順序析取。求出每個(gè)成假賦值對(duì)應(yīng)的極大項(xiàng)用稱號(hào)表示，按角標(biāo)從小到大順序析取。8數(shù)理邏輯命題邏輯q推理的方式構(gòu)造推理的方式構(gòu)造推理的前提推理的前提推理的結(jié)

8、論推理的結(jié)論 推理正確推理正確q判別推理能否正確的方法判別推理能否正確的方法真值表法真值表法等值演算法等值演算法 主析取范式法主析取范式法 q對(duì)于正確的推理，在自然推理系統(tǒng)對(duì)于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明中構(gòu)造證明 自然推理系統(tǒng)自然推理系統(tǒng)P的定義的定義自然推理系統(tǒng)自然推理系統(tǒng)P的推理規(guī)那么的推理規(guī)那么 附加前提證明法附加前提證明法歸謬法歸謬法9數(shù)理邏輯 一階邏輯q個(gè)體詞個(gè)體域、全總個(gè)體域，謂詞個(gè)體詞個(gè)體域、全總個(gè)體域，謂詞(特性謂詞特性謂詞)，量詞全稱量詞、存在量詞，量詞全稱量詞、存在量詞q命題符號(hào)化：命題符號(hào)化：q當(dāng)給定個(gè)體域時(shí)，在給定個(gè)體域內(nèi)將命題符號(hào)化。當(dāng)給定個(gè)體域時(shí)，在給定

9、個(gè)體域內(nèi)將命題符號(hào)化。q當(dāng)沒給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。當(dāng)沒給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。q在符號(hào)化時(shí)，當(dāng)引入特性謂詞時(shí)，留意全稱量詞與蘊(yùn)含結(jié)合詞的搭配，存在量詞與合取在符號(hào)化時(shí)，當(dāng)引入特性謂詞時(shí)，留意全稱量詞與蘊(yùn)含結(jié)合詞的搭配，存在量詞與合取結(jié)合詞的搭配。結(jié)合詞的搭配。 q邏輯有效式、矛盾式、可滿足式邏輯有效式、矛盾式、可滿足式 q閉式的性質(zhì)：在任何解釋下均為命題。閉式的性質(zhì)：在任何解釋下均為命題。 q對(duì)給定的解釋，會(huì)判別公式的真值或不能確定真值。對(duì)給定的解釋，會(huì)判別公式的真值或不能確定真值。10數(shù)理邏輯一階邏輯q深化了解重要的等值式，并能熟練地運(yùn)用它們。深化了解重要的等值

10、式，并能熟練地運(yùn)用它們。 q熟練地運(yùn)用置換規(guī)那么、換名規(guī)那么和替代規(guī)那么。熟練地運(yùn)用置換規(guī)那么、換名規(guī)那么和替代規(guī)那么。 q準(zhǔn)確地求出給定公式的前束范式方式可以不獨(dú)一。準(zhǔn)確地求出給定公式的前束范式方式可以不獨(dú)一。 q正確地運(yùn)用正確地運(yùn)用UI、UG、EI、EG規(guī)那么，特別地要留意它們之間的關(guān)系。規(guī)那么，特別地要留意它們之間的關(guān)系。 q一定對(duì)前束范式才干運(yùn)用一定對(duì)前束范式才干運(yùn)用UI、UG、EI、EG規(guī)那么，對(duì)不是前束范式的公式要運(yùn)用它們，規(guī)那么，對(duì)不是前束范式的公式要運(yùn)用它們，一定先求出公式的前束范式。一定先求出公式的前束范式。q記住記住UI、UG、EI、EG規(guī)那么的各自運(yùn)用條件。規(guī)那么的各自運(yùn)

11、用條件。q在同一推理的證明中，假設(shè)既要運(yùn)用在同一推理的證明中，假設(shè)既要運(yùn)用UI規(guī)那么，又要運(yùn)用規(guī)那么，又要運(yùn)用EI規(guī)那么，一定要先運(yùn)用規(guī)那么，一定要先運(yùn)用EI規(guī)那規(guī)那么，后運(yùn)用么，后運(yùn)用UI規(guī)那么，而且規(guī)那么，而且UI規(guī)那么運(yùn)用的個(gè)體常項(xiàng)一定是規(guī)那么運(yùn)用的個(gè)體常項(xiàng)一定是EI規(guī)那么中運(yùn)用過的。規(guī)那么中運(yùn)用過的。q對(duì)于給定的推理，正確地構(gòu)造出它的證明。對(duì)于給定的推理，正確地構(gòu)造出它的證明。11集合論集合代數(shù)q掌握集合的子集、相等、空集、選集、冪集等概念及其符號(hào)化表示。掌握集合的子集、相等、空集、選集、冪集等概念及其符號(hào)化表示。qB A x (xB xA) qB A x (xB xA)qq掌握集合的

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

13、方法q邏輯演算法邏輯演算法q利用邏輯等值式和推理規(guī)那么利用邏輯等值式和推理規(guī)那么q集合演算法集合演算法q利用集合恒等式和知結(jié)論利用集合恒等式和知結(jié)論13邏輯演算法的格式標(biāo)題：標(biāo)題：AB證明：證明： x， xA xB所以所以 AB或證或證 AB AB 標(biāo)題：標(biāo)題：AB證明：證明： x， xA xB所以所以 AB14集合演算法的格式標(biāo)題：標(biāo)題：AB證明：證明： A B所以所以 AB標(biāo)題：標(biāo)題：AB證明：證明：A B所以所以 AB15集合論二元關(guān)系q有序?qū)?、笛卡爾積、笛卡爾積的性質(zhì)有序?qū)?、笛卡爾積、笛卡爾積的性質(zhì) q二元關(guān)系，二元關(guān)系，A到到B的二元關(guān)系，的二元關(guān)系，A上的二元關(guān)系，關(guān)系的定義域和值

14、域，關(guān)系的逆，關(guān)系的上的二元關(guān)系，關(guān)系的定義域和值域，關(guān)系的逆，關(guān)系的合成，關(guān)系的定義域、值域、逆等的主要性質(zhì)合成，關(guān)系的定義域、值域、逆等的主要性質(zhì) q集合集合A上的二元關(guān)系的主要性質(zhì)自反性，反自反性，對(duì)稱性，反對(duì)稱性，傳送性的定上的二元關(guān)系的主要性質(zhì)自反性，反自反性，對(duì)稱性，反對(duì)稱性，傳送性的定義及判別法，對(duì)某些關(guān)系證明它們有或沒有中的性質(zhì)。義及判別法，對(duì)某些關(guān)系證明它們有或沒有中的性質(zhì)。qA上二元關(guān)系的上二元關(guān)系的n次冪的定義及主要性質(zhì)次冪的定義及主要性質(zhì) q等價(jià)關(guān)系、等價(jià)類、商集、劃分等概念，以及等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)等價(jià)關(guān)系、等價(jià)類、商集、劃分等概念，以及等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)

15、q偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、下確界等概念下確界等概念16關(guān)系性質(zhì)的特點(diǎn)自反性自反性反自反性反自反性對(duì)稱性對(duì)稱性反對(duì)稱性反對(duì)稱性傳遞性傳遞性定義定義xA RxA RR RRR x=yRR集合表達(dá)式集合表達(dá)式IA RRIARR-1RR-1 IAR R R關(guān)系矩陣關(guān)系矩陣主對(duì)角線元主對(duì)角線元素全是素全是1主對(duì)角線元主對(duì)角線元素全是素全是0 矩陣是對(duì)稱矩陣矩陣是對(duì)稱矩陣 若若 rij1，且，且 ij，則則rji0 對(duì)對(duì)M2中中1所在所在位置，位置，M中相中相應(yīng)的位置都是應(yīng)的

16、位置都是1 關(guān)系圖關(guān)系圖每個(gè)頂點(diǎn)都每個(gè)頂點(diǎn)都有環(huán)有環(huán)每個(gè)頂點(diǎn)都每個(gè)頂點(diǎn)都沒有環(huán)沒有環(huán) 如果兩個(gè)頂點(diǎn)之如果兩個(gè)頂點(diǎn)之間有邊，一定是間有邊，一定是一對(duì)方向相反的一對(duì)方向相反的邊邊(無單邊無單邊) 如果兩點(diǎn)之間如果兩點(diǎn)之間有邊，一定是有邊，一定是一條有向邊一條有向邊(無無雙向邊雙向邊) 如果頂點(diǎn)如果頂點(diǎn) xi到到 xj 有邊，有邊，xj 到到 xk 有邊，則從有邊，則從 xi到到 xk 也有邊也有邊 17關(guān)系性質(zhì)的證明通常的證明方法是利用定義證明。通常的證明方法是利用定義證明。R 在在 A 上自反上自反任取任取 x，有，有xA RR 在在 A 上對(duì)稱上對(duì)稱任取任取 ，有，有R RR 在在 A 上反對(duì)

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

18、主要性質(zhì)和求復(fù)合函數(shù)的方法。掌握復(fù)合函數(shù)的主要性質(zhì)和求復(fù)合函數(shù)的方法。 q掌握反函數(shù)的概念及主要性質(zhì)。掌握反函數(shù)的概念及主要性質(zhì)。19單射和滿射的證明方法q證明函數(shù)證明函數(shù) f : AB是滿射的，根本方法是：是滿射的，根本方法是：q任取任取 yB，找到，找到 xA ( x 與與 y 相關(guān)，能夠是一個(gè)關(guān)于相關(guān)，能夠是一個(gè)關(guān)于 y 的表達(dá)式的表達(dá)式)或者證明存在或者證明存在xA，使得，使得 f (x)y。q證明函數(shù)證明函數(shù) f : AB是單射的，根本方法是：是單射的，根本方法是：q假設(shè)假設(shè) A 中存在中存在 x1 和和 x2，使得，使得 f (x1)f (x2)，利用知條件或者相關(guān)的定理最終證，利

19、用知條件或者相關(guān)的定理最終證明明 x1x2。20集合論基數(shù)q掌握基數(shù)的根本概念掌握基數(shù)的根本概念q掌握可數(shù)集合和不可數(shù)集合的概念，以及相關(guān)結(jié)論掌握可數(shù)集合和不可數(shù)集合的概念，以及相關(guān)結(jié)論21圖論處理實(shí)踐問題(1) 很多離散問題可以用圖模型求解。很多離散問題可以用圖模型求解。(2) 為了建立一個(gè)圖模型，需求決議頂點(diǎn)和邊分別代表什么。為了建立一個(gè)圖模型，需求決議頂點(diǎn)和邊分別代表什么。(3) 在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。22圖論根本概念q了解與圖的定義有關(guān)的諸多概念，以及它們之間的相互關(guān)系。了解與圖的定義有關(guān)的諸多概念，以及它們之間的相

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