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

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

PQP僅當(dāng)Q(僅當(dāng)Q，則P):

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

Q只有Ｐ，才能Ｑ：

Q

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

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

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

R：你主修計(jì)算機(jī)科學(xué)。則原題譯為：

P(R∨

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

Q：你身高不足4英尺；

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

P(Q

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

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

要證明R在X上對(duì)稱(chēng)對(duì)x,y∈X,設(shè)<x,y>∈R，證出

<y,x>∈R

要證明R在X上傳遞對(duì)x,y,z∈X,設(shè)<x,y>∈R∧<y,z>∈R，證出<x,z>∈R

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

不包含于

domg，則gof為空復(fù)習(xí)書(shū)上定理和課后習(xí)題Ch5代數(shù)系統(tǒng)運(yùn)算的性質(zhì)(封閉性、交換性、結(jié)合性、分配律、吸收律、等冪律)特殊的元素(幺元、零元、逆元)廣群、半群、獨(dú)異點(diǎn)、群和子群阿貝爾群和循環(huán)群設(shè)<S，*>是一個(gè)半群，如果S是一個(gè)有限集，則必有對(duì)于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群中滿(mǎn)足消去律群中不可能有零元。任何一個(gè)循環(huán)群必定是阿貝爾群。群<G,*>中的幺元e必定也是其子群<S,*>中的幺元。子群的判定定理：當(dāng)Ｓ是有限集：*在Ｓ上封閉當(dāng)Ｓ是無(wú)限集：a，b∈S，

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

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

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

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