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

離散數(shù)學總結(jié)離散數(shù)學總結(jié)1離散數(shù)學離散數(shù)學(DiscreteMathematics)離散數(shù)學是以研究離散量的結(jié)構(gòu)和相互間的關系為主要目標，其研究對象一般地是有限個或可數(shù)個元素，因此它充分描述了計算機科學離散性的特點。集合論數(shù)理邏輯圖論代數(shù)結(jié)構(gòu)離散數(shù)學離散數(shù)學(DiscreteMathematics2離散數(shù)學的應用舉例關系型數(shù)據(jù)庫的設計(關系代數(shù))表達式解析(樹)優(yōu)化編譯器的構(gòu)造(閉包)編譯技術、程序設計語言(代數(shù)結(jié)構(gòu))Lisp和Prolog、人工智能、自動推理、機器證明(數(shù)理邏輯)網(wǎng)絡路由算法(圖論)游戲中的人工智能算法(圖論、樹、博弈論)專家系統(tǒng)(集合論、數(shù)理邏輯—知識和推理規(guī)則的計算機表達)軟件工程—團隊開發(fā)—時間和分工的優(yōu)化(圖論—網(wǎng)絡、劃分)(各種)算法的構(gòu)造、正確性的證明和效率的評估(離散數(shù)學的各分支)離散數(shù)學的應用舉例關系型數(shù)據(jù)庫的設計(關系代數(shù))3離散數(shù)學的學習要領概念（正確）

必須掌握好離散數(shù)學中大量的概念判斷（準確）

根據(jù)概念對事物的屬性進行判斷推理（可靠）

根據(jù)多個判斷推出一個新的判斷離散數(shù)學的學習要領概念（正確）

必須掌握好離散數(shù)學中大量的概4數(shù)理邏輯－命題邏輯命題、真值、簡單命題與復合命題、命題符號化。聯(lián)結(jié)詞：┐，∧，∨，→，

。命題公式、求公式的賦值。真值表、公式的成真賦值和成假賦值。公式的類型：重言式、矛盾式、可滿足式。等值式與等值演算。基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。與范式有關的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項、極大項、主析取范式、主合取范式。數(shù)理邏輯－命題邏輯命題、真值、簡單命題與復合命題、命題符號化5求給定公式范式的步驟(1)消去聯(lián)結(jié)詞→、(若存在)。

A→B┐A∨B

AB(┐A∨B)∧(A∨┐B)(2)否定號的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。

┐┐AA

┐(A∧B)┐A∨┐B

┐(A∨B)┐A∧┐B(3)利用分配律：利用∧對∨的分配律求析取范式，

∨對∧的分配律求合取范式。

A∧(B∨C)(A∧B)∨(A∧C)

A∨(B∧C)(A∨B)∧(A∨C)求給定公式范式的步驟(1)消去聯(lián)結(jié)詞→、(若存在)。

A→6求公式A的主析取范式的方法與步驟方法一、等值演算法(1)化歸為析取范式。(2)除去析取范式中所有永假的析取項。(3)將析取式中重復出現(xiàn)的合取項和相同的變元合并。(4)對合取項補入沒有出現(xiàn)的命題變元，即添加如(p∨┐p)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應的極小項（用名稱表示），按角標從小到大順序析取。求公式A的主析取范式的方法與步驟方法一、等值演算法7求公式A的主合取范式的方法與步驟方法一、等值演算法(1)化歸為合取范式。(2)除去合取范式中所有永真的合取項。(3)將合取式中重復出現(xiàn)的析取項和相同的變元合并。(4)對析取項補入沒有出現(xiàn)的命題變元，即添加如(p∧┐p)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應的極大項（用名稱表示），按角標從小到大順序析取。求公式A的主合取范式的方法與步驟方法一、等值演算法8數(shù)理邏輯－命題邏輯推理的形式結(jié)構(gòu)

推理的前提

推理的結(jié)論

推理正確判斷推理是否正確的方法

真值表法

等值演算法

主析取范式法

對于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明

自然推理系統(tǒng)P的定義

自然推理系統(tǒng)P的推理規(guī)則

附加前提證明法

歸謬法數(shù)理邏輯－命題邏輯推理的形式結(jié)構(gòu)

推理的前提

推理的結(jié)論9數(shù)理邏輯－一階邏輯個體詞（個體域、全總個體域），謂詞(特性謂詞)，量詞（全稱量詞、存在量詞）命題符號化：當給定個體域時，在給定個體域內(nèi)將命題符號化。當沒給定個體域時，應在全總個體域內(nèi)符號化。在符號化時，當引入特性謂詞時，注意全稱量詞與蘊含聯(lián)結(jié)詞的搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。

邏輯有效式、矛盾式、可滿足式

閉式的性質(zhì)：在任何解釋下均為命題。

對給定的解釋，會判別公式的真值或不能確定真值。數(shù)理邏輯－一階邏輯個體詞（個體域、全總個體域），謂詞(特性10數(shù)理邏輯－一階邏輯深刻理解重要的等值式，并能熟練地使用它們。熟練地使用置換規(guī)則、換名規(guī)則和代替規(guī)則。準確地求出給定公式的前束范式（形式可以不唯一）。正確地使用UI、UG、EI、EG規(guī)則，特別地要注意它們之間的關系。一定對前束范式才能使用UI、UG、EI、EG規(guī)則，對不是前束范式的公式要使用它們，一定先求出公式的前束范式。記住UI、UG、EI、EG規(guī)則的各自使用條件。在同一推理的證明中，如果既要使用UI規(guī)則，又要使用EI規(guī)則，一定要先使用EI規(guī)則，后使用UI規(guī)則，而且UI規(guī)則使用的個體常項一定是EI規(guī)則中使用過的。對于給定的推理，正確地構(gòu)造出它的證明。數(shù)理邏輯－一階邏輯深刻理解重要的等值式，并能熟練地使用它們。11集合論－集合代數(shù)掌握集合的子集、相等、空集、全集、冪集等概念及其符號化表示。B

A

x(x∈B→x∈A)

B

A

x(xBxA)……掌握集合的交、并、（相對和絕對）補、對稱差、廣義交、廣義并的定義及其性質(zhì)。

A∪B＝{x|x∈A∨x∈B}A－B＝{x|x∈A∧x

B}……掌握基本的集合恒等式（等冪律、交換律、結(jié)合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余補律、雙重否定律、補交轉(zhuǎn)換律）。運用邏輯演算或利用已知的集合恒等式或包含式證明新的等式或包含式

。集合論－集合代數(shù)掌握集合的子集、相等、空集、全集、冪集等概念12集合恒等式的證明方法邏輯演算法 利用邏輯等值式和推理規(guī)則集合演算法 利用集合恒等式和已知結(jié)論集合恒等式的證明方法邏輯演算法13邏輯演算法的格式題目：A＝B證明：

x，

x∈A ……

x∈B 所以A＝B或證A

B∧A

B題目：A

B證明：

x，

x∈A ……

x∈B 所以AB邏輯演算法的格式題目：A＝B題目：AB14集合演算法的格式題目：A＝B證明：A ＝…… ＝B 所以A＝B題目：A

B證明：A …… B 所以A

B集合演算法的格式題目：A＝B題目：AB15集合論－二元關系有序?qū)Α⒌芽柗e、笛卡爾積的性質(zhì)

二元關系，A到B的二元關系，A上的二元關系，關系的定義域和值域，關系的逆，關系的合成，關系的定義域、值域、逆等的主要性質(zhì)

集合A上的二元關系的主要性質(zhì)（自反性，反自反性，對稱性，反對稱性，傳遞性）的定義及判別法，對某些關系證明它們有或沒有中的性質(zhì)。A上二元關系的n次冪的定義及主要性質(zhì)等價關系、等價類、商集、劃分等概念，以及等價關系與劃分之間的對應偏序關系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、下確界等概念集合論－二元關系有序?qū)?、笛卡爾積、笛卡爾積的性質(zhì)

16關系性質(zhì)的特點關系性質(zhì)的特點17關系性質(zhì)的證明通常的證明方法是利用定義證明。R在A上自反 任取x，有 x∈A…………………<x,x>∈RR在A上對稱 任取<x,y>，有 <x,y>∈R……………<y,x>∈R R在A上反對稱 任取<x,y>，有 <x,y>∈R∧<y,x>∈R……………x＝y(tǒng)R在A上傳遞 任取<x,y>,<y,z>，有 <x,y>∈R∧<y,z>∈R……………<x,z>∈R關系性質(zhì)的證明通常的證明方法是利用定義證明。18集合論－函數(shù)掌握函數(shù)、A到B的函數(shù)、集合在函數(shù)下的像、集合在函數(shù)下的完全原像的概念及表示法；當A與B都是有窮集時，會求A到B的函數(shù)的個數(shù)。

掌握A到B的函數(shù)是單射、滿射、和雙射的定義及證明方法。

掌握常函數(shù)、恒等函數(shù)、單調(diào)函數(shù)、特征函數(shù)、自然映射等概念。

掌握復合函數(shù)的主要性質(zhì)和求復合函數(shù)的方法。

掌握反函數(shù)的概念及主要性質(zhì)。集合論－函數(shù)掌握函數(shù)、A到B的函數(shù)、集合在函數(shù)下的像、集合在19單射和滿射的證明方法證明函數(shù)f:A→B是滿射的，基本方法是：

任取y∈B，找到x∈A(x與y相關，可能是一個關于y的表達式)或者證明存在x∈A，使得f(x)＝y(tǒng)。證明函數(shù)f:A→B是單射的，基本方法是： 假設A中存在x1和x2，使得f(x1)＝f(x2)，利用已知條件或者相關的定理最終證明x1＝x2。單射和滿射的證明方法證明函數(shù)f:A→B是滿射的，基本方20集合論－基數(shù)掌握基數(shù)的基本概念掌握可數(shù)集合和不可數(shù)集合的概念，以及相關結(jié)論集合論－基數(shù)掌握基數(shù)的基本概念21圖論－解決實際問題(1)很多離散問題可以用圖模型求解。(2)為了建立一個圖模型，需要決定頂點和邊分別代表什么。(3)在一個圖模型中，邊經(jīng)常代表兩個頂點之間的關系。圖論－解決實際問題(1)很多離散問題可以用圖模型求解。22圖論－基本概念理解與圖的定義有關的諸多概念，以及它們之間的相互關系。深刻理解握手定理及其推論的內(nèi)容，并能熟練地應用它們。深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、二部圖等概念及其它們的性質(zhì)和相互關系，并能熟練地應用這些性質(zhì)和關系。深刻理解通路與回路的定義、相互關系及其分類，掌握通路與回路的各種不同的表示方法。理解無向圖的點連通度、邊連通度等概念及其之間的關系，并能熟練地求出給定的較為簡單的圖的點連通度與邊連通度。理解有向圖連通性的概念及其分類，掌握判斷有向連通圖類型的方法。圖論－基本概念理解與圖的定義有關的諸多概念，以及它們之間的相23歐拉圖和哈密頓圖深刻理解歐拉圖與半歐拉圖的定義及判別定理。會用Fleury算法求出歐拉圖中的歐拉回路。深刻理解哈密頓圖及半哈密頓圖的定義。會用破壞哈密頓圖應滿足的某些必要條件的方法判斷某些圖不是哈密頓圖。會用滿足哈密頓圖的充分條件的方法判斷某些圖是哈密頓圖。嚴格地分清哈密頓圖必要條件和充分條件，千萬不能將必要條件當充分條件，同樣地，也不能將充分