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

1、總 復(fù) 習(xí),復(fù)習(xí)重點(diǎn) 命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會(huì)命題符號(hào)化.3.永真式的證明.4.永真蘊(yùn)涵式的證明,記住并能熟練應(yīng)用常用公式.5.等價(jià)公式的證明,記住并能熟練應(yīng)用常用公式.6.會(huì)寫(xiě)命題公式的范式, 能應(yīng)用范式解決問(wèn)題.7.熟練掌握命題邏輯三種推理方法.,謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會(huì)命題符號(hào)化.3.掌握常用的等價(jià)公式和永真蘊(yùn)涵式.包括: 帶量詞的公式在論域內(nèi)展開(kāi)式,量詞否定,

2、量詞轄域擴(kuò)充, 量詞分配公式.4.會(huì)用等價(jià)公式求謂詞公式的真值.5.會(huì)寫(xiě)前束范式6.熟練掌握謂詞邏輯推理.,二元關(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)系的判斷,會(huì)畫(huà)Hasse圖,會(huì)求一個(gè)子集的極小(大) 元,最小(大)元,上界與下界,最小上界及最大下界.,

3、第八章 圖論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.會(huì)判定平面圖, 掌握歐拉公式.8.掌握樹(shù)的基本定義,v和e間的關(guān)系式.會(huì)畫(huà)生成樹(shù),會(huì)求最小生成樹(shù).根樹(shù)的概念,完全m叉樹(shù)的

4、公式,會(huì)畫(huà)最優(yōu)樹(shù),會(huì)設(shè)計(jì)前綴碼.,《離散數(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í),會(huì)用三種推理方法,進(jìn)行邏輯推理.例如:證明 ((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B1.直接推理:⑴ ?D P⑵ ?C∨D

5、 P⑶ ?C T ⑴⑵ I10 ?Q, (P∨Q) ?P⑷ (A∧B)?C P⑸ ?(A∧B) T ⑶⑷ I12 ?Q, P?Q ? ?P⑹ ?A∨?B T ⑸ E8 ?(P∧Q)??P∨?Q

6、,((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B2.條件論證:適用于結(jié)論是蘊(yùn)涵式. ?A∨?B ? A??B⑴A P(附加前提)⑵(A∧B)?C P⑶ A?(B?C) T⑵ E19⑷ B?C T⑴⑶ I11⑸?D P⑹?C∨D P⑺?C T ⑸⑹ I1

7、0 ⑻ ?B T ⑷⑺ I12⑼ A??B CP,((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B3.反證法:⑴ ?(?A∨?B) P(假設(shè)前提)⑵A∧B T⑴ E9⑶(A∧B)?C P⑷ C T ⑵ ⑸ I11⑸ ?D P⑹

8、?C∨D P⑺?C T ⑻⑼ I10⑻C∧?C T ⑷ ⑺ I9,用公式的等價(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

9、) ∨(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é)》

10、總復(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)) ⑵沒(méi)有大學(xué)生不懂外語(yǔ). S(x):x是大學(xué)生. F(x):x外語(yǔ). K(x,y):x懂得y. ??x(S(x)??y(F(y)??K(x

11、,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)))⑷每個(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))

12、),掌握常用的等價(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)??x?A(x) 2). ??xA(x)??x?A(x) 1). ?xA(x)∨B??x(A

13、(x)∨B) 2). ?xA(x)∧B??x(A(x)∧B) 3). ?xA(x)∨B??x(A(x)∨B) 4). ?xA(x)∧B??x(Ａ(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(

14、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))會(huì)用等價(jià)公式求謂詞公式的真值.例設(shè)論域?yàn)閧1,2},A(x,y):x+y=xy, 求??x?yA(x,y)的真值.??x?yA(x,y)? ?x?y?A(x,y)??y?A(1,y)??y?A(2,y)?(?A(1,1)??A(1,2))?(?A(2,1)?

15、?A(2,2))?(T?T)?(T?F) ?T,將下面謂詞公式寫(xiě)成前束范式(?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) ??y?G(y) ??xH(x,y) (量詞否定)??xF(x,z) ??y?G(y) ??tH(t,z)

16、 (變?cè)獡Q名)??x?y?t((F(x,z) ??G(y) ?H(t,z)) (轄域擴(kuò)充),《離散數(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)

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

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

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

20、⑷⑽ 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)U

21、S規(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

22、規(guī)則(1)(10),,關(guān)系性質(zhì)當(dāng)證明方法歸納: 設(shè)R是A上關(guān)系，1.證明R的自反性：方法1 用自反定義證：任取 x∈A,證出∈R.方法2 用恒等關(guān)系IA證：證出IA ?R. 方法3 用自反閉包證：證出r(R)=R, 即R∪IA=R.2.證明R的反自反性：方法1 用反自反定義證：任取 x∈A,證出?R.3.證明R的對(duì)稱性：方法1 用對(duì)稱定義證： 任取 x,y∈A,設(shè)∈R, 證出 ∈R.方法2

23、 用求逆關(guān)系證：證出 Rc=R.方法3 用對(duì)稱閉包證：證出 s(R)=R, 即R∪Rc =R.,4.證明R的反對(duì)稱性：方法1 用定義1證： 任取 x,y∈A,設(shè)∈R, ∈R.證出 x=y。方法2用定義2證： 任取 x,y∈A,x≠y, 設(shè)∈R,證出?R. 方法3 用定理證：證出 R∩Rc ? IA . 5.證明R的傳遞性：方法1 用傳遞定義證： 任取 x,y,z∈A,設(shè)∈R,∈R, 證

24、出 ∈R.方法2 用傳遞閉包證：證出 t(R)=R, 即 R∪R2∪R3∪... =R.方法3用定理證：證出 同學(xué)們可以根據(jù)具體情況,選用相應(yīng)方法證明.其中必須掌握的是用基本定義證明.,證明：一.證明R∩S的自反性方法1 用自反定義證：任取 x∈A, (證出∈R∩S)因R和S都自反，所以有∈R，∈S，于是有∈R∩S，所以R∩S也自反。,R和S都A上是自反、

25、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,方法2 用恒等關(guān)系IA證：(證出IA ?R∩S)因R和S都自反，所以 IA ?R ，IA ?S，所以 IA ?R∩S所以R∩S也自反。,R和S都A上是自反、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,方法3 用對(duì)稱閉包證： (證出 s(R∩S)=R∩S, 即(R∩S)∪(R∩S)c=R∩S.)因?yàn)镽和S對(duì)稱，所以s(R)=R,s(S)=Ss(R∩S)=

26、(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對(duì)稱。,證明：二.證明R∩S的對(duì)稱性：方法1 用對(duì)稱定義證：任取 x,y∈A,設(shè)∈R∩S, (證出 ∈R∩S.)則∈R，∈S，因?yàn)镽和S對(duì)稱，所以有∈R，∈S，于

27、是∈R∩S?！郣∩S對(duì)稱。,R和S都A上是自反、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,方法2 用求逆關(guān)系證：(證出 (R∩S)c=R∩S.)因?yàn)镽和S對(duì)稱，所以有Rc=R， Sc=S，而(R∩S)c=Rc∩Sc=R∩S ∴R∩S對(duì)稱。,證明：二.證明R∩S的對(duì)稱性：方法1 用對(duì)稱定義證：任取 x,y∈A,設(shè)∈R∩S, (證出 ∈R∩S.)則∈R，∈S，因?yàn)镽和S對(duì)稱，所以有∈R，∈S，于是∈

28、R∩S?！郣∩S對(duì)稱。,R和S都A上是自反、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,方法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,

29、 設(shè)∈R∩S,∈R∩S, (證出∈R∩S)∈R∩S∧∈R∩S? ∈R∧∈S∧∈R∧∈S? (∈R∧∈R)∧(∈S ∧∈S)? ∈R∧∈S （因?yàn)镽、S傳遞）? ∈R∩S 所以R∩S傳遞。,R和S都A上是自反、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,三.證明R的傳遞性：方法2 用傳遞閉包證：證出 t(R∩S)=R∩S, 即 (R∩S)∪(R∩S)2∪(R∩S)3∪...

30、=R∩S.方法3用定理證：證出(R∩S) ?(R∩S)?R∩S,R和S都A上是自反、對(duì)稱、傳遞的，求證R∩S也是自反、對(duì)稱和傳遞的。,用方法2、方法3證明此題的傳遞性有很大難度。R?(S∩T)?(R?S)∩(R?T),希望同學(xué)們靈活掌握證明關(guān)系性質(zhì)的方法。,證明：“ ?”設(shè)R是集合X上的一個(gè)自反關(guān)系，如果R是X上對(duì)稱和傳遞的，則當(dāng)任意a，b，c∈X，若有＜a，b＞∈R∧＜a，c＞∈R則＜b，a＞∈R∧＜a，c＞∈R（ ∵

31、 R是對(duì)稱的）故得＜b，c＞∈R（ ∵ R是傳遞的）,設(shè)R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)若＜a，b＞和＜a，c＞在R之中，則有＜b，c＞在R之中。,證明：“?”反之，若＜a，b＞∈R和＜a，c＞∈R，則＜b，c＞∈R成立，對(duì)任意x，y∈X，若＜x，y＞∈R，∵R自反，∴＜x，x＞∈R，得到＜y，x＞∈R，故R是對(duì)稱的。,設(shè)R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)若＜a，b＞

32、和＜a，c＞在R之中，則有＜b，c＞在R之中。,對(duì)任意x，y，z∈X，若＜x，y＞∈R且＜y，z＞∈R，∵R對(duì)稱，∴＜y，x＞∈R且＜y，z＞∈R，得到＜x，z＞∈R，故R是可傳遞的。,設(shè)R是集合A上的一個(gè)傳遞關(guān)系和自反關(guān)系，S是A上的一個(gè)關(guān)系，使得對(duì)任意a,b∈A，∈S當(dāng)且僅當(dāng)∈R且∈R，試證明S是A上的一個(gè)等價(jià)關(guān)系。,證明：1）對(duì)任意a∈A，因R是自反的，所以∈R。由∈R并且∈R，有∈S，即S是自反的。2）對(duì)任意a

33、,b∈A，若∈S，則由已知條件有∈R并且∈R，即有∈R并且∈R，所以，∈S，即S是對(duì)稱的。,3）對(duì)任意a,b,c∈A，若∈S，∈S，則由已知條件有：∈R并且∈R和∈R并且∈R。所以，由∈R并且∈R，有∈R；由∈R并且∈R，有∈R；由：∈R并且∈R，有∈S，即S是傳遞的。由1),2),3)知，S是A上的一個(gè)等價(jià)關(guān)系?！?《離散數(shù)學(xué)》總復(fù)習(xí),《離散數(shù)學(xué)》總復(fù)習(xí),《離散數(shù)學(xué)》總復(fù)習(xí),解先求A的劃分：只有1個(gè)劃分塊的劃分為П1，具有2個(gè),

34、設(shè)A={a,b,c}，求A上所有的等價(jià)關(guān)系。,劃分塊的劃分為П2、П3和П4，具有3個(gè)劃分塊的劃分為П5，如下圖所示。,設(shè)Пi導(dǎo)出的等價(jià)關(guān)系為Пi，i=1,2,3,4,5。則有R1={,,,,,,,,}=A?A；R2={,,,,}；R3={,,,,}；R4={,,,,}；R5={,,}=IA。,《離散數(shù)學(xué)》總復(fù)習(xí),,,,,,,,,《離散數(shù)學(xué)》總復(fù)習(xí),,,,,,,,,,,,,,,今有a,b,c,d,e,f,g七個(gè)人,已知下列

35、事實(shí): a:會(huì)講英語(yǔ). b:會(huì)講英語(yǔ)和漢語(yǔ). c:會(huì)講英語(yǔ),意大利語(yǔ)和俄語(yǔ) d:會(huì)講日語(yǔ)和漢語(yǔ). e:會(huì)講德語(yǔ)和意大利語(yǔ) f:會(huì)講法語(yǔ),日語(yǔ),俄語(yǔ) g:會(huì)講法語(yǔ)和德語(yǔ).試問(wèn)能否將這七個(gè)人適當(dāng)安排座位,使得每個(gè)人都能和他兩邊的人直接交談?若能,請(qǐng)給予安排.若不能,說(shuō)明理由.解. 以a,b,c,d,e,f,g為結(jié)點(diǎn),如果兩個(gè)人之間講同一種語(yǔ)言,則它們之間連一條直線.得到右圖.

36、 從此圖中找到H回路: abdfgeca按照此回路坐成一個(gè)圓圈,就可以使得每個(gè)人都可以和它兩邊的人直接交談.,《離散數(shù)學(xué)》總復(fù)習(xí),,,,,,,,,,證明: 多于一個(gè)頂點(diǎn)的樹(shù)，至少有兩片樹(shù)葉。,證明：設(shè) T=(V,E)是一棵樹(shù)，若T中最多只有一片樹(shù)葉，則有∑d(v) ≥1+2(|V|-1)=2|E|+1, 這與結(jié)論 ∑ d(v) =2|E| 矛盾! 矛盾說(shuō)明 T 不止一片樹(shù)葉。,證明: G或者G有一個(gè)是連通圖。

37、,,證明：因?yàn)镚不連通，則G可以分為若干連通子圖: G1=（V1，E1），--- ，Gn=（Vn，En） 根據(jù)G的補(bǔ)圖的構(gòu)造過(guò)程知V1中每個(gè)頂點(diǎn)與其它頂點(diǎn)集V2，--- ，Vn中頂點(diǎn)有邊相連。 這樣， 在G的補(bǔ)圖中，有,分別屬于兩個(gè)頂點(diǎn)子集Vi與Vj中的任意兩個(gè)頂點(diǎn)之間有邊直接相連，屬于同一個(gè)頂點(diǎn)子集Vi的任意兩個(gè)頂點(diǎn)借助頂點(diǎn)子集Vj的任意一個(gè)頂點(diǎn)連通。所以，根據(jù)連通的定義知：G的補(bǔ)圖一定連通 。,預(yù)