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

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

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

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

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

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

7、斥原理：方法有重疊：|AÈB|=|A|+|B|-|AÇB|3.包含條件的問題。6.2分類原理1.抽屜原理。2.抽屜原理推論：n插入k個抽屜：至少有一個抽屜含有n/k個元素（上取整）6.3排列組合1.排列：選擇的元素只出現一次r-permutation of SP(n,r) = n(n1)(nr+1) = n!/(nr)!2.組合：6.4二項式系數1.楊輝三角：C(n+1, k) = C(n, k-1) + C(n, k)第九章9.1關系1.關系：函數的推廣2.二元關系：.定義：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.數量：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.關系圖4.自身關系：A on A： A×A relation on A5.反身關系：reflexive：aA (a,a)RReflexive relations: 含有所有(a,a)元素的關系6.對稱關系：symmetric

9、 對所有(a,b) R 就有(b,a) R 非對稱關系：Antisymmetric: 只有當a=b時(a,b) (b,a)才會同時R。 即"ab, (a,b)ÎR (b,a)ÏR Asymmetric: 只要(a,b) R那么(b,a)Ï R 三者兩兩互不矛盾7.傳遞：有(a,b)和(b,c)就有(a,c)8.組合關系：A交并補B 復合關系：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元關系1.度，定義域9.3 關系的表示1.關系的表示方法: 1.元素組列表2.函數關系 3.零一矩陣 4.圖2.零一矩陣: |A|×|B| 0-1 matrix對角線全為1:自反性對稱矩陣:對稱性 antisymmetric: Mij = 0 or Mji = 0 for all ij3.零一矩陣的運算: 交: join M1M2補: meet M1M2復合: composition M1M29.4 關系的閉集1.反身閉集：原來的關系加上所有的(a,a) 在矩陣中則把對角線元素變為12.對稱閉集：原來有的關系(a,b)加上所有的(b,a)即R U R-1

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