2019北京交通大學(xué)02102離散數(shù)學(xué)專業(yè)課考試大綱

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

2、集合運(yùn)算和集合等式證明。掌握集合的概念和表示，集合元素計(jì)數(shù)。7、二元關(guān)系。（1）理解關(guān)系的定義，表示和性質(zhì)，等價(jià)關(guān)系與劃分；（2）掌握關(guān)系的定義，表示和性質(zhì)，偏序關(guān)系，哈斯圖與極值。8、函數(shù)。了解函數(shù)的定義與性質(zhì)，函數(shù)復(fù)合運(yùn)算與逆函數(shù)。9、代數(shù)系統(tǒng)。掌握代數(shù)系統(tǒng)概念，代數(shù)系統(tǒng)同態(tài)，同構(gòu)映射。10、群與環(huán)。掌握半群，獨(dú)異點(diǎn)，單位元，零元，群，子群，交換群，循環(huán)群，有限群，置換群，商群，陪集，環(huán)，整環(huán)，無零因子環(huán)的定義；（2）群，子群，循環(huán)

3、群，有限群，環(huán)，整環(huán)的性質(zhì)和判別方法。11、格與布爾代數(shù)。（1）理解格的同態(tài)的概念；（2）掌握格、子格、分配格和有補(bǔ)格的定義和基本性質(zhì)；（3）子格、分配格和有補(bǔ)格的判定方法；（4）有限布爾代數(shù)的結(jié)構(gòu)和性質(zhì)。12、圖的基本概念。（1）了解圖的運(yùn)算。理解有向圖、無向圖、通路、回路；（2）掌握握手定理及推論，圖的矩陣表示及應(yīng)用。13、歐拉圖與哈密頓圖。（1）理解歐拉圖，歐拉通路和回路，哈密爾頓圖，哈密爾頓通路和回路；（2）掌握歐拉圖的性質(zhì)和判

4、定方法，哈密爾頓圖的性質(zhì)和某些哈密爾頓圖的判定方法，Dijkstra標(biāo)號(hào)法求最短路徑；（3）了解中國(guó)郵遞員問題，貨郎擔(dān)問題。14、樹。（1）掌握求最小生成樹的多種算法，根樹的行遍方法，最優(yōu)二叉樹和Huffman算法；（2）熟練無向樹及其性質(zhì)，根樹的相關(guān)概念。15、平面圖。（1）理解平面圖的概念，平面圖的對(duì)偶圖及其應(yīng)用；（2）掌握歐拉公式及相關(guān)定理，平面圖或極大平面圖的性質(zhì)和判定條件。16、理解支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集、匹配，