《離散數(shù)》復(fù)習(xí)知識(shí)點(diǎn)

1、第1章集合及其運(yùn)算考核知識(shí)點(diǎn)1. 集合，元素，集合的表示，全集，空集2 集合的包含、相等，子集，幕集3. 集合的并、交、補(bǔ)、差、對(duì)稱(chēng)差等運(yùn)算及其運(yùn)算律4容斥原理考核要求1理解集合的概念，容斥原理.2. 理解集合的包含、子集、相等和幕集等概念，熟練掌握集合的表示方法和集合的并、 交、補(bǔ)、差和對(duì)稱(chēng)差等運(yùn)算，會(huì)用文氏圖表示集合的各種運(yùn)算.3掌握用集合運(yùn)算基本規(guī)律證明集合恒等式的方法.4掌握利用容斥原理進(jìn)行計(jì)數(shù)的方法.第2章關(guān)系與函數(shù)考核知識(shí)點(diǎn)1. 有序?qū)偷芽▋悍e2關(guān)系及其運(yùn)算性質(zhì)3. 二元關(guān)系的矩陣與圖4. 復(fù)合關(guān)系與逆關(guān)系5. 二元關(guān)系的性質(zhì)6. 等價(jià)關(guān)系與等價(jià)類(lèi)7. 偏序關(guān)系、復(fù)蓋集與哈斯圖，

2、極大 （小）元，最大（?。┰?，上（下）界，最小上界，最大 下界&函數(shù)反函數(shù)復(fù)合函數(shù)單射滿射和雙射考核要求1. 了解有序?qū)偷芽▋悍e的概念，掌握笛卡兒積的運(yùn)算.2. 理解關(guān)系的概念：包括二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系.掌握關(guān)系的集合表 示、關(guān)系矩陣和關(guān)系圖，掌握關(guān)系的運(yùn)算.3. 掌握求復(fù)合關(guān)系和逆關(guān)系的方法.4 .理解關(guān)系的性質(zhì)（自反性和反自反性、對(duì)稱(chēng)性和反對(duì)稱(chēng)性、傳遞性），掌握其判別方法.5. 理解等價(jià)關(guān)系和偏序關(guān)系概念，掌握等價(jià)關(guān)系、偏序關(guān)系的判定，掌握等價(jià)類(lèi)、復(fù)蓋集的求法和作偏序關(guān)系哈斯圖的方法.知道極大（?。┰?，最大（?。┰母拍?，會(huì)求極大（小）元、最大（小）元、最小上界和最

3、大下界.6. 理解函數(shù)概念：函數(shù)（映射），函數(shù)相等，復(fù)合函數(shù)和反函數(shù).7. 理解單射、滿射和雙射等概念，掌握其判別方法.第3章圖的基本概念與性質(zhì)考核知識(shí)點(diǎn)1 圖的概念與表示，有向圖，無(wú)向圖，簡(jiǎn)單圖，完全圖，結(jié)點(diǎn)的度數(shù)，圖的同構(gòu)，子 圖、補(bǔ)圖2通路，通路的長(zhǎng)度，初級(jí)通路，簡(jiǎn)單通路，回路，初級(jí)回路，簡(jiǎn)單回路3圖的連通性與連通度概念、判定，點(diǎn)割集與割點(diǎn)，邊割集與割邊4. 圖的矩陣表示、鄰接矩陣、可達(dá)性矩陣及其計(jì)算5 .最短路徑考核要求1. 理解圖的基本概念：結(jié)點(diǎn)、邊、有向圖，無(wú)向圖、簡(jiǎn)單圖、完全圖、結(jié)點(diǎn)的度數(shù)、 圖的同構(gòu)子圖等，理解握手定理.2. 了解通路與回路的概念：簡(jiǎn)單通路、初級(jí)通路和復(fù)雜通路，

4、簡(jiǎn)單回路、初級(jí)回路和 復(fù)雜回路，會(huì)求通路和回路的長(zhǎng)度.3. 了解無(wú)向圖的連通性，會(huì)求無(wú)向圖的連通分支.了解點(diǎn)割集、割點(diǎn)、邊割集、割邊、 點(diǎn)連通度、邊連通度等概念.4. 了解有向圖的強(qiáng)連通性、單向連通性、弱連通性；會(huì)判別有向圖連通性的類(lèi)型.5. 理解圖的矩陣表示法、鄰接矩陣、可達(dá)性矩陣的概念，掌握鄰接矩陣、可達(dá)性矩陣 的有關(guān)計(jì)算.6. 知道最短路徑的概念，會(huì)最短路徑的算法.第4章幾種特殊圖考核知識(shí)點(diǎn)1. 歐拉通路（回路），歐拉圖2 .哈密頓通路（回路），哈密頓圖3. 平面圖，歐拉公式4. 對(duì)偶圖及著色考核要求1. 了解歐拉回路、歐拉圖的概念及性質(zhì)，掌握歐拉圖的判別方法.2. 了解漢密爾頓回路、漢

5、密爾頓圖的概念及性質(zhì)，掌握漢密爾頓圖的判別方法.3. 了解平面圖的概念：平面圖、面、邊界、面的次數(shù)和非平面圖，掌握平面圖的判別 方法，掌握歐拉公式的應(yīng)用.4. 理解平面圖與對(duì)偶圖的關(guān)系、對(duì)偶圖在圖著色中的作用，掌握著色算法；5. 掌握?qǐng)D論中常用的證明方法.第5章樹(shù)及其應(yīng)用考核知識(shí)點(diǎn)1 .樹(shù)的定義及性質(zhì)Kruskal 算法2. 生成樹(shù)與最小生成樹(shù)的概念，最小生成樹(shù)的3. 根樹(shù)的概念及性質(zhì)4. 最優(yōu)樹(shù)的概念，最優(yōu)樹(shù)的Huffman算法，前綴碼的求法考核要求1. 了解無(wú)向樹(shù)、樹(shù)葉、分支點(diǎn)、平凡樹(shù)、生成樹(shù)和最小生成樹(shù)等概念及性質(zhì)，掌握最 小生成樹(shù)的Kruskal算法.2. 了解有向樹(shù)、根樹(shù)、有序樹(shù)、最

6、優(yōu)二元（叉）樹(shù)等概念及性質(zhì)，掌握最優(yōu)樹(shù)的 算法.3掌握利用最優(yōu)樹(shù)產(chǎn)生前綴碼的方法.第6章命題邏輯考核知識(shí)點(diǎn)1. 命題與聯(lián)結(jié)詞（否定、析取、合取、蘊(yùn)含、等價(jià) ），真值與真值表2命題公式的解釋3. 命題公式的等值式與蘊(yùn)涵式，等值演算4. 析取范式、合取范式、極小 （大）項(xiàng)，主析取范式、主合取范式的概念與求法5命題邏輯的推理理論考核要求1理解命題聯(lián)結(jié)詞概念，掌握命題公式的翻譯（命題符號(hào)化）及判斷語(yǔ)句是不是命題 的方法.2. 熟練掌握求給定公式真值表的方法.3. 掌握基本等值式以及用真值表法和等值演算法判別公式類(lèi)型和公式等值的方法.4. 了解析?。ê先。┓妒礁拍睿斫鈽O?。ù螅╉?xiàng)的概念和主析?。ê先。┓妒礁拍?握用基本等值式或真值表將公式化為主析?。ê先。┓妒降姆椒?5. 掌握命題公式的的直接證明方法與間接證明方法.第7章謂詞邏輯考核知識(shí)點(diǎn)1 .謂詞，量詞，個(gè)體詞，個(gè)體域，變?cè)?. 謂詞公式的解釋3. 前束范式的概念與求法4. 謂詞公式的等值式與蘊(yùn)涵式5. 謂詞邏輯的推理理論考核要求1.理解謂詞、量詞、個(gè)體詞、個(gè)體域、全域、原子公式、謂詞公式和變?cè)雀拍?掌 握謂詞公式的翻譯.2 .掌握在有限個(gè)體域下消去公式的量詞