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

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

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

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

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

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

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

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

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

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

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

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

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

14、對稱閉包s(R)、傳遞閉包t(R)§7.6 等價關系與劃分1. 等價關系 A上的自反、對稱和傳遞的關系。2. 等價類設R為非空集合A上的等價關系，"xA，令xR = y | yAxRy ，稱 xR 為 x 關于R 的等價類，簡稱為 x 的等價類，簡記為x。3. 等價類的性質(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. 商集 設R為非空集合A上的等價關系，以R的所有等價類作為元素的集合稱為

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

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

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