1、總 復(fù) 習(xí),復(fù)習(xí)重點 命題邏輯 1.聯(lián)結(jié)詞的定義(含義及真值表定義). 2.會命題符號化. 3.永真式的證明. 4.永真蘊涵式的證明,記住并能熟練應(yīng)用常用公式. 5.等價公式的證明,記住并能熟練應(yīng)用常用公式. 6.會寫命題公式的范式, 能應(yīng)用范式解決問題. 7.熟練掌握命題邏輯三種推理方法.,謂詞邏輯 1.準確掌握有關(guān)概念. 2.會命題符號化. 3.掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴充, 量詞分配公式. 4.會用等價公式求謂詞公式的真值. 5.會寫前束范式 6.熟練掌握謂詞邏輯推理.,二元關(guān)系 1.關(guān)系的概念,表示方法. 2.二元關(guān)系的 性

2、質(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.會判定平面圖, 掌握歐拉公式.

3、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í),會用三種推理方法,進行邏輯推理. 例如:證明 (AB)C)D(CD) AB 1.直接推理: D P CD P C T I10 Q, (PQ) P (AB)C P (AB) T I12 Q, PQ P AB T E8 (PQ)PQ,(AB)C)D(CD) AB 2.條件論證:適用于結(jié)論是蘊涵式. AB AB A P(附加前提) (AB)C P A(BC) T

4、 E19 BC T I11 D P CD P C T I10 B T I12 AB CP,(AB)C)D(CD) AB 3.反證法: (AB) P(假設(shè)前提) AB T E9 (AB)C P C T I11 D P CD P C T I10 CC T I9,用公式的等價變換. 主析取范式;A(P,Q,R) (PQ)R (PQ)R (PQ)R (PQ(RR)(PP)(QQ)R) (PQR) (PQR)(PQR) (PQR)(PQR)(PQR) (PQR )(PQR )(PQR) (PQR )(PQR ) 主合取范式:A(P,Q,R) (PQ)R (PQ)R (PQ)R ( PR )(QR) (

5、P(QQ)R )(PP)QR) (PQR )(PQR)(PQR ),離散數(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é)生都愛好一些文體活

6、動。 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(

7、x)B) 5). BxA(x)x(BA(x),6). BxA(x)x(BA(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) 會用等價公式求謂詞公式的真值. 例設(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

8、) 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)

9、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(

10、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)

11、(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),關(guān)系性質(zhì)當(dāng)證明方法歸納: 設(shè)R是A上關(guān)系， 1.證明R的自反性： 方法1 用自反定義證：任取 xA,證出R. 方法2 用恒等關(guān)系IA證：證出IA R. 方法3 用自反閉包證：證出r(R)=R, 即RIA=R. 2.證明R的反自反性： 方法1 用反自反定義證：任取 xA,證出R. 3.證明R的對稱性： 方法1 用對稱定義證： 任取 x,yA,設(shè)R, 證出 R. 方法2 用求逆關(guān)系證：證出 Rc=R. 方法3 用對稱閉包證：證出 s(R)=R, 即RRc =R.,4

12、.證明R的反對稱性： 方法1 用定義1證： 任取 x,yA,設(shè)R, R.證出 x=y。 方法2用定義2證： 任取 x,yA,xy, 設(shè)R,證出R. 方法3 用定理證：證出 RRc IA . 5.證明R的傳遞性： 方法1 用傳遞定義證： 任取 x,y,zA,設(shè)R,R, 證出 R. 方法2 用傳遞閉包證：證出 t(R)=R, 即 RR2R3. =R. 方法3用定理證：證出 同學(xué)們可以根據(jù)具體情況,選用相應(yīng)方法證明.其中必須掌 握的是用基本定義證明.,證明： 一.證明RS的自反性 方法1 用自反定義證： 任取 xA, (證出RS) 因R和S都自反， 所以有R，S， 于是有RS， 所以RS也自反。,R

13、和S都A上是自反、對稱、傳遞的，求證RS也 是自反、對稱和傳遞的。,方法2 用恒等關(guān)系IA證：(證出IA RS) 因R和S都自反， 所以 IA R ，IA S， 所以 IA RS 所以RS也自反。,R和S都A上是自反、對稱、傳遞的，求證RS也 是自反、對稱和傳遞的。,方法3 用對稱閉包證： (證出 s(RS)=RS, 即(RS)(RS)c=RS.) 因為R和S對稱， 所以s(R)=R,s(S)=S s(RS)= (RS)(RS)c =(RS)(RcSc) =(RRc)(RSc)(SSc)(SRc) =(s(R)(RSc)(s(S)(SRc) =(R(RSc)(S(SRc)=RS (吸收律) R

14、S對稱。,證明： 二.證明RS的對稱性： 方法1 用對稱定義證： 任取 x,yA,設(shè)RS, (證出 RS.) 則R，S， 因為R和S對稱， 所以有R，S， 于是RS。 RS對稱。,R和S都A上是自反、對稱、傳遞的，求證RS也 是自反、對稱和傳遞的。,方法2 用求逆關(guān)系證： (證出 (RS)c=RS.) 因為R和S對稱， 所以有Rc=R， Sc=S， 而(RS)c=RcSc=RS RS對稱。,證明： 二.證明RS的對稱性： 方法1 用對稱定義證： 任取 x,yA,設(shè)RS, (證出 RS.) 則R，S， 因為R和S對稱， 所以有R，S， 于是RS。 RS對稱。,R和S都A上是自反、對稱、傳遞的，求

15、證RS也 是自反、對稱和傳遞的。,方法3 用自反閉包證： (證出r(RS)=RS, 即 (RS)IA= RS) 因R和S都自反， 所以r(R)=R, r(S)=S, r(RS)=(RS)IA = (RIA)(SIA) = r(R)r(S)=RS 所以RS也自反。,三.證明R的傳遞性： 方法1 用傳遞定義證：任取 x,y,zA, 設(shè)RS,RS, (證出RS) RSRS RSRS (RR)(S S) RS （因為R、S傳遞） RS 所以RS傳遞。,R和S都A上是自反、對稱、傳遞的，求證RS也 是自反、對稱和傳遞的。,三.證明R的傳遞性： 方法2 用傳遞閉包證：證出 t(RS)=RS, 即 (RS)

16、(RS)2(RS)3. =RS. 方法3用定理證：證出(RS) (RS)RS,R和S都A上是自反、對稱、傳遞的，求證RS也 是自反、對稱和傳遞的。,用方法2、方法3證明此題的傳遞性有很大難度。 R(ST)(RS)(RT),希望同學(xué)們靈活掌握證明關(guān)系性質(zhì)的方法。,證明：“ ” 設(shè)R是集合X上的一個自反關(guān)系， 如果R是X上對稱和傳遞的， 則當(dāng)任意a，b，cX， 若有a，bRa，cR 則b，aRa，cR（ R是對稱的） 故得b，cR（ R是傳遞的）,設(shè)R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng)若a，b和a，c在R之中，則有b，c在R之中。,證明：“”反之， 若a，bR和a，cR，

17、則b，cR成立， 對任意x，yX， 若x，yR， R自反，x，xR， 得到y(tǒng)，xR， 故R是對稱的。,設(shè)R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng)若a，b和a，c在R之中，則有b，c在R之中。,對任意x，y，zX， 若x，yR且 y，zR， R對稱， y，xR 且y，zR， 得到x，zR， 故R是可傳遞的。,設(shè)R是集合A上的一個傳遞關(guān)系和自反關(guān)系，S是A上的一個關(guān)系，使得對任意a,bA，S當(dāng)且僅當(dāng)R且R，試證明S是A上的一個等價關(guān)系。,證明： 1）對任意aA，因R是自反的，所以R。由R并且R，有S，即S是自反的。 2）對任意a,bA，若S，則由已知條件有R并且R，即有R并且R

18、， 所以，S，即S是對稱的。,3）對任意a,b,cA，若S，S，則由已知條件有：R并且R和R并且R。所以，由R并且R，有R；由R并且R，有R；由：R并且R，有S，即S是傳遞的。 由1),2),3)知，S是A上的一個等價關(guān)系。,離散數(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=, ,=AA； R2=,； R3=,； R4=,； R5=,=IA。,離散數(shù)學(xué)總復(fù)習(xí),離散數(shù)學(xué)總復(fù)習(xí),今有a,b,c,d,e,f,g七個人,已知下列事