離散數(shù)學復習

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

PQP僅當Q(僅當Q，則P):

PQ除非P否則Q：PQ只要Ｐ，就有Ｑ：P

Q只有Ｐ，才能Ｑ：

Q

P定義一般翻譯為雙條件優(yōu)先級：

高低1、只有你主修計算機科學或者不是新生，才能從校園內訪問因特網(wǎng)。

解：設P：你能從校園內訪問因特網(wǎng)；Q：你是新生；

R：你主修計算機科學。則原題譯為：

P(R∨

Q)2、除非你已滿16周歲，否則只要你身高不足4英尺就不能乘公園滑行鐵道。解：設P：你已滿16周歲；

Q：你身高不足4英尺；

R：你能乘公園滑行鐵道。則原題譯為：

P(Q

R)推理理論P規(guī)則T規(guī)則證明方法：直接證法反證法CP規(guī)則(CP規(guī)則可以連續(xù)使用)原子命題拆成：客體＋謂詞全稱量詞“”，存在量詞“”翻譯注意：特性謂詞的位置：在全稱量詞的作用域內作條件句的前件，在存在量詞的作用域內作合取項。課后習題、上課例題看看Ch2謂詞邏輯量化斷言與命題的關系假設個體域D={a1,a2，…，an}(x)(P(x))P(a1)∧P(a2)∧…

∧P(an)(x)(P(x))P(a1)∨P(a2)∨…∨P(an)謂詞演算的推理理論消去、添加量詞規(guī)則全稱指定US全稱推廣UG存在指定ES存在推廣EG在謂詞推理中，必須注意的兩點：不能在量詞的作用域內使用等價式和蘊含式在同一證明中，若既要使用存在指定，又要使用全稱指定，則先用存在指定，后用全稱指定。謂詞推理理論P規(guī)則、T規(guī)則、US、UG、ES、EG證明方法：直接證法反證法CP規(guī)則課后習題、上課例題看看Ch3集合與關系定理集合A和B相等的充分必要條件是這兩個集合互為子集。集合的運算、、－(相對補)、～(絕對補)、(對稱差)運算的性質序偶與笛卡兒積關系的性質自反、對稱、傳遞、反自反、反對稱關系性質的證明方法：要證明R在X上自反假設x∈X，證出<x,x>∈R

要證明R在X上對稱對x,y∈X,設<x,y>∈R，證出

<y,x>∈R

要證明R在X上傳遞對x,y,z∈X,設<x,y>∈R∧<y,z>∈R，證出<x,z>∈R

要證明R在X上反自反假設x∈X，證出<x,x>?R）要證明R在X上反對稱對x,y∈X，設<x,y>∈R∧<y,x>∈R，證出x＝y(tǒng)關系的的運算：、、－(相對補)、～(絕對補)、(對稱差)關系的復合、關系的逆、關系的閉包運算集合的劃分與覆蓋劃分可以確定一個等價關系覆蓋可以確定一個相容關系(不同的覆蓋可能構造出相同的相容關系)。等價關系與等價類及其性質序關系偏序關系、哈斯圖、極大元、極小元、最大元、最小元、上界、下界、上確界、下確界函數(shù)函數(shù)的概念入射、滿射、雙射逆函數(shù)(當f是雙射函數(shù)時逆函數(shù)才有意義。)復合函數(shù)(注意寫法與關系的復合不同。)求gof時，若ranf

不包含于

domg，則gof為空復習書上定理和課后習題Ch5代數(shù)系統(tǒng)運算的性質(封閉性、交換性、結合性、分配律、吸收律、等冪律)特殊的元素(幺元、零元、逆元)廣群、半群、獨異點、群和子群阿貝爾群和循環(huán)群設<S，*>是一個半群，如果S是一個有限集，則必有對于bS

,

b*bS，記b2=b*bb2*b=b*b2S，記b3=b2*b=b*b2……由于S是有限集，所以必存在j>i，使得bi=bj……證明方法舉例：證明a是b的逆元?

a*b=b*a=e

例如：(a*b)-1=b-1*a-1群中滿足消去律群中不可能有零元。任何一個循環(huán)群必定是阿貝爾群。群<G,*>中的幺元e必定也是其子群<S,*>中的幺元。子群的判定定理：當Ｓ是有限集：*在Ｓ上封閉當Ｓ是無限集：a，b∈S，

有a*b-1∈S任何質數(shù)階的群必定是循環(huán)群。

陪集與拉格朗日定理設<H，*>是群<G,*>的一個子群，a∈G，則集合{a}H稱為由a所確定的H在G中的左陪集，記為aH。拉格朗日定理。書上定理和課后習題。每個圖中結點度數(shù)的總和等于邊數(shù)的兩倍。

Σdeg(v)=2|E|在任何有向圖中，所有結點的出度之和等于所有結點的入度之和。無向圖的連通性:連通性是結點集合上的一種等價關系。點割集、邊割集有向圖的可達性：強連通=>單側連通＝>弱連通強分圖、單側分圖、弱分圖在有向圖G=<V,E>中，它的每一個結點位于且只位于一個強分圖中。Ch7圖論歐拉圖與漢密爾頓圖給定無孤立結點圖G，若存在一條回路，經(jīng)過圖中的每邊一次且僅一次，該回路為歐拉回路。具有歐拉回路的圖，稱為歐拉圖。無向圖G具有一條歐拉回路當且僅當G是連通的，且所有結點度數(shù)全為偶數(shù)。

給定圖G，若存在一條回路，經(jīng)過圖中每個結點恰好一次，這條回路稱為漢密爾頓回路。具有哈密爾頓回路的圖，稱為漢密爾頓圖。平面圖一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。設有一個連通的平面圖G，共有v個結點e條邊和r個面，則歐拉公式v－ｅ＋r＝２成