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

1、方法、知識(shí)點(diǎn)總結(jié)（知識(shí)重點(diǎn)和考題重點(diǎn)）前三章重點(diǎn)內(nèi)容（知識(shí)重點(diǎn)）：1、 蘊(yùn)含（條件）“”的真值 PQ的真值為假，當(dāng)且僅當(dāng)P為真，Q為 假。2、 重言(永真)蘊(yùn)涵式證明方法 假設(shè)前件為真，推出后件也為真。 假設(shè)后件為假，推出前件也為假。易錯(cuò) 3、 等價(jià)公式和證明中運(yùn)用4、 重要公式重言蘊(yùn)涵式：PQ = P or QP or Q = pQA-B =(AorC)-(BorC)其他是在此基礎(chǔ)上演變等價(jià)公式：冪等律 PP=P PP=P 吸收律 P(PQ)=P P(PQ)=P 同一律 PF=P PT=P PT=T PF=FP Q = (P-Q)(Q-P) = (PQ)(PQ)5、 范式的寫(xiě)法（最方便就是真

2、值表法）6、 派遣人員、課表安排類(lèi)算法：第一步：列出所有條件，寫(xiě)成符號(hào)公式第二步：用合取連接第三步：求上一步中的析取范式即可7、 邏輯推理的寫(xiě)法直接推理論證：其中I公式是指 重言蘊(yùn)涵式那部分其中E公式是指 等價(jià)公式部分條件論證: 形如 , , = R-S R P(附加條件).S TR-S CP8、 謂詞基本內(nèi)容注意：任意用 連接 存在用 連接量詞的否定公式量詞的轄域擴(kuò)充公式量詞分配公式其他公式9、 帶量詞的公式在論域內(nèi)的展開(kāi)10、 量詞轄域的擴(kuò)充公式 11、 前束范式的寫(xiě)法 給定一個(gè)帶有量詞的謂詞公式， 1) 消去公式中的聯(lián)接詞和(為了便于量詞 轄域的擴(kuò)充)； 2) 如果量詞前有“”，則用量詞

3、否定公式”后移。再用摩根定律或求公式的否定公式，將“”后移到原子謂詞公式之前； 3) 用約束變?cè)母拿?guī)則或自由變?cè)拇?規(guī)則對(duì)變?cè)獡Q名(為量詞轄域擴(kuò)充作準(zhǔn)備)； 4) 用量詞轄域擴(kuò)充公式提取量詞，使之成為 前束范式形式。簡(jiǎn)要概括： 1、去 - ， 2、移 3、換元 4、量詞轄域擴(kuò)充12、 謂詞演算的推理理論 推理規(guī)則：P、T、CP、US、ES、EG、UG 的使用ES US 去量詞EG UG 添量詞 謹(jǐn)記：ES要在US之前,很重要 添加量詞注意事項(xiàng)：13、 集合的冪集（用P表示，也常有花P表示） A是集合，由A的所有子集構(gòu)成的集合，稱 之為A的冪集。記作P(A)或2的A次方給定有限集合A，如

4、果|A|=n, 則|P(A)|=2的n次方14、 求集合的劃分?jǐn)?shù)與等價(jià)關(guān)系數(shù) 相同15、 三種重要集合運(yùn)算1、 差運(yùn)算- (相對(duì)補(bǔ)集) 2、 絕對(duì)補(bǔ)集 3、 對(duì)稱差 前三章重點(diǎn)內(nèi)容（考題重點(diǎn)）：最常考內(nèi)容和方法需要看自己課件，前三章考試內(nèi)容不多且簡(jiǎn)單1、 命題符號(hào)化（包括第一章簡(jiǎn)單的命題和第二章謂詞的命題）2、 邏輯推理（命題邏輯和謂詞邏輯兩種推理，每章書(shū)最后部分）3、 主析取范式與主合取范式（命題邏輯和謂詞邏輯中的兩種范式寫(xiě)法）4、 真值的判斷后五章重點(diǎn)內(nèi)容（知識(shí)重點(diǎn)）：1、 笛卡爾積定義:設(shè)A、B是集合，由A的元素為第一元素， B的元素為第二元素組成序偶的集合，稱為A和B 的笛卡爾積，記作

5、AB如果A、B都是有限集，且|A|=m, |B|=n，則 |AXB |=mn. 2、 域的表示：定義域dom（關(guān)系的第一個(gè)元素的范圍）值域 Ran（關(guān)系的第二個(gè)元素的范圍）3、 空關(guān)系、完全關(guān)系、A上的恒等關(guān)系IA的定義空關(guān)系只有點(diǎn)，沒(méi)有一條邊。4、 關(guān)系的個(gè)數(shù) 5、 對(duì)稱、反對(duì)稱、自反、反自反、傳遞的判定6、 等價(jià)關(guān)系、等價(jià)類(lèi)定義：設(shè)R是A上關(guān)系,若R是自反的、對(duì)稱的和 傳遞的，則稱R是A中的等價(jià)關(guān)系等價(jià)關(guān)系的個(gè)數(shù)：劃分?jǐn)?shù)；由等價(jià)關(guān)系圖求等價(jià)類(lèi)：R圖中每個(gè)獨(dú)立子圖上的結(jié)點(diǎn)，構(gòu)成一個(gè)等價(jià)類(lèi)。 不同的等價(jià)類(lèi)個(gè)數(shù)=獨(dú)立子圖個(gè)數(shù)7、 相容關(guān)系、相容類(lèi)特點(diǎn)：自反、對(duì)稱。圖的簡(jiǎn)化：不畫(huà)環(huán)； 兩條對(duì)稱邊用

6、一條無(wú)向直線代替相容類(lèi)：設(shè)r是集合X上的相容關(guān)系，CX,如果對(duì)于C中任 意兩個(gè)元素x,y有r ,稱C是r的一個(gè)相容類(lèi)從簡(jiǎn)化圖找最大相容類(lèi)：最大相容類(lèi)的意義是一個(gè)相容類(lèi)加多一個(gè)點(diǎn)就不是相容類(lèi)了，所以最大相容類(lèi)可以是多個(gè)而不是唯一的“最大”的概念，定義類(lèi)似極大線性無(wú)關(guān)組，但元素個(gè)數(shù)不同-找最大完全多邊形。 最大完全多邊形：含有結(jié)點(diǎn)最多的多邊形中，每個(gè)結(jié)點(diǎn) 都與其它結(jié)點(diǎn)相聯(lián)結(jié)。 通過(guò)最大相容類(lèi)求完全覆蓋：完全覆蓋就是指 所有最大相容類(lèi)構(gòu)成的集合。8、 關(guān)系的分類(lèi)：偏序關(guān)系定義：R是A上自反、反對(duì)稱和傳遞的關(guān)系，則稱R 是A上的偏序關(guān)系。并稱是偏序集。 全序關(guān)系定義：是偏序集，任何x,yA，如果x與y

7、都是可 比較的，則稱是全序關(guān)系(線序、鏈)。 9、 偏序集Hasse圖的畫(huà)法1) .用“?！北硎続中元素。2) .如果xy,且xy，則結(jié)點(diǎn)y要畫(huà)在結(jié)點(diǎn)x的上方。 3). 如果xy,且y蓋住x，x與y之間連一直線。4). 一般先從最下層結(jié)點(diǎn)(全是射出的邊與之相連(不考慮 環(huán))，逐層向上畫(huà)，直到最上層結(jié)點(diǎn)(全是射入的邊與之 相連)。(采用抓兩頭，帶中間的方法 ) 10、 重要元素定義（極大小元、最大小元、上下界、最大下界與最小上界）11、 如何求映射是入（單）、滿、雙射？第一步：分別求出定義域和值域第二步：比較就出來(lái)了，就那么簡(jiǎn)單但是要證明的話：兩者結(jié)合得：雙射成立12、 復(fù)合函數(shù)中的重要性質(zhì)（常

8、考）：f:XY, g:YZ是兩個(gè)函數(shù), 則 如果f和g是滿射的，則 g。f 也是滿射的； 如果f和g是入射的，則 g。f 也是入射的； 如果f和g是雙射的，則 g。f 也是雙射的如果 g。f 是滿射的，則g是 滿射的； 如果g。f 是入射的，則 f 是入射的； 如果 g。f 是雙射的，則f是入射的和g是滿射的13、 函數(shù)種類(lèi)個(gè)數(shù)的求法14、 逆函數(shù)（性質(zhì)）設(shè)f:XY是雙射的函數(shù)，fC:YX 也是函數(shù), 稱 之為 f 的逆函數(shù)。設(shè)f:XY是雙射的函數(shù)，則有15、 第六章基礎(chǔ)知識(shí)重點(diǎn)冪等元、幺元e、零元0、逆元的概念同態(tài)同構(gòu)：f(x)滿射、并且滿足*不是雙射就一定復(fù)合同構(gòu)的條件：必須具有 幺元對(duì)幺

9、元、零元對(duì)零元.代數(shù)系統(tǒng)（重點(diǎn)）半群：封閉、可逆 獨(dú)異點(diǎn)：有幺元群：可逆 交換群：可交換群的特征：1.消去律 2.無(wú)零元 3.除幺元外無(wú)其他冪等元運(yùn)算表中：每個(gè)元素在每一行、列必須出現(xiàn)僅出現(xiàn)一次！16、 第七章基礎(chǔ)知識(shí)重點(diǎn)格：是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，則稱是格平凡格：所有全序都是格，稱之為平凡格。 分配格：（判定定理）所有鏈均為分配格。 設(shè)是分配格，對(duì)任何a,b,cA, 如果有 ab=ac及 ab=ac則必有 b=c . 有界格：（判定定理）有界格定義：如果一個(gè)格存在全上界1與全下界0，則 稱此格為有界格。 從格的圖形看：全上界1，就是圖的最上邊元素(只一個(gè)

10、)。 全下界0，就是圖的最下邊元素(只一個(gè))。 有補(bǔ)格：（判定定理：根據(jù)定義看是不是每個(gè)中間元素都有補(bǔ)元）補(bǔ)元：設(shè)是個(gè)有界格，aA, 如果存在 bA, 使得ab=1 ab=0 則稱a與b互為補(bǔ)元（其中是求最小上界，求最大下界）有補(bǔ)格的定義：一個(gè)有界格中，如果每個(gè)元素都有補(bǔ)元，則稱之為有補(bǔ)格 布爾格：如果一個(gè)格既是分配格又是有補(bǔ)格，則稱之為布爾格。 *重要定理： 在有界分配格中，如果元素有補(bǔ)元，則補(bǔ)元 是唯一的。17、 格的同構(gòu)條件（特別）需同時(shí)滿足：鉆石定律：一個(gè)布爾代數(shù)的所有原子（直接覆蓋最小元0的元素）構(gòu)成的布爾代數(shù)一定與元代數(shù)同構(gòu)18、 布爾代數(shù)表達(dá)式和布爾函數(shù) 是布爾代數(shù)的形式含有變?cè)?/p>

11、 x1,x2,xn 的布爾 表達(dá)式記作E(x1,x2,xn),也可以看成是一個(gè)函數(shù)f:BnB, 稱之為布爾函數(shù)布爾表達(dá)式的范式的寫(xiě)法（很重要，與第一第二章的方法類(lèi)似）19、 第八章圖論的重要知識(shí)點(diǎn)（好多好多的定義自己記吧）圖的同構(gòu)：兩個(gè)圖同構(gòu)的必要條件: 1. 結(jié)點(diǎn)個(gè)數(shù)相等. 2. 邊數(shù)相等. 3. 度數(shù)相同的結(jié)點(diǎn)數(shù)相等.4. 對(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看成無(wú)向圖后 (即把有向邊看成無(wú)向邊)是連通的,則稱G是弱連通強(qiáng)分

12、圖、單側(cè)分圖和弱分圖在簡(jiǎn)單有向圖中,具有強(qiáng)連通的最大子圖,稱為強(qiáng)分圖.具 有單側(cè)連通的最大子圖,稱為單側(cè)分圖.具有弱連通的最 大子圖,稱為弱分圖.圖的矩陣表示和寫(xiě)法（前兩個(gè)有點(diǎn)重要）：1、 鄰接矩陣每一行的1：在無(wú)向圖中代表一條線有向圖中代表出線列中的1代表入線2、 可達(dá)性矩陣3、 完全關(guān)系矩陣圖中結(jié)點(diǎn)的度與個(gè)數(shù)、邊的關(guān)系：考試需要兩則結(jié)合20、 歐拉圖與H（漢密爾）圖（重點(diǎn)）定義：在無(wú)孤立結(jié)點(diǎn)的圖G中,若存在一條回路,它 經(jīng)過(guò)圖中每條邊一次且僅一次,稱此回路為歐拉回路. 稱此圖為歐拉圖 漢密爾頓回路(H回路):通過(guò)G中每個(gè)結(jié)點(diǎn)恰好一次的回 路.具有漢密爾頓回路(H回路)的圖. 歐拉回路的判定

13、：（充要條件）無(wú)向圖G具有歐拉路,當(dāng)且僅當(dāng)G是連通的,且有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn). 漢密爾頓圖的判定: （只有充分條件）(充分條件)設(shè)G是有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,若G中每對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n,則G有一條H回路 歐拉回路的算法（重重重！雖然可能不考）（記做 閉跡交集法）H回路的算法（重重重！雖然可能不考）（記做 相鄰最小權(quán)法）21、 樹(shù)中的重要方法：樹(shù)的 結(jié)點(diǎn)與邊數(shù)：邊數(shù)=結(jié)點(diǎn)數(shù)-1 e = v-1m叉有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的方法：賦權(quán)圖的最小生成樹(shù)的求法（記做 相鄰最小權(quán)不回路法）：定義:一棵生成樹(shù)中的所有邊的權(quán)之和稱為該生成樹(shù)的 權(quán). 具有最小權(quán)的生成樹(shù),稱為最小生成樹(shù).最優(yōu)樹(shù)求法：定義*后五章

14、重點(diǎn)內(nèi)容（考題重點(diǎn)）：1、 求逆元（例如a逆）第一步：求出幺元e第二步：a逆與a進(jìn)行所定義的運(yùn)算，寫(xiě)出等式：如a*a逆=e,求解2、 群的階性質(zhì)*有一個(gè)群G，a屬于G，a元素的階為n，當(dāng)且僅當(dāng)k=mn(n的整數(shù)倍),a的k次方=e.*n階群中的元素x，x的n次方等于e3、 樹(shù)的邊數(shù)e與葉結(jié)點(diǎn)t的關(guān)系 e=2t-24、 圖的畫(huà)法與格的判斷畫(huà)法在前面總結(jié)過(guò)：偏序集Hasse圖的畫(huà)法3) .用“?！北硎続中元素。4) .如果xy,且xy，則結(jié)點(diǎn)y要畫(huà)在結(jié)點(diǎn)x的上方。 3). 如果xy,且y蓋住x，x與y之間連一直線。4). 一般先從最下層結(jié)點(diǎn)(全是射出的邊與之相連(不考慮 環(huán))，逐層向上畫(huà)，直到最上

15、層結(jié)點(diǎn)(全是射入的邊與之 相連)。(采用抓兩頭，帶中間的方法 ) 判斷格：看是否任意都有最小上界、最大下界；分配格：跟那倆個(gè)特別的格比較，沒(méi)有那樣的子格就是分配格； 鏈一定是分配格有界格：有無(wú)最大最小元（1,0表示），有限個(gè)元素的格一定是有界格；有補(bǔ)格：看是否每個(gè)元素都有補(bǔ)元若有補(bǔ)元，補(bǔ)元唯一的是有界分配格！布爾格：分配、有補(bǔ)5、 復(fù)合函數(shù)的性質(zhì)f:XY, g:YZ是兩個(gè)函數(shù), 則 如果f和g是滿射的，則 g。f 也是滿射的； 如果f和g是入射的，則 g。f 也是入射的； 如果f和g是雙射的，則 g。f 也是雙射的如果 g。f 是滿射的，則g是 滿射的； 如果g。f 是入射的，則 f 是入射的

16、； 如果 g。f 是雙射的，則f是入射的和g是滿射的6、 完全圖的邊數(shù)無(wú)向完全圖：邊數(shù)為 n(n-1)/2有向完全圖：邊數(shù)為 2的n次方7、 歐拉圖、H圖完全圖Kn，n為奇數(shù)時(shí)，完全圖既是歐拉圖又是H圖；8、 證明子格證明從封閉性入手，若對(duì),（取最小下界、最大上界運(yùn)算）運(yùn)算封閉則為子格。9、 證明子群第一步：證明非空集合；第二步：在集合中任取兩個(gè)進(jìn)行自定義的運(yùn)算，證明封閉性；第三步：任意取一個(gè)集合中的數(shù)a，證a逆屬于集合即證明可逆性。10、 證明等價(jià)關(guān)系證明三點(diǎn)：自反、對(duì)稱、傳遞11、 證明同態(tài)、同構(gòu)（或者自同構(gòu)）第一步：證明f(x)雙射，先證入射（單射），再證滿射，則為雙射第二步：證類(lèi)似如下

17、式子成立12、 求圖定點(diǎn)數(shù)與歐拉握手定理形如：“一個(gè)圖，邊12，有6個(gè)3度結(jié)點(diǎn)，其他結(jié)點(diǎn)度數(shù)都小于3，求最少有幾個(gè)結(jié)點(diǎn)”的問(wèn)題用歐拉握手定理：邊數(shù)|E|為m，則所有結(jié)點(diǎn)度數(shù)累加起來(lái)等于2m任何圖中都有：奇數(shù)度頂點(diǎn)個(gè)數(shù)為偶數(shù)。13、 布爾表達(dá)式的析取范式、合取范式的求法和前面說(shuō)的一樣，與第一第二章的范式寫(xiě)法類(lèi)似，最好列真值表14、 分清葉結(jié)點(diǎn)、分支節(jié)點(diǎn)、樹(shù)中節(jié)點(diǎn)數(shù)與邊的關(guān)系、度數(shù)和與節(jié)點(diǎn)數(shù)的關(guān)系15、 (G)，k(G)，(G)，(G)，W(G)，x(G) 分別表示圖G的( 最大度 )，( 點(diǎn)連通度 )，( 最小度 )，( 邊連通度 )，( 連通分支數(shù) )，( 最小著色數(shù) )K（G）表示 點(diǎn)連通度

18、 （G）表示邊連通度 d（u，v）表示最短兩點(diǎn)距離 deg(v)表示度 degi 表示入度 dego 表示出度16、 代數(shù)系統(tǒng)的證明半群獨(dú)異點(diǎn)群交換群對(duì)應(yīng)證明順序：封閉、可結(jié)合有幺元可逆性可交換！當(dāng)復(fù)雜時(shí)，可以用畫(huà)出運(yùn)算表的方法，就可以證明是否運(yùn)算封閉、有幺元、有逆元。17、 循環(huán)群、生成元( g )與交換群（循環(huán)群屬于需要了解）循環(huán)群一定是交換群素?cái)?shù)階群一定是循環(huán)群證明交換群： 證任意X、Y，對(duì)運(yùn)算 X * Y = Y * X 成立。循環(huán)群周期：g的N次方等于e(幺元)，則n為周期無(wú)限循環(huán)群與同構(gòu)，K階有限循環(huán)群與同構(gòu)+4、+6運(yùn)算的意義：模加運(yùn)算，將兩個(gè)數(shù)相加后取模p為素?cái)?shù)，p階循環(huán)群有p-1個(gè)生成元。18、 圖的面與歐拉公式歐拉公式：對(duì)于一個(gè)平面圖 V - e + r = 2 v為頂點(diǎn)數(shù)，e為邊數(shù)，r為面的數(shù)量。19、 完全二叉圖的頂點(diǎn)、邊數(shù)與葉的關(guān)系 (理解性記憶)葉子結(jié)點(diǎn)：n頂點(diǎn)數(shù)：2n-1邊數(shù)：2(n-1)m叉圖：