離散數(shù)學知識點

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

2、o邏輯等價式p A T ? ppVF ? p恒等律pAF ? FpVT ? T支配律p A p ? p募等律?(?P) ? p雙否律p A q ? q A p交換律(p A q) A r ? p A (q A r)結(jié)合律p V (q Ar)? (p V q) A (p V r)p A (q V r)? (p A q) V (p A r)分配律?(p A q) ? ?p V ?q?(p Vq) ? ?p A ?q德摩根律pV(p Aq) ? pPA(pVq) ? p吸收律pA?p ? FpV?p ? T否定律條件命題等價式pfq ? ?pVqpf q ? ?qf ?ppVq ? ?p f q p

3、Aq ? ?(pf?q)?(pf q) ? pA ?q(p f q) A (p f r) ? p f (q A r)(pr) A(qfr) ? ( pVq)f(pfq)V(pfr) ? pfqVr)(pr) V(qfr) ? ( pAq)fr雙條件命題等價式p?q ? (p fq) A(qf p) p?q ? ?p?q p?q ? (p A q) V (?p A ?q)?(p?q) ? p?q量詞謂詞+量詞變成一個更詳細的命題，量詞要說明論域，否則沒有意義，如果有約束條件就直接放在量詞后面，如 ?x0P(x) 0當論域中的元素可以一一列舉，那么?xP(x)就等價于P(x1) A P(x2).

4、A P(xn)同理，？xP(x)就等價于 P(x1) VP(x2). VP(xn)。兩個語句是邏輯等價的，如果不論他們謂詞是什么，也不論他們的論域是什么， 他們總有相同的真值，如 ?x (P(x) A Q(x) ffi( ?xP(x) A ( ?xQ(x)。量詞表達式的否定： ？?xP(x) ? ?x?P(x) , ?xP(x) ? ?x?P(x) o量詞嵌套我們采用循環(huán)的思考方法。量詞順序的不同會影響結(jié)果。語句到嵌套量詞語句的翻譯，注意論域。嵌套量詞的否定就是連續(xù)使用德摩根定律，將否定詞移入所有量 詞里。推理規(guī)則一個論證是有效的，如果它的所有前提為真且蘊含著結(jié)論為真。但有效論證不代表結(jié)論正確

5、，因為也許有的前提是假的。推理規(guī)則，都是基于永真式的，用來證明一個前提蘊含一個結(jié)論。而基于可滿足式的推理規(guī)則叫謬誤。pp” q(p A(p” q) “q假言推理qp” qqf r(p f q) A(q7 r) f(pfr)假言二段論pf r?qp” q(?q A(p“q) f?p取拒式?ppVq?p(p V q) A ?p) f q析取三段論qpp” (p V q)附加律pVqpAq(p Aq)f p化簡律PPq(pAq) ( pAq)合取律pAqPVq?pVr(p V q) A (?p V r) f (q V r)消解律q V r量化推理規(guī)則?xP(x)全稱實例P(c)P(c),任意c全稱引

6、入?P(x)?xP(x)存在實例P(c),對某個cP(c),對某個c存在引入?xP(x)命題和量化命題的組合使用。二、集合、函數(shù)、序列、與矩陣2.1集合G說的是元素與集合的關(guān)系，？說的是集合與集合的關(guān)系。常見數(shù)集有N=0,1,2,3.),2整數(shù)集，Z+正整數(shù)集，Q有理數(shù)集，R實數(shù)集，R+正實數(shù)集，C復(fù)數(shù)集。A和B相等當僅當？x(x G A?xG B); A是B的子集當僅當？x(x G Qx G B);A是 B 的真子集當僅當？x(x GA- x G B) A ?x(x?A A x G B)。募集：集合元素的所有可能組合，肯定有？何它自身。如？的募集就是?,而?的募集是? , ?。笛卡爾積：AX

7、 B,結(jié)果是序偶，其中的一個子集叫一個關(guān)系。帶量詞和集合符號如？xGR (x20)是真的，則所有真值構(gòu)成真值集。集合恒等式名稱(A U B)=A n B?(A n B)=A U B德摩根律AU (A n B)=AAn (A U B)=A吸收律函數(shù)考慮A-B的函數(shù)關(guān)系，定義域、陪域(實值函數(shù)、整數(shù)值函數(shù))、值域、像集(定義域的一個子集在值域的元素集合)一對一或者單射：B可能有多余的元素，但不重復(fù)指向映上或者滿射：B中沒有多余的元素，但可能重復(fù)指向。一一對應(yīng)或者雙射：符合上述兩種情況的函數(shù)關(guān)系。反函數(shù)：如果是一一對應(yīng)的就有反函數(shù)，否則沒有。合成函數(shù)：f o g(a)=f(g(a), 一般來說交換律

8、不成立。序列無限集分為：一組是和自然數(shù)集合有相同基數(shù)，另一組是沒有相同基數(shù)。前者是可數(shù)的，后者不可數(shù)。想要證明一個無限集是可數(shù)的只要證明它與自然數(shù)之間有一 一對應(yīng)的關(guān)系。如果A和B是可數(shù)的，則 AU B也是可數(shù)的。如果存在一對一函數(shù)f從A到B和一對一函數(shù)g從B到A,那么A和B之間是一 一對應(yīng)的。求和公式：a+ar+ar 2+ar3+.+ar n = (ar n+1-a)/(r-1)1+2+3+.+n = n(n+1)/21+22+32+.+n 2 = n(n+1)(2n+1)/61+23+33+.+n 3 = n 2(n+1) 2/42.6矩陣普通矩陣和、減、乘積，0-1矩陣還可以A、V、O

9、（和相乘類似，用V代替 +, 用A代替X）九、關(guān)系9.1關(guān)系及其性質(zhì)設(shè)A和B是集合，從A到B的二元關(guān)系是 AX B的子集。一個從 A到B的二元關(guān)系是集合R,第一個元素取自 A第二個元素取自B,當（a,b）屬于R時寫作aRbo集合A上的關(guān)系是A到A的關(guān)系，有n個元素就有n2個有序?qū)?，n2個有序?qū)陀?2n2個關(guān)系?？紤]集合A到A的關(guān)系R:任意aG A都有（a, a） G R,則R是集合A上的自反關(guān)系。任意a, bGA,若（a, b） G R都有（b, a） G R,則R是對稱關(guān)系。任意a, bGA,若（a, b） G R且（b, a） G R一定有a=b,則R是反對稱關(guān)系。任意 a, b, c

10、G A,若（a, b） G R 且（b, c） G R一定有（a, c） G R,則 R是 傳遞關(guān)系。若R是A到B的關(guān)系，S是B到C的關(guān)系，R與S的合成Ro S是有序數(shù)對（a, c）。 其中a GA, cGC,且存在一個bGB使得（a, b） G R, （b, c） G S。二元關(guān)系的5 種復(fù)合要會翻譯成漢語。關(guān)系的表示0-1矩陣法：A有n個元素，B有m個元素，用一個 nXm的矩陣M表示，m=1 表示有關(guān)系。自反關(guān)系的0-1矩陣主對角線全為1;對稱關(guān)系的0-1矩陣是對稱陣；反對稱關(guān)系的0-1矩陣關(guān)于主對角線反對稱。M1UR2=M1 V M2, MmRkM1A M2, M1 0 RkMQM2。有

11、向圖法：A有n個元素，每一個關(guān)系是一條有向邊。自反關(guān)系的圖每一個頂點 都有一個環(huán)；對稱關(guān)系的圖在不同頂點之間每一條邊都存在與之對應(yīng)的反方向邊(也可用無向圖)；反對稱關(guān)系的圖在不同頂點之間每一條邊都不存在與之對應(yīng)的反方 向邊；傳遞關(guān)系的圖在 3個不同頂點之間構(gòu)成正確方向的三角形。關(guān)系的閉包自反閉包：RUA,其中 = (a, a) |a G A對稱閉包：R并 R1,其中 R1= (b,a) | (a, b) G R傳遞閉包：r矩陣傳遞閉包=mvm2 v m3 . v mT , 了解沃舍爾算法等價關(guān)系：自反、對稱且傳遞的關(guān)系集合 A 的元素 a在 R上的 等價類a=s|(a,s) G R A s G

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

13、大元最小元：只有唯一的一個，比其他都或上界下界：只有唯一的一個，比其他都）或格：每對元素都有最小上界和最大下界十、圖圖的概念簡單圖：每對頂點最多只有一條邊多重圖：每對頂點可以有多條邊無向圖：邊沒有方向有向圖：邊有方向圖的術(shù)語無向圖中，點v的度為deg(v),如果v是一個環(huán)，則度為2。度為0的點是孤立 的，度為1的點是懸掛的。有 m條邊的無向圖則2m=2 deg(v)。無向圖有偶數(shù)個度 為奇數(shù)的點，因為 2m=S deg(Vi)+ Ndeg(Vj)。有向圖中，點v的入度為deg(v),出度為deg+(v),且deg-(v尸deg+(v尸邊數(shù)。 有向圖忽略邊的方向后得到的圖叫做基本無向圖，它們有相

14、同的邊數(shù)。會畫完全圖Kn、圈圖G、輪圖W。二分圖，將點分成2部分，每條邊都連著一部分和另一部分。用著色法判讀是否是二分圖。完全二分圖 (,m是邊最多的二分圖。圖的表示鄰接表：無向簡單圖包括頂點和相鄰頂點，不太好表示無向多重圖因為邊的數(shù)量不好表示。有向圖包括起點和終點。鄰接矩陣：無向簡單圖按頂點排列，如果 w和vj之間相鄰則a。是1,否則是 00無向多重圖這時aij是vi和vj之間的邊數(shù)。可知無向圖的鄰接矩陣都是對稱陣。 有向簡單圖也按照頂點排列，如果 vi, vj是邊則aij是1,否則是0。有向多重 圖也按頂點排列，只不過 aij是vi, vj之間的邊數(shù)。關(guān)聯(lián)矩陣：將圖G按v行e歹U排列，如果

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

16、含割點的圖叫做不可割圖。有向圖中，任意一對頂點 a和b,都有從a至ij b以及從b到a的通路，則這個有 向圖是強連通的，如果只是基本無向圖能保持聯(lián)通則叫做弱聯(lián)通的，會求強連通分 支。通路與同構(gòu)：可以用長度為 k2的簡單回路的存在性來證不同構(gòu)或者是潛在的 同構(gòu)映射f ,同樣找到f后還要驗證f保持邊。圖G （允許是有向和無向、 多重邊和環(huán)）的Vi到必的長度為n的不同通路的條數(shù) 等于Ani,j, A是G的鄰接矩陣。歐拉回路與哈密頓回路歐拉回路：包含G的每一條邊的簡單回路歐拉通路：包含 G的每一條邊的簡單通路。含有至少2個頂點的連通多重圖有歐拉回路當僅當它的每個頂點度都為偶數(shù)，有歐拉通路但無歐拉回路當

17、僅當它恰有2個度為奇數(shù)的頂點。哈密頓回路：包含G的每一個頂點恰好一次的簡單回路。哈密頓通路：包含 G的每一個頂點恰好一次的簡單通路。含有至少3個頂點的簡單圖，若每個頂點的度都(n/2),或者每一對不相鄰的頂點u和v都有deg(u)+deg(v) n,則有哈密頓回路。最短通路算法：迪克斯特拉算法和旅行商問題(枚舉)10.7平面圖歐拉公式：G是有e條邊和v個頂點的平面連通簡單圖，r是G的平面圖表示中的面數(shù)，則有r=e-v+2 o根據(jù)上述條件，有 3個推論，可以用來判斷不是平面圖：推論 1:若 v3,則 e 3v-6。推論2: G中有度不超過5的頂點。推論3: v)3且沒有長度為3的回路，則e 2V-4