總復(fù)習(xí)復(fù)習(xí)重點命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會命題符號化.3.永真式的證明.4.永真蘊涵式的證明,記住并能熟練應(yīng)用常用公式.5.等價公式的證明,記住并能熟練應(yīng)用常用公式.6.會寫命題公式的范式,能應(yīng)用范式解決問題.7.熟練掌握命題邏輯三種推理方法.謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會命題符號化.3.掌握常用的等價公式和永真蘊涵式.包括:帶量詞的公式在論域內(nèi)展開式,量詞否認,量詞轄域擴充,量詞分配公式.4.會用等價公式求謂詞公式的真值.5.會寫前束范式6.熟練掌握謂詞邏輯推理.二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運算(計算方法及有關(guān)性質(zhì))4.掌握等價關(guān)系的判斷,證明,求等價類和商集.5.偏序關(guān)系的判斷,會畫Hasse圖,會求一個子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.第八章圖論1.掌握圖的根本概念.(特別注意相似的概念)2.熟練掌握圖中關(guān)于結(jié)點度數(shù)的定理.(會應(yīng)用)3.無向圖的連通性的判定,連通分支及連通分支數(shù)的概念.4.有向圖的可達性,強連通,單側(cè)連通和弱連通的判定.求強分圖,單側(cè)分圖和弱分圖.5.會求圖的矩陣.6.會判定歐拉圖和漢密爾頓圖.7.會判定平面圖,掌握歐拉公式.8.掌握樹的根本定義,v和e間的關(guān)系式.會畫生成樹,會求最小生成樹.根樹的概念,完全m叉樹的公式,會畫最優(yōu)樹,會設(shè)計前綴碼.《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)會用三種推理方法,進行邏輯推理.例如:證明((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((A∧B)

C)∧

D∧(

C∨D)

A∨

B2.條件論證:適用于結(jié)論是蘊涵式.

A∨

B

A

B⑴AP(附加前提)⑵(A∧B)

CP⑶A(BC)T⑵E19⑷BCT⑴⑶I11⑸DP⑹C∨DP⑺CT⑸⑹I10

⑻BT⑷⑺I12⑼A

BCP((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用公式的等價變換.主析取范式;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í)《離散數(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)))

掌握常用的等價公式和永真蘊涵式.包括:帶量詞的公式在論域內(nèi)展開式,量詞否認,量詞轄域擴充,量詞分配公式.設(shè)論域為{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)→B

x(A(x)→B)8).

xA(x)→B

x(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))會用等價公式求謂詞公式的真值.例設(shè)論域為{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將下面謂詞公式寫成前束范式(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))(轄域擴充)《離散數(shù)學(xué)》總復(fù)習(xí)證明(x)(P(x)→(W(x)→T(x)),(x)(P(x)→(T(x)∨R(x)),(x)(P(x)∧R(x))(x)(P(x)∧W(x))(x)(P(x)∧R(x)) P規(guī)那么P(a)∧R(a) ES規(guī)那么P(a) T規(guī)那么(2)R(a) T規(guī)那么(2)(x)(P(x)→(T(x)∨R(x)) P規(guī)那么P(a)→(T(a)∨R(a)) US規(guī)那么(5)T(a)∨R(a) T規(guī)那么(3)(6)T(a) T規(guī)那么(4)(7)(x)(P(x)→(W(x)→T(x)) P規(guī)那么P(a)→(W(a)→T(a)) US規(guī)那么(9)W(a)→T(a) T規(guī)那么(3)(10)W(a) T規(guī)那么(8)(11)P(a)∧W(a) T規(guī)那么(3)(12)(x)(P(x)∧W(x)) EG規(guī)那么(13)首先使用含有存在量詞的前提例如.證明下面推理的有效性.證明:⑴

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⒀證明(x)(M(x)→(P(x)→Q(x))(x)Q(x)→(x)(M(x)∧P(x))(x)Q(x) P規(guī)那么〔附加前提〕(x)Q(x) T規(guī)那么(1)Q(a) US規(guī)那么(2)(x)(M(x)→(P(x)→Q(x)) P規(guī)那么M(a)→(P(a)→Q(a)) US規(guī)那么(4)M(a)∨P(a)∨Q(a) T規(guī)那么(5)M(a)∨P(a) T規(guī)那么(3)(6)(M(a)∧P(a)) T規(guī)那么(7)(x)(M(a)∧P(a)) UG規(guī)那么(8)(x)(M(x)∧P(x)) T規(guī)那么(9)(x)Q(x)→(x)(M(x)∧P(x)) CP規(guī)那么(1)(10)自反性反自反性對稱性傳遞性反對稱性每個結(jié)點都有環(huán)主對角線全是1每個結(jié)點都無環(huán)主對角線全是0不同結(jié)點間如果有邊,則有方向相反的兩條邊.是以對角線為對稱的矩陣不同結(jié)點間,最多有一條邊.以主對角線為對稱的位置不會同時為1如果有邊<a,b>,<b,c>,則也有邊<a,c>.或者使得前件為假.如果aij=1,且ajk=1,則aik=1從關(guān)系的矩陣從關(guān)系的有向圖性質(zhì)判定:關(guān)系性質(zhì)當(dāng)證明方法歸納:設(shè)R是A上關(guān)系，1.證明R的自反性：方法1

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

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

R.方法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.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.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用定理證：證出同學(xué)們可以根據(jù)具體情況,選用相應(yīng)方法證明.其中必須掌握的是用根本定義證明.RRRo證明：一.證明R∩S的自反性方法1

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

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

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

R，IA

S，所以IA

R∩S所以R∩S也自反。R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。方法3

用對稱閉包證：

(證出s(R∩S)=R∩S,即(R∩S)∪(R∩S)c=R∩S.)因為R和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對稱。證明：二.證明R∩S的對稱性：方法1用對稱定義證：任取x,y∈A,設(shè)<x,y>∈R∩S,(證出<y,x>∈R∩S.)那么<x,y>∈R，<x,y>∈S，因為R和S對稱，所以有<y,x>∈R，<y,x>∈S，于是<y,x>∈R∩S?！郣∩S對稱。R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。方法2

用求逆關(guān)系證：(證出(R∩S)c=R∩S.)因為R和S對稱，所以有Rc=R，Sc=S，而(R∩S)c=Rc∩Sc=R∩S∴R∩S對稱。證明：二.證明R∩S的對稱性：方法1用對稱定義證：任取x,y∈A,設(shè)<x,y>∈R∩S,(證出<y,x>∈R∩S.)那么<x,y>∈R，<x,y>∈S，因為R和S對稱，所以有<y,x>∈R，<y,x>∈S，于是<y,x>∈R∩S。∴R∩S對稱。R和S都A上是自反、對稱、傳遞的，求證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也自反。三.證明R的傳遞性：方法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〔因為R、S傳遞〕<x,z>∈R∩S所以R∩S傳遞。R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。三.證明R的傳遞性：方法2

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

即(R∩S)∪(R∩S)2∪(R∩S)3∪...=R∩S.方法3用定理證：證出(R∩S)

(R∩S)

R∩SR和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。用方法2、方法3證明此題的傳遞性有很大難度。R

(S∩T)

(R

S)∩(R

T)希望同學(xué)們靈活掌握證明關(guān)系性質(zhì)的方法。證明：“”設(shè)R是集合X上的一個自反關(guān)系，如果R是X上對稱和傳遞的，那么當(dāng)任意a，b，c∈X，假設(shè)有＜a，b＞∈R∧＜a，c＞∈R那么＜b，a＞∈R∧＜a，c＞∈R〔∵R是對稱的〕故得＜b，c＞∈R〔∵R是傳遞的〕設(shè)R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng)假設(shè)＜a，b＞和＜a，c＞在R之中，那么有＜b，c＞在R之中。證明：“”反之，假設(shè)＜a，b＞∈R和＜a，c＞∈R，那么＜b，c＞∈R成立，對任意x，y∈X，假設(shè)＜x，y＞∈R，∵R自反，∴＜x，x＞∈R，得到＜y，x＞∈R，故R是對稱的。設(shè)R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng)假設(shè)＜a，b＞和＜a，c＞在R之中，那么有＜b，c＞在R之中。對任意x，y，z∈X，假設(shè)＜x，y＞∈R且＜y，z＞∈R，∵R對稱，∴＜y，x＞∈R且＜y，z＞∈R，得到＜x，z＞∈R，故R是可傳遞的。

設(shè)R是集合A上的一個傳遞關(guān)系和自反關(guān)系，S是A上的一個關(guān)系，使得對任意a,b∈A，<a,b>∈S當(dāng)且僅當(dāng)<a,b>∈R且<b,a>∈R，試證明S是A上的一個等價關(guān)系。證明：1〕對任意a∈A，因R是自反的，所以<a,a>∈R。由<a,a>∈R并且<a,a>∈R，有<a,a>∈S，即S是自反的。2〕對任意a,b∈A，假設(shè)<a,b>∈S，那么由條件有<a,b>∈R并且<b,a>∈R，即有<b,a>∈R并且<a,b>∈R，所以，<b,a>∈S，即S是對稱的。3〕對任意a,b,c∈A，假設(shè)<a,b>∈S，<b,c>∈S，那么由條件有：<a,b>∈R并且<b,a>∈R和<b,c>∈R并且<c,b>∈R。所以，由<a,b>∈R并且<b,c>∈R，有<a,c>∈R；由<c,b>∈R并且<b,a>∈R，有<c,a>∈R；由：<a,c>∈R并且<c,a>∈R，有<a,c>∈S，即S是傳遞的。由1),2),3)知，S是A上的一個等價關(guān)系?！觥峨x散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)《離散數(shù)學(xué)》總復(fù)習(xí)解先求A的劃分：只有1個劃分塊的劃分為П1，具有2個設(shè)A={a,b,c}，求A上所有的等價關(guān)系。劃分塊的劃分為П2、П3和П4，具有3個劃分塊的劃分為П5，如以下圖所示。設(shè)Пi導(dǎo)出的等價關(guān)系為Пi，i=1,2,3,4,5。那么有R1={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}=