離散數(shù)學復習(08)

1、Ch1命題邏輯命題邏輯數(shù)理邏輯：研究一種形式語言，其本質是將數(shù)理邏輯：研究一種形式語言，其本質是將數(shù)學中的邏輯證明加以數(shù)學中的邏輯證明加以符號化符號化，因而推動各，因而推動各數(shù)學分支的迅速發(fā)展。數(shù)學分支的迅速發(fā)展。命題：表示判斷的具有確定真值的陳述句。命題：表示判斷的具有確定真值的陳述句。 命題只要能判斷真假，不一定已知真假命題只要能判斷真假，不一定已知真假 非陳述性語句不是命題非陳述性語句不是命題 方程不是命題方程不是命題 悖論不是命題悖論不是命題聯(lián)結詞聯(lián)結詞 否定否定 合取合取 析取：析取： 條件條件 雙條件雙條件 翻譯提示：翻譯提示： 不可兼或：不可兼或： (P Q ) 當當 P則則Q(

2、如果如果P，那么，那么Q) : P Q P僅當僅當 Q(僅當僅當Q，則，則P) : P Q 除非除非P否則否則Q： P P Q Q 只要，就有：只要，就有： P P Q Q 只有，才能：只有，才能： Q Q P P 定義一般翻譯為定義一般翻譯為雙條件雙條件優(yōu)先級：優(yōu)先級：高高低低1、只有你主修計算機科學或者不是新生，才能從校園內、只有你主修計算機科學或者不是新生，才能從校園內 訪問因特網(wǎng)。訪問因特網(wǎng)。2、除非你已滿、除非你已滿16周歲，否則只要你身高不足周歲，否則只要你身高不足4英尺就不英尺就不能乘公園滑行鐵道。能乘公園滑行鐵道。3、只要充分考慮一切論證，就能得到可靠見解。、只要充分考慮一切論

3、證，就能得到可靠見解。4、只有充分考慮一切論證，才能得到可靠見解。、只有充分考慮一切論證，才能得到可靠見解。5、我們不能既唱歌又看書。、我們不能既唱歌又看書。6、如果天下雨，我出不出去看你是否同意而定。、如果天下雨，我出不出去看你是否同意而定。7、我唱歌，僅當你伴奏。、我唱歌，僅當你伴奏。8、或者你沒有給我寫信，或者信在路上丟失了。、或者你沒有給我寫信，或者信在路上丟失了。9、如果天下雨，我就在家看書，否則我就去看電影。、如果天下雨，我就在家看書，否則我就去看電影。10、只有你考試不及格或者缺考，才能參加補考。、只有你考試不及格或者缺考，才能參加補考。11、除非你缺考，否則只要你考試不滿、除非

4、你缺考，否則只要你考試不滿60分就必須參加分就必須參加 補考。補考。 推理理論推理理論 P規(guī)則規(guī)則 T規(guī)則規(guī)則證明方法：證明方法： 直接證法直接證法 反證法反證法 CP規(guī)則規(guī)則(CP規(guī)則可以連續(xù)使用規(guī)則可以連續(xù)使用)1、 A B C D , DE F A F2、 PQ, QR, R S PS3、 P (QR) ,Q P, S R P S4、A(BC),(CD) E, F (D E) A(BF) 原子命題拆成：原子命題拆成：客體客體 謂詞謂詞 全稱量詞全稱量詞“ ”，存在量詞存在量詞“ ”翻譯注意：翻譯注意： 特性謂詞的位置：在特性謂詞的位置：在全稱量詞全稱量詞的作用域內作的作用域內作條件條件句

5、的前件句的前件，在，在存在量詞存在量詞的作用域內作的作用域內作合取項合取項。1、所有的人都犯錯誤。、所有的人都犯錯誤。2、有且僅有一個偶質數(shù)。、有且僅有一個偶質數(shù)。3、有些人對所有酒都感興趣。、有些人對所有酒都感興趣。4、所有的人都對某些酒感興趣。、所有的人都對某些酒感興趣。5、盡管有人可惡，但并不是所有的人都可惡。、盡管有人可惡，但并不是所有的人都可惡。6、對于任意實數(shù)，存在更大的實數(shù)。、對于任意實數(shù)，存在更大的實數(shù)。7、某些火車比所有飛機慢，但至少有一架飛機比所有火車快。、某些火車比所有飛機慢，但至少有一架飛機比所有火車快。 8、并非所有的人都喜歡喝酒。、并非所有的人都喜歡喝酒。Ch2謂詞

6、邏輯謂詞邏輯量化斷言與命題的關系量化斷言與命題的關系假設個體域假設個體域D=a1, a2，an( x) (P(x) P(a1) P(a2) P(an)( x)(P(x) P(a1) P(a2) P(an)謂詞演算的推理理論謂詞演算的推理理論消去、添加量詞規(guī)則消去、添加量詞規(guī)則 全稱指定全稱指定 US 全稱推廣全稱推廣 UG 存在指定存在指定 ES 存在推廣存在推廣 EG在謂詞推理中，必須注意的兩點：在謂詞推理中，必須注意的兩點： 不能在量詞的作用域內使用等價式和蘊含式不能在量詞的作用域內使用等價式和蘊含式 在同一證明中，若既要使用存在指定，又要使用全稱在同一證明中，若既要使用存在指定，又要使用

7、全稱指定，則先用存在指定，后用全稱指定。指定，則先用存在指定，后用全稱指定。謂詞推理理論謂詞推理理論 P規(guī)則、規(guī)則、T規(guī)則、規(guī)則、 US、UG、ES、EG證明方法：直接證法證明方法：直接證法 反證法反證法 CP規(guī)則規(guī)則1、( x)(P(x) Q(x) ( x)P(x) ( x)Q(x)2、( x)A(x) ( x)B(x) ( x)(A(x) B(x) 3、( x)P(x) ( x)(P(x)Q(x) R(x), ( x)P(x),( x)Q(x) ( x)( y)(R(x) R(y)4、( x) (A(x)B(x) ( x)A(x)( x)B(x)5、 ( x)(F(x) S(x) ( y)

8、(M(y) W(y), ( y)(M(y) W(y) ( x)(F(x) S(x) 6、 ( x)(F(x)H(x), ( x)(G(x)H(x) ( x)(G(x) F(x)Ch3 集合與關系集合與關系 定理定理 集合集合A和和B相等的充分必要條件是這兩個相等的充分必要條件是這兩個集合互為子集。集合互為子集。 集合的運算集合的運算 、 、( (相對補相對補) )、 ( (絕對絕對補補)、 ( (對稱差對稱差) 運算的性質運算的性質 序偶與笛卡兒積序偶與笛卡兒積1、若、若C ， 則則 AB ACBC 2、設、設A,B為兩個集合，若為兩個集合，若AB ，則，則 (AB)(AB)(AA)(BB)3

9、、證明、證明 P(A)P(B)=P(AB) 4、設A和和B是論域是論域E的子集，的子集，B= A A B=E A B= 關系性質的證明方法：關系性質的證明方法： 要證明要證明R R在在X X上自反上自反 假設假設 x xX X ，證出，證出 R 要證明要證明R R在在X X上對稱上對稱 對對 x,x,y y X,X,設設R ，證出，證出 R 要證明要證明R R在在X X上傳遞上傳遞 對對 x,y,zX,x,y,zX,設設R R ，證出，證出 R 要證明要證明R R在在X X上反自反上反自反 假設假設 x xX X，證出，證出 R ） 要證明要證明R R在在X X上反對稱上反對稱 對對 x,x,

10、y yX X，設，設RR ，證出，證出 x xy y 關系的性質關系的性質自反、對稱、自反、對稱、傳遞、反自反、傳遞、反自反、反對稱反對稱關系的關系的的運算：的運算： 、 、( (相對補相對補) )、 ( (絕對補絕對補)、 ( (對稱差對稱差) 關系的復合、關系的復合、關系的逆、關系的閉包運算關系的逆、關系的閉包運算集合的劃分與覆蓋集合的劃分與覆蓋劃分可以確定一個等價關系劃分可以確定一個等價關系覆蓋可以確定一個相容關系覆蓋可以確定一個相容關系等價關系與等價類及其性質等價關系與等價類及其性質序關系序關系偏序關系、哈斯圖、極大元、極小元、最大元、偏序關系、哈斯圖、極大元、極小元、最大元、最小元、

11、最小元、上界、下界、上確界、下確界上界、下界、上確界、下確界1、設、設R是集合是集合X上的一個自反關系。則上的一個自反關系。則R是對稱和傳遞的，當是對稱和傳遞的，當 且僅當且僅當RR，有，有在在R之中。之中。2、若關系、若關系R和和S在集合在集合X上是等價的，證明上是等價的，證明RS也是等價的。也是等價的。3、如果關系如果關系R在集合在集合X上是等價的，證明上是等價的，證明Rc也是等價的。也是等價的。4、設、設R是集合是集合A上的等價關系，則對于所有上的等價關系，則對于所有a,b A ，或者，或者 aR=bR或者或者aR bR= 。5、設集合設集合A有一個劃分有一個劃分S=S1,S2,Sm，試

12、由此劃分確定一，試由此劃分確定一 個等價關系。個等價關系。6、設、設S是是X上的二元關系，上的二元關系，S是傳遞的當且僅當是傳遞的當且僅當S S S。7、設、設R是是X上的二元關系，則上的二元關系，則: a）R是對稱的，當且僅當是對稱的，當且僅當R=Rc b）R是反對稱的，當且僅當是反對稱的，當且僅當R R c Ix函數(shù)函數(shù) 函數(shù)的概念函數(shù)的概念 入射、滿射、雙射入射、滿射、雙射 逆函數(shù)逆函數(shù)(當當f 是是雙射雙射函數(shù)時逆函數(shù)才有意義。函數(shù)時逆函數(shù)才有意義。) 復合函數(shù)復合函數(shù)(注意寫法與關系的復合不同。注意寫法與關系的復合不同。) 求求go of時，若時，若ranf 不包含于不包含于 dom

13、g，則，則go of為空為空1、令、令gof是一個復合函數(shù)，則是一個復合函數(shù)，則 (1)若若g 和和f 是滿射的是滿射的,則則 gof 是滿射的；是滿射的； (2)若若g 和和f 是入射的是入射的,則則 gof 是入射的；是入射的； (3)若若g 和和f 是雙射的是雙射的,則則 gof 是雙射的。是雙射的。2、令、令gof是復合函數(shù)，則是復合函數(shù)，則 (1)若若gof 是滿射的是滿射的,則則g是滿射的；是滿射的； (2)若若gof 是入射的是入射的,則則f是入射的；是入射的； (3)若若gof 是雙射的是雙射的,則則g是滿射的，是滿射的，f是入射的。是入射的。Ch5 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 運算的性

14、質運算的性質(封閉性、交換性、結合性、分配律、吸收封閉性、交換性、結合性、分配律、吸收律、等冪律律、等冪律) 特殊的元素特殊的元素(幺元、零元、逆元幺元、零元、逆元) 廣群、半群、獨異點、群和子群廣群、半群、獨異點、群和子群 阿貝爾群和循環(huán)群阿貝爾群和循環(huán)群設設是一個半群，如果是一個半群，如果S是一個有限集，則必有是一個有限集，則必有對于對于 b S , b*b S，記，記b2=b*b b2*b=b*b2 S，記，記b3=b2*b=b*b2 由于由于S是有限集，所以必存在是有限集，所以必存在 ji，使得，使得bi=bj 證明方法舉例：證明方法舉例：證明證明a是是b的逆元的逆元? a * b=

15、b * a =e例如：例如：(a * b)-1=b-1 * a-1 群中滿足消去律群中滿足消去律 群中不可能有零元。群中不可能有零元。 任何一個循環(huán)群必定是阿貝爾群。任何一個循環(huán)群必定是阿貝爾群。 群群中的幺元中的幺元 e 必定也是其子必定也是其子群群中的幺元。中的幺元。 子群的判定定理：當是子群的判定定理：當是有限集有限集： *在上封閉在上封閉 當是當是無限集無限集： a，bS， 有有a*b-1S 任何質數(shù)階的群必定是循環(huán)群。任何質數(shù)階的群必定是循環(huán)群。陪集與拉格朗日定理陪集與拉格朗日定理設設是群是群 的一個子群，的一個子群，aG，則集合，則集合 aH稱為由稱為由a所確所確定的定的H在在G中

16、的左陪集，記為中的左陪集，記為aH。拉格朗日定理。拉格朗日定理。1、設、設是一個半群，如果是一個半群，如果S是一個有限集，則必有是一個有限集，則必有aS，使，使得得a*a=a。2、設、設是一個群，是一個群，B是是G的非空子集，如果的非空子集，如果B是一是一 個有限集，個有限集，那末只要運算那末只要運算*在在B上封閉，上封閉，必定是必定是的子群。的子群。3、設、設是群，是群，S是是G的非空子集，如果對于的非空子集，如果對于S中的中的 任意元素任意元素a和和b有有a*b-1S，則，則是是的子群。的子群。4、設、設是有限的可交換獨異點，且對任意的是有限的可交換獨異點，且對任意的a,b,cS，等式，等

17、式 a*b=a*c 蘊含著蘊含著 b = c，證明，證明是阿貝爾群。是阿貝爾群。5、設、設是一個群，是一個群，是阿貝爾群的充要條件是阿貝爾群的充要條件 是對任意是對任意的的a,bG，有，有(a*b)*(a*b)=(a*a)*(b*b)6、設、設是群是群的子群，的子群， A=x|xG , x*H*x-1=H，證明，證明是是的一個子群。的一個子群。7、設、設是群是群的子群，的子群， aH和和bH是是H在在G中的任意中的任意兩個左陪集，證明：或者兩個左陪集，證明：或者aH=bH，或者，或者aHbH=。 8、若、若是半群，是半群，e是左幺元且對每一個是左幺元且對每一個xA，存在，存在x1A使得使得x1

18、 * x = e。 a)證明：對于任意的證明：對于任意的a，b，cA，如果，如果a*ba*c，則，則bc。 b)通過證明通過證明e是是中的幺元，證明中的幺元，證明是群。是群。9、證明：循環(huán)群的同態(tài)象必定是循環(huán)群。、證明：循環(huán)群的同態(tài)象必定是循環(huán)群。 每個圖中每個圖中結點度數(shù)結點度數(shù)的總和等于的總和等于邊數(shù)邊數(shù)的兩倍。的兩倍。 deg(v)= 2|E|deg(v)= 2|E| 在任何有向圖中，所有結點的出度之和等于所有結點的在任何有向圖中，所有結點的出度之和等于所有結點的入度之和。入度之和。 無向圖的連通性無向圖的連通性:連通性是結點集合上的一種連通性是結點集合上的一種等價關系等價關系。 點割集

19、、邊割集點割集、邊割集 有向圖的可達性：強連通有向圖的可達性：強連通=單側連通單側連通弱連通弱連通 強分圖、單側分強分圖、單側分圖、圖、弱分圖弱分圖在有向圖在有向圖G=中，它的每一個結點位于且只位于一中，它的每一個結點位于且只位于一個強分圖中。個強分圖中。Ch7 圖論圖論歐歐拉圖與漢密爾頓圖拉圖與漢密爾頓圖 給定給定無孤立結點圖無孤立結點圖G ，若存在一條回路，經(jīng)過圖中的，若存在一條回路，經(jīng)過圖中的每邊一次且僅一次，該回路為每邊一次且僅一次，該回路為歐拉回路歐拉回路。具有。具有歐拉回歐拉回路路的圖，稱為的圖，稱為歐拉圖歐拉圖。 無向圖無向圖G具有一條具有一條歐拉回路歐拉回路當且僅當當且僅當G是

20、是連通連通的，且的，且所所有結點度數(shù)全為偶數(shù)有結點度數(shù)全為偶數(shù)。 給定圖給定圖G G，若存在一條回路，經(jīng)過圖中每個結點恰好一，若存在一條回路，經(jīng)過圖中每個結點恰好一次，這條回路稱為次，這條回路稱為漢密爾頓回路漢密爾頓回路。具有具有哈密爾頓回路哈密爾頓回路的圖，稱為的圖，稱為漢密爾頓圖漢密爾頓圖。平面圖平面圖 一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。 設有一個連通的平面圖設有一個連通的平面圖G，共有，共有v個結點個結點e條邊和條邊和r個面，個面，則歐拉公式則歐拉公式vr成立。成立。 設是一個有個結點條邊的設是一個有個結點條邊的連通連通簡單簡單平面圖平面圖， 若若v3，則，則v。樹與生成樹樹與生成樹一個一個連通且無回路連通且無回路的無向圖稱為的無向圖稱為樹樹。一個無回路的無向圖稱作一個無回路的無向圖稱作森林森林任一樹中任一樹中e=v-1任一棵樹中至少有兩片樹葉。任一棵樹中至少有兩片樹葉。連通圖至少有一顆生成樹。連通圖至少有一顆生成樹。以下關于樹的定義是等價的。以下關于樹的定義是等價的。 無回路的連通圖。無回路的連通圖。 無回