離散結構複習指南

18周結課，20周期末考試。現在把學習知識點發給大家，請對照知識點抓緊複習。

離散結構複習指南

第一部分 數理邏輯

重點：

1. 會判斷命題

2.五個命題聯結詞的含義，真值表，與自然語言的對應關係。

（尤其是蘊含中的「除非」「只有」「僅當」等）

3. 會求公式的真值表

4. 會進行命題的符號化

5. 會判斷公式的成真成假賦值，會判斷公式類型。

6. 會求公式的主析取和主合取範式

7. 牢記16組基本等值式，會應用它們進行等值演算和公式化簡

8. 牢記13組推理規則，會應用它們進行推理證明（分清直接證明和附加前提證明法的使用條件）

9.理解個體（x,y,z;a,b,c）、謂詞、量詞的概念，會在一階邏輯中進行謂詞符號化(並非所有，沒有，不存在)

10. 會簡單的一階邏輯公式的解釋

11. 會消去量詞

12.會應用一階邏輯中的等值式證明轄域的收縮與擴張部分的公式

13. 會判斷公式的轄域、約束變元、自由變元，會給約束變元改名

14. 會求公式的前束範式

第二部分 集合論

重點：

1.集合的基本概念（集合、並交差補環和運算）

2. 會求集合的冪集、基數

3. 理解有序對與笛卡爾積的概念

4. 會證明笛卡爾積與並和交運算的分配率

5. 理解A到B的關係，A上的關係

6. 會求關係的前域、陪域、定義域、值域、域

7. 會關係的三種表示方法（集合、圖、矩陣）

8. 會用矩陣求關係的並交差補運算

9. 會在集合、圖、矩陣下求關係的逆

10. 會在集合、圖、矩陣下求關係的合成

11. 會在集合、圖、矩陣下求關係的閉包

12. 會判斷關係的五個性質

13. 會證明逆、合成、閉包運算部分的等式

14. 會證明等價關係.

15.理解劃分、等價類的含義

16.會求等價關係誘導的等價劃分，會根據等價劃分求等價關係

17. 會證明偏序關係

18. 會畫哈斯圖，並會根據哈斯圖求關係中的序偶

19. 八個概念（極大極小元、最大最小元、上下界、上下確界）

20.會判斷函數，會求所有A到B的函數

21. 會求集合在函數下的像，函數在集合下的完全原像

22. 會判斷單射、滿射、雙射

第三部分 圖論

重點：

1.理解無向圖與有向圖的基本概念

2. 給定邊和點的集合，會畫圖

3. 會根據握手定理求未知結點的個數

4. 會判斷整數列是否可圖化，可簡單圖化

5. 會求割點、割邊、點割集、邊割集

6. 會構造鄰接矩陣，會根據鄰接矩陣求長度為n的通路與迴路的條路。

7. 了解歐拉圖與哈密頓圖，會判斷

8. 會根據Kruskal演算法和Prim演算法求最小生成樹

9. 深刻理解前綴碼和二元前綴碼，以及二元前綴碼與二叉樹的關係。會根據哈夫曼演算法求最優二叉樹

10. 會對二叉樹進行前序、中序、後序遍歷

第三部分 代數系統

重點：

1. 理解n元運算的封閉、代數系統的相關概念。

2. 會求單位元、零元、可逆元素的逆元；會判斷運算有無 交換律、結合律、冪等律

3. 理解廣群、半群、獨異點、群的概念，並證明

4. 理解格、分配格、有界格、有補格、布爾格、布爾代數 的概念，會判斷各種格，理解格在計算機中的應用。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！