離散數(shù)學(xué)章節(jié)總結(jié)

1、離散數(shù)學(xué)章節(jié)總結(jié) 第一章1.1命題邏輯1.邏輯運(yùn)算1.否定:Negation ¬ NOT2.交:Conjunction Ù AND3.并:Disjunction Ú OR4.蘊(yùn)含:Implication ® IMPLIES5. Biconditional IFF6.Exclusive-Or Å XOR2.逆/否/逆否1.逆:converse 2.否:inverse3.逆否:conytrapositive3.問題的一致性1.2邏輯等價(jià)1.pq 等價(jià)于 ¬pÚq 等價(jià)于 ¬ q¬p2. pÚq 等價(jià)

2、于 ¬pq pÙq 等價(jià)于 ¬( p¬q)3.(pq) Ù (pr) 等價(jià)于p(qÙr) (pr) Ù (qr) 等價(jià)于(pÚq)r (pr) Ú (qr) 等價(jià)于(pÙq) r4.證明等價(jià): 真值表 邏輯符號(hào)證明 找反例(假設(shè)左為假 右必為假 假設(shè)右為假 左必為假)1.3 1.4 謂詞邏輯1.量詞 存在 任意量詞順序不能隨機(jī)改變不全為真:Ø(p1Ùp2ÙÙpn) Û (Øp1ÚØp2ÚÚ

3、6;pn)Ø "x P(x ) Û $x ØP(x )沒有一個(gè)為真:Ø(p1Úp2ÚÚpn) Û (Øp1ÙØp2ÙÙØpn)Ø $x P(x ) Û "x ØP(x )1.5 推理1.6 1.7 證明1.證明方法:直接證明 間接證明 反證 列舉證明(列舉所有情況) 構(gòu)造證明(構(gòu)造出滿足結(jié)論的元素)2.證明步驟:正向證明 反向證明 第二章2.1 2.2 集合及運(yùn)算1.特殊集合: R Q Z 無窮/有限集2.

4、集合表述方法: 列舉法 描述法 圖表法3.集合運(yùn)算: 交/并/補(bǔ)/差/取子集P(S)/元素?cái)?shù)|S|/乘積P×Q/容斥原理4.證明集合相等:1.證明互為子集 2.從屬表 3.邏輯證明2.3 函數(shù)1.函數(shù)的定義2.術(shù)語：定義域，值域，象，原象，范圍，3.f(a)/f(A) 第五章5.1序、歸納1.序：在某種關(guān)系下存在最小元素則為well-ordered2.第一數(shù)學(xué)歸納法：basic step P(C)成立and inductive step P(k)P(k+1)3.第二數(shù)學(xué)歸納法:basic step:P(c)成立 and inductive step: 任意k小于等于nP(k)成立P(

5、n+1)5.2遞歸1.遞歸：以相同形式用小的項(xiàng)來定義的大的項(xiàng) 不能一直遞歸下去（存在初始項(xiàng)）必須存在可以直接解決問題的一項(xiàng) basic step:原有元素 recursive step:原有元素如何產(chǎn)生新元素2.字符串的定義：空字符，回文3.結(jié)構(gòu)歸納：用于證明遞歸結(jié)構(gòu)對(duì)所有元素都成立：basic step:原有元素成立recursive step:用遞歸式導(dǎo)出的新元素成立5.3遞歸算法1.定義：把問題轉(zhuǎn)化為相同形式但值更小的算法2.遞歸算法有初始步驟（是可終止的）并且遞歸時(shí)至少改變一個(gè)參數(shù)值使之向初始步驟靠攏3.遞歸時(shí)間復(fù)雜度高，可以用非遞歸（loop或 stack）來代替5.4程序的正確性1

6、.測(cè)試與證明：證明更有說服力2.證明：程序會(huì)終止（部分正確）程序只要可以終止得出的結(jié)論都是正確的正確的程序：對(duì)任意可能的輸入都有正確的輸出部分正確，完全正確3.Hoare triple：PSQP: precondition S: assertion Q:postcondition?PSQ:當(dāng)PQ正確時(shí)為部分正確當(dāng)證明了S的可終止性為完全正確4.程序的基本語句：賦值，命題，條件，循環(huán)5.弱化結(jié)論：PSR RQ：PSQ 強(qiáng)化條件QR RSP：QSP 復(fù)合：PS1R RS2Q: PS1;S2Q第六章6.1加法乘法原理1.加法乘法原理：方法不重復(fù)，互不影響，做1or2 m+n 做1and2 mn2.容

7、斥原理：方法有重疊：|AÈB|=|A|+|B|-|AÇB|3.包含條件的問題。6.2分類原理1.抽屜原理。2.抽屜原理推論：n插入k個(gè)抽屜：至少有一個(gè)抽屜含有n/k個(gè)元素（上取整）6.3排列組合1.排列：選擇的元素只出現(xiàn)一次r-permutation of SP(n,r) = n(n1)(nr+1) = n!/(nr)!2.組合：6.4二項(xiàng)式系數(shù)1.楊輝三角：C(n+1, k) = C(n, k-1) + C(n, k)第九章9.1關(guān)系1.關(guān)系：函數(shù)的推廣2.二元關(guān)系：.定義：A binary relation from A to B is a set R where a

8、R b denotes (a, b) R 包含于A X B. a is said to be related to b by R.數(shù)量：with |A| = m and |B| = n共有2mn relations from A to B, including the empty relation as well as the relation A X B. 3.關(guān)系圖4.自身關(guān)系：A on A： A×A relation on A5.反身關(guān)系：reflexive：aA (a,a)RReflexive relations: 含有所有(a,a)元素的關(guān)系6.對(duì)稱關(guān)系：symmetric

9、 對(duì)所有(a,b) R 就有(b,a) R 非對(duì)稱關(guān)系：Antisymmetric: 只有當(dāng)a=b時(shí)(a,b) (b,a)才會(huì)同時(shí)R。 即"ab, (a,b)ÎR (b,a)ÏR Asymmetric: 只要(a,b) R那么(b,a)Ï R 三者兩兩互不矛盾7.傳遞：有(a,b)和(b,c)就有(a,c)8.組合關(guān)系：A交并補(bǔ)B 復(fù)合關(guān)系：S：AB R：BC R°S：AC (4,2);(2,3)(4,3)若A1，A2是可傳遞的，則A1并A2不一定可傳遞但A1°A2與 A2°A1是可傳遞的Rn = R°R°

10、; °R 9.2 n元關(guān)系1.度，定義域9.3 關(guān)系的表示1.關(guān)系的表示方法: 1.元素組列表2.函數(shù)關(guān)系 3.零一矩陣 4.圖2.零一矩陣: |A|×|B| 0-1 matrix對(duì)角線全為1:自反性對(duì)稱矩陣:對(duì)稱性 antisymmetric: Mij = 0 or Mji = 0 for all ij3.零一矩陣的運(yùn)算: 交: join M1M2補(bǔ): meet M1M2復(fù)合: composition M1M29.4 關(guān)系的閉集1.反身閉集：原來的關(guān)系加上所有的(a,a) 在矩陣中則把對(duì)角線元素變?yōu)?2.對(duì)稱閉集：原來有的關(guān)系(a,b)加上所有的(b,a)即R U R-1

11、其中R-1 代表R的轉(zhuǎn)置A表示補(bǔ)集3.路：長(zhǎng)度大于等于1(長(zhǎng)度指邊的條數(shù)) 從同一頂點(diǎn)開始、結(jié)束的路徑：回路4.傳遞閉集:兩個(gè)頂點(diǎn)可由某一路徑到達(dá),用一條路直接連接這兩個(gè)頂點(diǎn).傳遞閉集 包含所有這樣的路 Rn代表所有長(zhǎng)度為n的可以連接兩個(gè)頂點(diǎn)的路 R*代表所有任意長(zhǎng)度的可以連接兩個(gè)頂點(diǎn)的路 R*為傳遞閉集 路徑的最大長(zhǎng)度:元素總數(shù)n 零一矩陣: ××9.5 等價(jià)關(guān)系1.等價(jià)關(guān)系滿足自反性,對(duì)稱性,傳遞性.即f(x)=f(x) f(a)=f(b)則f(b)=f(a) f(a)=f(b) f(b)=f(c) 則f(a)=f(c)滿足以上三個(gè)條件的關(guān)系,若二者在關(guān)系R下值相等,則稱二者等價(jià)2.等價(jià)集: aR 所有與a在關(guān)系R下等價(jià)的元素 不混淆的情況下寫作R不同的等價(jià)集是互斥的(因具有對(duì)稱性)3.集合的劃分:把集合S劃分為非空互斥的子集,所有子集的并為S等價(jià)集可作為集合S的劃分依據(jù)9.6 偏序1.偏序是自反的,非對(duì)稱的(antisymmetric),可傳遞的.(A, ).偏序集2.哈希圖解:簡(jiǎn)化圖1.箭頭朝上2.去自反3.去傳遞4.去箭頭3.最小,最大元素(可能不只一個(gè)):a比min在關(guān)系下大:b比max在關(guān)系下小 4.字典順序:在某一偏序關(guān)系下排序5.全序: