離散數(shù)學(xué)復(fù)習

1、1西安交通大學(xué)西安交通大學(xué)電子與信息工程學(xué)院電子與信息工程學(xué)院計算機系計算機系2離散數(shù)學(xué) 第三章第三章 集集 合合 重點要求重點要求 w掌握集合、子集、全集、空集、單元素集等概念掌握集合、子集、全集、空集、單元素集等概念, ,掌握集合的四大掌握集合的四大性質(zhì)性質(zhì): :任意性任意性(抽象性抽象性)、確定性、無序性、無重復(fù)性、確定性、無序性、無重復(fù)性, ,熟悉常用的表熟悉常用的表示集合的方法以及用文氏圖來表示集合的方法示集合的方法以及用文氏圖來表示集合的方法, ,能夠判定元素與集能夠判定元素與集合合, ,集合與集合之間的關(guān)系集合與集合之間的關(guān)系. .理解兩個集合間的包含關(guān)系和相等關(guān)系理解兩個集合間

2、的包含關(guān)系和相等關(guān)系(外延性原理外延性原理)的定義和性質(zhì)的定義和性質(zhì), ,能夠利用這些定義、性質(zhì)來證明兩個能夠利用這些定義、性質(zhì)來證明兩個更復(fù)雜的集合的包含和相等。更復(fù)雜的集合的包含和相等。w掌握冪集的定義及計算有限集的冪集所含元素個數(shù)，所使用的計掌握冪集的定義及計算有限集的冪集所含元素個數(shù)，所使用的計算、證明的方法和思想。算、證明的方法和思想。w理解理解差別在于級別差別在于級別! !的判定集合間關(guān)系的思想。的判定集合間關(guān)系的思想。w掌握集合的五種基本運算掌握集合的五種基本運算: :交、并、余交、并、余(補補)、差和對稱差、差和對稱差(環(huán)和環(huán)和)的的定義定義, ,并熟記集合運算的基本定理并熟記

3、集合運算的基本定理(公式公式), ,能夠熟練的利用它們來證能夠熟練的利用它們來證明更復(fù)雜的集合公式。明更復(fù)雜的集合公式。屬于屬于 包含包含 相等相等 并集并集 差集差集 對稱差（環(huán)和）對稱差（環(huán)和） 冪集冪集3離散數(shù)學(xué) 第四章第四章 關(guān)關(guān) 系系 重點要求重點要求 w掌握序偶和笛卡爾積的概念掌握序偶和笛卡爾積的概念。（。（元組元組 叉積叉積）w掌握二元關(guān)系的形式定義及其各種表示方法：序偶，矩陣，關(guān)系圖掌握二元關(guān)系的形式定義及其各種表示方法：序偶，矩陣，關(guān)系圖等；能正確使用集合表達式，關(guān)系距陣，關(guān)系圖等表示給定的關(guān)系，等；能正確使用集合表達式，關(guān)系距陣，關(guān)系圖等表示給定的關(guān)系，并要求能夠從一種形式

4、寫出另一種形式。并要求能夠從一種形式寫出另一種形式。w特殊關(guān)系：全關(guān)系、空關(guān)系、幺關(guān)系特殊關(guān)系：全關(guān)系、空關(guān)系、幺關(guān)系w掌握關(guān)系的運算，包括集合運算以及關(guān)系的復(fù)合和關(guān)系的逆運算。掌握關(guān)系的運算，包括集合運算以及關(guān)系的復(fù)合和關(guān)系的逆運算。 關(guān)系，反對稱關(guān)系關(guān)系，反對稱關(guān)系, 對稱差對稱差(環(huán)和環(huán)和)關(guān)系，傳遞關(guān)系關(guān)系，傳遞關(guān)系, 并關(guān)系并關(guān)系w掌握二元關(guān)系的各種特殊性質(zhì)：掌握二元關(guān)系的各種特殊性質(zhì)：自反，反自反，對稱，反對稱，傳自反，反自反，對稱，反對稱，傳遞遞等，并理解這些性質(zhì)如何反映在關(guān)系圖上，關(guān)系矩陣上等。等，并理解這些性質(zhì)如何反映在關(guān)系圖上，關(guān)系矩陣上等。w掌握集合中二元關(guān)系的閉包的意義

5、和其基本性質(zhì)，能求出有限集上掌握集合中二元關(guān)系的閉包的意義和其基本性質(zhì)，能求出有限集上的二元關(guān)系的閉包。的二元關(guān)系的閉包。4離散數(shù)學(xué)w掌握等價關(guān)系的概念，并掌握覆蓋、劃分、等價類、商集的定掌握等價關(guān)系的概念，并掌握覆蓋、劃分、等價類、商集的定義和基本性質(zhì)，弄清楚等價關(guān)系與劃分之間的關(guān)系。牢記等價關(guān)義和基本性質(zhì)，弄清楚等價關(guān)系與劃分之間的關(guān)系。牢記等價關(guān)系的系的分類分類作用。作用。等價關(guān)系等價關(guān)系(R A2) 自反性：自反性： x A，(x, x) R對稱性：對稱性： x, y A，(x，y) R (y，x) R傳遞性：傳遞性： x, y, z A，(x，y) R且且(y，z) R (x，z)

6、R 代表元，等價類代表元，等價類aR = x : x A xRa反對稱性：反對稱性： x, y A，(x，y) R且且(y，x) R x=yw掌握半序、半序集等概念，以及半序集的可比較性、極大元、掌握半序、半序集等概念，以及半序集的可比較性、極大元、極小元、極小元、最大元、最小元、上界、下界、最大下界、最小上界最大元、最小元、上界、下界、最大下界、最小上界、直接后繼等概念。牢記半序關(guān)系的直接后繼等概念。牢記半序關(guān)系的非線性非線性特性。特性。w能畫出能畫出有限半序集的哈斯圖有限半序集的哈斯圖, ,并根據(jù)圖討論半序集的某些性質(zhì)。并根據(jù)圖討論半序集的某些性質(zhì)。w掌握掌握全序集、良序集全序集、良序集等

7、概念；等概念；良序集良序集定理定理3;5離散數(shù)學(xué) 第五章第五章 函函 數(shù)數(shù) 重點要求重點要求 w要求掌握函數(shù)、元素的像、集合的像等基本概念要求掌握函數(shù)、元素的像、集合的像等基本概念,理解元素及集合理解元素及集合的象及原象的定義及相關(guān)的性質(zhì)的象及原象的定義及相關(guān)的性質(zhì)。給定一個函數(shù)給定一個函數(shù),能夠確定一個點能夠確定一個點的象的象,一個集合的象一個集合的象,能夠確定一個點的原象能夠確定一個點的原象,一個集合的原象。一個集合的原象。w弄清單射弄清單射、滿射滿射、雙射之間的區(qū)別雙射之間的區(qū)別。給定一個函數(shù)給定一個函數(shù),要能夠確定它要能夠確定它是否是單射是否是單射、滿射滿射、雙射等雙射等。單射函數(shù)：單

8、射函數(shù)： x1, x2 X，f( (x1) )= f( (x2) ) x1 = x2滿射函數(shù)：滿射函數(shù)： y Y， x X，使，使f( (x) )= yw掌握逆函數(shù)和復(fù)合函數(shù)的定義和性質(zhì)掌握逆函數(shù)和復(fù)合函數(shù)的定義和性質(zhì),并弄清楚它們存在的條件和并弄清楚它們存在的條件和相關(guān)定理。能夠確定兩個函數(shù)的復(fù)合函數(shù)等相關(guān)定理。能夠確定兩個函數(shù)的復(fù)合函數(shù)等。 雙射函數(shù)的逆函數(shù)定理雙射函數(shù)的逆函數(shù)定理 復(fù)合函數(shù)定理復(fù)合函數(shù)定理w掌握集合的勢掌握集合的勢、可數(shù)集、不可數(shù)集等概念、可數(shù)集、不可數(shù)集等概念。無限集合無限集合 可數(shù)集合可數(shù)集合 6離散數(shù)學(xué) 第六章第六章 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 重點要求重點要求 w掌握代數(shù)系

9、統(tǒng)的概念掌握代數(shù)系統(tǒng)的概念,定義定義: 運算的封閉性運算的封閉性、幺元幺元、零元零元、逆元逆元及及相關(guān)的結(jié)論有清晰的理解相關(guān)的結(jié)論有清晰的理解。給定集合和集合上的運算能夠判斷該給定集合和集合上的運算能夠判斷該集合對運算是否封閉集合對運算是否封閉; ;能夠通過運算表確定幺元、能夠通過運算表確定幺元、零元零元、逆元等逆元等(如如果存在的話果存在的話); 對交換律對交換律、結(jié)合律結(jié)合律、分配律分配律、吸收律吸收律、消去律、消去律等的等的表示要十分清楚表示要十分清楚;給定集合和二元運算表能夠判斷運算是否滿足結(jié)給定集合和二元運算表能夠判斷運算是否滿足結(jié)合律等等合律等等。w掌握代數(shù)系統(tǒng)的同態(tài)和同構(gòu)的定義能

10、判斷兩個給定代數(shù)系統(tǒng)間的掌握代數(shù)系統(tǒng)的同態(tài)和同構(gòu)的定義能判斷兩個給定代數(shù)系統(tǒng)間的某個映射是否為同態(tài)同構(gòu)映射某個映射是否為同態(tài)同構(gòu)映射。 同態(tài)公式：同態(tài)公式： x1, x2 X，f( (x1*x2) )= f( (x1) ) f( (x2) ) 滿同態(tài)，定理滿同態(tài)，定理3 (同態(tài)遺傳性定理同態(tài)遺傳性定理(五條五條)；w掌握半群及含幺半群等概念掌握半群及含幺半群等概念。7離散數(shù)學(xué)w掌握群的概念掌握群的概念,并能靈活運用群的一些基本性質(zhì)并能靈活運用群的一些基本性質(zhì),理解群的同態(tài)和同理解群的同態(tài)和同構(gòu)構(gòu)。給定一個代數(shù)系統(tǒng)及其運算給定一個代數(shù)系統(tǒng)及其運算,能夠判斷是否為半群能夠判斷是否為半群、含幺半群含

11、幺半群、群等群等。 封閉性，幺元，逆元，反身律，鞋襪律，交換律，結(jié)合律，交封閉性，幺元，逆元，反身律，鞋襪律，交換律，結(jié)合律，交換群，循環(huán)群、左右陪集，冪等元換群，循環(huán)群、左右陪集，冪等元 ，群的階、元素的階，群的階、元素的階 反身律：反身律：(a-1)-1 =a 鞋襪律：鞋襪律：(a* *b)-1 = b-1* *a-1 w掌握子群的概念并清楚其判別方法掌握子群的概念并清楚其判別方法。w掌握環(huán)掌握環(huán)、整環(huán)整環(huán)、除環(huán)、除環(huán)的定義的定義, ,并熟悉環(huán)的基本性質(zhì)并熟悉環(huán)的基本性質(zhì)。給定集合及兩給定集合及兩個二元運算能夠判斷其是否為環(huán)個二元運算能夠判斷其是否為環(huán)、整環(huán)整環(huán)、除環(huán)、除環(huán)等等。w牢記消去

12、律牢記消去律、無零因子、有逆元三者間的兩層關(guān)系及其運用、無零因子、有逆元三者間的兩層關(guān)系及其運用。 環(huán)環(huán)(R)，子環(huán)，子環(huán)(S) 非空性：非空性：S 包含性：包含性：S R8離散數(shù)學(xué) 減法封閉性：減法封閉性： x, y S，x S y S x y S 乘法封閉性：乘法封閉性： x, y S，x S y S x y S 無零因子環(huán)無零因子環(huán)(S)； x, y S，x, y 0 x y 0w掌握域及有限域的定義掌握域及有限域的定義。 域，素域，有限域；域，素域，有限域；9離散數(shù)學(xué) 第七章第七章 格與布爾代數(shù)格與布爾代數(shù) 重點要求重點要求 w掌握格的兩種定義掌握格的兩種定義(半序格、代數(shù)格半序格、代

13、數(shù)格)及其等價性證明，能夠?qū)τ杉捌涞葍r性證明，能夠?qū)τ砂胄蚣_定的哈斯圖判定其是否為格，能夠?qū)τ嘘P(guān)格的一些論半序集所確定的哈斯圖判定其是否為格，能夠?qū)τ嘘P(guān)格的一些論題進行證明或構(gòu)造反例而將其否證。題進行證明或構(gòu)造反例而將其否證。w熟記格運算的基本運算性質(zhì)熟記格運算的基本運算性質(zhì)(交換律、結(jié)合律、吸收律、冪等律交換律、結(jié)合律、吸收律、冪等律)及其與序的關(guān)系及其與序的關(guān)系(等價性、保序性等價性、保序性)，并會靈活運用。，并會靈活運用。格同態(tài)格同態(tài) 半序格半序格, 定理定理4 (a b a*b = a a b = b)； 10離散數(shù)學(xué)w掌握分配不等式、模不等式等性質(zhì)的證明及應(yīng)用。掌握分配不等式、模

14、不等式等性質(zhì)的證明及應(yīng)用。w掌握分配律、零壹律、互補律等的定義，并清楚它們之間的關(guān)系，掌握分配律、零壹律、互補律等的定義，并清楚它們之間的關(guān)系，對于具體給出的格所對應(yīng)的哈斯圖，應(yīng)能判斷是否為分配格、有界對于具體給出的格所對應(yīng)的哈斯圖，應(yīng)能判斷是否為分配格、有界格或有補格等。格或有補格等。 分配格，分配律；分配格，分配律； 有界格，最小元，最大元，有界格，最小元，最大元， ( a L)(0 a 1) 即即 0*a=0 a*1=a 有補格，補元，互補律，唯一性有補格，補元，互補律，唯一性, ,定理定理1212，有界分配格補元唯一，有界分配格補元唯一w掌握布爾代數(shù)的概念和幾個重要的特例，熟記布爾代數(shù)

15、的許多重掌握布爾代數(shù)的概念和幾個重要的特例，熟記布爾代數(shù)的許多重要的基本性質(zhì)及其與序的關(guān)系，并會靈活運用。要的基本性質(zhì)及其與序的關(guān)系，并會靈活運用。w掌握格和布爾代數(shù)的對偶原理掌握格和布爾代數(shù)的對偶原理,并會靈活運用。并會靈活運用。w掌握布爾代數(shù)的原子概念掌握布爾代數(shù)的原子概念,和布爾表達式的原子表示的概念和布爾表達式的原子表示的概念,并會靈并會靈活運用。熟悉布爾代數(shù)的斯篤定理的內(nèi)容及證明。活運用。熟悉布爾代數(shù)的斯篤定理的內(nèi)容及證明。11離散數(shù)學(xué)12離散數(shù)學(xué)w 能夠利用能夠利用K ning算算法法求哈密頓路或密頓圈，求哈密頓路或密頓圈，能夠利用能夠利用翻邊翻邊法法求求有向哈密頓路或有向密頓圈，

16、有向哈密頓路或有向密頓圈，能夠利用能夠利用近鄰法近鄰法、交換法、交換法求解貨求解貨郎擔問題郎擔問題(最優(yōu)哈密頓圈最優(yōu)哈密頓圈)。 哈密頓圈，哈密頓圖，結(jié)點的度，哈密頓圈，哈密頓圖，結(jié)點的度，D.KD.Knignig定理定理3 3及其推論及其推論1 1 w 掌握掌握二分圖（偶圖）二分圖（偶圖）、奇圈、偶圈、二分圖定理、奇圈、偶圈、二分圖定理1 1，匹配、完美，匹配、完美匹配、最大匹配匹配、最大匹配等等概念，概念，掌握偶圖的掌握偶圖的判別性定理及判別法判別性定理及判別法- -標號標號法（著色法），法（著色法），能夠利用能夠利用匈牙利匈牙利法以增廣路法以增廣路求偶圖的求偶圖的最大匹配最大匹配。w 掌

17、握平面圖掌握平面圖、非、非平面圖平面圖、區(qū)域、區(qū)域( (面面) ) 等等概念概念。 掌握平面圖的掌握平面圖的歐歐拉公式及其拉公式及其必要性判別法和推論、拉邊法，必要性判別法和推論、拉邊法，了解了解Kuratowski平平面圖面圖最后定理，并能用其判別一個圖的平面性最后定理，并能用其判別一個圖的平面性。K K技術(shù)技術(shù)w 掌握掌握樹樹、樹葉、樹叉、樹枝、森林、樹葉、樹叉、樹枝、森林、生成樹生成樹、等概念。掌握樹、等概念。掌握樹的若干等價命題，并能夠利用它們判斷或證明樹的有關(guān)結(jié)論，的若干等價命題，并能夠利用它們判斷或證明樹的有關(guān)結(jié)論，掌握求連通圖的生成樹的破圈法和避圈法，掌握求帶權(quán)連通圖掌握求連通圖的生成樹的破圈法和避圈法，掌握求帶權(quán)連通圖的的最小生成樹最小生成樹的的Kruskal算法和管氏破圈算法算法和管氏破圈算法。13離散數(shù)學(xué)書后習題：書后習題：w 3: 3: 作業(yè)作業(yè)w 4 4： 作業(yè)作業(yè)w 5 5： 作業(yè)作業(yè) + 6 7 8 9 10+ 6 7 8 9 10w 6 6： 作業(yè)作業(yè) + 54 55 58 65+ 54 55 5