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

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

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

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

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

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

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

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

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

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

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