《離散數(shù)學》總復習

1、總 復 習,復習重點 命題邏輯1.聯(lián)結詞的定義(含義及真值表定義).2.會命題符號化.3.永真式的證明.4.永真蘊涵式的證明,記住并能熟練應用常用公式.5.等價公式的證明,記住并能熟練應用常用公式.6.會寫命題公式的范式, 能應用范式解決問題.7.熟練掌握命題邏輯三種推理方法.,謂詞邏輯1.準確掌握有關概念.2.會命題符號化.3.掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內展開式,量詞否定,

2、量詞轄域擴充, 量詞分配公式.4.會用等價公式求謂詞公式的真值.5.會寫前束范式6.熟練掌握謂詞邏輯推理.,二元關系1.關系的概念,表示方法.2.二元關系的 性質的定義, 熟練掌握性質的判斷及證明.3.掌握關系的復合,求逆及閉包運算(計算方法及有關性質)4.掌握等價關系的判斷,證明,求等價類和商集.5.偏序關系的判斷,會畫Hasse圖,會求一個子集的極小(大) 元,最小(大)元,上界與下界,最小上界及最大下界.,

3、第八章 圖論1.掌握圖的基本概念.(特別注意相似的概念)2.熟練掌握圖中關于結點度數(shù)的定理. (會應用)3.無向圖的連通性的判定,連通分支及連通分支數(shù)的概念.4.有向圖的可達性,強連通,單側連通和弱連通的判定.求強 分圖,單側分圖和弱分圖.5.會求圖的矩陣.6.會判定歐拉圖和漢密爾頓圖.7.會判定平面圖, 掌握歐拉公式.8.掌握樹的基本定義,v和e間的關系式.會畫生成樹,會求最小生成樹.根樹的概念,完全m叉樹的

4、公式,會畫最優(yōu)樹,會設計前綴碼.,《離散數(shù)學》總復習,《離散數(shù)學》總復習,《離散數(shù)學》總復習,《離散數(shù)學》總復習,,,,,,,,,,,,,《離散數(shù)學》總復習,《離散數(shù)學》總復習,,,,,,,,,,,,,,,,,《離散數(shù)學》總復習,會用三種推理方法,進行邏輯推理.例如:證明 ((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.條件論證:適用于結論是蘊涵式. ?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(假設前提)⑵A∧B T⑴ E9⑶(A∧B)?C P⑷ C T ⑵ ⑸ I11⑸ ?D P⑹

8、?C∨D P⑺?C T ⑻⑼ I10⑻C∧?C T ⑷ ⑺ 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

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ù)學》

10、總復習,,,,,,,,,,,,,《離散數(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)) ⑵沒有大學生不懂外語. S(x):x是大學生. F(x):x外語. 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)))⑷每個大學生都愛好一些文體活動。S(x):x是大學生,L(x,y):x愛好y, C(x):x是文娛活動，P(x):x是體育活動.) ?x(S(x)??y((C(y)∨P(y))?L(x,y))

12、),掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內展開式,量詞否定,量詞轄域擴充, 量詞分配公式. 設論域為{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))會用等價公式求謂詞公式的真值.例設論域為{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,將下面謂詞公式寫成前束范式(?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、 (變元換名)??x?y?t((F(x,z) ??G(y) ?H(t,z)) (轄域擴充),《離散數(shù)學》總復習,證明,(?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),,關系性質當證明方法歸納: 設R是A上關系，1.證明R的自反性：方法1 用自反定義證：任取 x∈A,證出∈R.方法2 用恒等關系IA證：證出IA ?R. 方法3 用自反閉包證：證出r(R)=R, 即R∪IA=R.2.證明R的反自反性：方法1 用反自反定義證：任取 x∈A,證出?R.3.證明R的對稱性：方法1 用對稱定義證： 任取 x,y∈A,設∈R, 證出 ∈R.方法2

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

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

25、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。,方法2 用恒等關系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)=

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

27、是∈R∩S?！郣∩S對稱。,R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。,方法2 用求逆關系證：(證出 (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,設∈R∩S, (證出 ∈R∩S.)則∈R，∈S，因為R和S對稱，所以有∈R，∈S，于是∈

28、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,

29、 設∈R∩S,∈R∩S, (證出∈R∩S)∈R∩S∧∈R∩S? ∈R∧∈S∧∈R∧∈S? (∈R∧∈R)∧(∈S ∧∈S)? ∈R∧∈S （因為R、S傳遞）? ∈R∩S 所以R∩S傳遞。,R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。,三.證明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上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。,用方法2、方法3證明此題的傳遞性有很大難度。R?(S∩T)?(R?S)∩(R?T),希望同學們靈活掌握證明關系性質的方法。,證明：“ ?”設R是集合X上的一個自反關系，如果R是X上對稱和傳遞的，則當任意a，b，c∈X，若有＜a，b＞∈R∧＜a，c＞∈R則＜b，a＞∈R∧＜a，c＞∈R（ ∵

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

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

33、,b∈A，若∈S，則由已知條件有∈R并且∈R，即有∈R并且∈R，所以，∈S，即S是對稱的。,3）對任意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上的一個等價關系。■,《離散數(shù)學》總復習,《離散數(shù)學》總復習,《離散數(shù)學》總復習,解先求A的劃分：只有1個劃分塊的劃分為П1，具有2個,

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

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

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

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