離散數(shù)學(xué)-課件總復(fù)習(xí)

復(fù)習(xí)時(shí)注意:準(zhǔn)確掌握每個(gè)概念靈活應(yīng)用所學(xué)定理注意解題思路清晰證明問(wèn)題時(shí),先用反向思維(從結(jié)論入手)分析問(wèn)題,再按正向思維寫出證明過(guò)程期末總復(fù)習(xí)全書知識(shí)網(wǎng)絡(luò)：圖論篇同構(gòu)同構(gòu)<{1,0},,,,,><p(E),~,∩,∪,－,>格與布爾代數(shù)半群,獨(dú)異點(diǎn),群,環(huán),域<P(A×A),~,∩,∪,－,,,c,r,s,1><YX,~,∩,∪,－,,,-1>代數(shù)系統(tǒng)篇n元運(yùn)算命題邏輯謂詞邏輯集合初步二元關(guān)系函數(shù)集合論篇數(shù)理邏輯篇總復(fù)習(xí)復(fù)習(xí)重點(diǎn)第一章命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會(huì)命題符號(hào)化.3.永真式的證明.4.等價(jià)公式的證明,記住并能熟練應(yīng)用常用公式.5.會(huì)寫命題公式的范式,能應(yīng)用范式解決問(wèn)題.6.熟練掌握命題邏輯三種推理方法.第一章命題邏輯1.聯(lián)結(jié)詞定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是：

(1)否定“”

(2)合取“∧”

(3)析取“∨”

(4)異或“

”

(5)蘊(yùn)涵“”

(6)等價(jià)“”要熟練掌握這六個(gè)聯(lián)結(jié)詞在自然語(yǔ)言中所表示的含義以及它們的真值表的定義。：否定表示“不”∧：合取表示“不但…,而且..”“既…又...”““并且”∨：析取表示“或者－可兼取的或”：異或表示“或者－不可兼取的或”：蘊(yùn)涵表示“如果…,則...”

“只要…,就...”

:等價(jià)表示“當(dāng)且僅當(dāng)”“充分且必要”可以將這六個(gè)聯(lián)結(jié)詞看成六種“運(yùn)算”。聯(lián)結(jié)詞的定義(包括真值表和含義).特別要注意：“或者”的二義性,即要區(qū)分給定的“或”是“相容或∨”還是“排斥或”?！啊钡挠梅ǎ缺硎尽俺浞謼l件”也表示“必要條件”,即要弄清哪個(gè)作為前件,哪個(gè)作為后件.

PQP∧QP∨QPQPQPQ

0000110

0101101

10010011111110

2.會(huì)命題符號(hào)化.

例如P:我有時(shí)間.Q:我上街.R:我在家.

表示P是Q的充分條件:如果p,則Q.只要P,就Q.

PQ

表示P是Q的必要條件:僅當(dāng)P,才Q.

只有P,才Q.QP

如果P,則Q;否則R.(PQ)(PR)3.永真式的證明.

方法1.列真值表.(R(QR)(PQ))P

方法2.用公式的等價(jià)變換,化簡(jiǎn)成1.例如證明(R(QR)(PQ))P是永真式.證:上式(R(QR)(PQ))P(PQPQ)(R(QR)(PQ))P(公式的否定公式)((R(QR))((PQ)P)(結(jié)合律)((RQ)(RR))((PP)(QP)(分配律)(RQ)(QP)RQQP1(互補(bǔ),同一律)4.等價(jià)公式的證明,記住常用的公式.

方法1.列真值表.

方法2.用公式的等價(jià)變換.

例如:證明P(QR)(P∧Q)RP(QR)P(QR)(PQ)R

(PQ)∨R(P∧Q)R注意:不論是證明永真蘊(yùn)涵式,還是證明等價(jià)公式以及后邊的求公式的范式,命題邏輯推理,都應(yīng)用9頁(yè)的公式。必須記憶一些常用的公式如:P9表中的5.會(huì)求主析取范式和主合取范式.求下面命題公式的范式:A(P,Q,R)

(P∨Q)R方法1.列真值表.主析取范式A(P,Q,R)

(P∨Q)R(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式A(P,Q,R)

(P∨Q)R

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)PQR(P∨Q)R00010011010001111000101111001111方法2.用公式的等價(jià)變換.主析取范式;A(P,Q,R)

(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∧Q∧(R∨R))∨((P∨P)∧(Q∨Q)∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式:A(P,Q,R)

(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)6.會(huì)用三種推理方法,進(jìn)行邏輯推理.

會(huì)用P22頁(yè)十個(gè)公式例如:證明((A∧B)C)∧D∧(C∨D)A∨B1).直接推理:⑴D

前提引入⑵C∨D前提引入⑶C⑴⑵析取三段論Q,(P∨Q)P⑷(A∧B)CP⑸(A∧B)⑶⑷拒取式Q,PQP⑹A∨B⑸置換

(P∧Q)P∨Q((A∧B)C)∧D∧(C∨D)A∨B2).附加前提推理:適用于結(jié)論是蘊(yùn)涵式.A∨BAB⑴A附加前提引入⑵(A∧B)C前提引入⑶A(BC)⑵置換⑷BC⑴⑶

假言推理⑸D前提引入⑹C∨D前提引入⑺C⑸⑹

析取三段論⑻B⑷⑺假言推理((A∧B)C)∧D∧(C∨D)A∨B3).歸謬法:⑴(A∨B)否定結(jié)論引入⑵A∧B⑴置換⑶(A∧B)C前提引入⑷CT⑵

（3）假言推理⑸D前提引入⑹C∨D前提引入⑺C（5）（6）析取三段論⑻C∧CT⑷⑺合取引入第二章謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會(huì)命題符號(hào)化3.掌握常用的等價(jià)公式和永真蘊(yùn)涵式.包括:

帶量詞的公式在論域內(nèi)展開(kāi)式,量詞否定,量詞轄域擴(kuò)充,

量詞分配公式.4.會(huì)用等價(jià)公式求謂詞公式的真值5.會(huì)寫前束范式6.熟練掌握謂詞邏輯推理.

第二章謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.

個(gè)體:

個(gè)體變?cè)?

謂詞,

量詞,

量詞后的指導(dǎo)變?cè)?

量詞的轄域,

約束變?cè)c自由變?cè)?

論域,

全總個(gè)體域,

謂詞公式(W00),

命題函數(shù),

前束范式,2.會(huì)命題符號(hào)化

命題的符號(hào)表達(dá)式與論域有關(guān)。當(dāng)論域擴(kuò)大時(shí)，需要添加特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個(gè)名詞。如“所有自然數(shù)...”、“有些大學(xué)生...”。如何添加特性謂詞：

如果前邊是全稱量詞，特性謂詞后邊是蘊(yùn)含聯(lián)結(jié)詞“→”；

如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“∧”。另外有些命題里有的客體在句中沒(méi)有明確的量詞,而在寫它的符號(hào)表達(dá)式時(shí),,必須把隱含的量詞明確的寫出來(lái).例如1.有些液體可以溶解所有固體.

F(x):x是液體.S(x):x是固體.D(x,y):x可溶解y.x(F(x)y(S(y)D(x,y)))2.每個(gè)大學(xué)生都愛(ài)好一些文體活動(dòng)。S(x):x是大學(xué)生,L(x,y):x愛(ài)好y,C(x):x是文娛活動(dòng)，P(x):x是體育活動(dòng).)x(S(x)y((C(y)∨P(y))L(x,y)))

3.掌握常用的等價(jià)公式和永真蘊(yùn)涵式.包括:

帶量詞的公式在論域內(nèi)展開(kāi)式,量詞否定,量詞轄域擴(kuò)充,

量詞分配公式.

設(shè)論域?yàn)閧a1,a2,....,an}，則

1).xA(x)A(a1)∧A(a2)∧......∧A(an)2).xB(x)B(a1)∨B(a2)∨......∨B(an)1).xA(x)xA(x)2).xA(x)xA(x)1).xA(x)∨Bx(A(x)∨B)2).xA(x)∧Bx(A(x)∧B)3).xA(x)∨Bx(A(x)∨B)4).xA(x)∧Bx(Ａ(x)∧B)5).B→xA(x)x(B→A(x))6).B→xA(x)x(B→A(x))7).xA(x)→Bx(A(x)→B)8).xA(x)→Bx(A(x)→B)1).x(A(x)∨B(x))xA(x)∨xB(x)2).x(A(x)∧B(x))xA(x)∧xB(x)3).x(A(x)∧B(x))xA(x)∧xB(x)4).xA(x)∨xB(x)x(A(x)∨B(x))4.會(huì)用等價(jià)公式求謂詞公式的真值.例設(shè)論域?yàn)閧1,2},A(x,y):x+y=xy,求xyA(x,y)的真值.xyA(x,y)xyA(x,y)yA(1,y)yA(2,y)(A(1,1)A(1,2))(A(2,1)A(2,2))(11)(10)15.將下面謂詞公式寫成前束范式(xF(x,y)yG(y))xH(x,y)(xF(x,y)yG(y))xH(x,y)(去)(xF(x,y)yG(y))xH(x,y)(摩根)(xF(x,y)yG(y))xH(x,y)(量詞否定)(xF(x,z)yG(y))tH(t,z)(變?cè)獡Q名)xyt((F(x,z)G(y))H(t,z))(轄域擴(kuò)充)6.熟練掌握謂詞邏輯推理.1).注意使用EI、UI、EG、UG的限制條件

(必須是前束范式，才可以用EI、UI)2).對(duì)于同一個(gè)客體變?cè)?，既有帶也有帶的前提，去量詞時(shí)，應(yīng)先去后去，即先用EI，再用UI這樣才可以特指同一個(gè)客體c.下面的作法是錯(cuò)誤的：正確作法:⑴xP(x)P⑴xP(x)P⑵P(c)⑴UI⑵xP(x)⑴

置換

（3）P(c)⑴EI

例如.證明下面推理的有效性.證明:⑴x(A(x)∧D(x))P⑵A(a)∧D(a))

EI⑴⑶A(a)T⑵I⑷D(a))T⑵I⑸x(A(x)→(B(x)→C(x)))P⑹A(a)→(B(a)→C(a))UI⑸⑺B(a)→C(a))T⑶⑹I⑻x(A(x)→(C(x)∨D(x)))P⑼A(a)→(C(a)∨D(a)))US⑻⑽C(a)∨D(a)T⑶⑼I⑾C(a)T⑷⑽I⑿B(a)T⑺⑾I⒀A(a)∧B(a))T⑶⑿I⒁x(A(x)∧B(x))EG⒀第三章集合論初步1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明.3.集合的五種運(yùn)算及相關(guān)性質(zhì).4.應(yīng)用包含排斥原理.第三章集合論初步基本概念:集合與元素,子集與真子集,空集,全集,冪集,并集,交集,相對(duì)補(bǔ)集(差集),絕對(duì)補(bǔ)集(補(bǔ)集)1.集合的表示,元素與集合的屬于關(guān)系∈.

集合的三種表示方法:

枚舉法:一一列出集合中的元素.描述法:用謂詞描述集合中元素的性質(zhì).

文氏圖:用一個(gè)平面區(qū)域表示.2.集合的三種關(guān)系(被包含,相等,被真包含)的定義及證明.ABx(x∈Ax∈B)A=BABBAx(x∈Ax∈B)ABABA≠Bx(x∈Ax∈B)x(x∈BxA)

3空集,全集,冪集空集φ:無(wú)元素的集合.x∈Φ是矛盾式.(空集是唯一的)

全集E:包含所討論所有集合的集合.(全集不唯一)x∈E是永真式冪集:由A的所有子集構(gòu)成的集合.

P(A)={X|XA}|P(A)|=2|A|

4.掌握集合的五種運(yùn)算及相關(guān)性質(zhì).A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈BA∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈BA-B={x|x∈A∧xB}x∈A-Bx∈A∧xB~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxAA-B=A∩~BAB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}AB=(A∪B)-(A∩B)邏輯演算法的格式題目：A＝B證明：x，

x∈A …… x∈B

所以A＝B或證AB∧BA題目：AB證明：x，

x∈A …… x∈B

所以AB集合演算法的格式題目：A＝B證明：A

＝……

＝B

所以A＝B題目：AB證明：A …… B

所以AB例證明:

(A-B)-C=A-(B∪C)方法1.(A-B)-C=(A∩~B)∩~C=A∩(~B∩~C)=A∩~(B∪C)=A-(B∪C)方法2.任取x∈(A-B)-C(x∈A∧xB)∧xCx∈A∧(xB∧xC)x∈A∧(x∈B∨x∈C)x∈A∧(x∈B∪C)x∈A∧xB∪Cx∈A-(B∪C)所以(A-B)-C=A-(B∪C)例7.有14位學(xué)生參加考試,9位同學(xué)數(shù)學(xué)得了優(yōu);5位同學(xué)物理得了優(yōu);4位同學(xué)化學(xué)得了優(yōu);其中物理和數(shù)學(xué)都得優(yōu)的同學(xué)有4人;數(shù)學(xué)和化學(xué)都得優(yōu)的同學(xué)有3人;物理和化學(xué)都得優(yōu)的同學(xué)有3人;三門都得優(yōu)的同學(xué)有2人;問(wèn)沒(méi)有得到優(yōu)的有多少人?恰有兩門得優(yōu)的同學(xué)有多少人?解.令A(yù)、B、C分別表示數(shù)學(xué)、物理、化學(xué)得優(yōu)同學(xué)集合.全集為E.于是有|E|=14|A|=9|B|=5|C|=4|A∩B|=4|A∩C|=3|B∩C|=3|A∩B∩C|=2|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|=9+5+4-4-3-3+2=10于是得到優(yōu)的人數(shù)是10人.∴沒(méi)有得到優(yōu)的人數(shù)是:14-10=4人恰有兩門得優(yōu)的人數(shù):(|A∩B|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=4第四章二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計(jì)算方法及有關(guān)性質(zhì))4.掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集.5.關(guān)系圖和矩陣的簡(jiǎn)化6.偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.一.關(guān)系的概念,表示方法,三個(gè)特殊關(guān)系.1.集合的笛卡爾積

A×B={<x,y>|x∈A∧y∈B}|A|=m,|B|=n|A×B|=mn

設(shè)A={0,1}，B={a,b}，求AB。

AB={<0,a>,<0,b>,<1,a>,<1,b>}2.二元關(guān)系的概念定義1:設(shè)A、Ｂ是集合,如果ＲA×B,則稱R是一個(gè)從A到

B的二元關(guān)系。如果RA×A,則稱R是A上的二元關(guān)系.

如果|A|=m|B|=n則可以確定2m*n個(gè)從A到B的不同關(guān)系.3.關(guān)系的表示方法1).枚舉法:

即將關(guān)系中所有序偶一一列舉出，寫在大括號(hào)內(nèi).

如:R={<1,2>,<3,4>,<4,2>}2).(描述法)謂詞公式法：即用謂詞公式描述序偶中元素的關(guān)系。例如

R={<x,y>|x<y}3).有向圖法：1。2。

3。

4。。。。ABabcR1:1。。4。。23R2:4).矩陣表示法：(實(shí)際上就是圖論中的鄰接矩陣)

設(shè)A={a1,a2,,am}，B={b1,b2,,bn}是個(gè)有限集，

RA×B，定義R的m×n階矩陣

MR=(rij)m×n，其中4.三個(gè)特殊關(guān)系1).空關(guān)系Φ：

ΦA(chǔ)×B，(或ΦA(chǔ)×A)，即無(wú)任何元素的關(guān)系.

它的關(guān)系圖中只有結(jié)點(diǎn),無(wú)任何邊；它的矩陣中全是0。2).完全關(guān)系(全域關(guān)系)

：

A×B(或A×A)本身是一個(gè)從A到B(或A上)的完全關(guān)系.

即含有全部序偶的關(guān)系。它的矩陣中全是1。

1若<ai,bj>∈R

0若<ai,bj>∈R(1≤i≤m,1≤j≤n)rij=3).恒等關(guān)系IA：

IAA×A,且IA={<x,x>|x∈A}稱之為A上的恒等關(guān)系。例如A={1,2,3},則IA={<1,1>,<2,2>,<3,3>}A上的Φ、完全關(guān)系A(chǔ)×A及IA的關(guān)系圖及矩陣如下：MIA=1000100013×31。2。。31。2。。31111111113×31。。2。30000000003×3MΦ=MA×A=ΦA(chǔ)×AIA二.關(guān)系的性質(zhì)的判斷與證明:自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義x∈A→<x,x>∈Rx∈A→<x,x>R<x,y>∈R→<y,x>∈R<x,y>∈R∧<y,x>∈R→x=y<x,y>∈R∧<y,z>∈R→<x,z>集合表達(dá)式IA

RR∩IA＝R＝R-1R∩R-1

IARRR關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1，且i≠j，則rji＝0對(duì)M2中1所在位置，M中相應(yīng)的位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒(méi)有環(huán)如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊(無(wú)單邊)如果兩點(diǎn)之間有邊，一定是一條有向邊(無(wú)雙向邊)如果頂點(diǎn)xi到xj

有邊，xj

到xk

有邊，則從xi到xk

也有邊判斷下面關(guān)系的性質(zhì):1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R1YNNYYR2NYNYNR3YNYNYR4YNYYY1。2。。1。2。。1。2。。1。2。。3333R5R6R7R8自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R5NYNYYR6NNYNNR7NNNNNR8NYYYY三.掌握關(guān)系復(fù)合,求逆及閉包運(yùn)算(計(jì)算方法及性質(zhì))(一)關(guān)系的復(fù)合

1.定義:設(shè)RX×Y，SY×Z，則RSX×Z。

RS={<x,z>|xXzZy(yY<x,y>R<y,z>S)}2.計(jì)算方法(俗稱過(guò)河拆橋法)

⑴枚舉法R={<a,b>,<b,c>,<c,a>}S={<a,b>,<b,c>,<b,b>,<c,a>}RS={<a,c>,<a,b>,<b,a>,<c,b>}3.性質(zhì)1).滿足結(jié)合律:RA×BSB×C1C×D則

R(S1)=(RS)12).RA×BSB×C1B×C⑴R(S∪1)=(RS)∪(R1)⑵R(S∩1)(RS)∩(R1)3).R是從A到B的關(guān)系，則

RIB=IAR=R

推論:RA×A,則RIA=IAR=R(IA是運(yùn)算的幺元)4).關(guān)系的乘冪

R0=IA，

RA×A,

Rm

Rn

=Rm+n(Rm)n=Rmn

(m,n為非負(fù)整數(shù))(二).逆關(guān)系1.定義

:設(shè)RX×Y，R的逆關(guān)系R-1={<y,x>|<x,y>R}<y,x>∈RC<x,y>R2.計(jì)算方法

1).R={<1,2>,<2,3>,<3,4>,<4,5>}R-1={<2,1>,<3,2>,<4,3>,<5,4>}2).R-1的有向圖:是將R的有向圖的所有邊的方向顛倒.3).R-1的矩陣MRC=(MR)T即為R矩陣的轉(zhuǎn)置3.性質(zhì)令R、S都是從X到Y(jié)的關(guān)系，則

1).(R-1)-1=R

2).(R∪S)-1=R-1∪S-1。

3).(R∩S)-1=R-1∩S-1。

(三).閉包運(yùn)算1.定義：給定A中關(guān)系R,若A上另一個(gè)關(guān)系R’，滿足：⑴RR’；⑵R’是自反的(對(duì)稱的、傳遞的)；⑶R’是“最小的”，即對(duì)于任何A上自反(對(duì)稱、傳遞)的關(guān)系R”,如果RR”,就有R’R”。則稱R’是R的自反(對(duì)稱、傳遞)閉包。記作r(R)、(s(R)、tR))2.計(jì)算方法給定A中關(guān)系R

r(R)=R∪IA。

s(R)=R∪R-1。

t(R)=R∪R2∪...∪Rn-1

閉包的運(yùn)算有三種形式:如A={a.b.c}RA×AR={<a,b>,<b,c>,<c,a>}

a).集合形式.

r(R)=R∪IA={<a,b>,<b,c>,<c,a>}{<a,a>,<b,b>,<c,c>}={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}s(R)=R∪R-1={<a,b>,<b,c>,<c,a>}{<b,a>,<c,b>,<a,c>}={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}R2={<a,c>,<b,a>,<c,b>}R3={<a,a>,<b,b>,<c,c>}

1(R)=R∪R2∪R3={<a,b>,<b,c>,<c,a>}∪{<a,c>,<b,a>,<c,b>}∪{<a,a>,<b,b>,<c,c>}={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>.<a,a>,<b,b>,<c,c>}b)有向圖形式.bacR3RbacbacIA∪=r(R)bac∪RbacbR2ac1(R)bac∪=c∪Rbac=bRCas(R)bacc)矩陣形式.Mr(R)=MR∨MIA=010001100100010001∨=111110011Ms(R)=MR∨MRC=010001100001100010∨=011101110M1(R)=M∨M∨M=010001100001100010∨=111111111R2R3R∨1000100013.性質(zhì)1).R是A上關(guān)系，則⑴R是自反的，當(dāng)且僅當(dāng)r(R)=R.⑵R是對(duì)稱的，當(dāng)且僅當(dāng)s(R)=R.⑶R是傳遞的，當(dāng)且僅當(dāng)t(R)=R.2).R是A上關(guān)系，則⑴R是自反的，則s(R)和t(R)也自反。⑵R是對(duì)稱的，則r(R)和t(R)也對(duì)稱。⑶R是傳遞的，則r(R)也傳遞。四.等價(jià)關(guān)系

掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集.

1.了解集合的劃分與覆蓋的概念.

例X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}A1,

A2,A3,A4是覆蓋。A1,

A2,A3也是劃分。

2.等價(jià)關(guān)系定義:設(shè)R是A上關(guān)系,若R是自反的、對(duì)稱的和傳遞的，則稱R是A中的等價(jià)關(guān)系。

3.等價(jià)關(guān)系R的有向圖:可能由若干個(gè)獨(dú)立子圖構(gòu)成的，每個(gè)獨(dú)立子圖都是完全關(guān)系圖。1。2。。3R11。2。。3R21。2。。R34.等價(jià)類：1).定義:R是A上的等價(jià)關(guān)系,a∈A,由a確定的集合[a]R[a]R={x|x∈A∧<a,x>∈R}

稱集合[a]R為由a形成的R等價(jià)類。2).由等價(jià)關(guān)系圖求等價(jià)類：R圖中每個(gè)獨(dú)立子圖上的結(jié)點(diǎn)構(gòu)成一個(gè)等價(jià)類。不同的等價(jià)類個(gè)數(shù)=獨(dú)立子圖個(gè)數(shù)。3).等價(jià)類性質(zhì)

R是A上等價(jià)關(guān)系，任意a,b,c∈A

⑴同一個(gè)等價(jià)類中的元素，彼此有等價(jià)關(guān)系R。⑵

[a]R∩[b]R=Φ，當(dāng)且僅當(dāng)<a,b>R。⑶

[a]R=[b]R當(dāng)且僅當(dāng)<a,b>∈R。⑷.A中任何元素a,a必屬于且僅屬于一個(gè)等價(jià)類。⑸.任意兩個(gè)等價(jià)類

[a]R,[b]R,

要么[a]R=[b]R，要么[a]R∩[b]R=Φ

。⑹R的所有等價(jià)類構(gòu)成的集合是A的一個(gè)劃分。5.商集:定義：R是A上等價(jià)關(guān)系，由R的所有等價(jià)類構(gòu)成的集合稱之為A關(guān)于R的商集。記作A/R。即

A/R={[a]R|a∈A}五.偏序關(guān)系判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.1.定義：R是A上自反、反對(duì)稱和傳遞的關(guān)系，則稱R是A上的偏序關(guān)系。并稱<A,R>是偏序集。2.x與y是可比較的：<A,≤>是偏序集，x,y∈A，如果要么x≤y,要么y≤x,則稱x與y是可比較的。3.定義：<A,≤>是偏序集，任何x,y∈A，如果x與y都是可比較的，則稱≤是全序關(guān)系(線序、鏈)。4.偏序集Hasse圖的畫法：令<A,≤>是偏序集，

1).用“

”表示A中元素。

2).如果x≤y,且x≠y，則結(jié)點(diǎn)y要畫在結(jié)點(diǎn)x的上方。

3).如果x≤y,且y蓋住x，x與y之間連一直線。

4).從最下層結(jié)點(diǎn)(全是射出的邊與之相連，逐層向上畫，直到最上層結(jié)點(diǎn)(全是射入的邊與之相連)。例如{1,2,4,6}上的整除關(guān)系2。。1。。64１。２。４。６。5.重要元素y是B的極小元y(y∈B∧x(x∈B∧x≠y∧x≤y))

(在B中沒(méi)有比y更小的元素了，y就是極小元)y是B的極大元y(y∈B∧x(x∈B∧x≠y∧y≤x))

(在B中沒(méi)有比y更大的元素了，y就是極大元)y是B的最小元y(y∈B∧x(x∈By≤x))

(最小元y是B中元素，該元素比B中所有元素都小)y是B的最大元y(y∈B∧x(x∈Bx≤y))(最大元y是B中元素，該元素比B中所有元素都大)y是B的上界y(y∈A∧x(x∈Bx≤y))

(上界y是A中元素，該元素比B中所有元素都大)y是B的下界y(y∈A∧x(x∈By≤x))

(下界y是A中元素，該元素比B中所有元素都小)

y是B的上界，并且對(duì)B的所有上界x,都有y≤x,則稱y是B的最小上界(上確界)，記作LUBB=y。

(即y是上界中最小的。如果B有上確界，則是唯一的)y是B的下界，并且對(duì)B的所有下界x,都有x≤y,則稱y是B的最大下界(下確界)，記作GLBB=y。

(即y是下界中最大的。如果B有上確界，則是唯一的)例如B={2,3,6}B的極小元:2,3極大元:6

最小元:無(wú)最大元:6

下界:1上界:6,12,18

下確界:1上確界:6１。6。18。12。2。。3第五章代數(shù)系統(tǒng)1.掌握運(yùn)算的定義.2.熟練掌握二元運(yùn)算的性質(zhì)的判斷及證明.3.掌握代數(shù)系統(tǒng)的同構(gòu)定義,會(huì)證明.了解同構(gòu)性質(zhì)的保持.4.了解半群,幺半群（獨(dú)異點(diǎn)）的概念.5.熟練掌握群,交換群一.掌握運(yùn)算和代數(shù)系統(tǒng)的概念.1.運(yùn)算定義：設(shè)X是個(gè)集合，F(xiàn):XnY是個(gè)映射，則稱F是

X上的n元運(yùn)算.(Xn=X×X×...×X--n個(gè)X的笛卡爾積)2代數(shù)系統(tǒng)定義：X是非空集合，X上的m個(gè)運(yùn)算

F1,F2,…Fm,構(gòu)成代數(shù)系統(tǒng)U,記作U=<X,F1,F2,…Fm>(m≥1)二.熟練掌握二元運(yùn)算的性質(zhì)的判斷及證明：<X,>和<X,,>是代數(shù)系統(tǒng),,是二元運(yùn)算：1.封閉性：x,y∈X,有xy∈X。2.可交換性：x,y∈X,有xy=yx。3.冪等性：

x∈X,有xx=x。4.

有幺元：e∈X,

x∈X，有ex=xe=x.5.有零元:θ∈x,x∈X，有θx=xθ=θ.6.可結(jié)合性：x,y,z∈X,有(xy)z=x(yz)。.7.有逆元：x∈X,有x-1∈X，使得

x-1x=xx-1=e8.可消去性：a∈X，x,y∈X,有

(ax=ay)∨(xa=ya)x=y.

9.分配律：對(duì)可分配：x,y,z∈X，有

x(yz)=(xy)(xz)或(xy)z=(xz)(yz)10.吸收律：x,y∈X，有x(xy)=x和x(xy)=x對(duì)這些性質(zhì)要求會(huì)判斷、會(huì)證明。

三.掌握代數(shù)系統(tǒng)同構(gòu)定義,會(huì)證明.了解同構(gòu)性質(zhì)的保持1.定義設(shè)<X,>,<Y,>是兩個(gè)代數(shù)系統(tǒng)，和都是二元運(yùn)算，如果存在映射F:XY,使得對(duì)任何x1,x2∈X，有

F(x1x2)=F(x1)F(x2)--------此式叫同態(tài)(同構(gòu))關(guān)系式則稱F是從<X,>到<Y,>的同態(tài)映射，簡(jiǎn)稱這兩個(gè)代數(shù)系統(tǒng)同態(tài)。記作X∽Y。并稱<F(X),>為<X,>的同態(tài)像。如果F是滿射的，稱此同態(tài)0是滿同態(tài)。如果F是入射的，稱此同態(tài)0是單一同態(tài)。如果F是雙射的，稱<X,>與<Y,>同構(gòu)，記作X≌Y。0是<X,>到

<X,>的同態(tài)(同構(gòu)),稱之為自同態(tài)(自同構(gòu))。2.代數(shù)系統(tǒng)同構(gòu)性質(zhì)的保持代數(shù)系統(tǒng)<X,>,<Y,>,X≌Y,0:XY是同構(gòu)映射,如果<X,>中滿足交換、結(jié)合、有幺元、有零元、每個(gè)元素可逆,則<Y,>中也滿足上述性質(zhì)。反之亦然.四.掌握半群,幺半群,群的概念.半群:封閉結(jié)合幺半群:

有幺元群可逆群與半群廣群二元運(yùn)算的封閉性結(jié)合律半群幺元幺半群每個(gè)元素可逆群交換律交換半群交換律交換幺半群交換律Abel群有限個(gè)元素有限群生成元循環(huán)群實(shí)例n元置換群實(shí)例Klein群例題以下哪些為半群、幺半群、群？1.代數(shù)系統(tǒng)<R，+>，其中R是實(shí)數(shù)集合，“+”為普通加法2.代數(shù)系統(tǒng)<R，*>，其中R是實(shí)數(shù)集合，“*”為普通乘法第六章格與布爾代數(shù)1.掌握格的定義,了解格的性質(zhì).2.會(huì)判斷格,分配格,有補(bǔ)格和布爾格,3.重點(diǎn)掌握兩個(gè)元素的布爾代數(shù)的性質(zhì)(10個(gè)).一.掌握格的定義1.格的定義<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格。

二.格的性質(zhì)格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。

四.分配格1.定義<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)a,b,c∈A，有

a∨(b∧c)=(a∨b)∧(a∨c)，

a∧(b∨c)=(a∧b)∨(a∧c)則稱<A,≤>是分配格。2.二個(gè)重要的五元素非分配格：3.分配格的判定：一個(gè)格是分配格的充分且必要條件是在該格中沒(méi)有任何子格與上述兩個(gè)非分配格之一同構(gòu).3130

25dea

bc五.有界格

有界格定義：如果一個(gè)格存在全上界1與全下界0，則稱此格為有界格.六.有補(bǔ)格一個(gè)有界格中，如果每個(gè)元素都有補(bǔ)元，則稱之為有補(bǔ)格。七.布爾格有補(bǔ)分配格為布爾格。用“Y”表示“是”，用“N”表示“否”填下表。

<A1,≤><A2,≤><A3,≤><A4,≤>

格 有補(bǔ)格 布爾格YYNNNYNNNYNN1。2。4。8。16。

30。3。１。2。5

。10。15

。6。<A2,≤><A1,≤><A3,≤><A4,≤>第七章圖論1.掌握?qǐng)D的基本概念.(特別注意相似的概念)2.熟練掌握?qǐng)D中關(guān)于結(jié)點(diǎn)度數(shù)的定理.(會(huì)應(yīng)用)3.無(wú)向圖的連通性的判定,連通分支及連通分支數(shù)的概念.4.有向圖的可達(dá)性,強(qiáng)連通,單側(cè)連通和弱連通的判定.求強(qiáng)分圖,單側(cè)分圖和弱分圖.5.會(huì)求圖的矩陣.6.會(huì)判定歐拉圖和漢密爾頓圖.7.掌握樹(shù)的基本定義,v和e間的關(guān)系式.會(huì)畫生成樹(shù),會(huì)求最小生成樹(shù).8。根樹(shù)的概念,完全m叉樹(shù)的公式,會(huì)畫最優(yōu)二叉樹(shù),會(huì)設(shè)計(jì)前綴碼.一.