離散數(shù)學(xué)考試大綱

離散數(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)的推理過程2.2命題演算的假設(shè)推理系統(tǒng)①假設(shè)推理系統(tǒng)的組成②假設(shè)推理系統(tǒng)的推理過程2.3命題演算的歸結(jié)推理法①歸結(jié)證明過程②歸結(jié)證明方法3謂詞演算基礎(chǔ)3.1謂詞和個(gè)體①個(gè)體②謂詞③語句的符號(hào)化3.2函數(shù)和量詞①函數(shù)項(xiàng)②量詞3.4永真性和可滿足性①真假性②同真假性③永真性和可滿足性④范式4謂詞演算的推理理論4.1謂詞演算的永真公理系統(tǒng)①公理系統(tǒng)的組成部分②公理系統(tǒng)的推理過程4.2謂詞演算的假設(shè)推理系統(tǒng)①假設(shè)推理系統(tǒng)的組成及證明方法②定理的推導(dǎo)過程4.3謂詞演算的歸結(jié)系統(tǒng)①置換②歸結(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ū)Γ虎诩系牡芽柗e集；③有序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)系與集合的劃分①等價(jià)關(guān)系；②等價(jià)類；③集合的劃分；④商集合。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圖的基本概念①有向圖；②無向圖；③頂點(diǎn)集；④邊集；⑤自環(huán)；⑥孤立點(diǎn)；⑦多重邊；⑧簡單圖；⑨完全圖；⑩關(guān)聯(lián)；⑾鄰接；⑿圖的同構(gòu)；⒀子圖；⒁生成子圖；⒂補(bǔ)圖；⒃圖的頂點(diǎn)度數(shù)（次數(shù)）；⒄?qǐng)D的頂點(diǎn)度數(shù)和與邊數(shù)關(guān)系。9．2圖中的通路、圖的連通性與圖的矩陣表示①圖中的通路；②簡單通路；③初等通路；④回路；⑤簡單回路；⑥初等回路（圈）；⑦連通圖；⑧有向連通圖；⑨有向單側(cè)連通圖；⑩有向強(qiáng)連通圖；⑾圖的鄰接矩陣；⑿圖的關(guān)聯(lián)矩陣；⒀圖的可達(dá)矩陣。9．3帶權(quán)圖與帶權(quán)圖中最短通路①帶權(quán)圖；②帶權(quán)圖的最短通路；③狄克斯瑞（Dijkstra）算法。9．4歐拉圖①歐拉圖；②歐拉通路；③歐拉回路；④歐拉定理。9．5哈密爾頓圖與貨郎擔(dān)問題①哈密爾頓通路；②哈密爾頓回路（圈）；③哈密爾頓圖；④哈密爾頓圖的必要條件；⑤哈密爾頓圖的充分條件；⑥貨郎擔(dān)問題；⑦最鄰近算法。9．6二部圖①二部圖（偶圖）；②二部圖的充要條件；③二部圖的匹配；④二部圖的極大匹配；⑤二部圖的完美匹配。9．7平面圖①平面圖；②平面圖的歐拉定理；③平面圖的必要條件；④平面圖的區(qū)域著色。10樹10．1樹的基本概念①樹；②樹中頂點(diǎn)與邊關(guān)系公式；③樹的等價(jià)定義。10．2連通圖的生成樹與帶權(quán)圖的最小生成樹①連通圖的生成樹；②割集；③割集與生成樹的關(guān)系；④帶權(quán)圖最小生成樹的算法。10．3有序樹①有向樹；②根樹；③有序樹；④有序n(n2)分樹；⑤正則有序n(n2)分樹。10．4前綴碼和最優(yōu)二分樹①前綴碼；②帶權(quán)圖的最優(yōu)二分樹；③霍夫曼（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變換群和置換群①變換含么半群；②變換群；③置換群；④n個(gè)文字對(duì)稱群。11．5循環(huán)群①循環(huán)群。11．6子群、群的子集生成的群①子群。11．7