東北大學(xué)離散數(shù)學(xué)復(fù)習(xí)總結(jié)滿分版

..方法、知識(shí)點(diǎn)總結(jié)〔知識(shí)重點(diǎn)和考題重點(diǎn)〕前三章重點(diǎn)容〔知識(shí)重點(diǎn)〕：蘊(yùn)含〔條件〕"→〞的真值P→Q的真值為假，當(dāng)且僅當(dāng)P為真，Q為假。重言(永真)蘊(yùn)涵式證明方法<1>假設(shè)前件為真，推出后件也為真。<2>假設(shè)后件為假，推出前件也為假。易錯(cuò)等價(jià)公式和證明中運(yùn)用重要公式重言蘊(yùn)涵式：P∧Q=>PorQPorQ=>p∨QA->B=>(A∧or∨C)->(B∧or∨C)其他是在此根底上演變等價(jià)公式：冪等律P∧P=PP∨P=P吸收律P∧(P∨Q)=PP∨(P∧Q)=P同一律P∨F=PP∧T=PP∨T=TP∧F=FP<->Q=(P->Q)∧(Q->P)=(P∧Q)∨(﹁P∧﹁Q)式的寫法〔最方便就是真值表法〕派遣人員、課表安排類算法：第一步：列出所有條件，寫成符號(hào)公式第二步：用合取∧連接第三步：求上一步中的析取式即可邏輯推理的寫法直接推理論證：其中I公式是指重言蘊(yùn)涵式那局部其中E公式是指等價(jià)公式局部條件論證:形如~,~,~=>R->SRP(附加條件)... ...STR->SCP謂詞根本容注意：任意用—>連接存在用∧連接量詞的否認(rèn)公式量詞的轄域擴(kuò)大公式量詞分配公式其他公式帶量詞的公式在論域的展開量詞轄域的擴(kuò)大公式前束式的寫法給定一個(gè)帶有量詞的謂詞公式，消去公式中的聯(lián)接詞→和←→(為了便于量詞轄域的擴(kuò)大)；如果量詞前有"﹁〞，則用量詞否認(rèn)公式﹁〞后移。再用摩根定律或求公式的否認(rèn)公式，將"﹁〞后移到原子謂詞公式之前；用約束變?cè)母拿?guī)則或自由變?cè)拇胍?guī)則對(duì)變?cè)獡Q名(為量詞轄域擴(kuò)大作準(zhǔn)備)；用量詞轄域擴(kuò)大公式提取量詞，使之成為前束式形式。簡(jiǎn)要概括：1、去->，<->2、移﹁3、換元4、量詞轄域擴(kuò)大謂詞演算的推理理論推理規(guī)則：P、T、CP、US、ES、EG、UG的使用ESUS去量詞EGUG添量詞*謹(jǐn)記：ES要在US之前,很重要添加量詞考前須知：集合的冪集〔用P表示，也常有花P表示〕A是集合，由A的所有子集構(gòu)成的集合，稱之為A的冪集。記作P(A)或2的A次方給定有限集合A，如果|A|=n,則|P(A)|=2的n次方求集合的劃分?jǐn)?shù)與等價(jià)關(guān)系數(shù)——一樣三種重要集合運(yùn)算差運(yùn)算-(相對(duì)補(bǔ)集)絕對(duì)補(bǔ)集~對(duì)稱差前三章重點(diǎn)容〔考題重點(diǎn)〕：最?？既莺头椒ㄐ枰醋约赫n件，前三章考試容不多且簡(jiǎn)單命題符號(hào)化〔包括第一章簡(jiǎn)單的命題和第二章謂詞的命題〕邏輯推理〔命題邏輯和謂詞邏輯兩種推理，每章書最后局部〕主析取式與主合取式〔命題邏輯和謂詞邏輯中的兩種式寫法〕真值的判斷后五章重點(diǎn)容〔知識(shí)重點(diǎn)〕：笛卡爾積定義:設(shè)A、B是集合，由A的元素為第一元素，B的元素為第二元素組成序偶的集合，稱為A和B的笛卡爾積，記作A×B如果A、B都是有限集，且|A|=m,|B|=n，則|A*B|=mn.域的表示：定義域dom〔關(guān)系的第一個(gè)元素的圍〕值域Ran〔關(guān)系的第二個(gè)元素的圍〕空關(guān)系、完全關(guān)系、A上的恒等關(guān)系IA的定義空關(guān)系只有點(diǎn)，沒有一條邊。關(guān)系的個(gè)數(shù)對(duì)稱、反對(duì)稱、自反、反自反、傳遞的判定等價(jià)關(guān)系、等價(jià)類定義：設(shè)R是A上關(guān)系,假設(shè)R是自反的、對(duì)稱的和傳遞的，則稱R是A中的等價(jià)關(guān)系等價(jià)關(guān)系的個(gè)數(shù)：劃分?jǐn)?shù)；由等價(jià)關(guān)系圖求等價(jià)類：R圖中每個(gè)獨(dú)立子圖上的結(jié)點(diǎn)，構(gòu)成一個(gè)等價(jià)類。不同的等價(jià)類個(gè)數(shù)=獨(dú)立子圖個(gè)數(shù)相容關(guān)系、相容類特點(diǎn)：自反、對(duì)稱。圖的簡(jiǎn)化：⑴不畫環(huán)；⑵兩條對(duì)稱邊用一條無向直線代替相容類：設(shè)r是集合*上的相容關(guān)系，C*,如果對(duì)于C中任意兩個(gè)元素*,y有<*,y>∈r,稱C是r的一個(gè)相容類從簡(jiǎn)化圖找最大相容類：最大相容類的意義是——一個(gè)相容類加多一個(gè)點(diǎn)就不是相容類了，所以最大相容類可以是多個(gè)而不是唯一的"最大〞的概念，定義類似極大線性無關(guān)組，但元素個(gè)數(shù)不同------找最大完全多邊形。最大完全多邊形：含有結(jié)點(diǎn)最多的多邊形中，每個(gè)結(jié)點(diǎn)都與其它結(jié)點(diǎn)相聯(lián)結(jié)。通過最大相容類求完全覆蓋：完全覆蓋就是指所有最大相容類構(gòu)成的集合。關(guān)系的分類：偏序關(guān)系定義：R是A上自反、反對(duì)稱和傳遞的關(guān)系，則稱R是A上的偏序關(guān)系。并稱<A,R>是偏序集。全序關(guān)系定義：<A,≤>是偏序集，任何*,y∈A，如果*與y都是可比擬的，則稱≤是全序關(guān)系(線序、鏈)。偏序集Hasse圖的畫法.用"。〞表示A中元素。.如果*≤y,且*≠y，則結(jié)點(diǎn)y要畫在結(jié)點(diǎn)*的上方。3).如果*≤y,且y蓋住*，*與y之間連一直線。4).一般先從最下層結(jié)點(diǎn)(全是射出的邊與之相連(不考慮環(huán)))，逐層向上畫，直到最上層結(jié)點(diǎn)(全是射入的邊與之相連)。(采用抓兩頭，帶中間的方法)重要元素定義〔極大小元、最大小元、上下界、最大下界與最小上界〕如何求映射是入〔單〕、滿、雙射？第一步：分別求出定義域和值域第二步：比擬就出來了，就則簡(jiǎn)單但是要證明的話：兩者結(jié)合得：雙射成立復(fù)合函數(shù)中的重要性質(zhì)〔常考〕：f:*→Y,g:Y→Z是兩個(gè)函數(shù),則⑴如果f和g是滿射的，則g。f也是滿射的；⑵如果f和g是入射的，則g。f也是入射的；⑶如果f和g是雙射的，則g。f也是雙射的⑴如果g。f是滿射的，則g是滿射的；⑵如果g。f是入射的，則f是入射的；⑶如果g。f是雙射的，則f是入射的和g是滿射的函數(shù)種類個(gè)數(shù)的求法逆函數(shù)〔性質(zhì)〕設(shè)f:*→Y是雙射的函數(shù)，fC:Y*也是函數(shù),稱之為f的逆函數(shù)。設(shè)f:*→Y是雙射的函數(shù)，則有第六章根底知識(shí)重點(diǎn)冪等元、幺元e、零元0、逆元的概念同態(tài)同構(gòu)：f(*)滿射、并且滿足*不是雙射就一定復(fù)合同構(gòu)的條件：必須具有幺元對(duì)幺元、零元對(duì)零元......代數(shù)系統(tǒng)〔重點(diǎn)〕半群：封閉、可逆獨(dú)異點(diǎn)：有幺元群：可逆交換群：可交換群的特征：1.消去律2.無零元3.除幺元外無其他冪等元運(yùn)算表中：每個(gè)元素在每一行、列必須出現(xiàn)僅出現(xiàn)一次！第七章根底知識(shí)重點(diǎn)格：<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格平凡格：所有全序都是格，稱之為平凡格。分配格：〔判定定理〕所有鏈均為分配格。設(shè)<A,≤>是分配格，對(duì)任何a,b,c∈A,如果有a∧b=a∧c及a∨b=a∨c則必有b=c.有界格：〔判定定理〕有界格定義：如果一個(gè)格存在全上界1與全下界0，則稱此格為有界格。從格的圖形看：全上界1，就是圖的最上邊元素(只一個(gè))。全下界0，就是圖的最下邊元素(只一個(gè))。有補(bǔ)格：〔判定定理：根據(jù)定義看是不是每個(gè)中間元素都有補(bǔ)元〕補(bǔ)元：設(shè)<A,≤>是個(gè)有界格，a∈A,如果存在b∈A,使得a∨b=1a∧b=0則稱a與b互為補(bǔ)元〔其中∨是求最小上界，∧求最大下界〕有補(bǔ)格的定義：一個(gè)有界格中，如果每個(gè)元素都有補(bǔ)元，則稱之為有補(bǔ)格布爾格：如果一個(gè)格既是分配格又是有補(bǔ)格，則稱之為布爾格。*重要定理：在有界分配格中，如果元素有補(bǔ)元，則補(bǔ)元是唯一的。格的同構(gòu)條件〔特別〕需同時(shí)滿足：鉆石定律：一個(gè)布爾代數(shù)的所有原子〔直接覆蓋最小元0的元素〕構(gòu)成的布爾代數(shù)一定與元代數(shù)同構(gòu)布爾代數(shù)表達(dá)式和布爾函數(shù)<B,∨,∧,ˉ>是布爾代數(shù)的形式含有變?cè)?1,*2,…,*n的布爾表達(dá)式記作E(*1,*2,…*n),也可以看成是一個(gè)函數(shù)f:Bn→B,稱之為布爾函數(shù)布爾表達(dá)式的式的寫法〔很重要，與第一第二章的方法類似〕第八章圖論的重要知識(shí)點(diǎn)〔好多好多的定義自己記吧〕圖的同構(gòu)：兩個(gè)圖同構(gòu)的必要條件:結(jié)點(diǎn)個(gè)數(shù)相等.邊數(shù)相等.度數(shù)一樣的結(jié)點(diǎn)數(shù)相等.對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)相等.圖的連通：強(qiáng)連通、單側(cè)連通和弱連通〔一般不考〕如果任何兩個(gè)結(jié)點(diǎn)間相互可達(dá),則稱G是強(qiáng)連通.如果任何一對(duì)結(jié)點(diǎn)間,至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá),則稱G是單側(cè)連通.如果將G看成無向圖后(即把有向邊看成無向邊)是連通的,則稱G是弱連通強(qiáng)分圖、單側(cè)分圖和弱分圖在簡(jiǎn)單有向圖中,具有強(qiáng)連通的最大子圖,稱為強(qiáng)分圖.具有單側(cè)連通的最大子圖,稱為單側(cè)分圖.具有弱連通的最大子圖,稱為弱分圖.圖的矩陣表示和寫法〔前兩個(gè)有點(diǎn)重要〕：鄰接矩陣每一行的1：在無向圖中代表一條線有向圖中代表—>出線列中的1代表<—入線可達(dá)性矩陣完全關(guān)系矩陣圖中結(jié)點(diǎn)的度與個(gè)數(shù)、邊的關(guān)系：考試需要兩則結(jié)合歐拉圖與H〔漢密爾〕圖〔重點(diǎn)〕定義：在無孤立結(jié)點(diǎn)的圖G中,假設(shè)存在一條回路,它經(jīng)過圖中每條邊一次且僅一次,稱此回路為歐拉回路.稱此圖為歐拉圖漢密爾頓回路(H回路):通過G中每個(gè)結(jié)點(diǎn)恰好一次的回路.具有漢密爾頓回路(H回路)的圖.歐拉回路的判定：〔充要條件〕無向圖G具有歐拉路,當(dāng)且僅當(dāng)G是連通的,且有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn).漢密爾頓圖的判定:〔只有充分條件〕(充分條件)設(shè)G是有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,假設(shè)G中每對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n,則G有一條H回路歐拉回路的算法〔重重重！雖然可能不考〕〔記做閉跡交集法〕H回路的算法〔重重重！雖然可能不考〕〔記做相鄰最小權(quán)法〕樹中的重要方法：樹的結(jié)點(diǎn)與邊數(shù)：邊數(shù)=結(jié)點(diǎn)數(shù)-1e=v-1m叉有序樹轉(zhuǎn)化成二叉樹的方法：賦權(quán)圖的最小生成樹的求法〔記做相鄰最小權(quán)不回路法〕：定義:一棵生成樹中的所有邊的權(quán)之和稱為該生成樹的權(quán).具有最小權(quán)的生成樹,稱為最小生成樹.最優(yōu)樹求法：定義***后五章重點(diǎn)容〔考題重點(diǎn)〕：<精華看完絕對(duì)不虧>求逆元〔例如a逆〕第一步：求出幺元e第二步：a逆與a進(jìn)展所定義的運(yùn)算，寫出等式：如a*a逆=e,求解群的階性質(zhì)*有一個(gè)群G，a屬于G，a元素的階為n，當(dāng)且僅當(dāng)k=mn(n的整數(shù)倍),a的k次方=e.*n階群中的元素*，*的n次方等于e樹的邊數(shù)e與葉結(jié)點(diǎn)t的關(guān)系e=2t-2圖的畫法與格的判斷畫法在前面總結(jié)過：偏序集Hasse圖的畫法.用"。〞表示A中元素。.如果*≤y,且*≠y，則結(jié)點(diǎn)y要畫在結(jié)點(diǎn)*的上方。3).如果*≤y,且y蓋住*，*與y之間連一直線。4).一般先從最下層結(jié)點(diǎn)(全是射出的邊與之相連(不考慮環(huán)))，逐層向上畫，直到最上層結(jié)點(diǎn)(全是射入的邊與之相連)。(采用抓兩頭，帶中間的方法)判斷——格：看是否任意都有最小上界、最大下界；分配格：跟那倆個(gè)特別的格比擬，沒有那樣的子格就是分配格；鏈一定是分配格有界格：有無最大最小元〔1,0表示〕，有限個(gè)元素的格一定是有界格；有補(bǔ)格：看是否每個(gè)元素都有補(bǔ)元假設(shè)有補(bǔ)元，補(bǔ)元唯一的是有界分配格！布爾格：分配、有補(bǔ)復(fù)合函數(shù)的性質(zhì)f:*→Y,g:Y→Z是兩個(gè)函數(shù),則⑴如果f和g是滿射的，則g。f也是滿射的；⑵如果f和g是入射的，則g。f也是入射的；⑶如果f和g是雙射的，則g。f也是雙射的⑴如果g。f是滿射的，則g是滿射的；⑵如果g。f是入射的，則f是入射的；⑶如果g。f是雙射的，則f是入射的和g是滿射的完全圖的邊數(shù)無向完全圖：邊數(shù)為n(n-1)/2有向完全圖：邊數(shù)為2的n次方歐拉圖、H圖完全圖Kn，n為奇數(shù)時(shí)，完全圖既是歐拉圖又是H圖；證明子格證明從封閉性入手，假設(shè)對(duì)∨,∧〔取最小下界、最大上界運(yùn)算〕運(yùn)算封閉則為子格。證明子群第一步：證明非空集合；第二步：在集合中任取兩個(gè)進(jìn)展自定義的運(yùn)算，證明封閉性；第三步：任意取一個(gè)集合中的數(shù)a，證a逆屬于集合即證明可逆性。證明等價(jià)關(guān)系證明三點(diǎn)：自反、對(duì)稱、傳遞證明同態(tài)、同構(gòu)〔或者自同構(gòu)〕第一步：證明f(*)雙射，①先證入射〔單射〕，②再證滿射，則為雙射第二步：證類似如下式子成立求圖定點(diǎn)數(shù)與歐拉握手定理形如："一個(gè)圖，邊12，有6個(gè)3度結(jié)點(diǎn)，其他結(jié)點(diǎn)度數(shù)都小于3，求最少有幾個(gè)結(jié)點(diǎn)〞的問題用歐拉握手定理：邊數(shù)|E|為m，則所有結(jié)點(diǎn)度數(shù)累加起來等于2m任何圖中都有：奇數(shù)度頂點(diǎn)個(gè)數(shù)為偶數(shù)。布爾表達(dá)式的析取式、合取式的求法和前面說的一樣，與第一第二章的式寫法類似，最好列真值表分清葉結(jié)點(diǎn)、分支節(jié)點(diǎn)、樹中節(jié)點(diǎn)數(shù)與邊的關(guān)系、度數(shù)和與節(jié)點(diǎn)數(shù)的關(guān)系Δ(G)，k(G)，δ(G)，λ(G)，W(G)，*(G)分別表示圖G的(最大度)，(點(diǎn)連通度)，(最小度)，(邊連通度)，(連通分支數(shù))，(最小著色數(shù))K〔G〕表示點(diǎn)連通度λ〔G〕表示邊連通度d〔u，v〕表示最短兩點(diǎn)距離deg(v)表示度degi表示入度dego表示出度代數(shù)系統(tǒng)的證明半群——"獨(dú)異點(diǎn)——"群——"交換群對(duì)應(yīng)證明順序：封閉、可結(jié)合——"有幺元——"可逆性——"可交換?。?！當(dāng)復(fù)雜時(shí)，可以用畫出運(yùn)算表的方法，就可以證明是否運(yùn)算封閉、有幺元、有逆元。循環(huán)群、生成元(g)與交換群〔循環(huán)群屬于需要了解〕循環(huán)群一定是交換群素?cái)?shù)階群一定是循環(huán)群證明交換群：證任意*、Y，對(duì)運(yùn)算**Y=Y**成立。循環(huán)群周期：g的N次方等于e(幺元)，則n為周期無限循環(huán)群與<I,+>同構(gòu)，K階有限循環(huán)群與<I，+K>同構(gòu)+4、+6運(yùn)算的意義：模加運(yùn)算，將兩個(gè)數(shù)相加后取模p為素?cái)?shù)，p階循環(huán)群有p-1個(gè)生成元。圖的面與歐拉公式歐拉公式：對(duì)于一個(gè)平面圖V-e+r=2v為頂點(diǎn)數(shù)，e為邊數(shù)，r為面的數(shù)量。完全二叉圖的頂點(diǎn)、邊數(shù)與葉的關(guān)系(理解性記憶)葉子結(jié)點(diǎn)：n頂點(diǎn)數(shù)：2n-1