離散數(shù)學(xué)考試大綱
　　1 命題演算基礎(chǔ)
　　1．1 命題與聯(lián)結(jié)詞
　�、倜�題 ②聯(lián)結(jié)詞 ③合式公式 ④命題的符號(hào)化
　　1.2 真假性
　�、俳忉� ②等價(jià)公式 ③聯(lián)結(jié)詞的完備集 ④對(duì)偶式和內(nèi)否式。
　　1.3 范式及其應(yīng)用
　�、俜妒� ②主范式
　　2 命題演算的推理理論
　　2.1 命題演算的公理系統(tǒng)
　�、俟�理系統(tǒng)的組成部分 ②公理系統(tǒng)的推理過(guò)程
　　2.2 命題演算的假設(shè)推理系統(tǒng)
　�、偌僭O(shè)推理系統(tǒng)的組成 ②假設(shè)推理系統(tǒng)的推理過(guò)程
　　2.3 命題演算的歸結(jié)推理法
　�、贇w結(jié)證明過(guò)程②歸結(jié)證明方法
　　3 謂詞演算基礎(chǔ)
　　3.1 謂詞和個(gè)體
　�、賯�(gè)體 ②謂詞 ③語(yǔ)句的符號(hào)化
　　3.2 函數(shù)和量詞
　�、俸瘮�(shù)項(xiàng) ②量詞
　　3.4 永真性和可滿足性
　�、僬婕傩� ②同真假性 ③永真性和可滿足性 ④范式
　　4 謂詞演算的推理理論
　　4.1 謂詞演算的永真公理系統(tǒng)
　�、俟�理系統(tǒng)的組成部分 ②公理系統(tǒng)的推理過(guò)程
　　4.2 謂詞演算的假設(shè)推理系統(tǒng)
　�、偌僭O(shè)推理系統(tǒng)的組成及證明方法 ②定理的推導(dǎo)過(guò)程
　　4.3 謂詞演算的歸結(jié)系統(tǒng)
　�、僦脫Q ②歸結(jié)反演系統(tǒng) ③霍恩子句邏輯程序
　　5遞歸函數(shù)論
　　5.1 數(shù)論函數(shù)和數(shù)論謂詞
　　5.2 函數(shù)的構(gòu)造
　　6 集合
　　6．1 集合的基本概念
　�、偌�合；②子集合；③空集合；④集合的相等。
　　6．2 集合的基本運(yùn)算
　�、偌�合的運(yùn)算；②集合的交；③集合的并；④集合的差；⑤集合的對(duì)稱差；⑥集合的廣義交；
　　⑦集合的廣義并；⑧冪集合。
　　6．3 全集和集合的補(bǔ)
　�、偃�集；②集合的補(bǔ)；③德·摩根定律。
　　6．4 自然數(shù)與自然數(shù)集
　�、僮匀粩�(shù)；②自然數(shù)集；③數(shù)學(xué)歸納法；④集合的歸納定義。
　　6．5 包含與排斥原理
　�、儆邢藜�；②包含與排斥原理。
　　7 關(guān)系
　　7．1 集合的笛卡爾積集
　�、儆行�?qū)Γ虎诩�合的笛卡爾積集；③有序n(n2)元組；④n重(n2)笛卡爾積集。
　　7．2 二元關(guān)系的基本概念
　�、俣�元關(guān)系；②二元關(guān)系的表示；③二元關(guān)系的圖形表示；④二元關(guān)系的矩表示；⑤二元關(guān)系的運(yùn)算；⑥二元關(guān)系的復(fù)合運(yùn)算；⑦二元關(guān)系的逆關(guān)系。
　　7．3 二元關(guān)系的性質(zhì)
　�、俣�元關(guān)系的性質(zhì)；②自反的二元關(guān)系；③反自反的二元關(guān)系 ；④對(duì)稱的二元關(guān)系；⑤反對(duì)稱的二元關(guān)系；⑥傳遞的二元關(guān)系。
　　7．4 二元關(guān)系的閉包運(yùn)算
　�、俣�元關(guān)系的閉包運(yùn)算；②自反閉包；③對(duì)稱閉包；④傳遞閉包。
　　7．5 等價(jià)關(guān)系與集合的劃分
　�、俚葍r(jià)關(guān)系；②等價(jià)類；③集合的劃分；④商集合。
　　7．6 偏序關(guān)系和格
　　①偏序關(guān)系；②偏序集；③極大元；④極小元；⑤比較大元；⑥比較小元； ⑦比較小上界；⑧比較大下界；⑨可比；⑩覆蓋；⑾有序集；⑿良序集；⒀格。
　　8 函數(shù)與集合的勢(shì)
　　8．1 函數(shù)的基本概念
　�、俸瘮�(shù)（映射）；②定義域；③陪域；④值域；⑤象集；⑥原象集；⑦單射函數(shù)；⑧滿射函數(shù)；⑨雙射函數(shù)。
　　8．2 函數(shù)的復(fù)合與可逆函數(shù)
　�、俸瘮�(shù)的復(fù)合；②左可逆函數(shù)；③右可逆函數(shù)；④可逆函數(shù)。
　　8．3 無(wú)限集
　�、偌�合的勢(shì)；②無(wú)限集；③集合的勢(shì)相等；④可數(shù)無(wú)限集；⑤不可數(shù)無(wú)限集； ⑥集合勢(shì)大小的比較。
　　9 圖論
　　9．1 圖的基本概念
　　①有向圖；②無(wú)向圖；③頂點(diǎn)集；④邊集；⑤自環(huán)；⑥孤立點(diǎn)；⑦多重邊；⑧簡(jiǎn)單圖；⑨完全圖；⑩關(guān)聯(lián)；⑾鄰接；⑿圖的同構(gòu)；⒀子圖；⒁生成子圖；⒂補(bǔ)圖；⒃圖的頂點(diǎn)度數(shù)（次數(shù)）；⒄?qǐng)D的頂點(diǎn)度數(shù)和與邊數(shù)關(guān)系。
　　9．2 圖中的通路、圖的連通性與圖的矩陣表示
　�、賵D中的通路；②簡(jiǎn)單通路；③初等通路；④回路；⑤簡(jiǎn)單回路；⑥初等回路（圈）；⑦連通圖；⑧有向連通圖；⑨有向單側(cè)連通圖；⑩有向強(qiáng)連通圖；⑾ 圖的鄰接矩陣；⑿圖的關(guān)聯(lián)矩陣；⒀圖的可達(dá)矩陣。
　　9．3 帶權(quán)圖與帶權(quán)圖中比較短通路
　�、賻�權(quán)圖；②帶權(quán)圖的比較短通路；③狄克斯瑞（Dijkstra）算法。
　　9．4 歐拉圖
　�、贇W拉圖；②歐拉通路；③歐拉回路；④歐拉定理。
　　9．5 哈密爾頓圖與貨郎擔(dān)問(wèn)題
　�、俟�密爾頓通路；②哈密爾頓回路（圈）；③哈密爾頓圖；④哈密爾頓圖的必要條件；⑤哈密爾頓圖的充分條件；⑥貨郎擔(dān)問(wèn)題；⑦比較鄰近算法。
　　9．6 二部圖
　�、俣�部圖（偶圖）；②二部圖的充要條件；③二部圖的匹配；④二部圖的極大匹配；⑤二部圖的完美匹配。
　　9．7 平面圖
　�、倨矫鎴D；②平面圖的歐拉定理；③平面圖的必要條件；④平面圖的區(qū)域著色。
　　10 樹(shù)
　　10．1 樹(shù)的基本概念
　�、贅�(shù)；②樹(shù)中頂點(diǎn)與邊關(guān)系公式；③樹(shù)的等價(jià)定義。
　　10．2 連通圖的生成樹(shù)與帶權(quán)圖的比較小生成樹(shù)
　�、龠B通圖的生成樹(shù)；②割集；③割集與生成樹(shù)的關(guān)系；④帶權(quán)圖比較小生成樹(shù)的算法。
　　10．3 有序樹(shù)
　�、儆邢驑�(shù)；②根樹(shù)；③有序樹(shù)；④有序n (n2)分樹(shù)；⑤正則有序n (n2) 分樹(shù)。
　　10．4 前綴碼和比較優(yōu)二分樹(shù)
　�、偾熬Y碼；②帶權(quán)圖的比較優(yōu)二分樹(shù)；③霍夫曼（Huffman）算法。
　　11 群和環(huán)
　　11．1 代數(shù)運(yùn)算的基本概念
　�、俣�元運(yùn)算；②封閉的二元運(yùn)算；③可結(jié)合的二元運(yùn)算；④可交換的二元運(yùn)算；⑤n元運(yùn)算
　　11．2 代數(shù)系統(tǒng)和半群
　�、俅鷶�(shù)系統(tǒng)；②左么元；③右么元；④么元；⑤半群；⑥含么半群（獨(dú)異點(diǎn)）；⑦半群的同態(tài)；⑧子半群；⑨子含么半群。
　　11．3 群的基本概念
　　①左逆元；②右逆元；③逆元；④群；⑤有限群；⑥交換群；⑦群同態(tài)；⑧群同構(gòu)；⑨群中元素的階。
　　11．4 變換群和置換群
　�、僮儞Q含么半群；②變換群；③置換群；④n個(gè)文字對(duì)稱群。
　　11．5 循環(huán)群
　　①循環(huán)群。
　　11．6 子群、群的子集生成的群
　�、僮尤�。
　　11．7 子群的陪集
　　①子群的陪集；②子群在群中的指數(shù)；③群中拉格朗日定理。
　　11．8 正規(guī)子群、商群、群同態(tài)
　�、僬�規(guī)子群；②商群；③群的同態(tài)基本定理。
　　主要參考教材：朱保平,葉有培,張琨.離散數(shù)學(xué).北京：北京理工大學(xué)出版社，2006