南京理工大學(xué)離散數(shù)學(xué)2011年考研大綱

來源：網(wǎng)絡(luò) 時間：2010-08-24 11:20:43

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