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

1、離散數(shù)學章節(jié)總結第一章命題邏輯1. 邏輯運算1. 否定:Negation?NOT2. 交:Conjunctionand3. 并:DisjunctionOR4. 蘊含:lmplicationimplies5. Biconditional?iffxor2. 逆/否/逆否1. 逆:converseTABLE8LogicalEquivalencesInvolvingBiconditionakpiq三(ptq)代(q7ppug三1i-ig卩戶g)三p+q2. 否:inverse3. 逆否:conytrapositive3. 問題的一致性邏輯等價fq等價于？pq等價于?q宀?p2. pq等價于?pfqpq

2、等價于？(pf?q)3. (pfq)(pfr)等價于pf(qr)(pfr)(qfr)等價于(pq)fr(pfr)(qfr)等價于(pq)fr4.證明等價：真值表邏輯符號證明假左必為假）找反例（假設左為假右必為假假設右為謂詞邏輯1.量詞弓存在匚任意量詞順序不能隨機改變不全為真：（P1P2Pn)(PlP2Pn)xP(x)xP(x)沒有一個為真：(PlP2Pn)(PlP2Pn)xP(x)xP(x)推理IART-ILIRulrjf1R科hr/rir/irrtrfftJVmwr嚴T/Cra(/*j-ipfolionejF*即V*尸二廠i子f詩i.峙、fgtjts-(/*rEEoLlit:iizj1llo

3、|isiiippg-ip化qwQja-rl1is_ilinelih?r尸nqAdditionra(/A*/*Sinipl嚴V/FA)A(i/-_c嚴小grdiyiinlvlicvn尸7Htjn-Vr-T-vrrC/TV/)A-pV/-)!*V-r)RfSQ)lLlt30-THIABLE2RulesofInferenceforQuantifiedStatements.RuleofInferenceNameVxP(x)/.Pic)UniversalinstantiationP(c)foranarbitraryc二VxP(jt)UniversalgeneralizationP(c)forsomeel

4、ementcExistentialinstantiationP(cforsomeelementcExistentialgeneralization證明1. 證明方法：直接證明間接證明反證列舉證明（列舉所有情況）構造證明（構造出滿足結論的元素）2. 證明步驟：正向證明反向證明第二章集合及運算1. 特殊集合：RQZ無窮/有限集2. 集合表述方法：列舉法描述法圖表法3. 集合運算：交/并/補/差/取子集P（S）/元素數(shù)|S|/乘積PXQ/ABABnn_AiAAiAABABi1aXi1AXnUAi容斥原理1IAAi1in1ijnAjK(1)nnAi14. 證明集合相等：1.證明互為子集2.從屬表3.邏

5、輯證明函數(shù)1. 函數(shù)的定義2. 術語：定義域，值域，象，原象，范圍，(a)/f(A)第五章序、歸納1. 序：在某種關系下存在最小元素則為well-orderedP(k+1)任意k小于等2. 第一數(shù)學歸納法：basicstepP(C)成立andinductivestepP(k)3. 第二數(shù)學歸納法:basicstep:P(c)成立andinductivestep:于nP(k)成立P(n+1)遞歸1. 遞歸：以相同形式用小的項來定義的大的項不能一直遞歸下去（存在初始項）必須存在可以直接解決問題的一項basicstep:原有元素recursivestep:原有元素如何產(chǎn)生新元素2. 字符串的定義：空

6、字符，回文3. 結構歸納：用于證明遞歸結構對所有元素都成立： basicstep:原有元素成立 recursivestep:用遞歸式導出的新元素成立遞歸算法1. 定義：把問題轉化為相同形式但值更小的算法2. 遞歸算法有初始步驟（是可終止的）并且遞歸時至少改變一個參數(shù)值使之向初始步驟靠攏3. 遞歸時間復雜度高，可以用非遞歸（loop或stack）來代替程序的正確性1. 測試與證明：證明更有說服力2. 證明：程序會終止（部分正確）程序只要可以終止得出的結論都是正確的正確的程序：對任意可能的輸入都有正確的輸出部分正確，完全正確triple：PSQP:preconditionS:assertionQ:

7、postconditionPSQ:當PQ正確時為部分正確當證明了S的可終止性為完全正確4. 程序的基本語句：賦值，命題，條件，循環(huán)5. 弱化結論：PSRQPSQ強化條件CHRRSP:QSP復合：PS1RRS2Q:PS1;S2Q第六章加法乘法原理做1and2mnn/k個元素(上1. 加法乘法原理：方法不重復，互不影響，做1or2m+n2. 容斥原理：方法有重疊：|AB|=|A|B|AB|3. 包含條件的問題。分類原理1. 抽屜原理。2. 抽屜原理推論：n插入k個抽屜：至少有一個抽屜含有取整)排列組合1. 排列：選擇的元素只出現(xiàn)一次r-permutationofSP(n,r)=n(n-1)(n-葉

8、1)=n!/(n-r)!nP(n,r)n!/(nr)!n!C(n,r)2. 組合：rP(r,r)r!r!(nr)!二項式系數(shù)1. 楊輝三角：C(n+1,k)=C(n,k-1)+C(n,k)第九章關系1. 關系：函數(shù)的推廣2. 二元關系：.定義：AbinaryrelationfromAtoBisasetRwhereaRbdenotes(a,b)ER包含于AXB.aissaidtoberelatedtobbyR.數(shù)量：with|A|=mand|B|=n共有2何relationsfromAtoB,includingtheemptyrelationaswellastherelationAXB.3. 關

9、系圖4. 自身關系：AonA:AxArelationonA5. 反身關系：reflexive:VaEA(a,a)ERReflexiverelations:含有所有(a,a)元素的關系6. 對稱關系：symmetric對所有(a,b)ER就有(b,a)ER非對稱關系：Antisymmetric:只有當a=b時(a,b)(b,a)才會同時ER。即ab,(a,b)R(b,a)RAsymmetric:只要(a,b)5-R那么(b,a)R三者兩兩互不矛盾7. 傳遞：有(a,b)和(b,c)就有(a,c)8. 組合關系：A交并補B若A1,A2是可傳遞的，則A1并A2不一定可傳遞但A1A2與A2A1是可傳遞

10、的R=RRRn元關系1. 度，定義域關系的表示1. 關系的表示方法：1.元素組列表2.函數(shù)關系3.零一矩陣4.圖2. 零一矩陣：|Ax|B|0-1matrix對角線全為1：自反性對稱矩陣：對稱性antisymmetric:M=0orM=0foralliMj3. 零一矩陣的運算：交：joinMVM補：meetMAM復合：compositionMOMk1(M1)ik(M2)kj關系的閉集1. 反身閉集：原來的關系加上所有的(a,a)在矩陣中則把對角線元素變?yōu)?2. 對稱閉集：原來有的關系(a,b)加上所有的(b,a)即RUR1其中R1代表R的轉置|表示補集3. 路：長度大于等于1(長度指邊的條數(shù))

11、從同一頂點開始、結束的路徑：回路4. 傳遞閉集:兩個頂點可由某一路徑到達，用一條路直接連接這兩個頂點.傳遞閉集包含所有這樣的路R1代表所有長度為n的可以連接兩個頂點的路代代表所有任意長度的可以連接兩個頂點的路代為傳遞閉集路徑的最大長度:元素總數(shù)n零一矩陣：MR*MRM2RM3RMnR101101111MrMR1.MR010o010010110110111等價關系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的劃分依據(jù)偏序1. 偏序是自反的,非對稱的(antisymmetric),可傳遞的.(A,?).偏序集2. 哈希圖解：簡化圖1.箭頭朝上2.去自反3.去傳遞4.去箭頭3. 最小，最大元素(可能不只一個)：a比min在關系？