離散數學必備知識點總結講解

1、總結離散數學知識點第二章命題邏輯1.7,前鍵為真，后鍵為假才為假； 一,相同為真，不同為假；2 .主析取范式：極小項（m）之和；主合取范式：極大項（M）之積；3 .求極小項時，命題變元的肯定為1,否定為0,求極大項時相反；4 .求極大極小項時，每個變元或變元的否定只能出現(xiàn)一次，求極小項 時變元不夠合取真，求極大項時變元不夠析取假；5 .求范式時，為保證編碼不錯，命題變元最好按P,Q,R的順序依次寫;6 .真值表中值為1的項為極小項，值為0的項為極大項；7 .n個變元共有2n個極小項或極大項，這2n為（02n-1）剛好為化簡完 后的主析取加主合取；8 .永真式沒有主合取范式，永假式沒有主析取范式

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

3、合A有n個元素，募集P(A)有2n個元素，|P(A)尸21A1 = 2n ；5 .集合的分劃：(等價關系)每一個分劃都是由集合 A的幾個子集構成的集合；這幾個子集相交為空，相并為全(A);6 .集合的分劃與覆蓋的比較：分劃：每個元素均應出現(xiàn)且僅出現(xiàn)一次在子集中；覆蓋：只要求每個元素都出現(xiàn)，沒有要求只出現(xiàn)一次；第五章 關系1 .若集合A有m個元素，集合B有n個元素，則笛卡爾AXB的基數為mn, A到B上可以定義2伽種不同的關系；2 .若集合A有n個元素，則|A淤尸n2, A上有2n2個不同的關系；3 .全關系的性質：自反性，對稱性，傳遞性；空關系的性質：反自反性，反對稱性，傳遞性;全封閉環(huán)的性質

4、：自反性，對稱性，反對稱性，傳遞性；4 .前域（domR）:所有元素x組成的集合；后域（ranR）：所有元素y組成的集合；5 .自反閉包：r（R）=RU lx；對稱閉包：s（R）=RU R-1;傳遞閉包：t（R）=RU R2UR3U6 .等價關系：集合A上的二元關系R滿足自反性，對稱性和傳遞性，則R稱為等價關系；7 .偏序關系：集合A上的關系R滿足自反性，反對稱性和傳遞性， 則稱R是A上的一個偏序關系；8 .covA=<x,y>|x,y 屬于 A, y 蓋住 x;9 .極小元：集合A中沒有比它更小的元素（若存在可能不唯一）；極大元：集合A中沒有比它更大的元素（若存在可能不唯一）；最

5、小元：比集合A中任何其他元素都?。ㄈ舸嬖诰鸵欢ㄎㄒ唬蛔畲笤罕燃螦中任何其他元素都大（若存在就一定唯一）；10 .前提：B是A的子集上界：A中的某個元素比B中任意元素都大，稱這個元素是 B的 上界（若存在，可能不唯一）；下界：A中的某個元素比B中任意元素都小，稱這個元素是 B的 下界（若存在，可能不唯一）；上確界：最小的上界（若存在就一定唯一）;下確界：最大的下界（若存在就一定唯一）;第六章 函數1 .若|X|=m,|Y|=n,則從X到Y有2種不同的關系，有nm種不同的函數；2 .在一個有n個元素的集合上，可以有2n2種不同的關系，有nn種不 同的函數，有n!種不同的雙射；3 .若|X|二

6、m,|Y|=n ,且m<=n ,則從X到Y有a；種不同的單射；4 .單射：f:X-Y ,對任意2,X2屬于X,且xia，若f(xi)力(X2);滿射：f:X-Y,對值域中任意一個元素 y在前域中都有一個或多個 元素對應；雙射：f:X-Y,若f既是單射又是滿射，則f是雙射；5 .復合函數：fog=g(f(x)；6 .設函數f:A-B, g:B-C,那么如果f,g都是單射，則fcg也是單射；如果f,g都是滿射，則fcg也是滿射；如果f,g都是雙射，則fcg也是雙射；如果fcg是雙射，則f是單射，g是滿射；第七章代數系統(tǒng)1 .二元運算：集合A上的二元運算就是A2到A的映射；2 .集合A上可定義

7、的二元運算個數就是從 AXA到A上的映射的個數, 即從從AXA到A上函數的個數，若|A|=2,則集合A上的二元運算的 個數為22*2 = 24 =16種；3,判斷二元運算的性質方法：封閉性：運算表內只有所給元素；交換律：主對角線兩邊元素對稱相等；哥等律：主對角線上每個元素與所在行列表頭元素相同；有幺元：元素所對應的行和列的元素依次與運算表的行和列相同；有零元：元素所對應的行和列的元素都與該元素相同；4.同態(tài)映射：<A,*>,<BJ>,滿足 f(a*b)=f(a)7(b),貝U f為由 <A,*> 至k8,八> 的同態(tài)映射；若f是雙射，則稱為同構；第八章

8、群1 .廣群的性質：封閉性；半群的性質：封閉性，結合律；含幺半群(獨異點)：封閉性，結合律，有幺元；群的性質：封閉性，結合律，有幺元，有逆元；2 .群沒有零元；3,阿貝爾群(交換群)：封閉性，結合律，有幺元，有逆元，交換律；4 .循環(huán)群中幺元不能是生成元；5 .任何一個循環(huán)群必定是阿貝爾群；第十章格與布爾代數1 .格：偏序集合A中任意兩個元素都有上、下確界;2 .格的基本性質：1)自反性a<a 對偶：a>a2)反對稱性a< b A b >a => a=b對偶:a nb Ab wa => a=b3)傳遞性a< b A b < c => a&l

9、t; c對偶:a nb Ab Ac => a>c4)最大下界描述之一aAb<a對偶 avb >aAAb< b對偶 avb > b5)最大下界描述之二c< a,c< b => c<aAb對偶 cAa,cnb => c>avb6)結合律aA(bAc)=(aAb)Ac對偶 av(bvc)=(avb)vc7)等哥律aAa=a 對偶 ava=a8)吸收律aA(avb)=a對偶 av(aAb)=a9)a< b <=>aAb=aavb=b10)a<c,b < d=> aAb < cAd avb

10、< cvd11)保序性b<c =>aAb < aAc avb < avc12)分配不等式av(bAc) < (avb)A(avc)對偶 aA(bvc) > (aAb)v(aAc)13)模不等式a <c <=>av(bAc) < (avbc3 .分酉己格：滿足 aA(bvc)=(aAb)v(aAc)和 av(bAc)=(avb)A(avc);4 .分配格的充要條件：該格沒有任何子格與鉆石格或五環(huán)格同構；5 .鏈格一定是分配格，分配格必定是模格；6 .全上界：集合A中的某個元素a大于等于該集合中的任何元素，則稱a為格<A,&l

11、t;=>的全上界，記為1;(若存在則唯一)全下界：集合A中的某個元素b小于等于該集合中的任何元素，則稱b為格<A,<=>的全下界，記為0;(若存在則唯一)7 .有界格：有全上界和全下界的格稱為有界格，即有 0和1的格；8 .補元：在有界格內，如果 aAb=0,avb=1 ,則a和b互為補元；9 .有補格：在有界格內，每個元素都至少有一個補元；10 .有補分配格(布爾格)：既是有補格，又是分配格；11 .布爾代數：一個有補分配格稱為布爾代數;第十一章圖論1 .鄰接：兩點之間有邊連接，則點與點鄰接；2 .關聯(lián)：兩點之間有邊連接，則這兩點與邊關聯(lián)；3 .平凡圖：只有一個孤立點

12、構成的圖；4 .簡單圖：不含平行邊和環(huán)的圖；5 .無向完全圖：n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單無向圖； 有向完全圖：n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單有向圖；6 .無向完全圖有n(n-1)/2條邊，有向完全圖有n(n-1)條邊；7 .r-正則圖：每個節(jié)點度數均為r的圖；8 .握手定理：節(jié)點度數的總和等于邊的兩倍；9 .任何圖中，度數為奇數的節(jié)點個數必定是偶數個；10 .任何有向圖中，所有節(jié)點入度之和等于所有節(jié)點的出度之和；11 .每個節(jié)點的度數至少為2的圖必定包含一條回路；12 .可達：對于圖中的兩個節(jié)點M,Vj,若存在連接Vi到的路，則稱m 與Vj相互可達，也稱Vi與Vj是連通

13、的；在有向圖中，若存在 Vi到Vj的 路，則稱M到Vj可達；13 .強連通：有向圖章任意兩節(jié)點相互可達；單向連通：圖中兩節(jié)點至少有一個方向可達；弱連通：無向圖的連通；(弱連通必定是單向連通)14 .點割集：刪去圖中的某些點后所得的子圖不連通了，如果刪去其他幾個點后子圖之間仍是連通的，則這些點組成的集合稱為點割集；割點：如果一個點構成點割集，即刪去圖中的一個點后所得子圖是不連通的，則該點稱為割點；15 .關聯(lián)矩陣：M(G), mj是m與ej關聯(lián)的次數，節(jié)點為行，邊為列；無向圖：點與邊無關系關聯(lián)數為 0,有關系為1,有環(huán)為2;有向圖：點與邊無關系關聯(lián)數為 0,有關系起點為1終點為-1,關聯(lián)矩陣的特

14、點：無向圖：行：每個節(jié)點關聯(lián)的邊，即節(jié)點的度；列：每條邊關聯(lián)的節(jié)點；有向圖：所有的入度(1)=所有的出度(0)；16 .鄰接矩陣：A(G), a。是w鄰接到看的邊的數目，點為行，點為歹U;17 .可達矩陣：P(G),至少存在一條回路的矩陣，點為行，點為列；P(G)=A(G)+ A2 (G)+ A3 (G)+ A4 (G)可達矩陣的特點：表明圖中任意兩節(jié)點之間是否至少存在一條路，以及在任何節(jié)點上是否存在回路；A(G)中所有數的和：表示圖中路徑長度為1的通路條數；A2(G)中所有數的和：表示圖中路徑長度為 2的通路條數；A3(G)中所有數的和：表示圖中路徑長度為 3的通路條數；A4(G)中所有數的

15、和：表示圖中路徑長度為 4的通路條數;P(G)中主對角線所有數的和：表示圖中的回路條數；18 .布爾矩陣：B(G), m到力有路為1,無路則為0,點為行，點為列;19 .代價矩陣：鄰接矩陣元素為1的用權值表示，為0的用無窮大表 示，節(jié)點自身到自身的權值為0;20 .生成樹：只訪問每個節(jié)點一次，經過的節(jié)點和邊構成的子圖；21 .構造生成樹的兩種方法：深度優(yōu)先；廣度優(yōu)先；深度優(yōu)先：選定起始點V。；選擇一個與V0鄰接且未被訪問過的節(jié)點V1 ;從V1出發(fā)按鄰接方向繼續(xù)訪問，當遇到一個節(jié)點所 有鄰接點均已被訪問時，回到該節(jié)點的前一個點，再尋求未被訪問過 的鄰接點，直到所有節(jié)點都被訪問過一次；廣度優(yōu)先：選

16、定起始點V0 ;訪問與V0鄰接的所有節(jié)點V1,V2,，Vk，這些作為第一層節(jié)點；在第一層節(jié)點中選定一個節(jié)點V1為起點；重復，直到所有節(jié)點都被訪問過一次；22 .最小生成樹：具有最小權值(T)的生成樹；23 .構造最小生成樹的三種方法：克魯斯卡爾方法；管梅谷算法；普利姆算法;(1)克魯斯卡爾方法將所有權值按從小到大排列；先畫權值最小的邊，然后去掉其邊值；重新按小到大排序；再畫權值最小的邊，若最小的邊有幾條相同的，選擇時要滿 足不能出現(xiàn)回路，然后去掉其邊值；重新按小到大排序；重復，直到所有節(jié)點都被訪問過一次；(2)管梅谷算法(破圈法)在圖中取一回路，去掉回路中最大權值的邊得一子圖；在子圖中再取一回

17、路，去掉回路中最大權值的邊再得一子圖；重復，直到所有節(jié)點都被訪問過一次；(3)普利姆算法在圖中任取一點為起點5,連接邊值最小的鄰接點V2；以鄰接點V2為起點，找到V2鄰接的最小邊值，如果最小邊值 比Vi鄰接的所有邊值都小(除已連接的邊值)，直接連接，否則退回, 連接Vi現(xiàn)在的最小邊值(除已連接的邊值)；重復操作，直到所有節(jié)點都被訪問過一次；24 .關鍵路徑例2求PERT圖中各頂點的最早完成時間，最晚完成時間，緩沖時間 及關鍵路徑.解：最早完成時間TE(v1)=0TE（V2）=max0+1=1TE(v3)=max0+2,1+0=2TE(v4)=max0+3,2+2=4TE(v5)=max1+3,

18、4+4=8TE(v6)=max2+4,8+1=9TE(v7)=max1+4,2+4=6TE(v8)=max9+1,6+6=12最晚完成時間TL(v8)=12TL(v7)=min12-6=6TL(v6)=min12-1=11TL(v5)=min11-1=10TL(v4)=min10-4=6TL(v3)=min6-2,11-4,6-4=2TL(v2)=min2-0,10-3,6-4=2TL(v1)=min2-1,2-2,6-3=0緩沖時間TS(v1)=0-0=0TS(v2)=2-1 = 1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)

19、=6-6=0TS(v8)=12-12=0關鍵路徑：v1-v3-v7-v825 .歐拉路：經過圖中每條邊一次且僅一次的通路；歐拉回路：經過圖中每條邊一次且僅一次的回路；歐拉圖：具有歐拉回路的圖；單向歐拉路：經過有向圖中每條邊一次且僅一次的單向路；歐拉單向回路：經過有向圖中每條邊一次且僅一次的單向回路；26 . (1)無向圖中存在歐拉路的充要條件：連通圖；有0個或2個奇數度節(jié)點；(2)無向圖中存在歐拉回路的充要條件：連通圖；所有節(jié)點度數均為偶數；(3)連通有向圖含有單向歐拉路的充要條件：除兩個節(jié)點外，每個節(jié)點入度=出度；這兩個節(jié)點中，一個節(jié)點的入度比出度多1 ,另一個節(jié)點的入;度比出度少1;（4）

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