離散數(shù)學(xué)期末復(fù)習(xí)大綱

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

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

量詞分配公式.4.會用等價公式求謂詞公式的真值.(如P66題(3))*5.會寫前束范式6.熟練掌握謂詞邏輯推理.第三章集合論初步1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明.3.集合的五種運(yùn)算及相關(guān)性質(zhì).*4.應(yīng)用包含排斥原理.離散數(shù)學(xué)期末復(fù)習(xí)大綱第四章二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計算方法及有關(guān)性質(zhì))4.掌握等價關(guān)系的判斷,證明,求等價類和商集.*4.掌握相容關(guān)系定義,簡化圖和簡化矩陣,相容類,最大相容類,完全覆蓋.5.偏序關(guān)系的判斷,會畫Hasse圖,會求一個子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.第六章函數(shù)1.函數(shù)的定義.2.函數(shù)的類型,會判斷,會證明.3.會計算函數(shù)的復(fù)合(左復(fù)合),求逆函數(shù).知道有關(guān)性質(zhì).*4.了解集合的特征函數(shù),了解集合的基數(shù),可數(shù)集合.離散數(shù)學(xué)期末復(fù)習(xí)大綱第六章代數(shù)系統(tǒng)1.掌握運(yùn)算的定義.2.熟練掌握二元運(yùn)算的性質(zhì)的判斷及證明.3.掌握代數(shù)系統(tǒng)的同構(gòu)定義,會證明.了解同構(gòu)性質(zhì)的保持.4.了解半群,獨(dú)異點(diǎn),*環(huán)和*域的概念.5.熟練掌握群,子群,交換群(會證明),了解循環(huán)群.*6,子群的陪集,Lagrange定理及其推論,(會應(yīng)用).*第七章格與布爾代數(shù)*

1.掌握格的定義,了解格的性質(zhì).*2.會判斷格,分配格,有補(bǔ)格和布爾格,*3.重點(diǎn)掌握兩個元素的布爾代數(shù)的性質(zhì)(10個).*4.會寫兩個元素的布爾表達(dá)式的范式.(實(shí)質(zhì)是第一章的主析取和主合取范式).離散數(shù)學(xué)期末復(fù)習(xí)大綱第八章圖論1.掌握圖的基本概念.(特別注意相似的概念)2.熟練掌握圖中關(guān)于結(jié)點(diǎn)度數(shù)的定理.(會應(yīng)用)3.無向圖的連通性的判定,連通分支及連通分支數(shù)的概念.4.有向圖的可達(dá)性,強(qiáng)連通,單側(cè)連通和弱連通的判定.求強(qiáng)分圖,單側(cè)分圖和弱分圖.5.會求圖的矩陣.6.會判定歐拉圖和漢密爾頓圖.*7.會判定平面圖,掌握歐拉公式.*8.了解對偶圖.9.掌握樹的基本定義,v和e間的關(guān)系式.會畫生成樹,會求最小生成樹.根樹的概念,完全m叉樹的公式,會畫最優(yōu)樹,*會設(shè)計前綴碼.離散數(shù)學(xué)期末復(fù)習(xí)大綱總復(fù)習(xí)復(fù)習(xí)重點(diǎn)第一章命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會命題符號化.3.永真式的證明.4.永真蘊(yùn)涵式的證明,記住并能熟練應(yīng)用常用公式.5.等價公式的證明,記住并能熟練應(yīng)用常用公式.6.會寫命題公式的范式,*能應(yīng)用范式解決問題.7.熟練掌握命題邏輯三種推理方法.離散數(shù)學(xué)期末復(fù)習(xí)大綱第一章命題邏輯1.聯(lián)結(jié)詞定義了六個邏輯聯(lián)結(jié)詞，分別是：

(1)否定“”(2)合取“∧”

(3)析取“∨”(4)異或“”

(5)蘊(yùn)涵“”(6)等價“”要熟練掌握這五個聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。：否定表示“不”∧：合取表示“不但…,而且...”“并且”∨：析取表示“或者－可兼取的或”：異或表示“或者－不可兼取的或”：蘊(yùn)涵表示“如果…,則...”:等價表示“當(dāng)且僅當(dāng)”“充分且必要”可以將這六個聯(lián)結(jié)詞看成六種“運(yùn)算”。離散數(shù)學(xué)期末復(fù)習(xí)大綱聯(lián)結(jié)詞的定義(包括真值表和含義).特別要注意：“或者”的二義性,即要區(qū)分給定的“或”是“可兼取的或∨”還是“不可兼取的或”?！啊钡挠梅ǎ缺硎尽俺浞謼l件”也表示“必要條件”,即要弄清哪個作為前件,哪個作為后件.

PQP∧QP∨QPQPQPQ

FFFFTTF

FTFTTFT

TFFTFFTTTTTTTF

離散數(shù)學(xué)期末復(fù)習(xí)大綱2.會命題符號化.

例如P:我有時間.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.用公式的等價變換,化簡成T.例如證明(R(QR)(PQ))P是永真式.證:上式(R(QR)(PQ))P(PQPQ)(R(QR)(PQ))P(公式的否定公式)((R(QR))((PQ)P)(結(jié)合律)((RQ)(RR))((PP)(QP)(分配律)(RQ)(QP)RQQPT(互補(bǔ),同一律)離散數(shù)學(xué)期末復(fù)習(xí)大綱4.永真蘊(yùn)涵式的證明,

記住常用的公式.

永真蘊(yùn)涵式:AB是永真式,則稱A永真蘊(yùn)涵B.(AB)

方法1.列真值表.

方法2.假設(shè)前件真,推出后件真.(即直接推理)

方法3.假設(shè)后件假,推出前件假.(即反證法)例證明(P(QR))((PQ)(PR))是永真蘊(yùn)涵式.證:假設(shè)后件(PQ)(PR)假,則PQ為T,PR為F,于是P為T,R為F,進(jìn)而又得Q為T.所以QR為F,所以前件P(QR)為F.所以(P(QR))((PQ)(PR))為永真式.

對于給定一個題,究竟是用哪種方法,原則上哪種都可以.但是哪個方法簡單,要根據(jù)具體題而定.ABA

BFFTFTTTFFTTT離散數(shù)學(xué)期末復(fù)習(xí)大綱5.等價公式的證明,記住常用的公式.

方法1.列真值表.

方法2.用公式的等價變換.

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

(PQ)∨R(P∧Q)R注意:不論是證明永真蘊(yùn)涵式,還是證明等價公式以及后邊的求公式的范式,命題邏輯推理,都應(yīng)用43頁的公式。必須記憶一些常用的公式如:P43表中的永真蘊(yùn)涵式:I1,I3,I9,I10,I11,I12,I13,等價公式:E1~

E16,E18,E19,E20,E21,離散數(shù)學(xué)期末復(fù)習(xí)大綱6.命題公式的范式1)析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)是合取式.

2)合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)是析取式.3)析取范式與合取范式的寫法.4)小項及小項的性質(zhì).

m3m2m1

m0PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFF離散數(shù)學(xué)期末復(fù)習(xí)大綱6)大項及其性質(zhì).M0M1M2M3PQP∨QP∨QP∨QP∨Q00FF

FTTT01FTT

FTT10TFTTFT11TTTTT

F7)主析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)小項.

8)主合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)大項.離散數(shù)學(xué)期末復(fù)習(xí)大綱9).會寫主析取范式和主合取范式.求下面命題公式的范式: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)RFFFTFFTTFTFFFTTTTFFFTFTTTTFFTTTT離散數(shù)學(xué)期末復(fù)習(xí)大綱方法2.用公式的等價變換.主析取范式;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)離散數(shù)學(xué)期末復(fù)習(xí)大綱已知A(P,Q,R)的主析取范式中含有如下小項:m0,m3,m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有大項:M1,M2,M6A(P,Q,R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)*范式的應(yīng)用如P39習(xí)題(7),(8):安排工作(排課表),判斷比賽名次,攜帶工具箱,…離散數(shù)學(xué)期末復(fù)習(xí)大綱7.會用三種推理方法,進(jìn)行邏輯推理.

會用三個推理規(guī)則:P,T,CP例如:證明((A∧B)C)∧D∧(C∨D)A∨B1.直接推理:⑴DP⑵C∨DP⑶CT⑴⑵I10

Q,(P∨Q)P⑷(A∧B)CP⑸(A∧B)T⑶⑷I12

Q,PQP⑹A∨BT⑸E8(P∧Q)P∨Q離散數(shù)學(xué)期末復(fù)習(xí)大綱((A∧B)C)∧D∧(C∨D)A∨B2.條件論證:適用于結(jié)論是蘊(yùn)涵式.A∨BAB⑴AP(附加前提)⑵(A∧B)CP⑶A(BC)T⑵E19⑷BCT⑴⑶I11⑸DP⑹C∨DP⑺CT⑸⑹I10

⑻BT⑷⑺I12⑼ABCP離散數(shù)學(xué)期末復(fù)習(xí)大綱((A∧B)C)∧D∧(C∨D)A∨B3.反證法:⑴(A∨B)P(假設(shè)前提)⑵A∧BT⑴E9⑶(A∧B)CP⑷CT⑵

⑸I11⑸DP⑹C∨DP⑺CT⑻⑼I10⑻C∧CT⑷⑺I9離散數(shù)學(xué)期末復(fù)習(xí)大綱

第二章謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會命題符號化.(如P60題(2))3.掌握常用的等價公式和永真蘊(yùn)涵式.包括:

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

量詞分配公式.4.會用等價公式求謂詞公式的真值.(如P66題(3))*5.會寫前束范式6.熟練掌握謂詞邏輯推理.離散數(shù)學(xué)期末復(fù)習(xí)大綱

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

客體:

客體變元,

謂詞,

量詞,

量詞后的指導(dǎo)變元,

量詞的轄域,

約束變元與自由變元,

論域,

全總個體域,

謂詞公式(WFF),

命題函數(shù),

前束范式,離散數(shù)學(xué)期末復(fù)習(xí)大綱2.會命題符號化.(如P60題(2))

命題的符號表達(dá)式與論域有關(guān)。當(dāng)論域擴(kuò)大時，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個名詞。如“所有自然數(shù)...”

、“有些大學(xué)生...”。如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關(guān)。

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

如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“∧”。另外有些命題里有的客體在句中沒有明確的量詞,而在寫它的符號表達(dá)式時,,必須把隱含的量詞明確的寫出來.離散數(shù)學(xué)期末復(fù)習(xí)大綱例如⑴金子閃光,但閃光的不一定都是金子.設(shè):G(x):x是金子.F(x):x閃光.x(G(x)F(x))x(F(x)G(x))x(G(x)F(x))x(F(x)G(x))⑵沒有大學(xué)生不懂外語.S(x):x是大學(xué)生.F(x):x外語.K(x,y):x懂得y.x(S(x)y(F(y)K(x,y)))x(S(x)y(F(y)K(x,y)))⑶有些液體可以溶解所有固體.F(x):x是液體.S(x):x是固體.D(x,y):x可溶解y.x(F(x)y(S(y)D(x,y)))⑷每個大學(xué)生都愛好一些文體活動。S(x):x是大學(xué)生,L(x,y):x愛好y,C(x):x是文娛活動，P(x):x是體育活動.)x(S(x)y((C(y)∨P(y))L(x,y)))

離散數(shù)學(xué)期末復(fù)習(xí)大綱3.掌握常用的等價公式和永真蘊(yùn)涵式.包括:

帶量詞的公式在論域內(nè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))離散數(shù)學(xué)期末復(fù)習(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.會用等價公式求謂詞公式的真值.(如P66題(3))例設(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))(TT)(TF)T離散數(shù)學(xué)期末復(fù)習(xí)大綱*5.將下面謂詞公式寫成前束范式(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)(變元換名)xyt((F(x,z)G(y)H(t,z))(轄域擴(kuò)充)離散數(shù)學(xué)期末復(fù)習(xí)大綱6.熟練掌握謂詞邏輯推理.1).注意使用ES、US、EG、UG的限制條件,特別是ES,UG2).對于同一個客體變元，既有帶也有帶的前提，去量詞時，應(yīng)先去后去，這樣才可以特指同一個客體c.3).去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。下面的作法是錯誤的：正確作法:⑴xP(x)→xQ(x)P⑴xP(x)→xQ(x)P⑵P(c)→xQ(x)US⑴⑵xP(x)∨xQ(x)T⑴E或⑵xP(x)→Q(c)ES⑴⑶xP(x)∨xQ(x)T⑵E實(shí)際上x的轄域擴(kuò)充后⑷x(P(x)∨Q(x))T⑶E量詞改成為x⑸P(c)∨Q(c)ES⑷⑹P(c)→Q(c)T⑸E離散數(shù)學(xué)期末復(fù)習(xí)大綱下面的作法是錯誤的：正確作法:⑴xP(x)P⑴xP(x)P⑵P(c)US⑴⑵xP(x)T⑴E實(shí)際上⑴中量詞不是⑶P(c)ES⑵

x而是x

⑴xyP(x,y)P⑴xyP(x,y)P⑵xP(x,c)ES⑴⑵yP(c,y)US⑴令P(x,y):y是x的生母，顯然⑵是個假命題4).添加量詞時，也要加在公式的最左邊，(即新加的量詞前也無任何符號??！)且其轄域作用到公式的末尾。 例如下面作法是錯誤的:⑴xP(x)→Q(c)P

⑵

xP(x)→yQ(y)EG⑴離散數(shù)學(xué)期末復(fù)習(xí)大綱例如.證明下面推理的有效性.證明:⑴x(A(x)∧D(x))P⑵A(a)∧D(a))

ES⑴⑶A(a)T⑵I⑷D(a))T⑵I⑸x(A(x)→(B(x)→C(x)))P⑹A(a)→(B(a)→C(a))US⑸⑺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⒀離散數(shù)學(xué)期末復(fù)習(xí)大綱第三章集合論初步1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明.3.集合的五種運(yùn)算及相關(guān)性質(zhì).*4.應(yīng)用包含排斥原理.離散數(shù)學(xué)期末復(fù)習(xí)大綱第三章集合論初步基本概念:集合與元素,子集與真子集,空集,全集,冪集,并集,交集,相對補(bǔ)集(差集),絕對補(bǔ)集(補(bǔ)集)1.集合的表示,元素與集合的屬于關(guān)系∈.

集合的三種表示方法:

枚舉法:一一列出集合中的元素.

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

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

離散數(shù)學(xué)期末復(fù)習(xí)大綱3空集,全集,冪集空集φ:無元素的集合.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)離散數(shù)學(xué)期末復(fù)習(xí)大綱例1.已知全集E={Φ,{Φ}},AE,計算:a)P({Φ})P({Φ})=()b)P(A)∩P(~A)=()c)P(E)-P(~{{Φ}})=()解:a)因?yàn)槿魏渭螦,都有AA=Φ所以

P({Φ})P({Φ})=Φb)因?yàn)棣礎(chǔ)Φ~A,即Φ∈P(A)Φ∈P(~A)所以

P(A)∩P(~A)={Φ}c)P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}~{{Φ}}={Φ}P(~{{Φ}})=P({Φ})={Φ,{Φ}}P(E)-P(~{{Φ}}))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}={{{Φ}},{Φ,{Φ}}}離散數(shù)學(xué)期末復(fù)習(xí)大綱例2證明各式彼此等價。PQ(P∨Q)∧(P∨Q)c)A∪B=B,A∩B=A,AB,~B~A.證明.A∪B=B

x(x∈A∪Bx∈B)x((xA∪Bx∈B)(x∈A∪BxB))x(((xAxB)x∈B)((x∈Ax∈B)xB))x((xAxB)x∈B)x((xAx∈B)(xBx∈B))x((xAx∈B)x(x∈Ax∈B)ABx(x∈Ax∈B)x(xBxA)x(x∈~Bx∈~A)~B~A

由A∪B=B得A(A∪B)=ABA=AB類似由A∩B=A,可以推出A∪B=B

所以A∪B=BA∩B=A從而證得A∪B=B,A∩B=A,AB,~B~A彼此等價。T離散數(shù)學(xué)期末復(fù)習(xí)大綱例3證明:

(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)例4.令全集E為信息學(xué)院的學(xué)生的集合,C表示計算機(jī)專業(yè)學(xué)生的集合,M表示學(xué)習(xí)了離散數(shù)學(xué)的學(xué)生的集合,D表示學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課學(xué)生的集合,F表示一年級的學(xué)生的集合.用集合的關(guān)系式表達(dá)下面句子.“學(xué)習(xí)了離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)課的學(xué)生,一定是計算機(jī)專業(yè)的非一年級的學(xué)生”.

解.(M∩D)(C∩~F)離散數(shù)學(xué)期末復(fù)習(xí)大綱例4.在什么條件下，下面命題為真？a)(A-B)∪(A-C)=A解.(A-B)∪(A-C)=(A∩~B)∪(A∩~C)=A∩(~B∪~C)=A∩~(B∩C)=A-(B∩C)=A

所以滿足此式的充要條件是：A∩B∩C=Φb)(A-B)∪(A-C)=Φ解.(A-B)∪(A-C)=A-(B∩C)=Φ充要條件是：AB∩Cc)(A-B)∩(A-C)=Φ解.(A-B)∩(A-C)=(A∩~B)∩(A∩~C)=A∩(~B∩~C)=A∩~(B∪C)=A-(B∪C)=Φ充要條件是:AB∪Cd)(A-B)(A-C)=Φ解.因?yàn)楫?dāng)且僅當(dāng)A=B，才有AB=Φ所以滿足此式的充要條件是:A-B=A-C離散數(shù)學(xué)期末復(fù)習(xí)大綱*例5.用謂詞邏輯推理證明對任何集合A、B、C，如果有AB且BC，則AC。證明:x(x∈Ax∈B)x(x∈BxA),x(x∈Bx∈C)x(x∈CxB)x(x∈Ax∈C)x(x∈CxA)⑴x(x∈Ax∈B)x(x∈BxA)P⑵x(x∈Ax∈B)T⑴I⑶x(x∈BxA)T⑴I⑷x(x∈Bx∈C)x(x∈CxB)P⑸x(x∈Bx∈C)T⑷I⑹x∈Ax∈BUS⑵⑺x∈Bx∈CUS⑸⑻x∈Ax∈CT⑹⑺I⑼x(x∈Ax∈C)UG⑻⑽x∈BxAES⑶⑾x∈BT⑽I⑿xAT⑽I⒀x∈CT⑺⑾I⒁x∈CxAT⑿⒀I⒂x(x∈CxA)EG⒁⒃x(x∈Ax∈C)x(x∈CxA)T⑼⒂I離散數(shù)學(xué)期末復(fù)習(xí)大綱*有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人;問沒有得到優(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人.∴沒有得到優(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離散數(shù)學(xué)期末復(fù)習(xí)大綱

第四章二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計算方法及有關(guān)性質(zhì))4.掌握等價關(guān)系的判斷,證明,求等價類和商集.*5.掌握相容關(guān)系的概念,關(guān)系圖和矩陣的簡化,求相容類,最大相容類和完全覆蓋.6.偏序關(guān)系的判斷,會畫Hasse圖,會求一個子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.

注意本章證明題的證明過程的思路離散數(shù)學(xué)期末復(fù)習(xí)大綱一.關(guān)系的概念,表示方法,三個特殊關(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是一個從A到

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

如果|A|=m|B|=n則可以確定2mn個從A到B的不同關(guān)系.定義2:任何序偶的集合，都稱之為一個二元關(guān)系。離散數(shù)學(xué)期末復(fù)習(xí)大綱3.關(guān)系的表示方法1).枚舉法:

即將關(guān)系中所有序偶一一列舉出，寫在大括號內(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:離散數(shù)學(xué)期末復(fù)習(xí)大綱4).矩陣表示法：(實(shí)際上就是圖論中的鄰接矩陣)

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

RA×B，定義R的m×n階矩陣MR=(rij)m×n，其中4.三個特殊關(guān)系1).空關(guān)系Φ：

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

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

：

A×B(或A×A)本身是一個從A到B(或A上)的完全關(guān)系.即含有全部序偶的關(guān)系。它的矩陣中全是1。1若<ai,bj>∈R0若<ai,bj>∈R(1≤i≤m,1≤j≤n)rij=離散數(shù)學(xué)期末復(fù)習(xí)大綱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離散數(shù)學(xué)期末復(fù)習(xí)大綱二.關(guān)系的性質(zhì):

熟練掌握性質(zhì)的判斷及證明.1.自反性定義:設(shè)R是集合A中的關(guān)系，如果對于任意x∈A都有

<x,x>∈R(xRx)，則稱R是A中自反關(guān)系。即

R是A中自反的x(xAxRx)2.反自反性定義：設(shè)R是集合A中的關(guān)系，如果對于任意的x∈A都有

<x,x>R，則稱R為A中的反自反關(guān)系。即

R是A中反自反的x(xA<x,x>R)3.對稱性定義:R是集合A中關(guān)系,若對任何x,y∈A,如果有xRy,必有

yRx,則稱R為A中的對稱關(guān)系。

R是A上對稱的xy((xAyAxRy)yRx)離散數(shù)學(xué)期末復(fù)習(xí)大綱4.反對稱性定義:設(shè)R為集合A中關(guān)系,若對任何x,y∈A,如果有xRy,和

yRx,就有x=y,則稱R為A中反對稱關(guān)系。R是A上反對稱的xy((xAyAxRyyRx)

x=y)xy((xAyAxy<x,y>∈R)<y,x>R)5.傳遞性定義:R是A中關(guān)系，對任何x,y,z∈A,如果有xRy,和yRz,就有xRz,則稱R為A中傳遞關(guān)系。即R在A上傳遞xyz((xAyAzAxRyyRz)xRz)這些性質(zhì)要求會判斷,會證明.這里特別要注意的是,這些定義都是蘊(yùn)涵式,所以當(dāng)蘊(yùn)涵式當(dāng)前件為假時,此蘊(yùn)涵式為真,即此性質(zhì)成立!!離散數(shù)學(xué)期末復(fù)習(xí)大綱自反性反自反性對稱性傳遞性反對稱性每個結(jié)點(diǎn)都有環(huán)主對角線全是1每個結(jié)點(diǎn)都無環(huán)主對角線全是0不同結(jié)點(diǎn)間如果有邊,則有方向相反的兩條邊.是以對角線為對稱的矩陣不同結(jié)點(diǎn)間,最多有一條邊.以主對角線為對稱的位置不會同時為1如果有邊<a,b>,<b,c>,則也有邊<a,c>.或者使得前件為假.如果aij=1,且ajk=1,則aik=1從關(guān)系的矩陣從關(guān)系的有向圖

性質(zhì)判定:離散數(shù)學(xué)期末復(fù)習(xí)大綱判斷下面關(guān)系的性質(zhì):1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性對稱性反對稱性傳遞性R1YNNYYR2NYNYNR3YNYNYR4YNYYY離散數(shù)學(xué)期末復(fù)習(xí)大綱1。2。。1。2。。1。2。。1。2。。3333R5R6R7R8自反性反自反性對稱性反對稱性傳遞性R5NYNYYR6NNYNNR7NNNNNR8NYYYY離散數(shù)學(xué)期末復(fù)習(xí)大綱關(guān)系性質(zhì)當(dāng)證明方法歸納:設(shè)R是A上關(guān)系，1.證明R的自反性：方法1

用自反定義證：任取x∈A,證出<x,x>∈R.方法2

用恒等關(guān)系IA證：證出IA

R.(見教材P119(2))方法3

用自反閉包證：證出r(R)=R,即R∪IA=R.2.證明R的反自反性：方法1

用反自反定義證：任取x∈A,證出<x,x>R.3.證明R的對稱性：方法1

用對稱定義證：任取x,y∈A,設(shè)<x,y>∈R,證出<y,x>∈R.方法2

用求逆關(guān)系證：證出Rc=R.方法3

用對稱閉包證：證出s(R)=R,即R∪Rc=R.離散數(shù)學(xué)期末復(fù)習(xí)大綱4.證明R的反對稱性：方法1

用定義1證：任取x,y∈A,設(shè)<x,y>∈R,<y,x>∈R.證出x=y。方法2用定義2證：任取x,y∈A,x≠y,設(shè)<x,y>∈R,證出<y,x>R.

方法3

用定理證：證出R∩RcIA.(見教材P118)5.證明R的傳遞性：方法1

用傳遞定義證：任取x,y,z∈A,設(shè)<x,y>∈R,<y,z>∈R,證出<x,z>∈R.方法2

用傳遞閉包證：證出t(R)=R,

即R∪R2∪R3∪...=R.方法3用定理證：證出

(見教材P119(2))同學(xué)們可以根據(jù)具體情況,選用相應(yīng)方法證明.其中必須掌握的是用基本定義證明.RRRo離散數(shù)學(xué)期末復(fù)習(xí)大綱三.掌握關(guān)系復(fù)合,求逆及閉包運(yùn)算(計算方法及性質(zhì))(一)關(guān)系的復(fù)合

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

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

⑴枚舉法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>}

⑵有向圖a。b。

c。X。。。YabcRS。。。Zabc。。。Zabca。b。

c。X離散數(shù)學(xué)期末復(fù)習(xí)大綱⑶矩陣3.性質(zhì)1).滿足結(jié)合律:RA×BSB×CTC×D則

R(ST)=(RS)T2).RA×BSB×CTB×C⑴R(S∪T)=(RS)∪(RT)⑵R(S∩T)(RS)∩(RT)3).R是從A到B的關(guān)系，則

RIB=IAR=R

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

RmRn=Rm+n(Rm)n=Rmn(m,n為非負(fù)整數(shù))MRS=010001100010011100=011100010離散數(shù)學(xué)期末復(fù)習(xí)大綱(二).逆關(guān)系1.定義

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

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

1).(RC)C=R

2).(R∪S)C=RC∪SC

。

3).(R∩S)C=RC∩SC

。

4).(R－S)C=RC－SC

。離散數(shù)學(xué)期末復(fù)習(xí)大綱5).RSRC

SC

。

6).(~R)C=~RC7).令R是從X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則

(RS)C=SC

RC

。

8).R是A上關(guān)系，則⑴R是對稱的，當(dāng)且僅當(dāng)RC=R⑵R是反對稱的，當(dāng)且僅當(dāng)R∩RCIA。

離散數(shù)學(xué)期末復(fù)習(xí)大綱(三).閉包運(yùn)算1.定義：給定A中關(guān)系R,若A上另一個關(guān)系R’，滿足：⑴RR’；⑵R’是自反的(對稱的、傳遞的)；⑶R’是“最小的”，即對于任何A上自反(對稱、傳遞)的關(guān)系R”,如果RR”,就有R’R”。則稱R’是R的自反(對稱、傳遞)閉包。記作r(R)、(s(R)、t(R))(reflexive、

symmetric、transitive)2.計算方法給定A中關(guān)系R

r(R)=R∪IA。

s(R)=R∪RC。

t(R)=R∪R2∪R3∪...

。

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

*求t(R)矩陣的Warshall算法.離散數(shù)學(xué)期末復(fù)習(xí)大綱閉包的運(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∪RC={<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>}

t(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>}離散數(shù)學(xué)期末復(fù)習(xí)大綱b)有向圖形式.bacR3RbacbacIA∪=r(R)bac∪RbacbR2act(R)bac∪=c∪Rbac=bRCas(R)bac離散數(shù)學(xué)期末復(fù)習(xí)大綱c)矩陣形式.Mr(R)=MR∨MIA=010001100100010001∨=111110011Ms(R)=MR∨MRC=010001100001100010∨=011101110Mt(R)=M∨M∨M=010001100001100010∨=111111111R2R3R∨100010001離散數(shù)學(xué)期末復(fù)習(xí)大綱3.性質(zhì)1).R是A上關(guān)系，則⑴R是自反的，當(dāng)且僅當(dāng)r(R)=R.⑵R是對稱的，當(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是對稱的，則r(R)和t(R)也對稱。⑶R是傳遞的，則r(R)也傳遞。*3).設(shè)R是A上關(guān)系，則

⑴

sr(R)=rs(R)

⑵tr(R)=rt(R)

⑶st(R)ts(R)離散數(shù)學(xué)期末復(fù)習(xí)大綱四.等價關(guān)系

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

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.等價關(guān)系定義:設(shè)R是A上關(guān)系,若R是自反的、對稱的和傳遞的，則稱R是A中的等價關(guān)系。

3.等價關(guān)系R的有向圖:可能由若干個獨(dú)立子圖構(gòu)成的，每個獨(dú)立子圖都是完全關(guān)系圖。1。2。。3R11。2。。3R21。2。。R3離散數(shù)學(xué)期末復(fù)習(xí)大綱4.等價類：1).定義:R是A上的等價關(guān)系,a∈A,由a確定的集合[a]R[a]R={x|x∈A∧<a,x>∈R}

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

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

⑴同一個等價類中的元素，彼此有等價關(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必屬于且僅屬于一個等價類。⑸.任意兩個等價類

[a]R,[b]R,

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

。⑹R的所有等價類構(gòu)成的集合是A的一個劃分。離散數(shù)學(xué)期末復(fù)習(xí)大綱5.商集:定義：R是A上等價關(guān)系，由R的所有等價類構(gòu)成的集合稱之為A關(guān)于R的商集。記作A/R。即

A/R={[a]R|a∈A}6.商集應(yīng)用.1)按照集合的等勢關(guān)系(是等價關(guān)系)“~”對集合族S進(jìn)行劃分，得到商集S/~，進(jìn)而得到基數(shù)類的概念。S={0,Φ,1,{1},{a},…,2,{0,1},{a,b},…,3,{0,1,2},…,N,I,…R,..}S/~={[0],[1],[2],[3],…,[N],[R],...}2).無向圖結(jié)點(diǎn)之間的連通關(guān)系是個等價關(guān)系.

令G=<V,E>是無向圖,R是V上連通關(guān)系,即

R={<u,v>|u和v是連通的}例.給定圖G如右上圖所示:V/R={{a,b,g},{c,d,e,f},{h}}無元素1個元素2個元素3個元素可數(shù)集不可數(shù)集...ghabefcd離散數(shù)學(xué)期末復(fù)習(xí)大綱3).圖的同構(gòu)關(guān)系≌是個等價關(guān)系.

令上述圖構(gòu)成的集合A={a,b,c,d,e,f,g,h,i,j,},求商集A/≌.A/≌={{a,h},{b,i},{c,e},puo4my9,{f},{g,j}}abcdefghij離散數(shù)學(xué)期末復(fù)習(xí)大綱練習(xí)1.R和S都是A上等價關(guān)系,下面哪個是A上等價關(guān)系?證明或舉反例說明.a)R∪Sb)R∩Sc)~R(即A×A-R)d)R-Se)R2f)r(R-S)e)Rc解.a)c)d)f)不是.請看反例:R。a。cb。。a。cb。。a。cb。SR∪S。a。cb。~R。a。cb。R’。a。cb。R’-S。a。cb。r(R’-S)離散數(shù)學(xué)期末復(fù)習(xí)大綱b)R∩S是等價關(guān)系.證明：1.證明R∩S的自反性方法1

用自反定義證：任取x∈A,(證出<x,x>∈R∩S)因R和S都自反，所以有<x,x>∈R，<x,x>∈S，于是有<x,x>∈R∩S，所以R∩S也自反。方法2

用恒等關(guān)系IA證：(證出IA

R)因R和S都自反，所以IA

R，IA

S，所以IA

R∩S所以R∩S也自反。方法3

用自反閉包證：

(證出r(R∩S)=R∩S,即(R∩S)∪IA=R∩S)因R和S都自反，所以r(R)=R,r(S)=S,r(R∩S)=(R∩S)∪IA=(R∪IA)∩(S∪IA)=r(R)∩r(S)=R∩S所以R∩S也自反。離散數(shù)學(xué)期末復(fù)習(xí)大綱2.證明R∩S的對稱性：方法1

用對稱定義證：任取x,y∈A,設(shè)<x,y>∈R∩S,(證出<y,x>∈R∩S.)則<x,y>∈R，<x,y>∈S，因?yàn)镽和S對稱，所以有<y,x>∈R，<y,x>∈S，于是<y,x>∈R∩S?！郣∩S對稱。方法2

用求逆關(guān)系證：(證出(R∩S)c=R∩S.)因?yàn)镽和S對稱，所以有Rc=R，Sc=S，而(R∩S)c=Rc∩Sc=R∩S

，∴R∩S對稱。方法3

用對稱閉包證：(證出s(R∩S)=R∩S,)因?yàn)镽和S對稱，所以s(R)=R,s(S)=Ss(R∩S)=(R∩S)∪(R∩S)c=(R∩S)∪(Rc∩Sc)=(R∪Rc)∩(R∪Sc)∩(S∪Sc)∩(S∪Rc)

=(s(R)∩(R∪Sc))∩(s(S)∩(S∪Rc))=(R∩(R∪Sc))∩(S∩(S∪Rc))=R∩S(吸收律)∴R∩S對稱。離散數(shù)學(xué)期末復(fù)習(xí)大綱3.證明R∩S的傳遞性：方法1

用傳遞定義證：任取x,y,z∈A,

設(shè)<x,y>∈R∩S,<y,z>∈R∩S,(證出<x,z>∈R∩S)<x,y>∈R∩S∧<y,z>∈R∩S<x,y>∈R∧<x,y>∈S∧<y,z>∈R∧<y,z>∈S(<x,y>∈R∧<y,z>∈R)∧(<x,y>∈S∧<y,z>∈S)

<x,z>∈R∧<x,z>∈S

（因?yàn)?/p>