復(fù)試《離散數(shù)學(xué)》科目考試大綱

一、考查目標(biāo)

理解命題邏輯的基本概念及應(yīng)用方法；掌握謂詞邏輯的基本概念及應(yīng)用方法；熟練掌握集合、關(guān)系函數(shù)的基本概念及運(yùn)算、論證方法；理解代數(shù)結(jié)構(gòu)的基本概念及研究方法；掌握?qǐng)D論的概念及應(yīng)用。

二、考試形式與試卷結(jié)構(gòu)

（一）試卷滿分及考試時(shí)間

復(fù)試科目滿分均為100分，考試時(shí)間為2小時(shí)。

（二）答題方式

答題方式為閉卷、筆試。

（三）試卷內(nèi)容結(jié)構(gòu)

命題邏輯：20%左右

謂詞邏輯：10%左右

集合與關(guān)系：20%左右

函數(shù)：10%左右

代數(shù)系統(tǒng)：15%左右

格：10%左右

圖論：15%左右

（四）試卷題型結(jié)構(gòu)

客觀題：選擇題20%左右，填空題20%左右；

證明30%左右；

綜合應(yīng)用30%左右

三、考查范圍

1、命題邏輯

2、謂詞邏輯

3、集合與關(guān)系

4、函數(shù)

5、代數(shù)系統(tǒng)

6、格

7、圖論

四、考試內(nèi)容及要求

1.數(shù)理邏輯

（1）命題邏輯

1）理解下列基本概念：

命題，聯(lián)結(jié)詞，合式公式，真值指派和真值表，永真式、永假式和可滿足式，等價(jià)式與蘊(yùn)涵式，規(guī)范式。

2)掌握命題符號(hào)化的方法；

3)熟練掌握基本等價(jià)式和蘊(yùn)涵式及其應(yīng)用；

4)理解和掌握推理規(guī)則（P、T、CP規(guī)則），直接證法和間接證法。

（2）謂詞邏輯

1)理解下列基本概念：謂詞，量詞，變?cè)募s束，謂詞公式；

2)能用謂詞公式表達(dá)自然語(yǔ)句表述命題；

3)熟練掌握基本謂詞的演算式和蘊(yùn)涵式及其應(yīng)用；

4)理解和掌握謂詞演算的推理理論（推論規(guī)則US、ES、UG、EG）；

5)了解前束范式。

2.集合、關(guān)系與函數(shù)

（3）理解下列基本概念：

集合，基數(shù)，序偶與笛卡爾集；關(guān)系，二元關(guān)系，逆關(guān)系，復(fù)合關(guān)系，序關(guān)系，關(guān)系的性質(zhì)及閉包，等價(jià)關(guān)系 ，等價(jià)類，覆蓋與劃分；映射與函數(shù)，逆函數(shù)，復(fù)合函數(shù)。

（4）了解可數(shù)無(wú)限集與不可數(shù)無(wú)限集的勢(shì)的概念；

（5）掌握集合運(yùn)算；

（6）熟練掌握集合相互包含和相等的論證方法；

（7）掌握關(guān)系閉包運(yùn)算；

（8）理解等價(jià)關(guān)系與劃分的內(nèi)在聯(lián)系；

（9）能正確區(qū)分單（入）射、滿射和雙射。

3.代數(shù)結(jié)構(gòu)

(10)理解下列基本概念：

代數(shù)系統(tǒng)，幺元，零元，逆元，同態(tài)與同構(gòu)，同余關(guān)系，商代數(shù)，積代數(shù)；半群，獨(dú)異點(diǎn)，群（包括Abel群，循環(huán)群，置換群），子群，陪集，正規(guī)子群，商群，環(huán)和域；偏序及哈斯圖，格分配格，有補(bǔ)格，布爾代數(shù)。

(11)理解拉格郎日定理及其推論；

(12)掌握哈斯圖的作法；

(13)了解代數(shù)系統(tǒng)的分類及研究方法。

4.圖論

(14)理解下列基本概念：

圖，結(jié)點(diǎn)的度數(shù)，路徑、回路與連通性，賦權(quán)圖，歐拉圖，哈密爾頓圖，平面圖，對(duì)偶圖與著色，樹、生成樹、根樹及最優(yōu)樹。

(15)掌握?qǐng)D的矩陣表示；

(16)掌握賦權(quán)圖的最短路徑求法；

(17)了解和掌握關(guān)于平面圖的 歐拉公式及其應(yīng)用；

(18)能求邊賦權(quán)圖的最小生成樹；

(19)能將n元樹轉(zhuǎn)換為二叉樹來(lái)表示；

(20)能畫出帶有一組權(quán)值的最優(yōu)樹，并給出哈夫曼編碼 。

五、考試用具說(shuō)明

考生應(yīng)自帶必需的文具，如2B鉛筆、藍(lán)（黑）色字跡鋼筆、圓珠筆或簽字筆。

考生將試題答案寫在答題紙上，標(biāo)清題號(hào)，無(wú)需抄題。