《離散數(shù)學(xué)總結(jié)》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)總結(jié)（25頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、離 散 數(shù) 學(xué),總結(jié),離散數(shù)學(xué),離散數(shù)學(xué)(Discrete Mathematics) 離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般地是有限個(gè)或可數(shù)個(gè)元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。,離散數(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、人工智能、自動(dòng)推理、機(jī)器證明(數(shù)理邏輯) 網(wǎng)絡(luò)路由算法(圖論) 游戲中的人工智能算法(圖論、樹、博弈論) 專家系統(tǒng)(集合論、數(shù)理邏輯知識(shí)和推理規(guī)則的計(jì)算機(jī)表達(dá)) 軟件工程團(tuán)隊(duì)開發(fā)時(shí)間和分工的優(yōu)化(圖論網(wǎng)絡(luò)、劃分) (各種)算

2、法的構(gòu)造、正確性的證明和效率的評(píng)估(離散數(shù)學(xué)的各分支),離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng),概念（正確）必須掌握好離散數(shù)學(xué)中大量的概念 判斷（準(zhǔn)確）根據(jù)概念對(duì)事物的屬性進(jìn)行判斷 推理（可靠）根據(jù)多個(gè)判斷推出一個(gè)新的判斷,數(shù)理邏輯命題邏輯,命題、真值、簡單命題與復(fù)合命題、命題符號(hào)化。 聯(lián)結(jié)詞：，，，，。 命題公式、求公式的賦值。 真值表、公式的成真賦值和成假賦值。 公式的類型：重言式、矛盾式、可滿足式。 等值式與等值演算。 基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊(yùn)含等值式、等價(jià)等值式、假言易位、等價(jià)否定等值式、歸謬論。 與范式有關(guān)的概念

3、：簡單合取式、簡單析取式、析取范式、合取范式、極小項(xiàng)、極大項(xiàng)、主析取范式、主合取范式。,求給定公式范式的步驟,(1)消去聯(lián)結(jié)詞、(若存在)。AB ABAB (AB)(AB) (2)否定號(hào)的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。A A(AB) AB(AB) AB (3)利用分配律：利用對(duì)的分配律求析取范式， 對(duì)的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC),求公式A的主析取范式的方法與步驟,方法一、等值演算法 (1)化歸為析取范式。 (2)除去析取范式中所有永假的析取項(xiàng)。 (3)將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變元合并。 (4)對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變

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

5、析取。,數(shù)理邏輯命題邏輯,推理的形式結(jié)構(gòu)推理的前提推理的結(jié)論推理正確 判斷推理是否正確的方法真值表法等值演算法主析取范式法 對(duì)于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明 自然推理系統(tǒng)P的定義自然推理系統(tǒng)P的推理規(guī)則附加前提證明法歸謬法,數(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ì)給定的

6、解釋，會(huì)判別公式的真值或不能確定真值。,數(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ī)則的各自使用條件。 在同一推理的證明中，如果既要使用UI規(guī)則，又要使用EI規(guī)則，一定要先使用EI規(guī)則，后使用UI規(guī)則，而且UI規(guī)則使用的個(gè)體常項(xiàng)一定是EI規(guī)則中使用過的。 對(duì)于給定的推理，正確地構(gòu)造出

7、它的證明。,集合論集合代數(shù),掌握集合的子集、相等、空集、全集、冪集等概念及其符號(hào)化表示。 B A x (xB xA) B A x (xB xA) 掌握集合的交、并、（相對(duì)和絕對(duì)）補(bǔ)、對(duì)稱差、廣義交、廣義并的定義及其性質(zhì)。 AB x | xA xB AB x | xA x B 掌握基本的集合恒等式（等冪律、交換律、結(jié)合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余補(bǔ)律、雙重否定律、補(bǔ)交轉(zhuǎn)換律）。 運(yùn)用邏輯演算或利用已知的集合恒等式或包含式證明新的等式或包含式。,集合恒等式的證明方法,邏輯演算法 利用邏輯等值式和推理規(guī)則 集合演算法 利用集合恒等式和已知結(jié)論,邏輯演算法的格式,題目

8、：AB 證明： x， xA xB 所以 AB 或證 AB AB,題目：AB 證明： x， xA xB 所以 AB,集合演算法的格式,題目：AB 證明： A B 所以 AB,題目：AB 證明：A B 所以 AB,集合論二元關(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)系證明它們有或沒有中的性質(zhì)。 A上二元關(guān)系的n次冪的定義及主要性質(zhì) 等價(jià)關(guān)系、等價(jià)類、商集、劃分

9、等概念，以及等價(jià)關(guān)系與劃分之間的對(duì)應(yīng) 偏序關(guān)系、偏序集、哈斯圖、最大元、最小元、極大元、極小元、上界、下界、上確界、下確界等概念,關(guān)系性質(zhì)的特點(diǎn),關(guān)系性質(zhì)的證明,通常的證明方法是利用定義證明。 R 在 A 上自反 任取 x，有 xA R R 在 A 上對(duì)稱 任取 ，有 R R R 在 A 上反對(duì)稱 任取 ，有 R R xy R 在 A 上傳遞 任取 , ，有 R R R,集合論函數(shù),掌握函數(shù)、A到B的函數(shù)、集合在函數(shù)下的像、集合在函數(shù)下的完全原像的概念及表示法；當(dāng)A與B都是有窮集時(shí)，會(huì)求A到B的函數(shù)的個(gè)數(shù)。 掌握A到B的函數(shù)是單射、滿射、和雙射的定義及證明方法。 掌握常函數(shù)、恒等函數(shù)、

10、單調(diào)函數(shù)、特征函數(shù)、自然映射等概念。 掌握復(fù)合函數(shù)的主要性質(zhì)和求復(fù)合函數(shù)的方法。 掌握反函數(shù)的概念及主要性質(zhì)。,單射和滿射的證明方法,證明函數(shù) f : AB是滿射的，基本方法是： 任取 yB，找到 xA ( x 與 y 相關(guān)，可能是一個(gè)關(guān)于 y 的表達(dá)式)或者證明存在xA，使得 f (x)y。 證明函數(shù) f : AB是單射的，基本方法是： 假設(shè) A 中存在 x1 和 x2，使得 f (x1)f (x2)，利用已知條件或者相關(guān)的定理最終證明 x1x2。,集合論基數(shù),掌握基數(shù)的基本概念 掌握可數(shù)集合和不可數(shù)集合的概念，以及相關(guān)結(jié)論,圖論解決實(shí)際問題,(1) 很多離散問題可以用圖模型求解。 (2)

11、為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。 (3) 在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。,圖論基本概念,理解與圖的定義有關(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)系，并能熟練地求出給定的較為簡單的圖的點(diǎn)連通度與邊連通度。 理解有向圖連通性的概念及其分類，掌握判斷有向連通圖類型的

12、方法。,歐拉圖和哈密頓圖,深刻理解歐拉圖與半歐拉圖的定義及判別定理。 會(huì)用 Fleury 算法求出歐拉圖中的歐拉回路。 深刻理解哈密頓圖及半哈密頓圖的定義。 會(huì)用破壞哈密頓圖應(yīng)滿足的某些必要條件的方法判斷某些圖不是哈密頓圖。 會(huì)用滿足哈密頓圖的充分條件的方法判斷某些圖是哈密頓圖。 嚴(yán)格地分清哈密頓圖必要條件和充分條件，千萬不能將必要條件當(dāng)充分條件，同樣地，也不能將充分條件當(dāng)成必要條件。,圖論樹,樹 連通無回路的無向圖 任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。 mn1。 任何邊均為橋。 在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。 n 階非平凡的無向樹中至少有兩片樹葉。 生成樹： G 的子圖并且是樹 樹枝（n-1）、弦（ m-n+1 ）、余樹（ m-n+1 條邊 ） 無向圖 G 具有生成樹當(dāng)且僅當(dāng) G 連通。,