離散數(shù)學(xué)必備知識點總結(jié)2392

.總結(jié)離散數(shù)學(xué)知識點第二章命題邏輯1.→,前鍵為真,后鍵為假才為假；<—>,相同為真,不同為假；2.主析取范式：極小項<m>之和；主合取范式：極大項<M>之積；3.求極小項時,命題變元的肯定為1,否定為0,求極大項時相反；4.求極大極小項時,每個變元或變元的否定只能出現(xiàn)一次,求極小項時變元不夠合取真,求極大項時變元不夠析取假；5.求范式時,為保證編碼不錯,命題變元最好按P,Q,R的順序依次寫；6.真值表中值為1的項為極小項,值為0的項為極大項；7.n個變元共有2個極小項或極大項,這2為<0~2-1>剛好為化簡完nnn后的主析取加主合??；8.永真式?jīng)]有主合取范式,永假式?jīng)]有主析取范式；9.推證蘊含式的方法<=>>：真值表法；分析法<假定前鍵為真推出后鍵為真,假定前鍵為假推出后鍵也為假>10.命題邏輯的推理演算方法：P規(guī)則,T規(guī)則①真值表法；②直接證法；③歸謬法；④附加前提法；第三章謂詞邏輯1.一元謂詞：謂詞只有一個個體,一元謂詞描述命題的性質(zhì)；多元謂詞：謂詞有n個個體,多元謂詞描述個體之間的關(guān)系；2.全稱量詞用蘊含→,存在量詞用合取^;3.既有存在又有全稱量詞時,先消存在量詞,再消全稱量詞；第四章集合1/15

.1.N,表示自然數(shù)集,1,2,3……,不包括0；2.基：集合A中不同元素的個數(shù),|A|；3.冪集：給定集合A,以集合A的所有子集為元素組成的集合,P<A>；4.若集合A有n個元素,冪集P<A>有個元素,|P<A>|=2=2；2nA||n5.集合的分劃：<等價關(guān)系>①每一個分劃都是由集合A的幾個子集構(gòu)成的集合；②這幾個子集相交為空,相并為全<A>；6.集合的分劃與覆蓋的比較：分劃：每個元素均應(yīng)出現(xiàn)且僅出現(xiàn)一次在子集中；覆蓋：只要求每個元素都出現(xiàn),沒有要求只出現(xiàn)一次；第五章關(guān)系1.若集合A有m個元素,集合B有n個元素,則笛卡爾A×B的基數(shù)為mn,A到B上可以定義2種不同的關(guān)系；mn2.若集合A有n個元素,則|A×A|=n2,A上有2n2個不同的關(guān)系；3.全關(guān)系的性質(zhì)：自反性,對稱性,傳遞性；空關(guān)系的性質(zhì)：反自反性,反對稱性,傳遞性；全封閉環(huán)的性質(zhì)：自反性,對稱性,反對稱性,傳遞性；4.前域<domR>：所有元素x組成的集合；后域<ranR>：所有元素y組成的集合；5.自反閉包：r<R>=RUI;x對稱閉包：s<R>=RUR;-1傳遞閉包：t<R>=RUR2UR3U……2/15

.6.等價關(guān)系：集合A上的二元關(guān)系R滿足自反性,對稱性和傳遞性,則R稱為等價關(guān)系；7.偏序關(guān)系：集合A上的關(guān)系R滿足自反性,反對稱性和傳遞性,則稱R是A上的一個偏序關(guān)系；8.covA={<x,y>|x,y屬于A,y蓋住x}；9.極小元：集合A中沒有比它更小的元素<若存在可能不唯一>；極大元：集合A中沒有比它更大的元素<若存在可能不唯一>；最小元：比集合A中任何其他元素都小<若存在就一定唯一>；最大元：比集合A中任何其他元素都大<若存在就一定唯一>；10.前提：B是A的子集上界：A中的某個元素比B中任意元素都大,稱這個元素是B的上界<若存在,可能不唯一>；下界：A中的某個元素比B中任意元素都小,稱這個元素是B的下界<若存在,可能不唯一>；上確界：最小的上界<若存在就一定唯一>；下確界：最大的下界<若存在就一定唯一>；第六章函數(shù)1.若|X|=m,|Y|=n,則從X到Y(jié)有2種不同的關(guān)系,有種不同的函數(shù)；mnnm2.在一個有n個元素的集合上,可以有2種不同的關(guān)系,有種不同的2nnn函數(shù),有n!種不同的雙射；3.若|X|=m,|Y|=n,且m<=n,則從X到Y(jié)有種不同的單射；Amn4.單射：f:X-Y,對任意,屬于X,且≠,若f<>≠f<>；xx12xxx1x2123/15

.滿射：f:X-Y,對值域中任意一個元素y在前域中都有一個或多個元素對應(yīng)；雙射：f:X-Y,若f既是單射又是滿射,則f是雙射；5.復(fù)合函數(shù)：fog=g<f<x>>;6.設(shè)函數(shù)f:A-B,g:B-C,那么①如果f,g都是單射,則fog也是單射；②如果f,g都是滿射,則fog也是滿射；③如果f,g都是雙射,則fog也是雙射；④如果fog是雙射,則f是單射,g是滿射；第七章代數(shù)系統(tǒng)1.二元運算：集合A上的二元運算就是A2到A的映射；2.集合A上可定義的二元運算個數(shù)就是從A×A到A上的映射的個數(shù),即從從A×A到A上函數(shù)的個數(shù),若|A|=2,則集合A上的二元運算的個數(shù)為22*2=24=16種；3.判斷二元運算的性質(zhì)方法：①封閉性：運算表內(nèi)只有所給元素；②交換律：主對角線兩邊元素對稱相等；③冪等律：主對角線上每個元素與所在行列表頭元素相同；④有幺元：元素所對應(yīng)的行和列的元素依次與運算表的行和列相同；⑤有零元：元素所對應(yīng)的行和列的元素都與該元素相同；4.同態(tài)映射：<A,*>,<B,^>,滿足f<a*b>=f<a>^f<b>,則f為由4/15

.<A,*>到<B,^>的同態(tài)映射；若f是雙射,則稱為同構(gòu)；第八章群1.廣群的性質(zhì)：封閉性；半群的性質(zhì)：封閉性,結(jié)合律；含幺半群<獨異點>：封閉性,結(jié)合律,有幺元；群的性質(zhì)：封閉性,結(jié)合律,有幺元,有逆元；2.群沒有零元；3.阿貝爾群<交換群>：封閉性,結(jié)合律,有幺元,有逆元,交換律；4.循環(huán)群中幺元不能是生成元；5.任何一個循環(huán)群必定是阿貝爾群；第十章格與布爾代數(shù)1.格：偏序集合A中任意兩個元素都有上、下確界；2.格的基本性質(zhì)：1>自反性a≤a對偶:a≥a2>反對稱性a≤b^b≥a=>a=b對偶:a≥b^b≤a=>a=b3>傳遞性a≤b^b≤c=>a≤c對偶:a≥b^b≥c=>a≥c4>最大下界描述之一5/15

.7>等冪律a^a=a對偶ava=a8>吸收律b≤c=>a^b≤a^cavb≤avc12分配不等式a≤c<=>av<b^c>≤<avb>^c3.分配格：滿足a^<bvc>=<a^b>v<a^c>和6/15.av<b^c>=<avb>^<avc>；4.分配格的充要條件：該格沒有任何子格與鉆石格或五環(huán)格同構(gòu)；5.鏈格一定是分配格,分配格必定是模格；6.全上界：集合A中的某個元素a大于等于該集合中的任何元素,則稱a為格<A,<=>的全上界,記為1；<若存在則唯一>全下界：集合A中的某個元素b小于等于該集合中的任何元素,則稱b為格<A,<=>的全下界,記為0；<若存在則唯一>7.有界格：有全上界和全下界的格稱為有界格,即有0和1的格；8.補元：在有界格內(nèi),如果a^b=0,avb=1,則a和b互為補元；9.有補格：在有界格內(nèi),每個元素都至少有一個補元；10.有補分配格<布爾格>：既是有補格,又是分配格；11.布爾代數(shù)：一個有補分配格稱為布爾代數(shù)；第十一章圖論1.鄰接：兩點之間有邊連接,則點與點鄰接；2.關(guān)聯(lián)：兩點之間有邊連接,則這兩點與邊關(guān)聯(lián)；3.平凡圖：只有一個孤立點構(gòu)成的圖；4.簡單圖：不含平行邊和環(huán)的圖；5.無向完全圖：n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單無向圖；有向完全圖:n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單有向圖；6.無向完全圖有n<n-1>/2條邊,有向完全圖有n<n-1>條邊；7/15

.7.r-正則圖：每個節(jié)點度數(shù)均為r的圖；8.握手定理：節(jié)點度數(shù)的總和等于邊的兩倍；9.任何圖中,度數(shù)為奇數(shù)的節(jié)點個數(shù)必定是偶數(shù)個；10.任何有向圖中,所有節(jié)點入度之和等于所有節(jié)點的出度之和；11.每個節(jié)點的度數(shù)至少為2的圖必定包含一條回路；12.可達：對于圖中的兩個節(jié)點v,v,若存在連接v到v的路,則稱v與ijijiv相互可達,也稱v與v是連通的；在有向圖中,若存在v到v的路,則jijij稱v到v可達；ij13.強連通：有向圖章任意兩節(jié)點相互可達；單向連通：圖中兩節(jié)點至少有一個方向可達；弱連通：無向圖的連通；<弱連通必定是單向連通>14.點割集：刪去圖中的某些點后所得的子圖不連通了,如果刪去其他幾個點后子圖之間仍是連通的,則這些點組成的集合稱為點割集；割點：如果一個點構(gòu)成點割集,即刪去圖中的一個點后所得子圖是不連通的,則該點稱為割點；15.關(guān)聯(lián)矩陣：M<G>,m是v與e關(guān)聯(lián)的次數(shù),節(jié)點為行,邊為列；ijij無向圖：點與邊無關(guān)系關(guān)聯(lián)數(shù)為0,有關(guān)系為1,有環(huán)為2；有向圖：點與邊無關(guān)系關(guān)聯(lián)數(shù)為0,有關(guān)系起點為1終點為-1,關(guān)聯(lián)矩陣的特點：無向圖：①行：每個節(jié)點關(guān)聯(lián)的邊,即節(jié)點的度；②列：每條邊關(guān)聯(lián)的節(jié)點；8/15

.有向圖：③所有的入度<1>=所有的出度<0>;16.鄰接矩陣：A<G>,a是v鄰接到v的邊的數(shù)目,點為行,點為列；ijij17.可達矩陣：P<G>,至少存在一條回路的矩陣,點為行,點為列；P<G>=A<G>+A2<G>+A3<G>+A4<G>可達矩陣的特點：表明圖中任意兩節(jié)點之間是否至少存在一條路,以及在任何節(jié)點上是否存在回路；A<G>中所有數(shù)的和：表示圖中路徑長度為1的通路條數(shù)；A2<G>中所有數(shù)的和：表示圖中路徑長度為2的通路條數(shù)；A3<G>中所有數(shù)的和：表示圖中路徑長度為3的通路條數(shù)；A4<G>中所有數(shù)的和：表示圖中路徑長度為4的通路條數(shù)；P<G>中主對角線所有數(shù)的和：表示圖中的回路條數(shù)；18.布爾矩陣：B<G>,v到v有路為1,無路則為0,點為行,點為列；ij19.代價矩陣：鄰接矩陣元素為1的用權(quán)值表示,為0的用無窮大表示,節(jié)點自身到自身的權(quán)值為0；20.生成樹：只訪問每個節(jié)點一次,經(jīng)過的節(jié)點和邊構(gòu)成的子圖；21.構(gòu)造生成樹的兩種方法：深度優(yōu)先；廣度優(yōu)先；深度優(yōu)先：①選定起始點；v0②選擇一個與v鄰接且未被訪問過的節(jié)點；v10③從v出發(fā)按鄰接方向繼續(xù)訪問,當遇到一個節(jié)點所有鄰接點均已被1訪問時,回到該節(jié)點的前一個點,再尋求未被訪問過的鄰接點,直到所有9/15

.節(jié)點都被訪問過一次；廣度優(yōu)先：①選定起始點v；0②訪問與v鄰接的所有節(jié)點v,v,……,v,這些作為第一層節(jié)點；012k③在第一層節(jié)點中選定一個節(jié)點為起點；v1④重復(fù)②③,直到所有節(jié)點都被訪問過一次；22.最小生成樹：具有最小權(quán)值<T>的生成樹；23.構(gòu)造最小生成樹的三種方法：克魯斯卡爾方法；管梅谷算法；普利姆算法；〔1克魯斯卡爾方法①將所有權(quán)值按從小到大排列；②先畫權(quán)值最小的邊,然后去掉其邊值；重新按小到大排序；③再畫權(quán)值最小的邊,若最小的邊有幾條相同的,選擇時要滿足不能出現(xiàn)回路,然后去掉其邊值；重新按小到大排序；④重復(fù)③,直到所有節(jié)點都被訪問過一次；〔2管梅谷算法<破圈法>①在圖中取一回路,去掉回路中最大權(quán)值的邊得一子圖；②在子圖中再取一回路,去掉回路中最大權(quán)值的邊再得一子圖；③重復(fù)②,直到所有節(jié)點都被訪問過一次；〔3普利姆算法①在圖中任取一點為起點v,連接邊值最小的鄰接點v；12②以鄰接點為起點,找到v鄰接的最小邊值,如果最小邊值比vv22110/15

.鄰接的所有邊值都小<除已連接的邊值>,直接連接,否則退回現(xiàn)在的最小邊值<除已連接的邊值>；③重復(fù)操作,直到所有節(jié)點都被訪問過一次；24.關(guān)鍵路徑v,連接v11例2求PERT圖中各頂點的最早完成時間,最晚完成時間,緩沖時間及關(guān)鍵路徑.解：最早完成時間TE<v1>=0TE<v2>=max{0+1}=1TE<v3>=max{0+2,1+0}=2TE<v4>=max{0+3,2+2}=4TE<v5>=max{1+3,4+4}=8TE<v6>=max{2+4,8+1}=9TE<v7>=max{1+4,2+4}=6TE<v8>=max{9+1,6+6}=12最晚完成時間TL<v8>=12TL<v7>=min{12-6}=6TL<v6>=min{12-1}=11TL<v5>=min{11-1}=10TL<v4>=min{10-4}=6TL<v3>=min{6-2,11-4,6-4}=211/15

.TL<v2>=min{2-0,10-3,6-4}=2TL<v1>=min{2-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>=6-6=0TS<v8>=12-12=0關(guān)鍵路徑:v1-v3-v7-v825.歐拉路：經(jīng)過圖中每條邊一次且僅一次的通路；歐拉回路：經(jīng)過圖中每條邊一次且僅一次的回路；歐拉圖：具有歐拉回路的圖；單向歐拉路：經(jīng)過有向圖中每條邊一次且僅一次的單向路；歐拉單向回路：經(jīng)過有向圖中每條邊一次且僅一次的單向回路；26.〔1無向圖中存在歐拉路的充要條件：①連通圖；②有0個或2個奇數(shù)度節(jié)點；〔2無向圖中存在歐拉回路的充要條件：①連通圖；②所有節(jié)點度數(shù)均為偶數(shù)；〔3連通有向圖含有單向歐拉路的充要條件：12/15

.①除兩個節(jié)點外,每個節(jié)點入度=出度；②這兩個節(jié)點中,一個節(jié)點的入度比出度多1,另一個節(jié)點的入；度比出度少1；（4）連通有向圖含有單向歐拉回路的充要條件：圖中每個節(jié)點的出度=入度；27.哈密頓路：經(jīng)過圖中每個節(jié)點一次且僅一次的通路；哈密頓回路：經(jīng)過圖中每個節(jié)點一次且僅一次的回路；哈密頓圖：具有哈密頓回路的圖；28.判定哈密頓圖〔沒有充要條件必要條件：任意去掉圖中n個節(jié)點及關(guān)聯(lián)的邊后,得到的分圖數(shù)目小于等于n；充分條件：圖中每一對節(jié)點的度數(shù)之和都大于等于圖中的總節(jié)點數(shù)；29.哈密頓圖的應(yīng)用：安排圓桌會議；方法：將每一個人看做一個節(jié)點,將每個人與和他能交流的人連接,找到一條經(jīng)過每個節(jié)點一次且僅一次的回路<哈密頓圖>,即可；30.平面圖：將圖形的交叉邊進行改造后,不會出現(xiàn)邊的交叉,則是平面圖；31.面次：面的邊界回路長度稱為該面的次；32.一個有限平面圖,面的次數(shù)之和等于其邊數(shù)的兩倍；33.歐拉定理：假設(shè)一個連通平面圖有v個節(jié)點,e條邊,r個面,則13/15

.v-e+r=2；34.判斷是平面圖的必要條件：<若不滿足,就一定不是平面圖>設(shè)圖G是v個節(jié)點,e條邊的簡單連通平面圖,若v>=3,則e<=3v-6；35.同胚：對于兩個圖G1,G2,如果它們是同構(gòu)的,或者通過反復(fù)插入和除去2度節(jié)點可以變成同構(gòu)的圖,則稱G1,G2是同胚的；36.判斷G是平面圖的充要條件：圖G不含同胚于K3.3或K5的子圖；37.二部圖：①無向圖的節(jié)點集合可以劃分為兩個子集V1,V2；②圖中每條邊的一個端點在V1,另一個則在V2中；完全二部圖：二部圖中V1的每個節(jié)點都