2018北京交通大學(xué)02102 離散數(shù)學(xué)考試大綱

1、2018北京交通大學(xué)02102離散數(shù)學(xué)考試大綱0210202102離散數(shù)學(xué)離散數(shù)學(xué)1、命題邏輯的基本概念。、命題邏輯的基本概念。掌握命題、聯(lián)結(jié)詞、命題公式、真值表。2、命題邏輯等值演算。、命題邏輯等值演算。掌握等價公式、重言式、蘊(yùn)含式、等值演算，合取范式、析取范式、主合取范式及主析取范式。3、命題邏輯的推理理論。、命題邏輯的推理理論。掌握命題推理理論。4、一階邏輯基本概念。、一階邏輯基本概念。掌握謂詞、量詞、謂詞公式。5、一階邏輯等值演

2、算與推理。、一階邏輯等值演算與推理。掌握謂詞演算公式的前束范式，謂詞演算公式真值的求解方法，謂詞推理理論。6、集合代數(shù)理解集合運(yùn)算和集合等式證明。、集合代數(shù)理解集合運(yùn)算和集合等式證明。掌握集合的概念和表示，集合元素計數(shù)。7、二元關(guān)系。、二元關(guān)系。（1）理解關(guān)系的定義，表示和性質(zhì)，等價關(guān)系與劃分；（2）掌握關(guān)系的定義，表示和性質(zhì)，偏序關(guān)系，哈斯圖與極值。8、函數(shù)。、函數(shù)。了解函數(shù)的定義與性質(zhì)，函數(shù)復(fù)合運(yùn)算與逆函數(shù)。9、代數(shù)系統(tǒng)。、代數(shù)系統(tǒng)

3、。掌握代數(shù)系統(tǒng)概念，代數(shù)系統(tǒng)同態(tài)，同構(gòu)映射。1010、群與環(huán)。、群與環(huán)。掌握半群，獨(dú)異點(diǎn)，單位元，零元，群，子群，交換群，循環(huán)群，有限群，置換群，商群，陪集，環(huán)，整環(huán)，無零因子環(huán)的定義；（2）群，子群，循環(huán)群，有限群，環(huán)，整環(huán)的性質(zhì)和判別方法。1111、格與布爾代數(shù)。、格與布爾代數(shù)。（1）理解格的同態(tài)的概念；（2）掌握格、子格、分配格和有補(bǔ)格的定義和基本性質(zhì)；（3）子格、分配格和有補(bǔ)格的判定方法；（4）有限布爾代數(shù)的結(jié)構(gòu)和性質(zhì)。1212

4、、圖的基本概念。圖的基本概念。（1）了解圖的運(yùn)算。理解有向圖、無向圖、通路、回路；（2）掌握握手定理及推論，圖的矩陣表示及應(yīng)用。1313、歐拉圖與哈密頓圖。、歐拉圖與哈密頓圖。（1）理解歐拉圖，歐拉通路和回路，哈密爾頓圖，哈密爾頓通路和回路；（2）掌握歐拉圖的性質(zhì)和判定方法，哈密爾頓圖的性質(zhì)和某些哈密爾頓圖的判定方法，Dijkstra標(biāo)號法求最短路徑；（3）了解中國郵遞員問題，貨郎擔(dān)問題。1414、樹。、樹。（1）掌握求最小生成樹的多種

5、算法，根樹的行遍方法，最優(yōu)二叉樹和Huffman算法；（2）熟練無向樹及其性質(zhì)，根樹的相關(guān)概念。1515、平面圖。、平面圖。（1）理解平面圖的概念，平面圖的對偶圖及其應(yīng)用；（2）掌握歐拉公式及相關(guān)定理，平面圖或極大平面圖的性質(zhì)和判定條件。1616、理解支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集、匹配，、理解支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集、匹配，Hall定理。定理。掌握邊覆蓋與匹配之間的關(guān)系、最大匹配或完美匹配存在的條件；了解點(diǎn)著色，點(diǎn)色

6、數(shù)，邊色數(shù)，色多項式，平面圖4色猜想。2018北京交通大學(xué)02102離散數(shù)學(xué)考試大綱0210202102離散數(shù)學(xué)離散數(shù)學(xué)1、命題邏輯的基本概念。、命題邏輯的基本概念。掌握命題、聯(lián)結(jié)詞、命題公式、真值表。2、命題邏輯等值演算。、命題邏輯等值演算。掌握等價公式、重言式、蘊(yùn)含式、等值演算，合取范式、析取范式、主合取范式及主析取范式。3、命題邏輯的推理理論。、命題邏輯的推理理論。掌握命題推理理論。4、一階邏輯基本概念。、一階邏輯基本概念。掌握謂

7、詞、量詞、謂詞公式。5、一階邏輯等值演算與推理。、一階邏輯等值演算與推理。掌握謂詞演算公式的前束范式，謂詞演算公式真值的求解方法，謂詞推理理論。6、集合代數(shù)理解集合運(yùn)算和集合等式證明。、集合代數(shù)理解集合運(yùn)算和集合等式證明。掌握集合的概念和表示，集合元素計數(shù)。7、二元關(guān)系。、二元關(guān)系。（1）理解關(guān)系的定義，表示和性質(zhì)，等價關(guān)系與劃分；（2）掌握關(guān)系的定義，表示和性質(zhì)，偏序關(guān)系，哈斯圖與極值。8、函數(shù)。、函數(shù)。了解函數(shù)的定義與性質(zhì)，函數(shù)復(fù)合

8、運(yùn)算與逆函數(shù)。9、代數(shù)系統(tǒng)。、代數(shù)系統(tǒng)。掌握代數(shù)系統(tǒng)概念，代數(shù)系統(tǒng)同態(tài)，同構(gòu)映射。1010、群與環(huán)。、群與環(huán)。掌握半群，獨(dú)異點(diǎn)，單位元，零元，群，子群，交換群，循環(huán)群，有限群，置換群，商群，陪集，環(huán)，整環(huán)，無零因子環(huán)的定義；（2）群，子群，循環(huán)群，有限群，環(huán)，整環(huán)的性質(zhì)和判別方法。1111、格與布爾代數(shù)。、格與布爾代數(shù)。（1）理解格的同態(tài)的概念；（2）掌握格、子格、分配格和有補(bǔ)格的定義和基本性質(zhì)；（3）子格、分配格和有補(bǔ)格的判定方法；（

9、4）有限布爾代數(shù)的結(jié)構(gòu)和性質(zhì)。1212、圖的基本概念。圖的基本概念。（1）了解圖的運(yùn)算。理解有向圖、無向圖、通路、回路；（2）掌握握手定理及推論，圖的矩陣表示及應(yīng)用。1313、歐拉圖與哈密頓圖。、歐拉圖與哈密頓圖。（1）理解歐拉圖，歐拉通路和回路，哈密爾頓圖，哈密爾頓通路和回路；（2）掌握歐拉圖的性質(zhì)和判定方法，哈密爾頓圖的性質(zhì)和某些哈密爾頓圖的判定方法，Dijkstra標(biāo)號法求最短路徑；（3）了解中國郵遞員問題，貨郎擔(dān)問題。1414、

10、樹。、樹。（1）掌握求最小生成樹的多種算法，根樹的行遍方法，最優(yōu)二叉樹和Huffman算法；（2）熟練無向樹及其性質(zhì)，根樹的相關(guān)概念。1515、平面圖。、平面圖。（1）理解平面圖的概念，平面圖的對偶圖及其應(yīng)用；（2）掌握歐拉公式及相關(guān)定理，平面圖或極大平面圖的性質(zhì)和判定條件。1616、理解支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集、匹配，、理解支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集、匹配，Hall定理。定理。掌握邊覆蓋與匹配之間的關(guān)系、最大匹配