《離散數(shù)學(xué)》總復(fù)習(xí)

《離散數(shù)學(xué)》總復(fù)習(xí)黃玉yuhua2k@163.com南航計算機學(xué)院A12-1161.主范式、集合、布爾格(有補分配格)運算2.命題符號化+命題/謂詞邏輯推理3.前束范式4.元素與集合、集合與集合的關(guān)系(判斷,證明)5.排列組合、容斥原理、遞推方程6.關(guān)系合成、函數(shù)復(fù)合、置換乘法7.等價關(guān)系(等價類、商集、劃分、自然映射)8.偏序集(偏序關(guān)系、覆蓋、哈斯圖)、格9.同構(gòu)=同態(tài)∩雙射10.代數(shù)系統(tǒng)及其性質(zhì)(判斷)11.域=整環(huán)∩除環(huán)0.重要概念:冪集,笛卡積,閉包,積代數(shù),循環(huán)群;0.重要概念:生成子圖,自補圖,自對偶圖,割集12.握手定理13.鄰接矩陣14.最短路徑(標(biāo)號法)與關(guān)鍵路徑(最長路徑)15.圖的類型(二部,歐拉,哈密頓,平面,樹)判別16.平面圖歐拉公式：n

m+r=217.樹的重要性質(zhì)：m=n-118.最小生成樹(避圈法)、基本回路/割集系統(tǒng)19.Huffman算法(最優(yōu)二元樹/最佳前綴碼)20.二/多項式定理與組合恒等式21.分治算法的常用遞推公式第1章命題邏輯1.1命題符號化及聯(lián)結(jié)詞（聯(lián)結(jié)詞是基礎(chǔ)）1.2命題公式及分類1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對偶與范式（主范式演算是重點）1.6推理理論（重點）聯(lián)結(jié)詞與復(fù)合命題(小結(jié))聯(lián)結(jié)詞優(yōu)先級:(),

,

,

,

,

同級按從左到右的順序進行

pq

pp∧qp∨qp

qp

q0010011011011010001001101111基本復(fù)合命題的真值1.3命題邏輯等值演算等值式定義：(A

B1)(A

B)（重點）基本等值式(重點) 雙重否定律

:

A

A等冪律：

A

A

A,A

A

A交換律:A

B

B

A,A

B

B

A結(jié)合律:(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律:A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律:

(A

B)

A

B

(A

B)

A

B基本等值式（續(xù)）吸收律:A

(A

B)

A,A

(A

B)

A零律:A

1

1,A

0

0同一律:A

0

A,

A

1

A排中律:A

A

1矛盾律:A

A

0蘊涵等值式:A

B

A

B等價等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等價否定等值式:A

B

A

B歸謬論:(A

B)

(A

B)

A1.4復(fù)合聯(lián)結(jié)詞（重要的非重點）與非式:p

q(p

q)；或非式:p

q(p

q)習(xí)題1.14，1.10(4)(5)異或：p

q

p

q

(p

q)

p

q

p

qA

p1

p2

…

pn,偶數(shù)個命題變項賦值為1T(A0),奇數(shù)個命題變項賦值為1T(A1);B

q1

q2

…

qn,偶數(shù)個命題變項賦值為0T(A1),奇數(shù)個命題變項賦值為0T(A0).習(xí)題1.221.5主范式（重點）成真賦值i對應(yīng)主析取范式的極小項mi；成假賦值j對應(yīng)主合取范式的極大項Mj。命題公式有幾個成真賦值，主析取范式就是幾個極小項相或(

)；命題公式有幾個成假賦值，主合取范式就是幾個極大項相與(

)。例1.31，1.32分配律Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)習(xí)題1.12(1),1.13(1)。五71.6

命題邏輯推理（重點）“推理正確”定義：(A?B1)(ATB)（重點）A

T(AúB) 附加律(AùB)T

A

化簡律(A?B)ùA

T

B

假言推理(A?B)ù?B

T

?A

拒取式(AúB)ù?B

T

A

析取三段論(A?B)ù(B?C)T(A?C) 假言三段論(A?B)ù(B?C)T(A?C) 等價三段論(A?B)ù(C?D)ù(AúC)T(BúD) 構(gòu)造性二難(A?B)ù(?A?B)ù(Aú?A)T

B

構(gòu)造性二難(特殊形式)(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難習(xí)題1.18,1.21,1.17(2)。六1注意事項1：命題只有能確定真假(但不能可真可假)的陳述句才是命題.不管是正確的觀點,還是錯誤的觀點,都是命題.猜想和預(yù)言是命題,如哥德巴赫猜想.感嘆句,祈使句,疑問句都不是命題.陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題.有些簡單命題貌似復(fù)合命題,要注意區(qū)分.題1(15)注意事項2：蘊涵聯(lián)結(jié)詞“

”p

q的邏輯關(guān)系:p為q的充分條件，q為p的必要條件.“如果p,則q”的多種表述方式：(1)若p,就q.(2)只要p,就q.(3)p僅當(dāng)q.(4)只有q

才p.(5)除非q,才p.(6)除非q,否則非p.p

q為假當(dāng)且僅當(dāng)p為真q為假，即當(dāng)p為假時，p

q為真(不管q為真,還是為假);當(dāng)q為真時，p

q為真(不管p為真,還是為假).習(xí)題1.5(6)(7)了解概念、掌握方法真值表、命題公式類型所有等值的含n個命題變項的公式對應(yīng)同一個n元真值函數(shù)F:{0,1}n

{0,1}；啞元最小聯(lián)結(jié)詞組對偶式與對偶原理簡單析取式、簡單合取式析取范式與合取范式附加前提證明法、反證法第2章一階邏輯2.1 一階邏輯基本概念（量詞是關(guān)鍵）2.2 一階邏輯公式、解釋及分類2.3 一階邏輯等值式、前束范式（重點）2.4 一階邏輯推理理論（重點）一階邏輯與命題邏輯關(guān)系一階邏輯將命題(公式)拆分為個體詞、謂詞、量詞(

、)。謂詞是核心，沒有謂詞，不構(gòu)成命題；量詞是關(guān)鍵。個體詞（元素）分為個體常項和個體變項.個體域（集合）:個體變項的取值范圍.

全總個體域:宇宙間一切事物組成一階邏輯≈命題邏輯+量詞

xF(x)

x

F(x),

xF(x)

x

F(x);

xF(x)

x

F(x),

xF(x)

x

F(x)2.3一階邏輯等值式基本等值式（重點）

:命題邏輯中16組基本等值式的代換實例消去量詞等值式設(shè)D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)量詞轄域收縮與擴張等值式

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)量詞分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)注意事項1：前束范式（重點）設(shè)A為一個一階邏輯公式,若A具有如下形式

Q1x1Q2x2…QkxkB,則稱A為前束范式,其中Qi(1

i

k)為

或

，B為不含量詞的公式.1）對

無分配律，

對

無分配律

xA(x)

xB(x)

x

y(A(x)

B(y))

x

y(A(x)

B(y))

xA(x)

xB(x)2）變量沖突，有一個要換名.3）x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B習(xí)題2.21,2.15(1),2.14(1)。四102.4一階邏輯推理理論（重點）重要的推理定律第一組命題邏輯推理定律代換實例第二組由基本等值式生成（置換規(guī)則）第三組

xA(x)

xB(x)

x(A(x)

B(x))

x(A(x)

B(x))

xA(x)

xB(x)(12)

全稱量詞消去規(guī)則（簡記為UI規(guī)則或UI）(13)

全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG）(14)存在量詞引入規(guī)則（簡記為EG規(guī)則或EG）(15)存在量詞消去規(guī)則（簡記為EI規(guī)則或EI）注:必須先消去存在量詞,后消去全稱量詞.七1第三版:習(xí)題2.22,2.16,2.19,2.17(1),2.23；例2.18注意事項2：一階邏輯中命題符號化無特別要求，用全總個體域量詞順序一般不要隨便顛倒

x

yA(x,y)

y

xA(x,y)全稱量詞一般對應(yīng)“”存在量詞一般對應(yīng)“”習(xí)題2.3(2)(5)(6)了解有限個體域,無限個體域;謂詞常項,謂詞變項,一元謂詞,多元謂詞(n元謂詞,n

2),0元謂詞,原子公式;項字母表包含：1)個體常項,2)個體變項,3)函數(shù)符號,4)謂詞符號,5)量詞符號(

,),6)聯(lián)結(jié)詞符號(

,

,

,

,),7)括號與逗號.指導(dǎo)變元，轄域，約束出現(xiàn)，自由出現(xiàn)閉式:不含自由出現(xiàn)的個體變項的公式.解釋I包含：(a)非空個體域DI,(b)DI中一些特定元素集,(c)DI上特定函數(shù)集,(d)DI上特定謂詞集.閉式在任何解釋下都是命題，不是閉式的公式在某些解釋下也可能是命題.公式類型.換名規(guī)則與代替規(guī)則第3章集合的基本概念和運算3.1集合的基本概念3.2集合的基本運算（重點）3.3集合中元素的計數(shù)（容斥原理是重點）3.1集合的基本概念元素x與集合A的關(guān)系：屬于x

A，不屬于x

A集合A與集合B的關(guān)系：習(xí)題3.2,3.8,3.12,3.16

包含(子集)A

B,不包含A?B

相等A=B,不相等A

B

真包含A

B,

不真包含A

B重要概念：集合A的冪集P(A)={x|x

A}。如果|A|=n，則|P(A)|=2n.習(xí)題3.14(4),3.18習(xí)題3.3,3.9,3.113.2集合的基本運算（重點）集合運算符，，，分別對應(yīng) 聯(lián)結(jié)詞∧,∨，，A

B=A

B=A

(A

B)A

B=(A

B)

(B

A)=(A

B)(A

B)

A

B

A

A

BA

B

A

B=B

A

B=A

A

B=

A

B=

A

B=A習(xí)題3.17,3.16；例3.17，3.18。四3，4；六4集合運算的文氏圖表示習(xí)題3.4,3.15(2)集合運算的算律（重點）

交換A

B=B

AA

B=B

AA

B=B

A結(jié)合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)冪等A

A=AA

A=A

與

與

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A吸收律的前提：、可交換集合運算的算律（續(xù)）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C雙重否定

A=A

E補元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=3.3集合中元素的計數(shù)容斥原理及其推論（重點）習(xí)題3.6,3.18,3.19。五10注意1）0是自然數(shù).2）對于任何集合A和元素x(可以是集合)，

x

A和x

A兩者成立其一，且僅成立其一.3）和

是不同層次的問題.4）空集是任何集合的子集.5）在給定問題中，全集E包含任何集合，即

A(A

E)了解概念、掌握方法1）集合的表示法：列元素法A={a,b,c,d}謂詞表示法B={x|P(x)}.習(xí)題3.10(4)2）文氏圖與文氏圖法.習(xí)題3.63）集合A的基數(shù)cardA=|A|=n4）證明

X

Y命題演算法包含傳遞法等價條件法反證法并交運算法5）證明X=Y命題演算法等式代入法反證法運算法第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運算（重點）4.3關(guān)系的性質(zhì)（基礎(chǔ)）4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系（重點）4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)4.1集合的笛卡兒積和二元關(guān)系1）重要概念：集合A與B的笛卡兒積A

B={<x,y>|x

A

y

B}.若|A|=m,|B|=n,則|A

B|=mn分配律A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)A

=

B=

(A

C=B

D)(A,B,C,D非空)(A=B)

(C=D)2）從A到B的二元關(guān)系R

A

B.A×B的子集有2mn個，所以A到B有2mn個不同的二元關(guān)系.注：笛卡兒積不適合交換律和結(jié)合律.如<x,y>∈R,可記作xRy.A上重要關(guān)系從A到A的二元關(guān)系叫做A上的二元關(guān)系.空關(guān)系

是A上的關(guān)系全域關(guān)系EA={<x,y>|x∈A∧y∈A}=A×A

恒等關(guān)系IA={<x,x>|x∈A}小于等于關(guān)系LA={<x,y>|x,y∈A∧x≤y},A

R整除關(guān)系DA={<x,y>|x,y∈A∧x整除y},A

Z包含關(guān)系R

={<x,y>|x,y∈A∧x

y},A是集合族.類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.4.2關(guān)系的運算逆R

1={<y,x>|<x,y>

R}合成R°S={<x,z>|

y(<x,y>

S

<y,z>

R)}(1)(F°G)°H=F°(G°H)(2)(F°G)

1=G

1°F

1.冪運算(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn°R習(xí)題4.13。五14.3關(guān)系的性質(zhì)（基礎(chǔ)，重中之重）(1)若

x∈A,<x,x>

R,則稱R在A上是自反的.(2)若

x∈A,<x,x>

R,稱R在A上是反自反的.(3)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對稱的關(guān)系.(4)若

x,y∈A,<x,y>∈R∧<y,x>∈R→x=y,則稱R為A上的反對稱關(guān)系.(5)若

x,y,z∈A,<x,y>∈R∧<y,z>∈R→<x,z>∈R,則稱R是A上的傳遞關(guān)系.習(xí)題4.4關(guān)系性質(zhì)判別

自反反自反對稱反對稱傳遞表達式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0對M2中1所在位置,M中相應(yīng)位置都是1關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊,是一對方向相反的邊(無單邊)如果兩點之間有邊,是一條有向邊(無雙向邊)如果頂點xi連通到xk,則從xi到xk有邊

恒等關(guān)系IA既是等價關(guān)系,又是篇序關(guān)系。運算與性質(zhì)的關(guān)系（了解）自反性反自反性對稱性反對稱性傳遞性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1°R2

√××××4.5等價關(guān)系和偏序關(guān)系（重點）(1)等價關(guān)系、等價類、商集、劃分、自然映射等價關(guān)系:同時滿足自反、對稱和傳遞的關(guān)系.若<x,y>∈等價關(guān)系R,稱x等價于y,記做x～y.x(x∈A)關(guān)于集合A上等價關(guān)系R的等價類

[x]R

={y|y∈A∧xRy}.以集合A上的等價關(guān)系R的所有等價類為元素的集合稱為A關(guān)于R的商集,記做A/R.商集A/R就是A的一個劃分;等價關(guān)系與商集、劃分一一對應(yīng).習(xí)題4.5，4.15，4.24。五2；六14(2)偏序關(guān)系,覆蓋,偏序集與哈斯圖偏序關(guān)系：同時滿足自反、反對稱和傳遞的關(guān)系,記作?.如果<x,y>∈偏序關(guān)系?,則記作x?y.x?y且不存在z

A使得x?z?y,則稱y覆蓋x.集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.習(xí)題4.6，4.16。五3哈斯圖：簡化關(guān)系圖。特點（注意）：每個結(jié)點沒有環(huán)，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個結(jié)點之間才連邊.特定元素：區(qū)分最小(大)元與極小(大)元；下界、上界、下確界、上確界注意事項：特定元素對于有窮集，極小元和極大元必存在，可能存在多個.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是極小元;最大元一定是極大元.反之不對.

孤立結(jié)點既是極小元，也是極大元.下界、上界、下確界、上確界不一定存在.下界、上界存在不一定惟一.下確界、上確界如果存在，則惟一.集合的最小元就是它的下確界，最大元就是它的上確界；反之不對.4.6函數(shù)

x∈domF都存在唯一的y∈ranF使xFy成立,則稱二元關(guān)系F為函數(shù).對于函數(shù)F,如果有xFy,則記作y=F(x),并稱y為F在x的值.所有從A到B的函數(shù)的集合記作BA,讀作“B上A”，符號化表示為BA

={f|f：A→B}函數(shù)f：A→B，domF=A，|f|=|A|，ranF

B.計數(shù)：|A|=m,|B|=n,且m,n>0,|BA|=nm.B

={

}.A≠

,則

A=

.恒等函數(shù)IA(x)=x習(xí)題4.22了解有序?qū)?lt;x,y>，有序n元組<x1,x2,…,xn>.關(guān)系矩陣、關(guān)系圖;關(guān)系的定義域、值域和域.習(xí)題4.2關(guān)系F在集合A上的限制F?A={<x,y>|xFy

x

A}

F.A在F下的像F[A]=ran(F?A)ranF.習(xí)題4.3R的自反閉包r(R)=R∪R0,對稱閉包s(R)=R∪R

1,傳遞閉包t(R)=R∪R2∪R3∪…。習(xí)題4.14Mr

=M+E，Ms

=M+M’，Mt

=M+M2+M3+…(不)可比。全序(線序)關(guān)系：所有元素可比；良序集單射,滿射,雙射；常函數(shù)、單調(diào)函數(shù)；特征函數(shù).g(a)=[a]是從A到商集A/R的自然映射.習(xí)題4.10,4.18函數(shù)復(fù)合與反函數(shù)良序集：任意非空子集都有最小元素的全序集第5章代數(shù)系統(tǒng)的一般性質(zhì)5.1二元運算及其性質(zhì)（基礎(chǔ)）5.2代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)（重要概念積代數(shù)）5.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)（重點）5.1一、二元運算,代數(shù)系統(tǒng),封閉性函數(shù)f：S×S→S稱為集合S上的二元運算,也稱S對f

封閉;即

x,y∈S,f(x,y)∈S.函數(shù)f：S→S稱為集合S上的一元運算;即

x∈S,f(x)∈S.函數(shù)的性質(zhì)：運算結(jié)果唯一性.非空集合S和S上k個一元或二元運算f1,f2,…,fk

組成的系統(tǒng)稱為一個代數(shù)系統(tǒng),簡稱代數(shù)，記做

V=<S,f1,f2,…,fk>.習(xí)題5.8，5.7二元運算可能的性質(zhì)

x,y,z∈S

(1)交換律：

x°

y=y°x.(2)結(jié)合律：(x°

y)°

z=x°

(y°z).

(3)冪等律：

x°

x=x.(4)消去律：若x°

y=x°

z,且x不是零元,則y=z;

若y°

x=z°

x,且x不是零元，則y=z.

無零因子：(x°y=

x=

∨y=)

消去律.

(1)°

運算對?運算滿足分配律：

z°(x?y)=(z°

x)?(z°

y).(2)°

和?運算滿足吸收律(前提°

和?都可交換)：

x°

(x?y)=x；x?(x°

y)=x.一些二元運算的性質(zhì)集合運算交換律結(jié)合律冪等律消去律Z,Q,R,C普通加法+有有無有普通乘法

有有無有Mn(R)矩陣加法+有有無有矩陣乘法

無有無無P(B){0,1}并

(或∨)有有有無交

(與∧)有有有無對稱差

(

,

)有有無有AA函數(shù)復(fù)合

無有無無Zn模乘

有有無無Z+lcm,gcd有有有無{0,1}與非

,或非有無無無一些二元運算的性質(zhì)

集合運算分配律吸收律Z,Q,R,CMn(R)普通加法+與乘法

矩陣加法+與乘法

對+可分配無+對

不分配P(B){0,1}并

與交(或∨和與∧)

對

可分配有

對

可分配交

與對稱差(與∧和排斥或)

對

可分配無

對

不分配Zn模加

與模乘

對

可分配無

對

不分配全集E并

與笛卡兒積

對可分配無交

與笛卡兒積

對可分配Z+lcm與gcd有有二元運算可能的特異元素

x∈S,(e°x=x)

(x°e=x),稱e為單位元(幺元)(惟一性).

x∈S,(θ°x=θ)

(x°θ=θ),稱θ是零元(惟一性).注:只有左或右單位元(零元),不稱為有單位元(零元).(y°x=e)

(x°y=e),稱y為x的逆元,并稱x是可逆元素.注:逆元的存在以幺元的存在為前提.e-1=e.對于可結(jié)合的二元運算,可逆元素x只有惟一的逆元,記作x

1.

習(xí)題5.14，5.15，5.3，5.12，5.2一些二元運算的特異元素集合運算幺元e零元θ逆元x-1(e-1=e)Z,Q,R,C普通加法+0無

x普通乘法

101/x(x≠0)Mn(R)矩陣加法+0陣無

x矩陣乘法

單位陣In0陣x

1(逆陣,x可逆)P(B){0,1}并

(或∨)

(0)B(1)

-1=(0-1=0)交

(與∧)B(1)

(0)B-1=B(1-1=1)

(

)

(0)無xAA函數(shù)復(fù)合

IA無雙射逆元=反函數(shù)Zn模乘

10x,n互質(zhì),x有逆元模加

0無n

x(0-1=0)Z+lcm1無1-1=1gcd無1無{0,1}等價

1無x由運算表判別算律的一般方法交換律：運算表關(guān)于主對角線對稱冪等律：主對角線元素排列與表頭順序一致消去律：所在的行與列中沒有重復(fù)元素單位元:所在行與列的元素排列都與表頭一致零元：元素的行與列都由該元素自身構(gòu)成A的可逆元：a所在的行中某列(比如第j列)元素為e，且第j行

i列的元素也是e，那么a

與第j個元素互逆結(jié)合律：除了單位元、零元之外，要對所有3個元素的組合驗證表示結(jié)合律的等式是否成立習(xí)題5.1，5.95.2代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)重要概念：<S1,o>和<S2,>是代數(shù)系統(tǒng)，積代數(shù)<S1

S2,?>有：<x1,y1>?<x2,y2>=<x1ox2,y1

y2>.題5.10(1)若o

和

運算是可交換的，那么?運算也是可交換的

(2)若o

和

運算是可結(jié)合的，那么?運算也是可結(jié)合的

(3)若o

和

運算是冪等的，那么?運算也是冪等的

(4)若

o

和

運算分別具有單位元

e1

和e2，那么?運算也具有單位元<e1,e2>(5)若o

和

運算分別具有零元1和2，那么?運算也具有零元<

1,

2>(6)若x關(guān)于

o

的逆元為x

1,y關(guān)于

的逆元為y1，那么<x,y>關(guān)于?運算也具有逆元<x1,y1>5.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)(重點)V1=<S1,°>和V2=<S2,>是代數(shù)系統(tǒng),f:S1

S2,x,y∈S1,

f(x°y)=f(x)f(y),則稱f為V1到V2的同態(tài)(映射).如果同態(tài)f是滿射，則稱為滿同態(tài)，這時稱V2是V1的同態(tài)像，記作V1

V2；如果同態(tài)f是雙射，則稱為同構(gòu)，記作V1

V2.習(xí)題5.6，5.5。六13，15滿同態(tài)保持運算的算律及特異元素V1=<S1,°,?>和V2=<S2,o’,?’

>是代數(shù)系統(tǒng)，f：V1

V2是滿同態(tài)，那么(1)若o運算是可交換的（可結(jié)合、冪等的），則o’運算也是可交換的（可結(jié)合、冪等的）.(2)若o運算對?運算是可分配的，則o’運算對?’運算也是可分配的；若o

和?運算是可吸收的，則o’和?’運算也是可吸收的。(3)若e為o

運算的單位元，則f(e)為o’運算的單位元.(4)若

為o

運算的零元，則f(

)為o’運算的零元.(5)設(shè)u

V1，若u1是

u

關(guān)于o運算的逆元，則f(u

1)

是

f(u)關(guān)于o’運算的逆元。注意事項1）集合S上的二元運算就是S×S→S的二元函數(shù).集合S上的一元運算就是S→S的一元函數(shù).2）e-1=e.當(dāng)|S|

2，單位元與零元是不同的，零元無逆元；當(dāng)|S|=1時，這個元素既是單位元也是零元.3）子代數(shù)B和原代數(shù)S含有相同的代數(shù)常數(shù)4）同態(tài)映射保持運算的算律及特異元素僅在滿同態(tài)時成立，如果不是滿同態(tài)，那么相關(guān)性質(zhì)在同態(tài)像中成立.

同態(tài)映射不一定能保持消去律成立.了解運算表代數(shù)系統(tǒng)的載體，成分，代數(shù)常數(shù)同類型與同種代數(shù)系統(tǒng)子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng)最大的子代數(shù)就是V本身.代數(shù)常數(shù)(對運算封閉)構(gòu)成最小的子代數(shù).最大和最小子代數(shù)稱為平凡的子代數(shù).真子代數(shù).習(xí)題5.4零同態(tài)、單(自)同態(tài)、(滿)自同態(tài)和自同構(gòu).第6章幾個典型的代數(shù)系統(tǒng)6.1半群與群6.2環(huán)與域（“域”是重點）6.3格與布爾代數(shù)（“布爾代數(shù)”是重點）6.1 (半)群|S|≥2<S,o>封閉性結(jié)合律含幺所有元有逆元交換律<a>={az}消去律含零代數(shù)系統(tǒng)√半群√√交換半群獨異點√√√群√√√√√×Abel群√√√√√√×循環(huán)群√√√√√√√×重要概念：循環(huán)群，n元置換群。(半)群實例(1)<Z+,+>,交換半群,不含幺;<N,+,0>,交換半群,含幺半群,非群;<Z,+,0>,<Q,+,0>,<R,+,0>,<C,+,0>都是交換群;<Z+,*,1>,<N,*,1,0>,<Z,*,1,0>都是交換半群,含幺半群,非群;<Q*,*,1>,<R*,*,1>,<C*,*,1>都是交換群。+是普通加法,*是普通乘法.(2)<Mn(R),+,0n>是交換群;<Mn(R),·,In,0n>是含幺半群,非交換。+和·分別表示矩陣加法和乘法.(3)<P(B),

,,B>,<P(B),

,B,>為交換半群,含幺半群,非群;<P(B),,>為交換群。并

,交

,對稱差.(4)<Zn,,0>為交換群;<Zn,

,1,0>為交換半群,含幺半群,非群;<Zn*,

,1>(n為素數(shù))為交換群。模加,模乘(5)<AA,,IA>為含幺半群,非交換,

為函數(shù)復(fù)合. n元對稱群及其子群n元置換群為(非交換)群.注：Q*,R*,C*,Zn*不含0；Zn={0,1,…,n

1}.習(xí)題6.2，6.4，6.8掌握重要概念，了解性質(zhì)設(shè)G為群，a∈G，令H={ak|k∈Z}，則H是G的子群，稱為由a生成的子群，記作<a>.設(shè)G是群，若存在a∈G使得G={ak

|k∈Z}，則稱G是循環(huán)群，記作G=<a>，稱a為G的生成元.習(xí)題6.5，6.9(1)若G=<a>是無限循環(huán)群，則G只有a和a

1兩個生成元.

(2)若G=<a>是n階循環(huán)群，則ar是G的生成元當(dāng)且僅當(dāng)r是小于等于n且與n互質(zhì)的正整數(shù).(1)設(shè)G=<a>是循環(huán)群，則G的子群仍是循環(huán)群.(2)若G=<a>是無限循環(huán)群，則G的子群除{e}以外都是無限循環(huán)群.(3)若G=<a>是n階循環(huán)群，則對n的每個正因子d，G恰好含有一個d階子群.6.2環(huán)與域<S,+,*>含幺所有元素有逆元交換律分配律消去律|S|≥2環(huán)*是半群√+是Abel群√√√√域整環(huán)交換環(huán)*是交換半群√含幺環(huán)*是獨異點√除環(huán)無零因子環(huán)*√*√(θ除外)√n為素數(shù)

<Zn,

,

>是域環(huán)與域的實例(1)整數(shù)集、有理數(shù)集、實數(shù)集和復(fù)數(shù)集關(guān)于普通加法和乘法構(gòu)成環(huán)，分別稱為整數(shù)環(huán)Z(整環(huán))、有理數(shù)環(huán)Q(域)、實數(shù)環(huán)R(域)和復(fù)數(shù)環(huán)C(域).(2)n(n≥2)階實矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)成環(huán)，稱為n階實矩陣環(huán)(含幺環(huán)).(3)冪集P(B)關(guān)于對稱差和交運算構(gòu)成環(huán)(交換環(huán),含幺環(huán)).(4)Zn＝{0,1,...,n－1}，

和

分別表示模n加法和乘法，<Zn,

,

>構(gòu)成環(huán)，稱為模n的整數(shù)環(huán)(交換環(huán),含幺環(huán))；n為素數(shù)

<Zn,

,

>是域.習(xí)題6.6。六56.3格與布爾代數(shù)(“布爾代數(shù)”是重點)<L,∧,∨>結(jié)合律交換律冪等律吸收律封閉性幺元e零元

格∧√√√√√10∨√√√√01布爾格=有補分配格冪集格(|P|=2n)有界格鉆石格和五角格是有補格，非分配格。<Z,≤>是鏈;鏈?zhǔn)欠峙涓?中間元素?zé)o補。6.3格與布爾代數(shù)1）設(shè)<S,?>是偏序集，如果

x,y?S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?作成一個格.Sn是n的正因子的集合.D為整除關(guān)系,則偏序集<Sn,D>構(gòu)成分配格.n分解為素數(shù)的單次冪相乘時,Sn是布爾格.<P(B),>為B的冪集格

布爾格.<Z,≤>是鏈；任何一條鏈(中間元素?zé)o補元)都是分配格.2）定理設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格.小于五元的格都是分配格.3）格L若存在全下界0或全上界1,一定是惟一的.a∧b=0和a∨b=1成立,則稱b是a的補元.0,1互補.有界分配格L中元素a若存在補元,則存在惟一的補元.4）有限布爾代數(shù)(布爾格=有補分配格)L含有2n個元素.習(xí)題6.13，6.12，6.3，6.14，6.7；例6.13。七2；四8注意事項1）兩個n元置換的乘法就是函數(shù)的復(fù)合運算n

元置換的求逆就是求反函數(shù).題6.10。五9.所有的n元置換構(gòu)成集合Sn，Sn關(guān)于置換乘法構(gòu)成n元對稱群.恒等置換(1)是單位元，逆置換σ

1是σ的逆元.n元對稱群的子群稱為n元置換群.2）x的加法逆元為負(fù)元，記作

x.3）全下界0與全上界1互補.了解冪運算子半群與子獨異點;子群,真子群,平凡子群;子格積半群與積獨異點半群和獨異點的同態(tài)，格同態(tài).習(xí)題6.11Klein四元群有限群，無限群.群G的基數(shù)稱為群G的階|G|.元素x的階(或周期)|x|=k，稱x為k階元.無限階元.子群判定定理；群G的中心C.k階輪換與對換格的對偶命題與對偶原理第四部分 圖論圖論基本定理——握手定理任意無向圖和有向圖的所有頂點度數(shù)之和都等于邊數(shù)的2倍,并且有向圖的所有頂點入度之和等于出度之和等于邊數(shù).推論

在任何無向圖和有向圖中，奇度頂點的個數(shù)必為偶數(shù).不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體.習(xí)題7.1,7.14,7.19,7.5,7.6;例7.8(六3)。五6第7章圖的基本概念7.1無向圖及有向圖(握手定理、自補圖是重點)7.2通路、回路、圖的連通性(割集是重點)7.3圖的矩陣表示(由有向圖的鄰接矩陣求通路數(shù)和回路數(shù)是重點)7.4最短路徑(Dijkstra標(biāo)號法)與關(guān)鍵(最長)路徑7.1無向圖及有向圖重要概念：1）設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個無向圖(有向圖),若存在雙射函數(shù)f:V1

V2,使得對于任意的vi,vj

V1,(vi,vj)

E1（<vi,vj>

E1）當(dāng)且僅當(dāng)(f(vi),f(vj))

E2（<f(vi),f(vj)>

E2），并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重數(shù)相同，則稱G1與G2是同構(gòu)的，記作G1

G2.同構(gòu)的必要條件,但它們都不是充分條件:①邊數(shù)相同，頂點數(shù)相同②度數(shù)列相同(不計度數(shù)的順序)③對應(yīng)頂點的關(guān)聯(lián)集及鄰域的元素個數(shù)相同.2）既無平行邊也無環(huán)的圖稱為簡單圖.題7.13n階無向完全圖Kn:邊數(shù)m=n(n-1)/2,

=

=n-1.題7.7n階有向完全圖:邊數(shù)m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-1.習(xí)題7.93）若G

G且V

=V，則稱G

為G的生成子圖.4）設(shè)G=<V,E>為n階無向簡單圖，以V為頂點集,所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作.習(xí)題7.8若G

,則稱G是自補圖.習(xí)題7.20，7.12習(xí)題7.12，7.10；例7.107.1無向圖及有向圖(自補圖是重點)7.2通路、回路、圖的連通性(了解)1）區(qū)分初級通路(路徑)與簡單通路,初級回路(圈)與簡單回路.2）u

v(連通,不一定直通).規(guī)定u與自身總連通.四6，11，12連通關(guān)系R={<u,v>|u,v

V且u

v}是V上的等價關(guān)系連通圖:平凡圖,任意兩點都連通的圖.G是連通圖

p(G)=1連通分支:V關(guān)于R的等價類的導(dǎo)出子圖.設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,其個數(shù)記作p(G)=k.3）D弱連通(連通):基圖為無向連通圖.D單向連通:

u,v

V，u可達v

或v可達u.D強連通:

u,v

V，u與v相互可達強連通

單向連通

弱連通.習(xí)題7.21，7.16(強連通判別法)D強連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的回路.(單向連通判別法)D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路割集（重點）記G

v:從G中刪除頂點v及關(guān)聯(lián)的邊.G

V

:從G中刪除V

中所有頂點及關(guān)聯(lián)的邊.G

e:從G中刪除邊e.G

E

:從G中刪除E

中所有邊.設(shè)無向圖G=<V,E>,V

V,若p(G

V

)>p(G)且

V

V

,p(G

V

)=p(G),稱V

為G的點割集.若{v}為點割集,稱v為割點.V

為點割集且V

?V

V

∪V

非點割集.設(shè)無向圖G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),稱E

為G的邊割集.若{e}為邊割集,稱e為割邊或橋.E

為邊割集且E

?E

E

∪E

非邊割集.Kn無點割集.n階零圖既無點割集，也無邊割集.若G連通，E

為邊割集，則p(G

E

)=2.例7.11若G連通，V

為點割集，則p(G

V

)

2.習(xí)題7.177.3圖的矩陣表示有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令aij(1)為頂點vi鄰接到頂點vj邊的條數(shù),稱(aij(1))m

n為D的鄰接矩陣,記作A(D),簡記為A.有向圖的鄰接矩陣（重點）定理設(shè)A為n階有向圖D的鄰接矩陣,則Al(l

1)中元素為D中vi到vj長度為l的通路數(shù)，為vi到自身長度為l的回路數(shù)，為D中長度為l的通路總數(shù)，為D中長度為l的回路總數(shù).習(xí)題7.18推論設(shè)Bl=A+A2+…+Al(l

1),則Bl中元素為D中長度小于或等于l的通路數(shù)，為D中長度小于或等于l的回路數(shù).7.4最短路徑與關(guān)鍵(最長)路徑帶權(quán)圖；最短路徑與Dijkstra標(biāo)號法.習(xí)題7.22。五4PERT圖(計劃評審技術(shù)圖)與關(guān)鍵路徑.關(guān)鍵路徑:PETR圖中從始點到終點的最長路徑vi的最早完成時間TE(vi):從始點v1沿最長路徑到vi所需的時間.TE(v1)=0 TE(vi)=max{TE(vj)+wji|vj

-(vi)},i=2,3,,nvi的最晚完成時間TL(vi):在保證終點vn的最早完成時間不增加的條件下,從始點v1最遲到達vi的時間

TL(vn)=TE(vn) TL(vi)=min{TL(vj)-wij|vj

+(vi)},i=n-1,n-2,,1vi的緩沖時間TS(vi)=TL(vi)-TE(vi),i=1,2,,nvi在關(guān)鍵路徑上

TS(vi)=0.習(xí)題7.23了解n階圖:n個頂點的圖.有限圖:V,E都是有窮集的圖.零圖:E=.平凡圖:1階零圖.空圖:V=.端點(始點,終點),關(guān)聯(lián)次數(shù),環(huán),孤立點,相鄰,鄰接.鄰域(先驅(qū)元集∪后繼元集),閉鄰域,關(guān)聯(lián)集.v的度數(shù)d(v)=出度d+(v)+入度d

(v);懸掛頂點,懸掛邊;G的最大度

(G),最小度

(G);D的最大出度

+(D),最小出度

+(D),最大入度

(D),最小入度

(D);度數(shù)列,出度列,入度列;平行邊,重數(shù),多重圖;n階k正則圖;子圖,母圖,真子圖,導(dǎo)出子圖;連通度.可達矩陣P(D)主對角線上的元素全為1.關(guān)聯(lián)矩陣.D強連通當(dāng)且僅當(dāng)可達矩陣P(D)的元素全為1.第8章一些特殊的圖圖的類型(二部圖,歐拉圖,哈密頓圖,平面圖,樹)判別是重點.習(xí)題8.18,8.21;例8.2~8.5.四148.1二部圖（了解匹配）8.2歐拉圖（前提連通）8.3哈密頓圖（前提連通）8.4平面圖（歐拉公式是重點，了解自對偶圖）8.1二部圖設(shè)無向圖G=<V,E>,若能將V分成V1和V2(V1

V2=V,V1

V2=),使得G中的每條邊的兩個端點都一個屬于V1,另一個屬于V2,則稱G為二部圖,記為<V1,V2,E>,稱V1和V2為互補頂點子集.又若G是簡單圖,且V1中每個頂點均與V2中每個頂點都相鄰,則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|.注:n階零圖為二部圖.題8.2,8.3定理無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇圈.二部圖無環(huán)；平行邊不影響圖的二部性.匹配(邊獨立集):任2條邊均不相鄰的邊子集.習(xí)題8.4極大匹配,最大匹配,匹配數(shù)

1,(非)飽和點,完美匹配.注：匹配不限于二部圖；完備匹配專門針對二部圖而言.滿足t條件

滿足相異性條件

存在完備匹配(Hall定理).8.2歐拉圖歐拉通路:圖中恰好經(jīng)過每條邊一次的通路.歐拉回路:圖中恰好經(jīng)過每條邊一次的回路.歐拉圖:有歐拉回路的圖.半歐拉圖:有歐拉通路而無歐拉回路的圖.定理有向圖D是歐拉圖當(dāng)且僅當(dāng)D連通且每個頂點的入度都等于出度.習(xí)題8.10有向圖D具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個奇度頂點,其中一個入度比出度大1,另一個出度比入度大1,其余頂點的入度等于出度.歐拉通路是簡單通路,歐拉回路是簡單回路.規(guī)定平凡圖為歐拉圖.環(huán)不影響圖的歐拉性.哥尼斯堡七橋問題無歐拉通路也無歐拉回路.8.3哈密頓圖哈密頓通路:經(jīng)過圖中所有頂點恰好一次的通路.哈密頓回路:經(jīng)過圖中所有頂點恰好一次的回路.哈密頓圖:具有哈密頓回路的圖.半哈密頓圖:具有哈密頓通路而無哈密頓回路的圖.哈密頓通路是初級通路，哈密頓回路是初級回路.平凡圖是哈密頓圖.環(huán)與平行邊不影響圖的哈密頓性.定理(必要條件)設(shè)無向圖G=<V,E>是哈密頓圖,則對于任意V1

V且V1,均有p(G

V1)

|V1|.Kr,s當(dāng)s

r+1時不是哈密頓圖.設(shè)G為n階無向連通簡單圖,若G中有割點或橋,則G不是哈密頓圖.習(xí)題8.12無向哈密頓圖的一個充分條件定理

G是n階無向簡單圖,若任意兩個不相鄰的頂點的度數(shù)之和大于等于n

1,則G中存在哈密頓通路.當(dāng)n

3時,若任意兩個不相鄰的頂點的度數(shù)之和大于等于n,則G中存在哈密頓回路,從而G為哈密頓圖.當(dāng)n

3時,Kn均為哈密頓圖.習(xí)題8.11(四7),8.14,8.19當(dāng)r

2時,Kr,r是哈密頓圖,而Kr,r+1是半哈密頓圖.哈密頓周游世界問題中存在哈密頓回路,故它是哈密頓圖.注意,并不滿足充分條件.8.4平面圖（歐拉公式是重點）如果能將圖G除頂點外邊不相交地畫在平面上,則稱G是平面圖.這個畫出的無邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.平行邊與環(huán)不影響圖的平面性.設(shè)G

G,若G為平面圖,則G

也是平面圖;若G

為非平面圖,則G也是非平面圖.Kn(n

5),Km,n(m,n

3)都是非平面圖.定理平面圖各面的次數(shù)之和等于邊數(shù)的2倍.歐拉公式的推廣：n

m+r=p+1.習(xí)題8.16定理設(shè)G為簡單平面圖，則

(G)

5.六8庫拉圖斯基定理：G是平面圖

G中不含與K5,K3,3同胚收縮的子圖.習(xí)題8.23了解無限面(外部面)R0,有限面(內(nèi)部面),邊界,面Ri的次數(shù)deg(Ri)極大平面圖(習(xí)題8.20).若簡單平面圖中已無不相鄰頂點,則是極大平面圖.K1,K2,K3,K4都是極大平面圖.極大平面圖必連通.n(n3)階極大平面圖中不可能有割點和橋.設(shè)G為n(n3)階極大平面圖,則G每個面的次數(shù)均為3.任何n(n

4)階極大平面圖G均有δ(G)

3.極小非平面圖：K5,K3,3都是極小非平面圖極小非平面圖必為簡單圖同胚與收縮平面圖G的對偶圖G*是平面圖,而且是平面嵌入.G*是連通圖.若邊e為G中的環(huán),則G*與e對應(yīng)的邊e*為橋;若e為橋,則G*中與e對應(yīng)的邊e*為環(huán).在多數(shù)情況下,G*含有平行邊.同構(gòu)的平面圖的對偶圖不一定同構(gòu).題17(1)n*=r;(2)m*=m;(3)r*=n-p+1;(4)d(vi*)=deg(Ri).題22第9章樹9.1無向樹及生成樹(利用Kruskal避圈法求最小生成樹是重點，并求對應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng))9.2根樹及其應(yīng)用(利用Huffman算法求最優(yōu)r元樹或最佳前綴碼是重點,了解波蘭符號法與逆波蘭符號法)9.1無向樹及生成樹無向樹:連通無回路的無向圖.例9.5.平凡樹:平凡圖.森林:每個連通分支都是樹的非連通的無向圖.題9.3樹葉:樹中度數(shù)為1的頂點.分支點:度數(shù)

2的頂點.n階無向樹的性質(zhì):1)(重要)邊數(shù)m=n

1;習(xí)題9.2,9.52)G中任意兩個頂點之間存在惟一的路徑;例9.113)G是連通的且G中任何邊均為橋;四1(2)，六64)G中沒有回路,但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈.定理

n階非平凡的無向樹T中