2021大連海事大學(xué)離散數(shù)學(xué)專業(yè)研究生考試大綱 正文

考試科目：離散數(shù)學(xué)
試卷滿分及考試時(shí)間:試卷滿分為100分，考試時(shí)間為180分鐘。

一、命題邏輯
考試內(nèi)容
命題，連接詞的真值，重言式/矛盾式/可滿足式，  代入規(guī)則與替換規(guī)則，等價(jià)與蘊(yùn)含，對(duì)偶式與對(duì)偶原理，連接詞的最小功能完備集，范式與主范式，命題邏輯的推理規(guī)則法

考試要求
1．理解命題的概念，理解連接詞的真值（特別是單條件連接詞的真值）。
2．簡(jiǎn)要了解 重言式/矛盾式/可滿足式， 以及 代入規(guī)則與替換規(guī)則。
3．掌握等價(jià)式和蘊(yùn)含式的的推導(dǎo)，掌握常見(jiàn)的基本等價(jià)式和基本蘊(yùn)含式。
4．簡(jiǎn)要了解對(duì)偶式的概念與對(duì)偶原理的公式。
5．了解連接詞的最小功能完備集。
6．掌握范式的概念，特別是主范式的概念，會(huì)求命題公式的主析取范式和主合取范式，并能表示成mi和ΠMj的形式。
7．重點(diǎn)掌握推理規(guī)則法的證明題。

二、謂詞邏輯
謂詞，量詞與全總個(gè)體域與特性謂詞，謂詞公式，自由變?cè)c約束變?cè)?，謂詞公式的等價(jià)式與蘊(yùn)含式，謂詞邏輯的推理規(guī)則法

考試要求
1．理解謂詞的概念，會(huì)使用謂詞和量詞對(duì)一個(gè)問(wèn)題符號(hào)化，特別要理解符號(hào)化時(shí)默認(rèn)個(gè)體域是全總個(gè)體域時(shí)的處理。
2．簡(jiǎn)要了解什么是自由變?cè)c約束變?cè)?br /> 3．掌握謂詞公式的等價(jià)推導(dǎo)和蘊(yùn)含推導(dǎo)（重點(diǎn)是一元量詞公式的量詞轉(zhuǎn)換律，量詞轄域擴(kuò)大收縮律和量詞分配律）
4．重點(diǎn)掌握謂詞邏輯的推理規(guī)則法的證明題

三、集合
集合的基本概念和基本定理，集合的運(yùn)算，容斥原理，笛卡爾積

考試要求
1．理解空集、全集、冪集的概念的理解，會(huì)熟練求冪集。掌握集合相等的判定定理、空集的屬性定理以及冪集計(jì)數(shù)定理。
2．掌握集合的基本運(yùn)算和常見(jiàn)的集合等式，會(huì)做集合等式的證明推導(dǎo)。
3．了解容斥原理，會(huì)做簡(jiǎn)單的利用容斥原理的計(jì)算問(wèn)題。
4．掌握笛卡爾積的概念及其性質(zhì)，笛卡爾積元素計(jì)數(shù)公式。

四、二元關(guān)系
關(guān)系的概念及其性質(zhì)，關(guān)系圖與關(guān)系矩陣，關(guān)系的運(yùn)算，等價(jià)關(guān)系與劃分，偏序關(guān)系

考試要求
1．理解關(guān)系的概念，集合上能建立有多少種不同的二元關(guān)系的計(jì)算
2．從定義、關(guān)系圖、關(guān)系矩陣三個(gè)角度理解關(guān)系的5個(gè)性質(zhì)（自反、反自反、對(duì)稱、反對(duì)稱和傳遞性）
3．掌握關(guān)系的的合成運(yùn)算、逆運(yùn)算和閉包運(yùn)算（自反閉包、對(duì)稱閉包、傳遞閉包）
4．掌握劃分、等價(jià)關(guān)系、等價(jià)類的概念，理解非空集合X上的等價(jià)關(guān)系與X的劃分是一一對(duì)應(yīng)的。
5．給定等價(jià)關(guān)系，會(huì)求對(duì)應(yīng)的劃分；給定劃分，會(huì)求的對(duì)應(yīng)的等價(jià)關(guān)系（掌握笛卡爾積的概念及其性質(zhì)，笛卡爾積元素計(jì)數(shù)公式。
6．重點(diǎn)掌握等價(jià)關(guān)系相關(guān)的證明題。
7．偏序關(guān)系的定義，會(huì)畫偏序關(guān)系的的哈斯圖，并會(huì)求最大元和最小元、極大元和極小元、上界和下界、上確界和下確界。

五、函數(shù)
函數(shù)的概念，滿射、單射、雙射函數(shù)，復(fù)合函數(shù)，逆函數(shù)

考試要求
1．理解函數(shù)的概念，特別是函數(shù)（或映射）的全域性和惟一性。
2．會(huì)計(jì)算函數(shù)個(gè)數(shù)：設(shè)X和Y都為有限集,則從X到Y(jié)共有|Y||X|不同的函數(shù)。
3．理解滿射、單射、雙射函數(shù)。
4．會(huì)求復(fù)合函數(shù)。
5．了解逆函數(shù)的概念。

六、代數(shù)系統(tǒng)
代數(shù)運(yùn)算的性質(zhì)，特異元，可約性，代數(shù)系統(tǒng)的概念，同態(tài)/同構(gòu)，代換性質(zhì)與同余關(guān)系。

考試要求
1．理解代數(shù)運(yùn)算的封閉性，交換性、結(jié)合性、分配性等。會(huì)做性質(zhì)判斷的計(jì)算題。掌握常見(jiàn)的特異元（幺元、零元、逆元等），并會(huì)熟練計(jì)算。了解可約性及其可約性的判定定理。
2．代數(shù)系統(tǒng)的概念和子代數(shù)系統(tǒng)的概念，要會(huì)證一個(gè)代數(shù)系統(tǒng)A是代數(shù)系統(tǒng)B的子代數(shù)。
3．重點(diǎn)理解同態(tài)、同構(gòu)，理解同態(tài)與同構(gòu)的性質(zhì)，會(huì)做同態(tài)、同構(gòu)的證明題。
4．簡(jiǎn)要了解代換性質(zhì)與同余關(guān)系的概念。

七、群
半群、子半群、循環(huán)半群，群，阿貝爾群，群同態(tài)，循環(huán)群，子群。

考試要求
1．了解半群、子半群、循環(huán)半群的概念。
2．理解群的概念及群的基本性質(zhì)，會(huì)證明給定的代數(shù)系統(tǒng)是否是群，會(huì)證明阿貝爾群以及群同態(tài)（同構(gòu)）問(wèn)題的證明。
3．理解循環(huán)群概念以及循環(huán)群的分類
4．理解子群的概念，掌握子群的證明方法。

八、圖
圖的相關(guān)基本概念，子圖，路徑與連通性，圖的矩陣表示

考試要求
1．理解簡(jiǎn)單圖的概念、特別度相關(guān)的概念、掌握握手定理與奇結(jié)點(diǎn)個(gè)數(shù)必是偶數(shù)的定理，零圖、平凡圖、正則圖、完全圖的概念，以及完全圖的邊數(shù)定理。會(huì)判斷圖同構(gòu)的問(wèn)題。
2．理解常見(jiàn)的幾種子圖的概念，特別是生成子圖和導(dǎo)出子圖，會(huì)求相對(duì)于完全圖的補(bǔ)圖。
3．理解基本路徑/簡(jiǎn)單路徑，可達(dá)性，掌握無(wú)向圖和有向圖的連通性及分圖（分支）的概念以及相關(guān)的定理。
4．圖的矩陣表示中主要理解鄰接矩陣A（無(wú)向圖/有向圖）、AAT、 ATA、Am表示的意義。

九、特殊圖
歐拉圖與哈密頓圖，平面圖，樹與生成樹

考試要求
1．理解歐拉圖的概念，掌握判斷無(wú)向圖是歐拉圖的歐拉定理。
2．了解哈密頓圖的概念。
3．會(huì)用簡(jiǎn)單連通平面圖的歐拉不等式結(jié)合握手定理做計(jì)算或證明。會(huì)用庫(kù)拉托夫斯基定理 判斷平面圖還是非平面圖。
4．理解樹的概念以及樹的六個(gè)等價(jià)定義、（最?。┥蓸?、根樹、（完全）m叉樹的概念。
5．會(huì)做 樹相關(guān)的計(jì)算題，會(huì)求最小生成樹，會(huì)求最優(yōu)二叉樹（Huffman樹）。

參閱：
《離散數(shù)學(xué)》趙廣利  大連海事大學(xué)出版社

大連海事大學(xué)

本文來(lái)源：http://www.scstrans.com/dalianhaishi/cankaoshumu_366483.html