離散數(shù)學知識點整理

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

2、式是通過p推導出T邏輯等價式pAT pVF?p p恒等律pAF pVT?FT支配律pAp?p幕等右于?(?P)?p雙否律pAq?q八p交換律(p A q) A r? p A (q A r)結合律pV(q Ar pA(q Vr) )?(p Vq)A(pVr)(p A q) V (p A r)分配律?(p 八 q)?(p V q)?pV ?q?pA ?q德摩根律p V (p A c PA (p Vc1)1)? p ? p吸收律pA?p pV?p萬 ?FT否定律條件命題等價式p-q?pV qp-q? ?q-?ppVq?p-qpAq?(p-?q)?(p q)?pA ?q(p-q) A (p-r)?p

3、一 (q A r)(p-r)八（qr）?(pV q) r(p-q) V (pr) ? p 一 (q V r)(pr) V(qr) ? ( pA q) 一 r雙條件命題等價式p?q ? (p - q) A(q p)p?q ? ?p?qp?q ? (p A q) V (?p A ?q)?(p?q) ? p?q量詞謂詞+量詞變成一個更詳細的命題，量詞要說明論域，否則沒有意義，如果 有約束條件就直接放在量詞后面，如？ x>0P(x)。當論域中的元素可以列舉，那么 ？ xP(x)就等價于P(x1) AP(x2) A P(xn)。同理，？ xP(x)就等價于 P(x1) V P(x2) VP(xn)

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

5、論。 而基于可涉足 式的推理規(guī)則叫謬誤。p p-q(p A(p-q) 一 q假百推理qp-q q-r(p - q) A(q - r) (p r)假百二段論p-r?q p-q(?q A (pq) 一?p取拒式?ppVq ?p(p Vq) A?p) -q析取三段論qpp一 (p Vq)附加律pVqpAq(p Aq) p化簡律pp q(pA q) ( pAq)合取律pAqpVq?pV r(p V q) A (?p V r) 一 (q V r)消解律q V r量化推理規(guī)則? xP(x)全稱實例P(c)P(c),任意c全稱引入? P(x)? xP(x)存在實例P(c),對某個cP(c),對某個c存在引入

6、? xP(x)命題和量化命題的組合使用二、集合、函數(shù)、序列、與矩陣集合e說的是元素與集合的關系， ？說的是集合與集合的關系。常見數(shù)集有 N=0,1,2,3, Z整數(shù)集，Z+正整數(shù)集，Q有理數(shù)集，R實數(shù)集，R+正實數(shù)集,C復數(shù)集。A和B相等當僅當？ x(x C A?xC B)； A是B的子集當僅當？ x(x RA x C B)； A是 B 的真子集當僅當？ x(x Zx C B) A ? x(x ?AA x C B)。募集：集合元素的所有可能組合，肯定有 ？何它自身。如？的募集就是?, 而?的募集是?, ?。笛卡爾積：AX B,結果是序偶，其中的一個子集叫一個關系。帶量詞和集合符號如？ xCR

7、(x2>0)是真的，則所有真值構成真值集。集合恒等式名稱(A U B)'=A' AB'(A A B)'=A' UB'德摩根律AU (A n B)=A An (A U B)=A吸收律函數(shù)考慮ZB的函數(shù)關系，定義域、陪域(實信函數(shù)、整數(shù)值函數(shù))、值域、 像集(定義域的一個子集在值域的元素集合)。一對一或者單射：B可能有多余的元素，但不重復指向。映上或者滿射：B中沒有多余的元素，但可能重復指向。一一對應或者雙射：符合上述兩種情況的函數(shù)關系。反函數(shù)：如果是一一對應的就有反函數(shù)，否則沒有。合成函數(shù)：f o g(a)=f(g(a), 一般來說交換律不成

8、立。序列無限集分為：一組是和自然數(shù)集合有相同基數(shù)，另一組是沒有相同基數(shù)。前 者是可數(shù)的，后者不可數(shù)。想要證明一個無限集是可數(shù)的只要證明它與自然數(shù)之 間有 對應的關系。如果A和B是可數(shù)的，則AU B也是可數(shù)的。如果存在一對一函數(shù)f從A到B和一對一函數(shù)g從B到A,那么A和B之間是一一對應的。求和公式：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/4矩陣普通矩陣和、減、乘積，0-1矩陣還可以A、V、O (和相乘類似，

9、用V代替+,用A代替X)九、關系關系及其性質設A和B是集合，從A到B的二元關系是AX B的子集。一個從A到B的二 元關系是集合R,第一個元素取自A,第二個元素取自B,當(a,b)屬于R時寫作 aRb。集合A上的關系是A到A的關系，有n個元素就有n2個有序對，n2個有序對 就有2n2 個關系?？紤]集合A到A的關系R任意aC A都有(a, a) R,則R是集合A上的自反關系。任意a, bC A,若(a,b) R都有(b,a) R,則R是對稱關系。任意a, bC A,若(a,b)C R且(b, a) CR一定有a=b,則R是反對稱關系。任意 a, b, c C A,若(a, b) C R且(b, c

10、) R一定有(a, c) R,則 R 是傳遞關系。若R是A到B的關系，S是B到C的關系，R與S的合成Ro S是有序數(shù)對(a, c)。其中 a A, cCC,且存在一個 bCB 使得(a, b) C R, (b, c) CS。二 元關系的 5 種復合要會翻譯成漢語。關系的表示0-1矩陣法：A有n個元素，B有m個元素，用一個nXm的矩陣MR表示，m=1表示有關系。自反關系的 0-1 矩陣主對角線全為1；對稱關系的0-1 矩陣是對稱陣；反對稱關系的 0-1 矩陣關于主對角線反對稱。MRwr2=MRiV MR2, Minr尸MiA M2, MR1 0 R2=MliO MR20有向圖法： A 有 n 個

11、元素，每一個關系是一條有向邊。自反關系的圖每一個頂點都有一個環(huán)； 對稱關系的圖在不同頂點之間每一條邊都存在與之對應的反方向邊 (也可用無向圖) ； 反對稱關系的圖在不同頂點之間每一條邊都不存在與之對應的反方向邊；傳遞關系的圖在3 個不同頂點之間構成正確方向的三角形。關系的閉包自反閉包：RUA,其中A = (a, a) |a C A對稱閉包：R并 R1,其中 R1= (b,a) | (a, b) R傳遞閉包：R矩陣傳遞閉包=MVM2VMR3V MRn,了解沃舍爾算法等價關系：自反、對稱且傳遞的關系集合 A的元素a在 R上的等價類a=s(a,s) C R A s C A。如 A=1,2,3,4,5

12、,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偏序關系：自反、反對稱且傳遞的的關系偏序集(S, <)中如果既沒有a< b,也沒有b<a,則a和b是不可比的。全序集：如果偏序集中每個元素都可比，則為全序集，如( Z, <)是全序集，但(Z+， | )不是，因為有5 和 7 是不可比的。良序集：如果是全序集，而且S 的每個非空機子都有一個最小元素，則為良序集。哈塞圖：對有窮偏序集，去掉環(huán)，去掉所有由傳遞性可以得到的邊，排列所有的邊使得方向向上。極大元極小元：圖中的頂元素和底元素，可能有

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

14、有向圖忽略邊的方向后得到的圖叫做基本無向圖，它們有相同的邊數(shù)。會畫完全圖左、圈圖G、輪圖W。二分圖，將點分成2 部分，每條邊都連著一部分和另一部分。用著色法判讀是否是二分圖。完全二分圖 (,m是邊最多的二分圖。圖的表示鄰接表：無向簡單圖包括頂點和相鄰頂點，不太好表示無向多重圖因為邊的數(shù)量不好表示。有向圖包括起點和終點。鄰接矩陣：無向簡單圖按頂點排列，如果 vi和w之間相鄰則aj是1,否 則是00無向多重圖這時aj是vi和vj之間的邊數(shù)?？芍獰o向圖的鄰接矩陣都 是對稱陣。有向簡單圖也按照頂點排列，如果 vvj是邊則aj是1,否則是 00有向多重圖也按頂點排列，只不過aj是vi, vj之間的邊數(shù)。

15、關聯(lián)矩陣：將圖G按v行e歹I排列，如果vi和ej關聯(lián)，則aj是1,否則是0。圖的同構：簡單圖G1和G2,如果存在對應的從 V1到V2的函數(shù)f ,且 對 V1 的 a 和 b 來說， a 與 b 相鄰當僅當 f(a) 與 f(b) 在 G2 中相鄰，則 G1 和 G2 是同構的， f 稱為同構。 圖形不變量如頂點數(shù)、 邊數(shù)、 度數(shù)， 如果不同則不同構，如果相同則可能同構。 當我們找到 f 后， 還要比較兩個圖的鄰接矩陣， 看 f 是否 是保持邊的。 圖的連通性簡單圖中，用x0=u， x1.x n=v 來表示一條通路，若u=v 且路長度大于0，則是回路，如果不包含重復的邊，則這條通路是簡單的。無向

16、圖中每對不同頂點之間都有通路則這個圖是連通的，割點(關節(jié)點)、割邊(橋)去掉后就會使圖變得不連通，不含割點的圖叫做不可割圖。有向圖中，任意一對頂點a和b,都有從a到b以及從b到a的通路，則這 個有向圖是強連通的， 如果只是基本無向圖能保持聯(lián)通則叫做弱聯(lián)通的， 會求強 連通分支。通路與同構：可以用長度為 k>2的簡單回路的存在性來證不同構或者是潛 在的同構映射f ，同樣找到 f 后還要驗證f 保持邊。圖G (允許是有向和無向、多重邊和環(huán))的Vi到Vj的長度為n的不同通路的條數(shù)等于Ani,j, A是G的鄰接矩陣。歐拉回路與哈密頓回路歐拉回路：包含G的每一條邊的簡單回路。歐拉通路：包含G的每一

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