資源描述：
《《離散數(shù)學(xué)總結(jié)》PPT課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、離散數(shù)學(xué)總結(jié)離散數(shù)學(xué)離散數(shù)學(xué)(DiscreteMathematics)離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象一般地是有限個或可數(shù)個元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。集合論數(shù)理邏輯圖論代數(shù)結(jié)構(gòu)離散數(shù)學(xué)的應(yīng)用舉例關(guān)系型數(shù)據(jù)庫的設(shè)計(jì)(關(guān)系代數(shù))表達(dá)式解析(樹)優(yōu)化編譯器的構(gòu)造(閉包)編譯技術(shù)、程序設(shè)計(jì)語言(代數(shù)結(jié)構(gòu))Lisp和Prolog、人工智能、自動推理、機(jī)器證明(數(shù)理邏輯)網(wǎng)絡(luò)路由算法(圖論)游戲中的人工智能算法(圖論、樹、博弈論)專家系統(tǒng)(集合論、數(shù)理邏輯—知識和推理規(guī)則的計(jì)算機(jī)表達(dá))軟件工
2、程—團(tuán)隊(duì)開發(fā)—時間和分工的優(yōu)化(圖論—網(wǎng)絡(luò)、劃分)(各種)算法的構(gòu)造、正確性的證明和效率的評估(離散數(shù)學(xué)的各分支)離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)概念（正確）必須掌握好離散數(shù)學(xué)中大量的概念判斷（準(zhǔn)確）根據(jù)概念對事物的屬性進(jìn)行判斷推理（可靠）根據(jù)多個判斷推出一個新的判斷數(shù)理邏輯－命題邏輯命題、真值、簡單命題與復(fù)合命題、命題符號化。聯(lián)結(jié)詞：┐，∧，∨，→，?。命題公式、求公式的賦值。真值表、公式的成真賦值和成假賦值。公式的類型：重言式、矛盾式、可滿足式。等值式與等值演算。基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德·摩根律、
3、吸收律、零律、同一律、排中律、矛盾律、蘊(yùn)含等值式、等價(jià)等值式、假言易位、等價(jià)否定等值式、歸謬論。與范式有關(guān)的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項(xiàng)、極大項(xiàng)、主析取范式、主合取范式。求給定公式范式的步驟(1)消去聯(lián)結(jié)詞→、?(若存在)。A→B?┐A∨B A?B?(┐A∨B)∧(A∨┐B)(2)否定號的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。┐┐A?A ┐(A∧B)?┐A∨┐B ┐(A∨B)?┐A∧┐B(3)利用分配律：利用∧對∨的分配律求析取范式， ∨對∧的分配律求合取范式。A∧(B∨C)?(A∧B)∨(A∧
4、C) A∨(B∧C)?(A∨B)∧(A∨C)求公式A的主析取范式的方法與步驟方法一、等值演算法(1)化歸為析取范式。(2)除去析取范式中所有永假的析取項(xiàng)。(3)將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變元合并。(4)對合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加如(p∨┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應(yīng)的極小項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。求公式A的主合取范式的方法與步驟方法一、等值演算法(1)化歸為合取范式。(2)除去合取范式中所有永真的合取項(xiàng)。
5、(3)將合取式中重復(fù)出現(xiàn)的析取項(xiàng)和相同的變元合并。(4)對析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加如(p∧┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應(yīng)的極大項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。數(shù)理邏輯－命題邏輯推理的形式結(jié)構(gòu)?推理的前提?推理的結(jié)論?推理正確判斷推理是否正確的方法?真值表法?等值演算法?主析取范式法對于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明?自然推理系統(tǒng)P的定義?自然推理系統(tǒng)P的推理規(guī)則?附加前提證明法?歸謬法數(shù)理邏輯－一階邏輯個體詞（
6、個體域、全總個體域），謂詞(特性謂詞)，量詞（全稱量詞、存在量詞）命題符號化：當(dāng)給定個體域時，在給定個體域內(nèi)將命題符號化。當(dāng)沒給定個體域時，應(yīng)在全總個體域內(nèi)符號化。在符號化時，當(dāng)引入特性謂詞時，注意全稱量詞與蘊(yùn)含聯(lián)結(jié)詞的搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。邏輯有效式、矛盾式、可滿足式閉式的性質(zhì)：在任何解釋下均為命題。對給定的解釋，會判別公式的真值或不能確定真值。數(shù)理邏輯－一階邏輯深刻理解重要的等值式，并能熟練地使用它們。熟練地使用置換規(guī)則、換名規(guī)則和代替規(guī)則。準(zhǔn)確地求出給定公式的前束范式（形式可以不唯一）。正確地使用UI、UG、EI
7、、EG規(guī)則，特別地要注意它們之間的關(guān)系。一定對前束范式才能使用UI、UG、EI、EG規(guī)則，對不是前束范式的公式要使用它們，一定先求出公式的前束范式。記住UI、UG、EI、EG規(guī)則的各自使用條件。在同一推理的證明中，如果既要使用UI規(guī)則，又要使用EI規(guī)則，一定要先使用EI規(guī)則，后使用UI規(guī)則，而且UI規(guī)則使用的個體常項(xiàng)一定是EI規(guī)則中使用過的。對于給定的推理，正確地構(gòu)造出它的證明。集合論－集合代數(shù)掌握集合的子集、相等、空集、全集、冪集等概念及其符號化表示。B?A??x(x∈B→x∈A)B?A??x(x?B?x?A)……掌握集合的交、
8、并、（相對和絕對）補(bǔ)、對稱差、廣義交、廣義并的定義及其性質(zhì)。A∪B＝{x
9、x∈A∨x∈B}A－B＝{x
10、x∈A∧x?B}……掌握基本的集合恒等式（等冪律、交換律、結(jié)合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余補(bǔ)律、雙重否定律、補(bǔ)
