南京理工大學離散數學2011年考研大綱

　離散數學考試大綱
　　1 命題演算基礎
　　1．1 命題與聯結詞
　　①命題 ②聯結詞 ③合式公式 ④命題的符號化
　　1.2 真假性
　　①解釋 ②等價公式 ③聯結詞的完備集 ④對偶式和內否式。
　　1.3 范式及其應用
　　①范式 ②主范式
　　2 命題演算的推理理論
　　2.1 命題演算的公理系統
　　①公理系統的組成部分 ②公理系統的推理過程
　　2.2 命題演算的假設推理系統
　　①假設推理系統的組成 ②假設推理系統的推理過程
　　2.3 命題演算的歸結推理法
　　①歸結證明過程②歸結證明方法
　　3 謂詞演算基礎
　　3.1 謂詞和個體
　　①個體 ②謂詞 ③語句的符號化
　　3.2 函數和量詞
　　①函數項 ②量詞
　　3.4 永真性和可滿足性
　　①真假性 ②同真假性 ③永真性和可滿足性 ④范式
　　4 謂詞演算的推理理論
　　4.1 謂詞演算的永真公理系統
　　①公理系統的組成部分 ②公理系統的推理過程
　　4.2 謂詞演算的假設推理系統
　　①假設推理系統的組成及證明方法 ②定理的推導過程
　　4.3 謂詞演算的歸結系統
　　①置換 ②歸結反演系統 ③霍恩子句邏輯程序
　　5遞歸函數論
　　5.1 數論函數和數論謂詞
　　5.2 函數的構造
　　6 集合
　　6．1 集合的基本概念
　　①集合；②子集合；③空集合；④集合的相等。
　　6．2 集合的基本運算
　　①集合的運算；②集合的交；③集合的并；④集合的差；⑤集合的對稱差；⑥集合的廣義交；
　　⑦集合的廣義并；⑧冪集合。
　　6．3 全集和集合的補
　　①全集；②集合的補；③德·摩根定律。
　　6．4 自然數與自然數集
　　①自然數；②自然數集；③數學歸納法；④集合的歸納定義。
　　6．5 包含與排斥原理
　　①有限集；②包含與排斥原理。
　　7 關系
　　7．1 集合的笛卡爾積集
　　①有序對；②集合的笛卡爾積集；③有序n(n2)元組；④n重(n2)笛卡爾積集。
　　7．2 二元關系的基本概念
　　①二元關系；②二元關系的表示；③二元關系的圖形表示；④二元關系的矩表示；⑤二元關系的運算；⑥二元關系的復合運算；⑦二元關系的逆關系。
　　7．3 二元關系的性質
　　①二元關系的性質；②自反的二元關系；③反自反的二元關系 ；④對稱的二元關系；⑤反對稱的二元關系；⑥傳遞的二元關系。
　　7．4 二元關系的閉包運算
　　①二元關系的閉包運算；②自反閉包；③對稱閉包；④傳遞閉包。
　　7．5 等價關系與集合的劃分
　　①等價關系；②等價類；③集合的劃分；④商集合。
　　7．6 偏序關系和格
　　①偏序關系；②偏序集；③極大元；④極小元；⑤比較大元；⑥比較小元； ⑦比較小上界；⑧比較大下界；⑨可比；⑩覆蓋；⑾有序集；⑿良序集；⒀格。
　　8 函數與集合的勢
　　8．1 函數的基本概念
　　①函數（映射）；②定義域；③陪域；④值域；⑤象集；⑥原象集；⑦單射函數；⑧滿射函數；⑨雙射函數。
　　8．2 函數的復合與可逆函數
　　①函數的復合；②左可逆函數；③右可逆函數；④可逆函數。
　　8．3 無限集
　　①集合的勢；②無限集；③集合的勢相等；④可數無限集；⑤不可數無限集； ⑥集合勢大小的比較。
　　9 圖論
　　9．1 圖的基本概念
　　①有向圖；②無向圖；③頂點集；④邊集；⑤自環；⑥孤立點；⑦多重邊；⑧簡單圖；⑨完全圖；⑩關聯；⑾鄰接；⑿圖的同構；⒀子圖；⒁生成子圖；⒂補圖；⒃圖的頂點度數（次數）；⒄圖的頂點度數和與邊數關系。
　　9．2 圖中的通路、圖的連通性與圖的矩陣表示
　　①圖中的通路；②簡單通路；③初等通路；④回路；⑤簡單回路；⑥初等回路（圈）；⑦連通圖；⑧有向連通圖；⑨有向單側連通圖；⑩有向強連通圖；⑾ 圖的鄰接矩陣；⑿圖的關聯矩陣；⒀圖的可達矩陣。
　　9．3 帶權圖與帶權圖中比較短通路
　　①帶權圖；②帶權圖的比較短通路；③狄克斯瑞（Dijkstra）算法。
　　9．4 歐拉圖
　　①歐拉圖；②歐拉通路；③歐拉回路；④歐拉定理。
　　9．5 哈密爾頓圖與貨郎擔問題
　　①哈密爾頓通路；②哈密爾頓回路（圈）；③哈密爾頓圖；④哈密爾頓圖的必要條件；⑤哈密爾頓圖的充分條件；⑥貨郎擔問題；⑦比較鄰近算法。
　　9．6 二部圖
　　①二部圖（偶圖）；②二部圖的充要條件；③二部圖的匹配；④二部圖的極大匹配；⑤二部圖的完美匹配。
　　9．7 平面圖
　　①平面圖；②平面圖的歐拉定理；③平面圖的必要條件；④平面圖的區域著色。
　　10 樹
　　10．1 樹的基本概念
　　①樹；②樹中頂點與邊關系公式；③樹的等價定義。
　　10．2 連通圖的生成樹與帶權圖的比較小生成樹
　　①連通圖的生成樹；②割集；③割集與生成樹的關系；④帶權圖比較小生成樹的算法。
　　10．3 有序樹
　　①有向樹；②根樹；③有序樹；④有序n (n2)分樹；⑤正則有序n (n2) 分樹。
　　10．4 前綴碼和比較優二分樹
　　①前綴碼；②帶權圖的比較優二分樹；③霍夫曼（Huffman）算法。
　　11 群和環
　　11．1 代數運算的基本概念
　　①二元運算；②封閉的二元運算；③可結合的二元運算；④可交換的二元運算；⑤n元運算
　　11．2 代數系統和半群
　　①代數系統；②左么元；③右么元；④么元；⑤半群；⑥含么半群（獨異點）；⑦半群的同態；⑧子半群；⑨子含么半群。
　　11．3 群的基本概念
　　①左逆元；②右逆元；③逆元；④群；⑤有限群；⑥交換群；⑦群同態；⑧群同構；⑨群中元素的階。
　　11．4 變換群和置換群
　　①變換含么半群；②變換群；③置換群；④n個文字對稱群。
　　11．5 循環群
　　①循環群。
　　11．6 子群、群的子集生成的群
　　①子群。
　　11．7 子群的陪集
　　①子群的陪集；②子群在群中的指數；③群中拉格朗日定理。
　　11．8 正規子群、商群、群同態
　　①正規子群；②商群；③群的同態基本定理。
　　主要參考教材：朱保平,葉有培,張琨.離散數學.北京：北京理工大學出版社，2006