復(fù)試《離散數(shù)學(xué)》科目考試大綱
一、考查目標(biāo)
理解命題邏輯的基本概念及應(yīng)用方法；掌握謂詞邏輯的基本概念及應(yīng)用方法；熟練掌握集合、關(guān)系函數(shù)的基本概念及運(yùn)算、論證方法；理解代數(shù)結(jié)構(gòu)的基本概念及研究方法；掌握圖論的概念及應(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)掌握命題符號化的方法；
3)熟練掌握基本等價(jià)式和蘊(yùn)涵式及其應(yīng)用；
4)理解和掌握推理規(guī)則（P、T、CP規(guī)則），直接證法和間接證法。
（2）謂詞邏輯
1)理解下列基本概念：謂詞，量詞，變元的約束，謂詞公式；
2)能用謂詞公式表達(dá)自然語句表述命題；
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ù)無限集與不可數(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)圖，歐拉圖，哈密爾頓圖，平面圖，對偶圖與著色，樹、生成樹、根樹及最優(yōu)樹。
(15)掌握圖的矩陣表示；
(16)掌握賦權(quán)圖的最短路徑求法；
(17)了解和掌握關(guān)于平面圖的 歐拉公式及其應(yīng)用；
(18)能求邊賦權(quán)圖的最小生成樹；
(19)能將n元樹轉(zhuǎn)換為二叉樹來表示；
(20)能畫出帶有一組權(quán)值的最優(yōu)樹，并給出哈夫曼編碼 。
五、考試用具說明
考生應(yīng)自帶必需的文具，如2B鉛筆、藍(lán)（黑）色字跡鋼筆、圓珠筆或簽字筆。
考生將試題答案寫在答題紙上，標(biāo)清題號，無需抄題。