離散數(shù)學(xué)知識點(diǎn)整理

1、離散數(shù)學(xué)一、邏輯和證明1.1命題邏輯命題：是一個(gè)可以判斷真假的陳述句。聯(lián)接詞：八、V、一、？、？。記彳i“p僅當(dāng)q”意思是“如果p,則q"，即p-。記住“q除非p”意思是“？p-q”。會(huì)考察條件語句翻譯成漢語。構(gòu)造真值表pqpAqpVqp一qp?qpOq?pTTTTTTFF1TFFTFFTFFTFTTFTTFFFFTTFT1.2語句翻譯系統(tǒng)規(guī)范說明的一致性是指系統(tǒng)沒有可能會(huì)導(dǎo)致矛盾的需求，即若pq無論取何值都無法讓復(fù)合語句為真，則該系統(tǒng)規(guī)范說明是不一致的。1.3命題等價(jià)式邏輯等價(jià)：在所有可能情況下都有相同的真值的兩個(gè)復(fù)合命題，可以用真值表或者構(gòu)造新的邏輯等價(jià)式。證邏輯等價(jià)是通過p推導(dǎo)

2、出q,證永真式是通過p推導(dǎo)出T邏輯等價(jià)式pAT?p恒等律pVF?ppAF?FpVT?T支配律pAp?p幕等律?(?P)?p雙否律pAq?qAp交換律(pAq)Ar?pA(qAr)結(jié)合律pV(qAr)?(pVq)A(pVr)分配律pA(qVr)?(pAq)V(pAr)?(pAq)?pV?q德摩根律?(pVq)?pA?qpV(pAq)?p吸收律PA(pVq)?ppA?p?FpV?p?T否定律條件命題等價(jià)式p-q?pVqp-q?q一？ppVq?p-qpAq?(p-?q)?(p-q)?pA?q(p-q)A(p-r)?p一(qAr)(p-r)A(qr)？(pVq)-r(p-q)V(pr)？p一(qVr)

3、(p-r)V(qr)？(pAq)一r雙條件命題等價(jià)式p？q？(p一q)A(qp)p？q？p？qp？q？(pAq)V(？pA？q)？(p？q)？|p？q1.4量詞謂詞+量詞變成一個(gè)更詳細(xì)的命題，量詞要說明論域，否則沒有意義，如果有約束條件就直接放在量詞后面，如？x>0P(x)。當(dāng)論域中的元素可以列舉，那么？xP(x)就等價(jià)于P(x1)AP(x2)AP(xn)。同理，？xP(x)就等價(jià)于P(x1)VP(x2)VP(xn)。兩個(gè)語句是邏輯等價(jià)的，如果不論他們謂詞是什么，也不論他們的論域是什么，他們總有相同的真值，如？x(P(x)AQ(x)和(？xP(x)A(?xQ(x)。量詞表達(dá)式的否定：？x

4、P(x)？x？P(x),?？xP(x)？x？P(x)。1.5量詞嵌套我們采用循環(huán)的思考方法。量詞順序的不同會(huì)影響結(jié)果。語句到嵌套量詞語句的翻譯，注意論域。嵌套量詞的否定就是連續(xù)使用德摩根定律，將否定詞移入所有量詞里。1.6推理規(guī)則一個(gè)論證是有效的，如果它的所有前提為真且蘊(yùn)含著結(jié)論為真。但有效論證不代表結(jié)論正確，因?yàn)橐苍S有的前提是假的。推理規(guī)則，都是基于永真式的，用來證明一個(gè)前提蘊(yùn)含一個(gè)結(jié)論。而基于可涉足式的推理規(guī)則叫謬誤。pp-q(pA(p-q)一q假百推理qp-qq-r(p-q)A(q-r)(pr)假百二段論p-r？qp-q(？qA(pq)一?p取拒式？ppVq？p(pVq)A？p)-q析取

5、三段論qpp一(pVq)附加律pVqpAq(pAq)p化簡律ppq(pAq)(pAq)合取律pAqpVq?pVr(pVq)A(?pVr)一(qVr)消解律qVr量化推理規(guī)則?xP(x)全稱實(shí)例P(c)P(c),任意c全稱引入?P(x)?xP(x)存在實(shí)例P(c),對某個(gè)cP(c),對某個(gè)c存在引入?xP(x)命題和量化命題的組合使用二、集合、函數(shù)、序列、與矩陣2.1集合e說的是元素與集合的關(guān)系，？說的是集合與集合的關(guān)系。常見數(shù)集有N=0,1,2,3,Z整數(shù)集，Z+正整數(shù)集，Q有理數(shù)集，R實(shí)數(shù)集，R+正實(shí)數(shù)集,C復(fù)數(shù)集。A和B相等當(dāng)僅當(dāng)？x(xCA?xCB)；A是B的子集當(dāng)僅當(dāng)？x(xCA-xC

6、B)；A是B的真子集當(dāng)僅當(dāng)？x(xZxCB)A?x(x?AAxCB)。募集：集合元素的所有可能組合，肯定有？何它自身。如？的募集就是?,而?的募集是?,?。笛卡爾積：AXB,結(jié)果是序偶，其中的一個(gè)子集叫一個(gè)關(guān)系。帶量詞和集合符號如？xCR(x2>0)是真的，則所有真值構(gòu)成真值集。集合恒等式名稱(AUB)'=A'AB'(AAB)'=A'UB'德摩根律AU(AnB)=AAn(AUB)=A吸收律2.3函數(shù)考慮2B的函數(shù)關(guān)系，定義域、陪域(實(shí)信函數(shù)、整數(shù)值函數(shù))、值域、像集(定義域的一個(gè)子集在值域的元素集合)。一對一或者單射：B可能有多余的元素，但

7、不重復(fù)指向。映上或者滿射：B中沒有多余的元素，但可能重復(fù)指向。一一對應(yīng)或者雙射：符合上述兩種情況的函數(shù)關(guān)系。反函數(shù)：如果是一一對應(yīng)的就有反函數(shù)，否則沒有。合成函數(shù)：fog(a)=f(g(a),一般來說交換律不成立。2.4序列無限集分為：一組是和自然數(shù)集合有相同基數(shù)，另一組是沒有相同基數(shù)。前者是可數(shù)的，后者不可數(shù)。想要證明一個(gè)無限集是可數(shù)的只要證明它與自然數(shù)之間有對應(yīng)的關(guān)系。如果A和B是可數(shù)的，則AUB也是可數(shù)的。如果存在一對一函數(shù)f從A至UB和一對一函數(shù)g從B到A,那么A和B之間是一一對應(yīng)的。求和公式：a+ar+ar2+ar3+.+arn=(arn+1-a)/(r-1)1+2+3+.+n=n(

8、n+1)/21+22+32+.+n2=n(n+1)(2n+1)/61+23+33+.+n3=n2(n+1)2/42.6矩陣普通矩陣和、減、乘積，0-1矩陣還可以A、V、O(和相乘類似，用V代替+,用A代替X)九、關(guān)系9.1 關(guān)系及其性質(zhì)設(shè)A和B是集合，從A到B的二元關(guān)系是AXB的子集。一個(gè)從A到B的二元關(guān)系是集合R,第一個(gè)元素取自A,第二個(gè)元素取自B,當(dāng)(a,b)屬于R時(shí)寫作aRb。集合A上的關(guān)系是A到A的關(guān)系，有n個(gè)元素就有n2個(gè)有序?qū)Γ琻2個(gè)有序?qū)陀?n2個(gè)關(guān)系。考慮集合A到A的關(guān)系R任意aCA都有(a,a)R,則R是集合A上的自反關(guān)系。任意a,bCA,若(a,b)R都有(b,a)R,則

9、R是對稱關(guān)系。任意a,bCA,若(a,b)CR且(b,a)CR一定有a=b,則R是反對稱關(guān)系。任意a,b,cCA,若(a,b)CR且(b,c)R一定有(a,c)R,則R是傳遞關(guān)系。若R是A到B的關(guān)系，S是B到C的關(guān)系，R與S的合成RoS是有序數(shù)對(a,c)o其中aA,cCC,且存在一個(gè)bCB使得(a,b)CR,(b,c)CS。二元關(guān)系的5種復(fù)合要會(huì)翻譯成漢語。9.3 關(guān)系的表示0-1矩陣法：A有n個(gè)元素，B有m個(gè)元素，用一個(gè)nXm的矩陣MR表示，m=1表示有關(guān)系。自反關(guān)系的0-1矩陣主對角線全為1；對稱關(guān)系的0-1矩陣是對稱陣；反對稱關(guān)系的0-1矩陣關(guān)于主對角線反對稱。MRwr2=MRiVMR

10、2,Minr尸MiAM2,MR10R2=MliOMR20有向圖法：A有n個(gè)元素，每一個(gè)關(guān)系是一條有向邊。自反關(guān)系的圖每一個(gè)頂點(diǎn)都有一個(gè)環(huán)；對稱關(guān)系的圖在不同頂點(diǎn)之間每一條邊都存在與之對應(yīng)的反方向邊(也可用無向圖)；反對稱關(guān)系的圖在不同頂點(diǎn)之間每一條邊都不存在與之對應(yīng)的反方向邊；傳遞關(guān)系的圖在3個(gè)不同頂點(diǎn)之間構(gòu)成正確方向的三角形。9.4 關(guān)系的閉包自反閉包：RUA,其中A=(a,a)|aCA對稱閉包：R并R1,其中R1=(b,a)|(a,b)R傳遞閉包：R矩陣傳遞閉包=MVM2VMR3VMRn,了解沃舍爾算法9.5 等價(jià)關(guān)系：自反、對稱且傳遞的關(guān)系集合A的元素a在R上的等價(jià)類a=s(a,s)CR

11、AsCA。如A=1,2,3,4,5,6,7,8，R=(a,b)|a=b(mod3)的等價(jià)類劃分如下1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,69.6 偏序關(guān)系：自反、反對稱且傳遞的的關(guān)系偏序集(S,<)中如果既沒有a<b,也沒有b<a,則a和b是不可比的。全序集：如果偏序集中每個(gè)元素都可比，則為全序集，如(Z,<)是全序集，但(Z+,|)不是，因?yàn)橛?和7是不可比的。良序集：如果是全序集，而且S的每個(gè)非空機(jī)子都有一個(gè)最小元素，則為良序集。哈塞圖：對有窮偏序集，去掉環(huán)，去掉所有由傳遞性可以得到的邊，排列所有的邊使得方向向上。極大元極小元：圖中的頂元素和底

12、元素，可能有多個(gè)最大元最小元：只有唯一的一個(gè)，比其他都>或<上界下界：只有唯一的一個(gè)，比其他都學(xué)或格：每對元素都有最小上界和最大下界十、圖10.1 圖的概念簡單圖：每對頂點(diǎn)最多只有一條邊多重圖：每對頂點(diǎn)可以有多條邊無向圖：邊沒有方向有向圖：邊有方向10.2 圖的術(shù)語無向圖中，點(diǎn)v的度為deg(v),如果v是一個(gè)環(huán)，則度為2。度為0的點(diǎn)是孤立的，度為1的點(diǎn)是懸掛的。有m條邊的無向圖則2m與deg(v)。無向圖有偶數(shù)個(gè)度為奇數(shù)的點(diǎn)，因?yàn)?m至deg(Vi)+2deg(Vj)。有向圖中，點(diǎn)v的入度為deg-(v),出度為deg+(v),且deg-(v)=deg+(v尸邊數(shù)。有向圖忽略邊的

13、方向后得到的圖叫做基本無向圖，它們有相同的邊數(shù)。會(huì)畫完全圖K、圈圖C、輪圖W。二分圖，將點(diǎn)分成2部分，每條邊都連著一部分和另一部分。用著色法判讀是否是二分圖。完全二分圖Kn,m是邊最多的二分圖。10.3 圖的表示鄰接表：無向簡單圖包括頂點(diǎn)和相鄰頂點(diǎn)，不太好表示無向多重圖因?yàn)檫叺臄?shù)量不好表示。有向圖包括起點(diǎn)和終點(diǎn)。鄰接矩陣：無向簡單圖按頂點(diǎn)排列，如果Vi和Vj之間相鄰則aij是1,否則是00無向多重圖這時(shí)aj是Vi和Vj之間的邊數(shù)?？芍獰o向圖的鄰接矩陣都是對稱陣。有向簡單圖也按照頂點(diǎn)排列，如果Vi,Vj是邊則aj是1,否則是00有向多重圖也按頂點(diǎn)排列，只不過aj是Vi,Vj之間的邊數(shù)。關(guān)聯(lián)矩陣：

14、將圖G按v行e歹I排列，如果Vi和ej關(guān)聯(lián)，則aj是1,否則是0。圖的同構(gòu)：簡單圖G1和G2,如果存在對應(yīng)的從V1到V2的函數(shù)f,且對V1的a和b來說，a與b相鄰當(dāng)僅當(dāng)f（a）與f（b）在G2中相鄰，則G1和G2是同構(gòu)的，f稱為同構(gòu)。圖形不變量如頂點(diǎn)數(shù)、邊數(shù)、度數(shù)，如果不同則不同構(gòu)，如果相同則可能同構(gòu)。當(dāng)我們找到f后，還要比較兩個(gè)圖的鄰接矩陣，看f是否是保持邊的。10.4 圖的連通性簡單圖中，用x0=u，x1.xn=V來表示一條通路，若u=V且路長度大于0，則是回路，如果不包含重復(fù)的邊，則這條通路是簡單的。無向圖中每對不同頂點(diǎn)之間都有通路則這個(gè)圖是連通的，割點(diǎn)（關(guān)節(jié)點(diǎn)）、割邊（橋）去掉后就會(huì)使

15、圖變得不連通，不含割點(diǎn)的圖叫做不可割圖。有向圖中，任意一對頂點(diǎn)a和b,都有從a到b以及從b到a的通路，則這個(gè)有向圖是強(qiáng)連通的，如果只是基本無向圖能保持聯(lián)通則叫做弱聯(lián)通的，會(huì)求強(qiáng)連通分支。通路與同構(gòu)：可以用長度為k>2的簡單回路的存在性來證不同構(gòu)或者是潛在的同構(gòu)映射f，同樣找到f后還要驗(yàn)證f保持邊。圖G（允許是有向和無向、多重邊和環(huán)）的Vi到Vj的長度為n的不同通路的條數(shù)等于Ani,j,A是G的鄰接矩陣。10.5 歐拉回路與哈密頓回路歐拉回路：包含G的每一條邊的簡單回路。歐拉通路：包含G的每一條邊的簡單通路。含有至少2個(gè)頂點(diǎn)的連通多重圖有歐拉回路當(dāng)僅當(dāng)它的每個(gè)頂點(diǎn)度都為偶數(shù)，有歐拉通路但無歐拉回路當(dāng)僅當(dāng)它恰有2個(gè)度為奇數(shù)的頂點(diǎn)。哈密頓回路：包含G的每一個(gè)頂點(diǎn)恰好一次的簡單回路。哈密頓通路：包含G的每一個(gè)頂點(diǎn)恰好一次的簡單通路。含有至少3個(gè)頂點(diǎn)的簡單圖，若每個(gè)頂點(diǎn)的度都>（n/2）,或者每一對不相鄰的頂點(diǎn)u和v都有deg（u）+deg（v）>n,則有哈密頓回路。最短通路算法：迪克斯特拉算法和旅行商問題（枚舉）10.7 平面圖歐拉公式：G是有e條邊和v個(gè)頂點(diǎn)的平面連通簡單圖，r是G的平面圖表示中的面數(shù)，則有r=e-V+2。根據(jù)上述條件，有3個(gè)推論，可以用來判斷不是平面圖：推論1:若v>3,則e<3v-6o推論2:G中有度不超過5的頂點(diǎn)