一、　數(shù)理邏輯

[復(fù)習(xí)知識(shí)點(diǎn)]

1、命題與聯(lián)結(jié)詞（否定￢、析取∨、合取∧、蘊(yùn)涵→、等價(jià)?），命題(非真既假的陳述句),復(fù)合命題(由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題)

2、命題公式與賦值（成真、成假），真值表，公式類型（重言、矛盾、可滿足），公式的基本等值式

3、范式：析取范式、合取范式，極大（小）項(xiàng)，主析取范式、主合取范式??

4、公式類型的判別方法：真值表法、等值演算法、主析取/合取范式法?

5、命題邏輯的推理理論

?

6、謂詞、量詞、個(gè)體詞（公式一階邏輯3要素）、個(gè)體域、變元（約束出現(xiàn)與自由出現(xiàn)）

7、命題符號(hào)化、謂詞賦值與解釋，謂詞公式的類型（永真、永假、可滿足）

8、謂詞公式的等值式（代換實(shí)例、消去量詞、量詞否定和量詞轄域收與擴(kuò)、量詞分配）和置換規(guī)則（置換規(guī)則、換名規(guī)則）

9、一階邏輯前束范式（定義、求法）

本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、（主）析取范式與（主）合取范式、公式類型的判定、命題邏輯的推理、謂詞與量詞、命題符號(hào)化、謂詞公式賦值與解釋、求前束范式。

?[復(fù)習(xí)要求]

1、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。

2、理解公式與賦值的概念；掌握求給定公式真值表的方法，用基本等值式化簡其它公式，公式在解釋下的真值。

3、了解析取（合取）范式的概念；理解極大（小）項(xiàng)的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表將公式化為主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價(jià)方法。

5、掌握命題邏輯的推理理論。

6、理解謂詞、量詞、個(gè)體詞、個(gè)體域、變元的概念；理解用謂詞、量詞、邏輯聯(lián)結(jié)詞描述一個(gè)簡單命題；掌握命題的符號(hào)化。

7、理解公式與解釋的概念；掌握在有限個(gè)體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類型。

8、掌握求一階邏輯前束范式的方法。

二、 集 合

[復(fù)習(xí)知識(shí)點(diǎn)]

1、集合、元素、集合的表示方法（列元素法、謂詞表示法）、子集、空集、全集、集合的包含、相等、冪集

2、集合的交、并、差、補(bǔ)以及對稱差等運(yùn)算及有窮集的計(jì)數(shù)（文氏（Venn）圖、包含排斥原理）

3、集合恒等式（冪等律、交換律、結(jié)合律、分配律、吸收律、矛盾律、德摩根律等）及應(yīng)用

本章重點(diǎn)內(nèi)容：集合的概念、集合的運(yùn)算性質(zhì)、集合恒等式的證明。

[復(fù)習(xí)要求]

三、 二元關(guān)系

?[復(fù)習(xí)要求]

1、了解序偶與笛卡爾積的概念，掌握笛卡爾積的運(yùn)算。

2、理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全域關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算?！?/p>

3、掌握求復(fù)合關(guān)系與逆關(guān)系的方法。

4、理解關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性、傳遞性），掌握其判別方法（定義、圖）。

自反性：全部頂點(diǎn)均有環(huán)；反自反性：全部頂點(diǎn)均無環(huán)；對稱性：有邊均雙邊（無單邊，頂點(diǎn)有無環(huán)不影響） ；反對稱性：有邊均單邊（頂點(diǎn)有無環(huán)不影響）（無平行邊）

傳遞性：a到b有邊，b到c有邊，則a到c也有邊，否則不然。

5、掌握求關(guān)系的閉包?（自反閉包、對稱閉包、傳遞閉包）的方法。

換言之：r=加自環(huán) s=單邊變雙邊? ?t:努力變傳遞

6.理解等價(jià)關(guān)系和劃分、掌握等價(jià)類和劃分的求法

7、理解偏序關(guān)系的概念，掌握畫哈斯圖的方法，極大/小元、最大/小元的求法。

相關(guān)概念：

哈斯圖的方法：?

?如圖7.7：5,9,6,8,7均是極大元，1是極小元，無最大元，最小元為1；右邊： {a，b，c}是極大元，?是極小元，最大元是 {a，b，c}，最小元為??

四、函數(shù)

[復(fù)習(xí)知識(shí)點(diǎn)]

1. 理解函數(shù)概念：函數(shù)、函數(shù)相等、A到B的函數(shù)。

2、理解單射、滿射、雙射等概念，掌握其判別方法。

單射：不同的x所對應(yīng)的y不同。

滿射：y的值域全用到了。

?雙射：單+滿

3、函數(shù)的復(fù)合與反函數(shù)

函數(shù)復(fù)合及相關(guān)聯(lián)習(xí)

?反函數(shù)：

本章重點(diǎn)內(nèi)容：函數(shù)的定義及判別方法、函數(shù)的三大性質(zhì)、函數(shù)的復(fù)合與反函數(shù)。

[復(fù)習(xí)要求]

1. 掌握函數(shù)及從A到B的函數(shù)的判別方法。

函數(shù)：

從A到B的函數(shù)：

? ? ?

2、理解函數(shù)的像與原像。

3.掌握函數(shù)的單射、滿射、雙射的判別方法。

4、掌握求函數(shù)的復(fù)合與反函數(shù)的方法。

五、 圖論

[復(fù)習(xí)知識(shí)點(diǎn)]

1、 圖的基本概念：無向圖與有向圖(根據(jù)聯(lián)結(jié)的邊是否有方向）、頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系、頂點(diǎn)（邊）與頂點(diǎn)（邊）之間鄰接關(guān)系、簡單圖與多重圖、頂點(diǎn)度數(shù)（度）與握手定理、圖的同構(gòu)、完全圖、子（補(bǔ)）圖。

度：?

?

?握手定理：

簡單圖與多重圖：?

?

?

?

2、 通路與回路、簡單通（回）路與初級(jí)通（回）路；連通圖與非連通圖、連通分支、點(diǎn)割集、邊割集、點(diǎn)（邊）連通度；強(qiáng)連通圖、單向連通圖與弱連通圖；二部圖。

3、 圖的矩陣表示：關(guān)聯(lián)矩陣、鄰接矩陣、可達(dá)矩陣。

?

4、 歐拉通（回）路、（半）歐拉圖；哈密爾頓通（回）路、（半）哈密爾頓圖；

?

?

5、 無向樹、生成樹、帶權(quán)樹、最小生成樹。

6、 有向樹、樹根、有序樹、二叉樹、最優(yōu)二叉樹、前綴碼、最佳前綴碼、霍夫曼（Huffman）算法、二叉樹的周游及應(yīng)用。

本章重點(diǎn)內(nèi)容：?握手定理、點(diǎn)（邊）割集、通路與回路、特殊圖（歐拉圖與哈密頓圖、無（有）向樹）、最優(yōu)二叉樹、最佳前綴碼、霍夫曼（Huffman）算法。

[復(fù)習(xí)要求]

1、理解圖的有關(guān)概念：圖、完全圖、簡單圖、子圖、母圖、生成子圖等。

2、深刻理解握手定理及其推論的內(nèi)容，并能熟練地應(yīng)用它們。

3、能判斷兩個(gè)圖是否同構(gòu)。

4、理解連通度、點(diǎn)割集、邊割集、割邊和割點(diǎn)。

5、能判斷圖是否為強(qiáng)連通圖、單向連通圖與弱連通圖。

6、理解圖的矩陣表示（關(guān)聯(lián)矩陣、相鄰矩陣）和性質(zhì)以及熟練掌握用有向圖的鄰接矩陣及各次冪求圖中通路與回路數(shù)的方法。

4、理解歐拉圖、哈密頓圖的定義及判別定理。在無向圖中找出一條歐拉通路或歐拉回路、哈密頓通路或哈密頓回路。

5、理解無向樹的定義，熟練掌握無向樹的主要性質(zhì)，并能靈活應(yīng)用它們。

6、理解生成樹的有關(guān)概念與性質(zhì)。

7、理解有向樹、根樹、二叉樹和前綴碼的有關(guān)概念；掌握用霍夫曼（Huffman）算法求帶權(quán)圖的最優(yōu)二分樹，掌握求最佳前綴碼方法，二叉樹的中序和前序行遍法。