離散數(shù)學(xué)必備知識(shí)點(diǎn)總結(jié)(共16頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上總結(jié) 離散數(shù)學(xué)知識(shí)點(diǎn)第2章 命題邏輯1. ，前鍵為真，后鍵為假才為假；<>，相同為真，不同為假；2. 主析取范式：極小項(xiàng)(m)之和；主合取范式：極大項(xiàng)(M)之積；3. 求極小項(xiàng)時(shí)，命題變?cè)目隙?，否定為0，求極大項(xiàng)時(shí)相反；4. 求極大極小項(xiàng)時(shí)，每個(gè)變?cè)蜃冊(cè)姆穸ㄖ荒艹霈F(xiàn)一次，求極小項(xiàng)時(shí)變?cè)粔蚝先≌?，求極大項(xiàng)時(shí)變?cè)粔蛭鋈〖伲?. 求范式時(shí)，為保證編碼不錯(cuò)，命題變?cè)詈冒碢,Q,R的順序依次寫；6. 真值表中值為1的項(xiàng)為極小項(xiàng)，值為0的項(xiàng)為極大項(xiàng)；7. n個(gè)變?cè)灿袀€(gè)極小項(xiàng)或極大項(xiàng)，這為(0-1)剛好為化簡(jiǎn)完后的主析取加主合?。?. 永真式?jīng)]有主合取

2、范式，永假式?jīng)]有主析取范式；9. 推證蘊(yùn)含式的方法(=>)：真值表法；分析法(假定前鍵為真推出后鍵為真，假定前鍵為假推出后鍵也為假)10.命題邏輯的推理演算方法：P規(guī)則，T規(guī)則 真值表法；直接證法；歸謬法；附加前提法；第3章 謂詞邏輯1. 一元謂詞：謂詞只有一個(gè)個(gè)體，一元謂詞描述命題的性質(zhì)； 多元謂詞：謂詞有n個(gè)個(gè)體，多元謂詞描述個(gè)體之間的關(guān)系；2. 全稱量詞用蘊(yùn)含，存在量詞用合取;3. 既有存在又有全稱量詞時(shí)，先消存在量詞，再消全稱量詞；第4章 集合1. N，表示自然數(shù)集，1,2,3，不包括0；2. 基：集合A中不同元素的個(gè)數(shù)，|A|；3. 冪集：給定集合A，以集合A的所有子集為元素組

3、成的集合，P(A)；4. 若集合A有n個(gè)元素，冪集P(A)有個(gè)元素，|P(A)|=；5. 集合的分劃：(等價(jià)關(guān)系) 每一個(gè)分劃都是由集合A的幾個(gè)子集構(gòu)成的集合； 這幾個(gè)子集相交為空，相并為全(A)；6. 集合的分劃與覆蓋的比較： 分劃：每個(gè)元素均應(yīng)出現(xiàn)且僅出現(xiàn)一次在子集中； 覆蓋：只要求每個(gè)元素都出現(xiàn)，沒有要求只出現(xiàn)一次；第5章 關(guān)系1. 若集合A有m個(gè)元素，集合B有n個(gè)元素，則笛卡爾A×B的基數(shù)為mn，A到B上可以定義種不同的關(guān)系；2. 若集合A有n個(gè)元素，則|A×A|=，A上有個(gè)不同的關(guān)系；3. 全關(guān)系的性質(zhì)：自反性，對(duì)稱性，傳遞性； 空關(guān)系的性質(zhì)：反自反性，反對(duì)稱性，

4、傳遞性； 全封閉環(huán)的性質(zhì)：自反性，對(duì)稱性，反對(duì)稱性，傳遞性；4. 前域(domR)：所有元素x組成的集合； 后域(ranR)：所有元素y組成的集合；5. 自反閉包：r(R)=RU; 對(duì)稱閉包：s(R)=RU; 傳遞閉包：t(R)=RUUU6. 等價(jià)關(guān)系：集合A上的二元關(guān)系R滿足自反性，對(duì)稱性和傳遞性，則R稱為等價(jià)關(guān)系；7. 偏序關(guān)系：集合A上的關(guān)系R滿足自反性，反對(duì)稱性和傳遞性，則稱R是A上的一個(gè)偏序關(guān)系；8. covA=<x,y>|x,y屬于A，y蓋住x；9. 極小元：集合A中沒有比它更小的元素(若存在可能不唯一)； 極大元：集合A中沒有比它更大的元素(若存在可能不唯一)； 最小

5、元：比集合A中任何其他元素都小(若存在就一定唯一)； 最大元：比集合A中任何其他元素都大(若存在就一定唯一)；10. 前提：B是A的子集 上界：A中的某個(gè)元素比B中任意元素都大，稱這個(gè)元素是B的上界(若存在，可能不唯一)； 下界：A中的某個(gè)元素比B中任意元素都小，稱這個(gè)元素是B的下界(若存在，可能不唯一)； 上確界：最小的上界(若存在就一定唯一)； 下確界：最大的下界(若存在就一定唯一)；第6章 函數(shù)1. 若|X|=m,|Y|=n,則從X到Y(jié)有種不同的關(guān)系，有種不同的函數(shù)；2. 在一個(gè)有n個(gè)元素的集合上，可以有種不同的關(guān)系，有種不同的函數(shù)，有n!種不同的雙射；3. 若|X|=m,|Y|=n，且

6、m<=n，則從X到Y(jié)有種不同的單射；4. 單射：f:X-Y，對(duì)任意,屬于X,且，若f()f()； 滿射：f:X-Y，對(duì)值域中任意一個(gè)元素y在前域中都有一個(gè)或多個(gè)元素對(duì)應(yīng)； 雙射：f:X-Y，若f既是單射又是滿射，則f是雙射；5. 復(fù)合函數(shù)：fºg=g(f(x);6. 設(shè)函數(shù)f:A-B，g:B-C，那么 如果f,g都是單射，則fºg也是單射； 如果f,g都是滿射，則fºg也是滿射； 如果f,g都是雙射，則fºg也是雙射； 如果fºg是雙射，則f是單射，g是滿射；第7章 代數(shù)系統(tǒng)1. 二元運(yùn)算：集合A上的二元運(yùn)算就是到A的映射；2. 集合A上

7、可定義的二元運(yùn)算個(gè)數(shù)就是從A×A到A上的映射的個(gè)數(shù)，即從從A×A到A上函數(shù)的個(gè)數(shù)，若|A|=2,則集合A上的二元運(yùn)算的個(gè)數(shù)為=16種；3. 判斷二元運(yùn)算的性質(zhì)方法：封閉性：運(yùn)算表內(nèi)只有所給元素；交換律：主對(duì)角線兩邊元素對(duì)稱相等；冪等律：主對(duì)角線上每個(gè)元素與所在行列表頭元素相同；有幺元：元素所對(duì)應(yīng)的行和列的元素依次與運(yùn)算表的行和列相同；有零元：元素所對(duì)應(yīng)的行和列的元素都與該元素相同；4. 同態(tài)映射：<A,*>,<B,>,滿足f(a*b)=f(a)f(b),則f為由<A,*>到<B,>的同態(tài)映射；若f是雙射，則稱為同構(gòu)；第8章 群

8、1. 廣群的性質(zhì)：封閉性； 半群的性質(zhì)：封閉性，結(jié)合律； 含幺半群(獨(dú)異點(diǎn))：封閉性，結(jié)合律，有幺元； 群的性質(zhì)：封閉性，結(jié)合律，有幺元，有逆元；2. 群沒有零元；3. 阿貝爾群(交換群)：封閉性，結(jié)合律，有幺元，有逆元，交換律；4. 循環(huán)群中幺元不能是生成元；5. 任何一個(gè)循環(huán)群必定是阿貝爾群；第10章 格與布爾代數(shù)1. 格：偏序集合A中任意兩個(gè)元素都有上、下確界；2. 格的基本性質(zhì)： 1) 自反性 aa 對(duì)偶: aa 2) 反對(duì)稱性 ab ba => a=b 對(duì)偶:ab ba => a=b 3) 傳遞性 ab bc => ac 對(duì)偶:ab bc => ac 4) 最

9、大下界描述之一 aba 對(duì)偶 avba Abb 對(duì)偶 avbb 5）最大下界描述之二 ca,cb => cab 對(duì)偶ca,cb =>Þcavb 6) 結(jié)合律 a(bc)=(ab)c 對(duì)偶 av(bvc)=(avb)vc 7)   等冪律 aa=a 對(duì)偶 ava=a 8) 吸收律 a(avb)=a 對(duì)偶 av(ab)=a 9)    ab <=> ab=a avb=b 10) ac,bd => abcd avbcvd 11) 保序性 bc => abac avbavc 12） 分配不等式 av(bc)

10、(avb)(avc) 對(duì)偶 a(bvc)(ab)v(ac) 13）模不等式 ac <=>Û av(bc)(avb)c3. 分配格：滿足a(bvc)=(ab)v(ac)和av(bc)=(avb)(avc)；4. 分配格的充要條件：該格沒有任何子格與鉆石格或五環(huán)格同構(gòu)；5.鏈格一定是分配格，分配格必定是模格；6. 全上界：集合A中的某個(gè)元素a大于等于該集合中的任何元素，則稱a為格<A,<=>的全上界，記為1；(若存在則唯一) 全下界：集合A中的某個(gè)元素b小于等于該集合中的任何元素，則稱b為格<A,<=>的全下界，記為0；(若存在則唯一)7.

11、 有界格：有全上界和全下界的格稱為有界格，即有0和1的格；8. 補(bǔ)元：在有界格內(nèi)，如果ab=0,avb=1，則a和b互為補(bǔ)元；9. 有補(bǔ)格：在有界格內(nèi)，每個(gè)元素都至少有一個(gè)補(bǔ)元；10. 有補(bǔ)分配格(布爾格)：既是有補(bǔ)格，又是分配格；11. 布爾代數(shù)：一個(gè)有補(bǔ)分配格稱為布爾代數(shù)；第11章 圖論1. 鄰接：兩點(diǎn)之間有邊連接，則點(diǎn)與點(diǎn)鄰接；2. 關(guān)聯(lián)：兩點(diǎn)之間有邊連接，則這兩點(diǎn)與邊關(guān)聯(lián)；3. 平凡圖：只有一個(gè)孤立點(diǎn)構(gòu)成的圖；4. 簡(jiǎn)單圖：不含平行邊和環(huán)的圖；5. 無向完全圖：n個(gè)節(jié)點(diǎn)任意兩個(gè)節(jié)點(diǎn)之間都有邊相連的簡(jiǎn)單無向圖； 有向完全圖:n個(gè)節(jié)點(diǎn)任意兩個(gè)節(jié)點(diǎn)之間都有邊相連的簡(jiǎn)單有向圖；6. 無向完全圖

12、有n(n-1)/2條邊，有向完全圖有n(n-1)條邊；7. r-正則圖：每個(gè)節(jié)點(diǎn)度數(shù)均為r的圖；8. 握手定理：節(jié)點(diǎn)度數(shù)的總和等于邊的兩倍；9. 任何圖中，度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必定是偶數(shù)個(gè)；10. 任何有向圖中，所有節(jié)點(diǎn)入度之和等于所有節(jié)點(diǎn)的出度之和；11. 每個(gè)節(jié)點(diǎn)的度數(shù)至少為2的圖必定包含一條回路；12. 可達(dá)：對(duì)于圖中的兩個(gè)節(jié)點(diǎn),，若存在連接到的路，則稱與相互可達(dá)，也稱與是連通的；在有向圖中，若存在到的路，則稱到可達(dá)；13. 強(qiáng)連通：有向圖章任意兩節(jié)點(diǎn)相互可達(dá)； 單向連通：圖中兩節(jié)點(diǎn)至少有一個(gè)方向可達(dá)； 弱連通：無向圖的連通；(弱連通必定是單向連通)14. 點(diǎn)割集：刪去圖中的某些點(diǎn)后所得

13、的子圖不連通了，如果刪去其他幾個(gè)點(diǎn)后子圖之間仍是連通的，則這些點(diǎn)組成的集合稱為點(diǎn)割集； 割點(diǎn)：如果一個(gè)點(diǎn)構(gòu)成點(diǎn)割集，即刪去圖中的一個(gè)點(diǎn)后所得子圖是不連通的，則該點(diǎn)稱為割點(diǎn)；15. 關(guān)聯(lián)矩陣：M(G)，是與關(guān)聯(lián)的次數(shù)，節(jié)點(diǎn)為行，邊為列； 無向圖：點(diǎn)與邊無關(guān)系關(guān)聯(lián)數(shù)為0，有關(guān)系為1，有環(huán)為2； 有向圖：點(diǎn)與邊無關(guān)系關(guān)聯(lián)數(shù)為0，有關(guān)系起點(diǎn)為1終點(diǎn)為-1， 關(guān)聯(lián)矩陣的特點(diǎn)：無向圖： 行：每個(gè)節(jié)點(diǎn)關(guān)聯(lián)的邊，即節(jié)點(diǎn)的度； 列：每條邊關(guān)聯(lián)的節(jié)點(diǎn)；有向圖： 所有的入度(1)=所有的出度(0);16.鄰接矩陣：A(G)，是鄰接到的邊的數(shù)目，點(diǎn)為行，點(diǎn)為列；17.可達(dá)矩陣：P(G)，至少存在一條回路的矩陣，點(diǎn)為行

14、，點(diǎn)為列； P(G)=A(G)+(G)+(G)+(G) 可達(dá)矩陣的特點(diǎn)：表明圖中任意兩節(jié)點(diǎn)之間是否至少存在一條路，以及在任何節(jié)點(diǎn)上是否存在回路； A(G)中所有數(shù)的和：表示圖中路徑長(zhǎng)度為1的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長(zhǎng)度為2的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長(zhǎng)度為3的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長(zhǎng)度為4的通路條數(shù)；P(G)中主對(duì)角線所有數(shù)的和：表示圖中的回路條數(shù)；18. 布爾矩陣：B(G)，到有路為1，無路則為0，點(diǎn)為行，點(diǎn)為列；19. 代價(jià)矩陣：鄰接矩陣元素為1的用權(quán)值表示，為0的用無窮大表示，節(jié)點(diǎn)自身到自身的權(quán)值為0；20. 生成樹：只訪問每個(gè)

15、節(jié)點(diǎn)一次，經(jīng)過的節(jié)點(diǎn)和邊構(gòu)成的子圖；21. 構(gòu)造生成樹的兩種方法：深度優(yōu)先；廣度優(yōu)先； 深度優(yōu)先： 選定起始點(diǎn)； 選擇一個(gè)與鄰接且未被訪問過的節(jié)點(diǎn)； 從出發(fā)按鄰接方向繼續(xù)訪問，當(dāng)遇到一個(gè)節(jié)點(diǎn)所有鄰接點(diǎn)均已被訪問時(shí)，回到該節(jié)點(diǎn)的前一個(gè)點(diǎn)，再尋求未被訪問過的鄰接點(diǎn)，直到所有節(jié)點(diǎn)都被訪問過一次；廣度優(yōu)先： 選定起始點(diǎn)； 訪問與鄰接的所有節(jié)點(diǎn),這些作為第一層節(jié)點(diǎn)； 在第一層節(jié)點(diǎn)中選定一個(gè)節(jié)點(diǎn)為起點(diǎn)； 重復(fù)，直到所有節(jié)點(diǎn)都被訪問過一次；22. 最小生成樹：具有最小權(quán)值(T)的生成樹；23. 構(gòu)造最小生成樹的三種方法： 克魯斯卡爾方法；管梅谷算法；普利姆算法； （1）克魯斯卡爾方法 將所有權(quán)值按從小到大排

16、列； 先畫權(quán)值最小的邊，然后去掉其邊值；重新按小到大排序； 再畫權(quán)值最小的邊，若最小的邊有幾條相同的，選擇時(shí)要滿足不能出現(xiàn)回路，然后去掉其邊值；重新按小到大排序； 重復(fù)，直到所有節(jié)點(diǎn)都被訪問過一次； （2）管梅谷算法(破圈法) 在圖中取一回路，去掉回路中最大權(quán)值的邊得一子圖； 在子圖中再取一回路，去掉回路中最大權(quán)值的邊再得一子圖； 重復(fù)，直到所有節(jié)點(diǎn)都被訪問過一次； （3）普利姆算法 在圖中任取一點(diǎn)為起點(diǎn)，連接邊值最小的鄰接點(diǎn)； 以鄰接點(diǎn)為起點(diǎn)，找到鄰接的最小邊值，如果最小邊值比鄰接的所有邊值都小(除已連接的邊值)，直接連接，否則退回，連接現(xiàn)在的最小邊值(除已連接的邊值)； 重復(fù)操作，直到所有

17、節(jié)點(diǎn)都被訪問過一次；24. 關(guān)鍵路徑例2 求PERT圖中各頂點(diǎn)的最早完成時(shí)間, 最晚完成時(shí)間, 緩沖時(shí)間及關(guān)鍵路徑.解：最早完成時(shí)間 TE(v1)=0 TE(v2)=max0+1=1 TE(v3)=max0+2,1+0=2 TE(v4)=max0+3,2+2=4 TE(v5)=max1+3,4+4=8 TE(v6)=max2+4,8+1=9 TE(v7)=max1+4,2+4=6 TE(v8)=max9+1,6+6=12最晚完成時(shí)間 TL(v8)=12 TL(v7)=min12-6=6 TL(v6)=min12-1=11 TL(v5)=min11-1=10 TL(v4)=min10-4=6 T

18、L(v3)=min6-2,11-4,6-4=2 TL(v2)=min2-0,10-3,6-4=2 TL(v1)=min2-1,2-2,6-3=0緩沖時(shí)間 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5=10-8=2 TS(v6)=11-9=2 TS(v7)=6-6=0 TS(v8)=12-12=0關(guān)鍵路徑: v1-v3-v7-v825. 歐拉路：經(jīng)過圖中每條邊一次且僅一次的通路； 歐拉回路：經(jīng)過圖中每條邊一次且僅一次的回路； 歐拉圖：具有歐拉回路的圖； 單向歐拉路：經(jīng)過有向圖中每條邊一次且僅一次的單向路； 歐拉單向回路：經(jīng)過有

19、向圖中每條邊一次且僅一次的單向回路；26. （1）無向圖中存在歐拉路的充要條件： 連通圖；有0個(gè)或2個(gè)奇數(shù)度節(jié)點(diǎn)； （2）無向圖中存在歐拉回路的充要條件： 連通圖；所有節(jié)點(diǎn)度數(shù)均為偶數(shù)； （3）連通有向圖含有單向歐拉路的充要條件：除兩個(gè)節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)入度=出度；這兩個(gè)節(jié)點(diǎn)中，一個(gè)節(jié)點(diǎn)的入度比出度多1，另一個(gè)節(jié)點(diǎn)的入；度比出度少1；（4） 連通有向圖含有單向歐拉回路的充要條件： 圖中每個(gè)節(jié)點(diǎn)的出度=入度；27. 哈密頓路：經(jīng)過圖中每個(gè)節(jié)點(diǎn)一次且僅一次的通路； 哈密頓回路：經(jīng)過圖中每個(gè)節(jié)點(diǎn)一次且僅一次的回路； 哈密頓圖：具有哈密頓回路的圖；28. 判定哈密頓圖（沒有充要條件） 必要條件： 任意去

20、掉圖中n個(gè)節(jié)點(diǎn)及關(guān)聯(lián)的邊后，得到的分圖數(shù)目小于等于n； 充分條件： 圖中每一對(duì)節(jié)點(diǎn)的度數(shù)之和都大于等于圖中的總節(jié)點(diǎn)數(shù)；29. 哈密頓圖的應(yīng)用：安排圓桌會(huì)議； 方法：將每一個(gè)人看做一個(gè)節(jié)點(diǎn)，將每個(gè)人與和他能交流的人連接，找到一條經(jīng)過每個(gè)節(jié)點(diǎn)一次且僅一次的回路(哈密頓圖)，即可；30. 平面圖：將圖形的交叉邊進(jìn)行改造后，不會(huì)出現(xiàn)邊的交叉，則是平面圖；31. 面次：面的邊界回路長(zhǎng)度稱為該面的次；32. 一個(gè)有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍；33. 歐拉定理：假設(shè)一個(gè)連通平面圖有v個(gè)節(jié)點(diǎn)，e條邊，r個(gè)面，則 v-e+r=2；34. 判斷是平面圖的必要條件：(若不滿足，就一定不是平面圖) 設(shè)圖G是v個(gè)節(jié)點(diǎn)，e條邊的簡(jiǎn)單連通平面圖，若v>=3，則e<=3v-6；35. 同胚：對(duì)于兩個(gè)圖G1,G2，如果它們是同構(gòu)的，或者通過反復(fù)插入和除去2度節(jié)點(diǎn)可以變成同構(gòu)的圖，則稱G1，G2是同胚的；36. 判斷G是平面圖的充要條件： 圖G不