離散數(shù)學(xué)復(fù)習(xí)提綱

1、2010-2011-1離散數(shù)學(xué)復(fù)習(xí)提綱第一部分 數(shù)理邏輯第一章 命題邏輯基本概念§1.1 命題與聯(lián)結(jié)詞1. 命題與真值 命題，命題的真值，真命題，假命題，簡單命題（原子命題），復(fù)合命題2. 命題與真值的符號化 用p，q，r等小寫英文字母表示命題，用數(shù)字1代表真，0代表假。3. 常用聯(lián)結(jié)詞及其符號化 否定，合取，析取，蘊涵，等價4. 基本復(fù)合命題 設(shè)p，q為命題否定式p合取式pq析取式pq蘊涵式pq 分清邏輯關(guān)系、真值以及在自然語言中對“pq”的不同的描述方法。等價式pq5. 復(fù)合命題 基本復(fù)合命題以及多次使用常用聯(lián)結(jié)詞復(fù)合而成的命題統(tǒng)稱為復(fù)合命題。深刻理解5種常用聯(lián)結(jié)詞的涵義，并能準(zhǔn)

2、確地應(yīng)用它們將復(fù)合命題符號化。§1.2 命題公式及其賦值1. 命題常項與命題變項 命題常項（簡單命題），命題變項（取值為1或0的變量p，q，r）2. 命題公式與賦值 合式公式（也稱命題公式或公式），公式的層次，公式的賦值，成真賦值，成假賦值，真值表3. 命題公式的類型 重言式（永真式），矛盾式（永假式），可滿足式4. 判斷公式類型的方法 在本章內(nèi)主要用真值表判斷命題公式的類型，進而求公式的成真賦值和成假賦值。理解命題的賦值、成真賦值，成假賦值，重言式、矛盾式、可滿足式第二章 命題邏輯等值演算§2.1 等值式1. 等值式 若AB為重言式，則稱A與B是等值的。記為A B2. 基

3、本等值式3. 等值演算 由已知等值式推演除新的等值式的過程。4. 重言式與矛盾式的判別法 A為重言式當(dāng)且僅當(dāng)A1，A為矛盾式當(dāng)且僅當(dāng)A0。§2.2 析取范式與合取范式1. 基本概念 文字，簡單析取式，簡單合取式，極小項，極大項，析取范式，合取范式，主析取范式，主合取范式深刻理解極小項、極大項的定義、名稱、下腳標(biāo)與成真賦值的關(guān)系。2. 主要定理 在命題邏輯中，任何公式都存在與之等值的主析取范式和主合取范式，并且是唯一的。3. 求公式A的主析取范式的方法和步驟等值演算法（1）消去A聯(lián)結(jié)詞，（若存在）（2）否定聯(lián)結(jié)詞的內(nèi)移（3）使用分配律以上三步將A等值地化成析取范式（4）將析取范式中不是

4、極小項的簡單合取式利用排中律、同一律、分配律化成若干個極小項（5）將極小項用名稱mi表示，使用冪等律，最后排序4. 求公式A的主合取范式的方法和步驟等值演算法同上熟練掌握求主析取范式與主合取范式的方法。第三章 命題邏輯的推理理論§3.1 推理的形式結(jié)構(gòu)1. 推理 推理的形式結(jié)構(gòu)的符號化形式： 若A1A2AkB為重言式，稱推理是有效的?；颍?前提：A1，A2，Ak 結(jié)論：B2. 判斷推理是否正確的方法用第二章的只是判斷推理是否正確的方法有以下三種：真值表法、等值演算法、主析取范式法3. 推理規(guī)則9條牢記各條推理規(guī)則的內(nèi)容及名稱。§3.2 自然推理系統(tǒng)1. 自然推理系統(tǒng) 由字母

5、表、合式公式、推理規(guī)則構(gòu)成。2. 在自然推理系統(tǒng)中構(gòu)造證明前提：A1，A2，Ak結(jié)論：B構(gòu)造證明的方法：直接證明法：由前提A1，A2，Ak出發(fā)，應(yīng)用推理規(guī)則，推出B。附加前提證明法：當(dāng)結(jié)論為CB形式時，可以將C列入前提中，然后用直接證明法推出B，這里稱C為附加前提。歸謬證明法：將結(jié)論B的否定式B列入前提中，然后用直接證明法推出矛盾式。熟練掌握在系統(tǒng)中構(gòu)造證明的直接證明法、附加前提證明法、歸謬證明法。第四章 一階邏輯基本概念§4.1 一階邏輯命題符號化1. 個體詞 個體，個體常項，個體變項，個體域，有限個體域，無限個體域，全總個體域2. 謂詞 謂詞常項，謂詞變項，1元謂詞（表示事物性質(zhì)

6、），n（n2）元謂詞（表示事物之間的關(guān)系），0元謂詞，特性謂詞3. 量詞及其分類 量詞，全稱量詞，存在量詞4. 命題符號化 設(shè)D為個體域（1）“D中所有x都有性質(zhì)F”符號化為 xF（x）（2）“D中有的x有性質(zhì)F”符號化為 xF（x）（3）“對D中所有x而言，如果x有性質(zhì)F，x就有性質(zhì)G”符號化為 x（F（x）G（x）（基本公式1）（4）“對D中有的x既有性質(zhì)F，又有性質(zhì)G”符號化為 x（F（x）G（x）（基本公式2）（5）“對于D中所有x而言，若x有性質(zhì)F，就存在y有性質(zhì)G，則x與y就有關(guān)系H”符號化為 x（F（x）y（G（y）H（x，y）（6）“存在D中x有性質(zhì)F，并且對D中所有的y而言，

7、如果y有性質(zhì)G，則x與y就有關(guān)系H”符號化為 x（F（x）y（G（y）H（x，y）準(zhǔn)確地將給定命題符號化，分清各種符號化形式，特別要注意兩個基本公式。§4.2 一階邏輯公式及其解釋1. 一階語言 由非邏輯符集合L生成的一階語言的字母表，項，原子公式，合式公式2. 量詞的轄域 量詞的轄域，指導(dǎo)變元，個體變項的自由出現(xiàn)與約束出現(xiàn)，閉式3. 一階語言的解釋 公式在解釋I下的解釋對于給定的解釋I，會在解釋I下解釋公式，判斷公式是否是命題，是真命題、還是假命題。4. 公式的類型 永真式，永假式，可滿足式第五章 一階邏輯等值演算與推理§5.1 一階邏輯等值式與置換規(guī)則1. 等值式 設(shè)A

8、、B為一階邏輯公式，若AB為永真式，則稱A與B等值。2. 基本的等值式第一組 命題邏輯中基本等值式的代換實例。第二組 一階邏輯中的重要等值式（1）在有限個體域中消去量詞等值式（2）量詞否定等值式（3）量詞轄域收縮與擴張等值式（4）量詞分配等值式三個主要規(guī)則 置換規(guī)則、換名規(guī)則、代替規(guī)則熟練使用置換規(guī)則、換名規(guī)則、代替規(guī)則§5.2 一階邏輯前束范式1. 前束范式 公式A的前束范式2. 求給定的前束范式 利用重要的等值式、置換規(guī)則、換名規(guī)則、代替規(guī)則等，對給定公式進行等值演算即可求出給定公式的前束范式。熟練地求出給定公式的前束范式。§5.3 一階邏輯的推理理論1. 推理的形式結(jié)

9、構(gòu) 形式結(jié)構(gòu)1若A1A2AkB（其中A1，A2，Ak，B均為一階邏輯公式）為永真式，稱推理正確，否則稱推理不正確。形式結(jié)構(gòu)2前提：A1，A2，Ak結(jié)論：B2. 一階邏輯中重要的推理定律第一組 命題邏輯推理定律的代換實例第二組 一階邏輯中每個基本等值式均生成兩條推理定律第三組 一些常用的重要推理定律3. 自然推理系統(tǒng) 由字母表、合式公式、推理規(guī)則構(gòu)成。4. 在自然推理系統(tǒng)中構(gòu)造證明前提：A1，A2，Ak結(jié)論：B構(gòu)造證明的方法：直接證明法：由前提A1，A2，Ak出發(fā)，應(yīng)用推理規(guī)則，推出B。附加前提證明法：當(dāng)結(jié)論為CB形式時，可以將C列入前提中，然后用直接證明法推出B，這里稱C為附加前提。歸謬證明法

10、：將結(jié)論B的否定式B列入前提中，然后用直接證明法推出矛盾式。 牢記各條推理規(guī)則，能正確給出有效推理的證明。第二部分 集合論第六章 集合代數(shù)§6.1 集合的基本概念1. 元素與集合 集合，元素，屬于或者不屬于2. 特殊集合 自然數(shù)集N，有理數(shù)集Q，實數(shù)集R，空集，全集E，集合A的冪集P（A）=x|xA3. 集合的表示法 列元素法，謂詞表示法，文氏圖 熟練掌握集合的前兩種表示法4. 集合之間的關(guān)系 、=及它們的否定能夠判斷兩個集合之間是否存在包含、相等、真包含等關(guān)系。5. 重要結(jié)果 空集是任何集合的子集 如果|A| = n，則| P（A）| = 2n§6.2 集合的運算1. 集

11、合初級運算 并，交，相對補，絕對補，對稱差2. 集合廣義運算 廣義并，廣義交3. 運算的優(yōu)先權(quán)規(guī)定 稱廣義并，廣義交，冪集，絕對補運算為一類運算；并，交，相對補，對稱差運算為二類運算。一類運算優(yōu)先于二類運算，一類運算之間有右向左順序進行，二類運算之間由括號決定先后順序。熟練掌握集合的基本運算（冪集運算，普通運算和廣義運算）并能化簡集合表達式。§6.4 集合恒等式掌握證明集合等式或者包含關(guān)系的基本方法。第七章 二元關(guān)系§7.1 有序?qū)εc笛卡爾積1. 有序?qū)?<x,y>2. 笛卡爾積 設(shè)A，B為集合，A與B的笛卡爾積記作A×B，A×B=<x

12、，y>|xAyB3. 笛卡爾積運算的性質(zhì) 不適合交換律、結(jié)合律，但對于并和交運算滿足分配律。4. 笛卡爾積中元素的個數(shù) |A|=m，|B |= n，則|A×B|=mn§7.2 二元關(guān)系1. 二元關(guān)系2. 從A到B的二元關(guān)系與A上的關(guān)系3. A上的某些特殊關(guān)系 空關(guān)系、全域關(guān)系EA、恒等關(guān)系IA4. 關(guān)系的表示 集合表達式、關(guān)系矩陣、關(guān)系圖熟練掌握關(guān)系矩陣、關(guān)系圖的表示法。§7.3 關(guān)系的運算1. 關(guān)系運算的定義 定義域、值域、域、逆、右復(fù)合、限制、像、冪2. 關(guān)系運算的性質(zhì) 熟練掌握關(guān)系的定義域、值域、域、逆、右復(fù)合、限制、像、冪運算。§7.4 關(guān)

13、系的性質(zhì)1. 關(guān)系的性質(zhì) 自反、反自反、對稱、反對稱、傳遞2. 判別關(guān)系性質(zhì)的三種方法 書P117 表7.1 熟練掌握判斷關(guān)系五種性質(zhì)的方法，并能對關(guān)系的性質(zhì)給出證明。3. 關(guān)系運算與關(guān)系性質(zhì)之間的聯(lián)系 書P118 表7.2§7.5 關(guān)系的閉包1. 關(guān)系的閉包 自反閉包r(R)、對稱閉包s(R)、傳遞閉包t(R)2. 構(gòu)造閉包的三種方法集合表達式：r(R) = RR0= RIA、 s(R) = RR-1、t(R) = RR2R3關(guān)系矩陣：Mr = M + E Ms = M + M Mt = M + M2 + M3 + 關(guān)系圖3. 閉包的性質(zhì) 熟練計算集合A上關(guān)系R的自反閉包r(R)、

14、對稱閉包s(R)、傳遞閉包t(R)§7.6 等價關(guān)系與劃分1. 等價關(guān)系 A上的自反、對稱和傳遞的關(guān)系。2. 等價類設(shè)R為非空集合A上的等價關(guān)系，"xA，令xR = y | yAxRy ，稱 xR 為 x 關(guān)于R 的等價類，簡稱為 x 的等價類，簡記為x。3. 等價類的性質(zhì)(1) "xA，x 是A的非空子集。 (2) "x, yA，如果 x R y，則 x=y。 (3) "x, yA，如果 x y，則 x與y不交。 (4) x | xA=A，即所有等價類的并集就是A。 4. 商集 設(shè)R為非空集合A上的等價關(guān)系，以R的所有等價類作為元素的集合稱為

15、A關(guān)于R的商集，記做A/R，A/R = xR | xA 。5. 集合A的劃分設(shè)A為非空集合，若A的子集族(ÍP(A) 滿足下面條件： (1) ÏÆ (2) "x"y (x,yxyxy=Æ) (3) =A 則稱是A的一個劃分，稱中的元素為A的劃分塊。6. 集合A上的等價關(guān)系與A的劃分之間的一一對應(yīng) 熟練掌握等價關(guān)系、等價類、商集、劃分的概念，以及等價關(guān)系與劃分的對應(yīng)性質(zhì)。§7.7 偏序關(guān)系1. 偏序關(guān)系 A上的自反、反對稱和傳遞的關(guān)系。2. 哈斯圖3. 偏序集中的特殊元素 最大元、最小元、極大元、極小元、上界、下界、最小上界、

16、最大下界 熟練掌握偏序關(guān)系、哈斯圖、特殊元素等概念。第五部分 圖論第十四章 圖的基本概念§14.1 圖1. 圖的定義 無向圖，有向圖，n階圖，零圖，平凡圖，標(biāo)定圖，非標(biāo)定圖，基圖。2. 頂點與邊的關(guān)系 頂點與邊的關(guān)聯(lián)關(guān)系，關(guān)聯(lián)次數(shù)，環(huán)，孤立點；頂點與頂點的相鄰關(guān)系，邊與邊的相鄰關(guān)系；無向圖的鄰域與關(guān)聯(lián)集；有向圖的后繼元集、先驅(qū)元集與鄰域。3. 簡單圖與多重圖 平行邊，多重圖，簡單圖 理解與圖的定義有關(guān)的諸多概念。4. 頂點的度數(shù)與握手定理及推論 深刻理解握手定理及推論的內(nèi)容，并能熟練地應(yīng)用它們。5. 圖的同構(gòu) 定義，圖的同構(gòu)關(guān)系是等價關(guān)系。6. 完全圖與競賽圖 n階有向完全圖Kn，n

17、階無向完全圖，n階競賽圖，以及簡單性質(zhì)。7. 正則圖 n階k正則圖的定義及簡單性質(zhì)。8. 子圖 子圖的定義，真子圖，生成子圖，導(dǎo)出子圖。9. 補圖 補圖的定義，自補圖。理解上述概念及它們的性質(zhì)和相互關(guān)系。10. 圖的運算 刪除運算、收縮邊、加新邊§14.2 圖1. 通路與回路的定義 定義，通路與回路的長度2. 通路與回路的分類 簡單通路與簡單回路，初級通路（路徑）與初級回路（圈），復(fù)雜通路與復(fù)雜回路3. 通路與回路的性質(zhì) 定理14.5、定理14.6§14.3 圖的連通性1. 無向圖的連通性 頂點之間的連通關(guān)系，無向連通圖，非連通圖，連通分支，頂點之間的短程線與距離。2. 無向圖的連通度 點割集與割點，邊割集與割邊（橋），G的點連通度(G)，k-連通圖，G的邊連通度(G)，r邊-連通圖，(G)與(G)的關(guān)系。