離散數(shù)學(xué)總結(jié)ppt課件市公開課獲獎(jiǎng)?wù)n件省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

離散數(shù)學(xué)總結(jié)1/33離散數(shù)學(xué)離散數(shù)學(xué)(DiscreteMathematics)離散數(shù)學(xué)是以研究離散量結(jié)構(gòu)和相互間關(guān)系為主要目標(biāo)，其研究對(duì)象普通地是有限個(gè)或可數(shù)個(gè)元素，所以它充分描述了計(jì)算機(jī)科學(xué)離散性特點(diǎn)。集合論數(shù)理邏輯圖論代數(shù)結(jié)構(gòu)2/33離散數(shù)學(xué)應(yīng)用舉例關(guān)系型數(shù)據(jù)庫設(shè)計(jì)(關(guān)系代數(shù))表示式解析(樹)優(yōu)化編譯器結(jié)構(gòu)(閉包)編譯技術(shù)、程序設(shè)計(jì)語言(代數(shù)結(jié)構(gòu))Lisp和Prolog、人工智能、自動(dòng)推理、機(jī)器證實(shí)(數(shù)理邏輯)網(wǎng)絡(luò)路由算法(圖論)游戲中人工智能算法(圖論、樹、博弈論)教授系統(tǒng)(集合論、數(shù)理邏輯—知識(shí)和推理規(guī)則計(jì)算機(jī)表示)軟件工程—團(tuán)體開發(fā)—時(shí)間和分工優(yōu)化(圖論—網(wǎng)絡(luò)、劃分)(各種)算法結(jié)構(gòu)、正確性證實(shí)和效率評(píng)定(離散數(shù)學(xué)各分支)3/33離散數(shù)學(xué)學(xué)習(xí)要領(lǐng)概念（正確）

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

依據(jù)概念對(duì)事物屬性進(jìn)行判斷推理（可靠）

依據(jù)多個(gè)判斷推出一個(gè)新判斷4/33數(shù)理邏輯－命題邏輯命題、真值、簡單命題與復(fù)合命題、命題符號(hào)化。聯(lián)結(jié)詞：┐，∧，∨，→，

。命題公式、求公式賦值。真值表、公式成真賦值和成假賦值。

公式類型：重言式、矛盾式、可滿足式。等值式與等值演算?；镜戎凳?，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊(yùn)含等值式、等價(jià)等值式、假言易位、等價(jià)否定等值式、歸謬論。與范式相關(guān)概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項(xiàng)、極大項(xiàng)、主析取范式、主合取范式。5/33求給定公式范式步驟(1)消去聯(lián)結(jié)詞→、(若存在)。

A→B┐A∨B

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

┐┐AA

┐(A∧B)┐A∨┐B

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

∨對(duì)∧分配律求合取范式。

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

A∨(B∧C)(A∨B)∧(A∨C)6/33求公式A主析取范式方法與步驟方法一、等值演算法(1)化歸為析取范式。(2)除去析取范式中全部永假析取項(xiàng)。(3)將析取式中重復(fù)出現(xiàn)合取項(xiàng)和相同變?cè)喜ⅰ?4)對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)命題變?cè)?，即添加?p∨┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A真值表。(2)找出A成真賦值。(3)求出每個(gè)成真賦值對(duì)應(yīng)極小項(xiàng)（用名稱表示），按角標(biāo)從小到大次序析取。7/33求公式A主合取范式方法與步驟方法一、等值演算法(1)化歸為合取范式。(2)除去合取范式中全部永真合取項(xiàng)。(3)將合取式中重復(fù)出現(xiàn)析取項(xiàng)和相同變?cè)喜ⅰ?4)對(duì)析取項(xiàng)補(bǔ)入沒有出現(xiàn)命題變?cè)刺砑尤?p∧┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A真值表。(2)找出A成假賦值。(3)求出每個(gè)成假賦值對(duì)應(yīng)極大項(xiàng)（用名稱表示），按角標(biāo)從小到大次序析取。8/33數(shù)理邏輯－命題邏輯推理形式結(jié)構(gòu)

推理前提

推理結(jié)論

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

真值表法

等值演算法

主析取范式法

對(duì)于正確推理，在自然推理系統(tǒng)P中結(jié)構(gòu)證實(shí)

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

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

附加前提證實(shí)法

歸謬法9/33數(shù)理邏輯－一階邏輯個(gè)體詞（個(gè)體域、全總個(gè)體域），謂詞(特征謂詞)，量詞（全稱量詞、存在量詞）命題符號(hào)化：當(dāng)給定個(gè)體域時(shí)，在給定個(gè)體域內(nèi)將命題符號(hào)化。當(dāng)沒給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。在符號(hào)化時(shí)，當(dāng)引入特征謂詞時(shí)，注意全稱量詞與蘊(yùn)含聯(lián)結(jié)詞搭配，存在量詞與合取聯(lián)結(jié)詞搭配。

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

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

對(duì)給定解釋，會(huì)判別公式真值或不能確定真值。10/33數(shù)理邏輯－一階邏輯深刻了解主要等值式，并能熟練地使用它們。熟練地使用置換規(guī)則、換名規(guī)則和代替規(guī)則。準(zhǔn)確地求出給定公式前束范式（形式能夠不唯一）。正確地使用UI、UG、EI、EG規(guī)則，尤其地要注意它們之間關(guān)系。一定對(duì)前束范式才能使用UI、UG、EI、EG規(guī)則，對(duì)不是前束范式公式要使用它們，一定先求出公式前束范式。記住UI、UG、EI、EG規(guī)則各自使用條件。在同一推理證實(shí)中，假如既要使用UI規(guī)則，又要使用EI規(guī)則，一定要先使用EI規(guī)則，后使用UI規(guī)則，而且UI規(guī)則使用個(gè)體常項(xiàng)一定是EI規(guī)則中使用過。對(duì)于給定推理，正確地結(jié)構(gòu)出它證實(shí)。11/33集合論－集合代數(shù)掌握集合子集、相等、空集、全集、冪集等概念及其符號(hào)化表示。B

A

x(x∈B→x∈A)

B

A

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

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

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

。12/33集合恒等式證實(shí)方法邏輯演算法 利用邏輯等值式和推理規(guī)則集合演算法 利用集合恒等式和已知結(jié)論13/33邏輯演算法格式題目：A＝B證實(shí)：

x，

x∈A ……

x∈B 所以A＝B或證A

B∧A

B題目：A

B證實(shí)：

x，

x∈A ……

x∈B 所以AB14/33集合演算法格式題目：A＝B證實(shí)：A ＝…… ＝B 所以A＝B題目：A

B證實(shí)：A …… B 所以A

B15/33集合論－二元關(guān)系有序?qū)?、笛卡爾積、笛卡爾積性質(zhì)

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

集合A上二元關(guān)系主要性質(zhì)（自反性，反自反性，對(duì)稱性，反對(duì)稱性，傳遞性）定義及判別法，對(duì)一些關(guān)系證實(shí)它們有或沒有中性質(zhì)。A上二元關(guān)系n次冪定義及主要性質(zhì)等價(jià)關(guān)系、等價(jià)類、商集、劃分等概念，以及等價(jià)關(guān)系與劃分之間對(duì)應(yīng)偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、下確界等概念16/33關(guān)系性質(zhì)特點(diǎn)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義x∈A→<x,x>∈Rx∈A→<x,x>

R<x,y>∈R→<y,x>∈R<x,y>∈R∧<y,x>∈R→x=y<x,y>∈R∧<y,z>∈R→<x,z>集合表示式IA

RR∩IA＝

R＝R-1R∩R-1

IAR

R

R關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1，且i≠j，則rji＝0對(duì)M2中1所在位置，M中對(duì)應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)假如兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反邊(無單邊)假如兩點(diǎn)之間有邊，一定是一條有向邊(無雙向邊)假如頂點(diǎn)xi到xj有邊，xj到xk有邊，則從xi到xk也有邊17/33關(guān)系性質(zhì)證實(shí)通常證實(shí)方法是利用定義證實(shí)。R在A上自反 任取x，有 x∈A…………………<x,x>∈RR在A上對(duì)稱 任取<x,y>，有 <x,y>∈R……………<y,x>∈R R在A上反對(duì)稱 任取<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>∈R18/33集合論－函數(shù)掌握函數(shù)、A到B函數(shù)、集合在函數(shù)下像、集合在函數(shù)下完全原像概念及表示法；當(dāng)A與B都是有窮集時(shí)，會(huì)求A到B函數(shù)個(gè)數(shù)。

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

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

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

掌握反函數(shù)概念及主要性質(zhì)。19/33單射和滿射證實(shí)方法證實(shí)函數(shù)f:A→B是滿射，基本方法是：

任取y∈B，找到x∈A(x與y相關(guān)，可能是一個(gè)關(guān)于y表示式)或者證實(shí)存在x∈A，使得f(x)＝y(tǒng)。證實(shí)函數(shù)f:A→B是單射，基本方法是： 假設(shè)A中存在x1和x2，使得f(x1)＝f(x2)，利用已知條件或者相關(guān)定理最終證實(shí)x1＝x2。20/33集合論－基數(shù)掌握基數(shù)基本概念掌握可數(shù)集合和不可數(shù)集合概念，以及相關(guān)結(jié)論21/33代數(shù)結(jié)構(gòu)-代數(shù)系統(tǒng)組成代數(shù)系統(tǒng)基本成份 非空集合 集合上若干個(gè)封閉二元和一元運(yùn)算 代數(shù)常數(shù)二元運(yùn)算性質(zhì)和特異元素同類型與同種代數(shù)系統(tǒng)子代數(shù)定義與實(shí)例22/33代數(shù)結(jié)構(gòu)知識(shí)體系半群與群環(huán)與域格與布爾代數(shù)分類∑代數(shù)推廣成份：載體及運(yùn)算公理：運(yùn)算性質(zhì)代數(shù)系統(tǒng)組成代數(shù)系統(tǒng)同態(tài)與同構(gòu)代數(shù)系統(tǒng)間關(guān)系映射子代數(shù)積代數(shù)商代數(shù)等價(jià)關(guān)系笛卡兒積子集新代數(shù)系統(tǒng)同種同類型產(chǎn)生23/33群與半群廣群二元運(yùn)算封閉性結(jié)合律半群單位元獨(dú)異點(diǎn)每個(gè)元素可逆群交換律交換半群交換律交換獨(dú)異點(diǎn)交換律Abel群有限個(gè)元素有限群生成元循環(huán)群實(shí)例n元置換群實(shí)例Klein群24/33代數(shù)結(jié)構(gòu)-環(huán)代數(shù)系統(tǒng)<R,+,·>組成環(huán)條件：<R,+>組成Abel群；<R,·>組成半群；·對(duì)于+滿足分配律。

環(huán)中運(yùn)算性質(zhì)：a0=0a=0；a(-b)=(-a)b=-(ab)；乘法對(duì)加法廣義分配律。

環(huán)R非空子集S組成R子環(huán)條件：任取a,b屬于S,有a-b屬于S；ab屬于S。

環(huán)同態(tài)映射定義、判別法及其實(shí)例。25/33代數(shù)結(jié)構(gòu)-格與布爾代數(shù)偏序集組成格條件：任意二元子集都有最大下界和最小上界。

格實(shí)例：正整數(shù)因子格，冪集格，子群格。格性質(zhì)：對(duì)偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。

格作為代數(shù)系統(tǒng)定義。格L非空子集S組成L子格條件： S對(duì)L兩個(gè)運(yùn)算封閉。

函數(shù)

組成格同態(tài)條件：

(a∧b)＝

(a)∧

(b)

(a∨b)＝

(a)∨

(b)格同態(tài)保序性。26/33代數(shù)結(jié)構(gòu)-格與布爾代數(shù)假如格中一個(gè)運(yùn)算對(duì)另一個(gè)運(yùn)算是可分配，稱這個(gè)格是分配格。

分配格兩種判別法： 不存在與鉆石格或五角格同構(gòu)子格； 對(duì)于任意元素a,b,c,有

a∧b＝a∧c且a∨b＝a∨c

b＝c。

有界格定義及其實(shí)例。

格中元素補(bǔ)元及其性質(zhì)（分配格中補(bǔ)元唯一性）。

有補(bǔ)格定義。27/33代數(shù)結(jié)構(gòu)-格與布爾代數(shù)布爾代數(shù)兩個(gè)等價(jià)定義：有補(bǔ)分配格；有兩個(gè)二元運(yùn)算并滿足交換律、分配律、同一律和補(bǔ)元律代數(shù)系統(tǒng)。

布爾代數(shù)特殊性質(zhì)：雙重否定律和德摩根律。子布爾代數(shù)定義及其判別。

布爾代數(shù)同態(tài)判定：f(a∧b)＝f(a)∩f(b)(或f(a∨b)＝f(a)∪f(b)),f(a

)＝-f(a)

對(duì)于任意自然數(shù)n，只有一個(gè)2n元有限布爾代數(shù)，就是冪集代數(shù)。28/33圖論－處理實(shí)際問題(1)很多離散問題能夠用圖模型求解。(2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。(3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間關(guān)系。29/33圖論－基本概念了解與圖定義相關(guān)很多概念，以及它們之間相互關(guān)系。深刻了解握手定理及其推論內(nèi)容，并能熟練地應(yīng)用它們。深刻了解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖等概念及其它們性質(zhì)和相互關(guān)系，并能熟練地應(yīng)用這些性質(zhì)和關(guān)系。深刻了解通路與回路定義、相互關(guān)系及其分類，掌握通路與回路各種不一樣表示方法。了解無向圖點(diǎn)連通度、邊連通度等概念及其之間關(guān)系