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

方法、知識(shí)點(diǎn)總結(jié)（知識(shí)重點(diǎn)和考題重點(diǎn)）前三章重點(diǎn)內(nèi)容（知識(shí)重點(diǎn)）：1、蘊(yùn)含（條件）“f”的真值P+Q的真值為假，當(dāng)且僅當(dāng)P為真，Q為假。2、重言（永真）蘊(yùn)涵式證明方法<1>假設(shè)前件為真，推出后件也為真。<2>假設(shè)后件為假，推出前件也為假。易錯(cuò)?例5,若天不下雨，我就上街；否則在家。P：天下雨。Q：我上街。R：我在家。該命題可寫(xiě)成：JPfQ）A（PfR）.注意：中間的聯(lián)結(jié)詞一定是“八”，而不是也不是7因?yàn)樵}表示：“天不下雨時(shí)我做什么，天下雨我又做什么”的兩種作法，其中有一種作法是假的，則我說(shuō)的就是假話，所以中間的聯(lián)結(jié)詞一定是

3、等價(jià)公式和證明中運(yùn)用4、重要公式重言蘊(yùn)涵式：PAQ=>PorQPorQ=>pVQA->B=>(AAorVC)->(BAorVC)其他是在此基礎(chǔ)上演變等價(jià)公式：冪等律pA等價(jià)公式：冪等律pAp=ppVp=p吸收律pA(pVQ)=p pV(pAq)=p同一律pvf=p pAt=ppVt=t pAf=fP<->Q=(P->Q)A(Q->P)=(PAQ)V(「PA「Q)5、范式的寫(xiě)法（最方便就是真值表法）6、派遣人員、課表安排類(lèi)算法:第一步：列出所有條件，寫(xiě)成符號(hào)公式第二步：用合取A連接第三步：求上一步中的析取范式即可7、邏輯推理的寫(xiě)法直接推理論證：其中I公式是指重言蘊(yùn)涵式那部分其中E公式是指等價(jià)公式部分

條件論證:條件論證:形如~,~=>R->SR P(附加條件)... ...STR->SCP8、謂詞基本內(nèi)容注意：任意V用一>連接存在三用A連接量詞的否定公式—nVxA(x)odx-iA(x)2.-n3xA(x)0Vx-iA(x)量詞的轄域擴(kuò)充公式2：3.5.VxA(x)VBoVx(A(x)VB)VxA(x)八BoVx(A(x)AB)3xA(x)VB<?3x(A(x)VB)SxA(x)2：3.5.B~?3xA(x)udx(B-A(x))VxA(x)fBudx(A(x)fB)3xA(x)fBoVx(A(x)fB)

量詞分配公式LBx(A(x)VB(x))^>BxA(x)V3xB(x)2.Vx(A(x)AB(x))<^>VxA(x)AVxB(x)3.3x(A(x)AB(x))n玄A(x)ABxB(x)4.VxA(x)VVxB(x)=>Vx(A(x)VB(x))其他公式L3x(A(x)-B(x))oVxA(x)-*3xB(x)2.3xA(x)fVxB(x)=Dx(A(x)fB(x))9、帶量詞的公式在論域內(nèi)的展開(kāi)10、量詞轄域的擴(kuò)充公式11、前束范式的寫(xiě)法給定一個(gè)帶有量詞的謂詞公式，1）消去公式中的聯(lián)接詞f和+f（為了便于量詞轄域的擴(kuò)充）;2）如果量詞前有“」”，則用量詞否定公式」”后移。再用摩根2）如果量詞前有“」”，則用量詞否定公式」”后移。再用摩根定律或求公式的否定公式，將“」”后移到原子謂詞公式之前;3）用約束變?cè)母拿?guī)則或自由變?cè)拇胍?guī)則對(duì)變?cè)獡Q名（為量詞轄域擴(kuò)充作準(zhǔn)備）；4）用量詞轄域擴(kuò)充公式提取量詞，使之成為前束范式形式。簡(jiǎn)要概括：1、去->,<-> 2、移」4、量詞轄域擴(kuò)充3、換元4、量詞轄域擴(kuò)充12、謂詞演算的推理理論推理規(guī)則：P、T、CP、US、ES、EG、UG的使用ESUS去量詞EGUG添量詞★謹(jǐn)記：ES要在US之前，很重要(2)用ES指定的客體C不應(yīng)該是在此之前用US規(guī)則或者用ES規(guī)則所指定的客體c(即本次用ES特指客體c,不應(yīng)該是以前特指的客體)。添加量詞注意事項(xiàng)：4.添加量詞時(shí)，也要加在公式的最左邊即新加的量詞前也無(wú)任何符號(hào)??！)且其轄域作用到公式的末尾. ，(3) L⑷P3)fQ(b)VxP(x)fQ(b)UG(1)X(6)VxP(x)-*3yQ(y)EG⑵X正確作法：⑷P(a)-Q(b)⑸Vx(P(x)-Q(b))UG(1)3yVx(P(x)-Q(y))EG(2) J13、集合的冪集(用P表示，也常有花P表示)A是集合，由A的所有子集構(gòu)成的集合，稱(chēng)之為A的冪集。記作P(A)或2的A次方給定有限集合A，如果|A|=n,貝?|P(A)|=2的n次方14、求集合的劃分?jǐn)?shù)與等價(jià)關(guān)系數(shù)——相同第130頁(yè)⑴*X是集合*且|X|=4,X有多少個(gè)不同的劃分?解.劃分塊數(shù)各塊元素個(gè)數(shù)相應(yīng)劃分個(gè)數(shù)總數(shù)14C44=115213CJ=4221/2C43=33112CJ=641111C/=l15、三種重要集合運(yùn)算

二、絕對(duì)補(bǔ)集~三、對(duì)稱(chēng)差二、絕對(duì)補(bǔ)集~三、對(duì)稱(chēng)差A(yù)十B前三章重點(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的元素為第二元素組成序偶的集合，稱(chēng)為A和B的笛卡爾積，記作AXB如果A、B都是有限集，且|A|=m,|B|=n,則|AXB|=mn.2、域的表示：定義域dom定義域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ù)思考題：如果|A|=m, 則可以定義多少個(gè)從A到B的不同的關(guān)系？答案：有2m口個(gè)口因?yàn)閨AxB|=mn,|P（AxB）|=2m%即AxB有2mli個(gè)子集。

5、對(duì)稱(chēng)、反對(duì)稱(chēng)、自反、反自反、傳遞的判定性質(zhì)判定：從關(guān)系的有向圖從關(guān)系的矩陣自反性每個(gè)結(jié)點(diǎn)都有環(huán)主對(duì)角線全是1反自反性每個(gè)結(jié)點(diǎn)都無(wú)環(huán)主對(duì)角線全是0對(duì)稱(chēng)性不同結(jié)點(diǎn)間如果有邊有方向相反的兩條邊.是以對(duì)角線為對(duì)稱(chēng)的矩陣反對(duì)稱(chēng)性不同結(jié)點(diǎn)間、最多有一條邊.以主對(duì)角線為對(duì)稱(chēng)的位置不會(huì)同時(shí)為1傳遞性如果有邊<a,b>,<b,c>,則也有邊<a,c>.或者定義的前件為假.如果洵=1,且、則%=16、等價(jià)關(guān)系、等價(jià)類(lèi)定義：設(shè)R是A上關(guān)系，若R是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)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ì)稱(chēng)。圖的簡(jiǎn)化：⑴不畫(huà)環(huán);⑵兩條對(duì)稱(chēng)邊用一條無(wú)向直線代替相容類(lèi)：設(shè)r是集合X上的相容關(guān)系，CX,如果對(duì)于C中任意兩個(gè)元素x,y有＜x,y＞er,稱(chēng)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é)。找最大完全多邊形l=J1找最大完全多邊形l=J1大完全多邊形：含有通過(guò)最大相容類(lèi)求完全覆蓋完全覆蓋就是指所有最大相容類(lèi)構(gòu)成的集合。8、關(guān)系的分類(lèi)：偏序關(guān)系定義：R是A上自反、反對(duì)稱(chēng)和傳遞的關(guān)系，則稱(chēng)R是A上的偏序關(guān)系。并稱(chēng)＜A,R＞是偏序集。全序關(guān)系定義：＜A,令是偏序集，任何勺￡人，如果x與y都是可比較的，則稱(chēng)W是全序關(guān)系（線序、鏈）。9、偏序集Hasse圖的畫(huà)法.用“。”表示A中元素。.如果x^y,KxWy,則結(jié)點(diǎn)y要畫(huà)在結(jié)點(diǎn)x的上方。.如果、&,且y蓋住x,x與y之間連一直線。.一般先從最下層結(jié)點(diǎn)（全是射出的邊與之相連（不考慮環(huán)）），逐層向上畫(huà)，直到最上層結(jié)點(diǎn)（全是射入的邊與之相連）。（采用抓兩頭，帶中間的方法）10、重要元素定義（極大小元、最大小元、上下界、最大下界與最小上界）11、如何求映射是入（單）、滿、雙射？第一步：分別求出定義域和值域第二步：比較就出來(lái)了，就那么簡(jiǎn)單但是要證明的話：L證明f:XfY是滿射的：任取y￡Y,推出存在x￡X,使得產(chǎn)f（二）?2.證明f:Xf￥是入射的：方法1:任取x36X,設(shè)工法以推出心1*10）。方法Z：任取Xi*jeX^f（Xi）=f（xO推出x1=x2o兩者結(jié)合得：雙射成立12、復(fù)合函數(shù)中的重要性質(zhì)（常考）：f:X—Y,g:Y—Z是兩個(gè)函數(shù)，貝。⑴如果f和g是滿射的，貝4g。f也是滿射的；⑵如果f和g是入射的，貝4g。f也是入射的；⑶如果f和g是雙射的，則gof也是雙射的⑴如果g。f是滿射的，則g是滿射的；⑵如果gof是入射的，貝If是入射的；⑶如果gof是雙射的，則f是入射的和g是滿射的13、函數(shù)種類(lèi)個(gè)數(shù)的求法如果X和Y是有限集合，|X|二mJY|=n,因?yàn)閄中的每個(gè)元素對(duì)應(yīng)的函數(shù)值都有n種選擇，于是可構(gòu)成1個(gè)不同的函數(shù)，因此|YX|=|Y||X|=n/可見(jiàn)符號(hào)丫乂有雙重含義.14、逆函數(shù)（性質(zhì)）設(shè)f:XfY是雙射的函數(shù)，fC:YX也是函數(shù)，稱(chēng)之為f的逆函數(shù)。設(shè)f:X-Y是雙射的函數(shù)，則有fLf=Ix且1=IY°15、第六章基礎(chǔ)知識(shí)重點(diǎn)冪等元、幺元e、零元0、逆元的概念同態(tài)同構(gòu)：f(x)滿射、并且滿足f(X]—2)=f(Xl)of&) 此式叫同態(tài)(同構(gòu))關(guān)系式*不是雙射就一定復(fù)合同構(gòu)的條件:必須具有幺元對(duì)幺元、零元對(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,W＞是偏序集，如果任何a,b￡A,使得｛a,b｝都有]大下界和最小上界，則稱(chēng)＜A,W＞是格平凡格：所有全序都是格，稱(chēng)之為平凡格。分配格：(判定定理)3.分配格的判定：見(jiàn)書(shū)P245一個(gè)格是分配格的充分且必要條件是在該格庵司任何子格與上述兩個(gè)五元素非分配格之一同構(gòu)，t所有鏈均為分配格。設(shè)＜A,W＞是分配格，對(duì)任何a,b,ceA,如果有aAb=aAc及aVb=aVc則必有b=c.有界格：（判定定理）有界格定義：如果一個(gè)格存在全上界1與全下界0,則稱(chēng)此格為有界格。從格的圖形看：全上界1，就是圖的最上邊元素（只一個(gè)）。全下界0，就是圖的最下邊元素（只一個(gè)）。有補(bǔ)格：（判定定理：根據(jù)定義看是不是每個(gè)中間元素都有補(bǔ)元）補(bǔ)元：設(shè)＜A,W＞是個(gè)有界格，aeA,如果存在beA,使得aVb=1 aAb=0則稱(chēng)a與b互為補(bǔ)元（其中V是求最小上界，A求最大下界）有補(bǔ)格的定義：一個(gè)有界格中，如果每個(gè)元素都有補(bǔ)元，則稱(chēng)之為有補(bǔ)格布爾格： 如果一個(gè)格既是分配格又是有補(bǔ)格，則稱(chēng)之為布爾格。*重要定理：在有界分配格中，如果元素有補(bǔ)元，則補(bǔ)元是唯一的。17、格的同構(gòu)條件(特別)需同時(shí)滿足：f(aV1b)=f(a)V2f(b)Ra/\ib)=f(a)八2f(b)鉆石定律：一個(gè)布爾代數(shù)的所有原子(直接覆蓋最小元0的元素)構(gòu)成的布爾代數(shù)一定與元代數(shù)同構(gòu)18、布爾代數(shù)表達(dá)式和布爾函數(shù)<b,V,A,">是布爾代數(shù)的形式含有變?cè)獂1,x2，…,xn的布爾表達(dá)式記作E(x1,x2，…xn),也可以看成是一個(gè)函數(shù)f:Bn，B,稱(chēng)之為布爾函數(shù)布爾表達(dá)式的范式的寫(xiě)法(很重要，與第一第二章的方法類(lèi)似)19、第八章圖論的重要知識(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á),則稱(chēng)G是強(qiáng)連通.如果任何一對(duì)結(jié)點(diǎn)間,至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)，則稱(chēng)G是單側(cè)連通.如果將G看成無(wú)向圖后（即把有向邊看成無(wú)向邊）是連通的，則稱(chēng)G是弱連通強(qiáng)分圖、單側(cè)分圖和弱分圖在簡(jiǎn)單有向圖中,具有強(qiáng)連通的最大子圖,稱(chēng)為強(qiáng)分圖.具有單側(cè)連通的最大子圖,稱(chēng)為單側(cè)分圖.具有弱連通的最大子圖,稱(chēng)為弱分圖.圖的矩陣表示和寫(xiě)法（前兩個(gè)有點(diǎn)重要）：一、鄰接矩陣每一行的1：在無(wú)向圖中代表一條線有向圖中代表—＞出線列中的1代表＜—入線二、可達(dá)性矩陣三、完全關(guān)系矩陣圖中結(jié)點(diǎn)的度與個(gè)數(shù)、邊的關(guān)系：考試需要兩則結(jié)合4.定理8-1」每個(gè)無(wú)向圖所有結(jié)點(diǎn)度總和等于邊數(shù)的2倍.即，褪黑⑺=2|E|定理8-L2（握手定理）每個(gè)無(wú)向圖中，奇數(shù)度的結(jié)點(diǎn)必為偶數(shù)個(gè).（在一次集會(huì)中,與奇數(shù)個(gè)人握手的人，共有偶數(shù)個(gè).）20、歐拉圖與H（漢密爾）圖（重點(diǎn)定義：在無(wú)孤立結(jié)點(diǎn)的圖G中，若存在一條回路，它經(jīng)過(guò)圖中每條邊一次且僅一次,稱(chēng)此回路為歐拉回路.稱(chēng)此圖為歐拉圖漢密爾頓回路（H回路）:通過(guò)G中每個(gè)結(jié)點(diǎn)恰好一次的回路.具有漢密爾頓回路（H回路）的圖.歐拉回路的判定：（充要條件無(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回路歐拉回路的算法（重重重！雖然可能不考）（記做閉跡交集法5《有E打印E以某公共點(diǎn)為起、末點(diǎn)，對(duì)%中的邊重新排序得新的閉跡C4《有E打印E以某公共點(diǎn)為起、末點(diǎn)，對(duì)%中的邊重新排序得新的閉跡C4.求歐拉回路的算法:在GE】中找一個(gè)閉跡電使嗚與E±至少有一個(gè)公共點(diǎn)以v為起點(diǎn)找閉跡場(chǎng)選結(jié)點(diǎn)vH回路的算法（重重重！雖然可能不考）（記做相鄰最小權(quán)法）3?用"最鄰近法”求H回路如果已經(jīng)確定圖G有H回路.a）.任選初始結(jié)點(diǎn)叫找一個(gè)最鄰近的（邊的權(quán)最?。┙Y(jié)點(diǎn)工b）?設(shè)x是新加入到這條路的結(jié)點(diǎn),再?gòu)牟辉诖寺飞系慕Y(jié)點(diǎn)中找到一個(gè)與x鄰近的（邊的權(quán)最?。┙Y(jié)點(diǎn),加到此路中.3.重復(fù)b）,直到G中所有結(jié)點(diǎn)都在此路上.d）.最后再回到起點(diǎn).構(gòu)成回路.就是H回路.21、樹(shù)中的重要方法：樹(shù)的結(jié)點(diǎn)與邊數(shù)：邊數(shù)=結(jié)點(diǎn)數(shù)-1e=v-1m叉有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的方法：七.m叉有序樹(shù)轉(zhuǎn)化成二叉樹(shù)因?yàn)槎鏄?shù)便于存貯,也便于處理,所以通?？梢詫⒍嗖鏄?shù)化成二叉樹(shù)『方法是：L每個(gè)結(jié)點(diǎn)保留左兒子結(jié)點(diǎn)，剪掉右邊其分支，被剪掉的結(jié)點(diǎn)如下處理（重新嫁接人2.同一個(gè)層次的結(jié)點(diǎn),從左到右依次畫(huà)出（被剪掉的結(jié)點(diǎn)嫁接到它的哥哥結(jié)點(diǎn)上）。賦權(quán)圖的最小生成樹(shù)的求法（記做相鄰最小權(quán)不回路法）：定義:一棵生成樹(shù)中的所有邊的權(quán)之和稱(chēng)為該生成樹(shù)的權(quán).具有最小權(quán)的生成樹(shù),稱(chēng)為最小生成樹(shù).Kruskid算法:設(shè)G是有n個(gè)結(jié)點(diǎn)條邊的連通圖.S=SU㈤

曰+1S=(D1=0j=l將所有邊按照權(quán)升序排序:i=i+l邊按升序排序:邊的，叩記成,邊e28e38比7?24%e57e“權(quán)112223334邊e7s?e35?，7e5&e1之e18權(quán)44566778丫1<\7、H3.|S|二D-1,說(shuō)明是樹(shù)最后％”最優(yōu)樹(shù)求法：定義九.最優(yōu)樹(shù)(哈夫里樹(shù)Hdffhlan)二又樹(shù)的一個(gè)重要應(yīng)用就是最優(yōu)樹(shù).L帶權(quán)二叉樹(shù)的定義:設(shè)有一組權(quán)值二噌I，w2,行不…，科抽，不仿設(shè)孫乃亞盧/三..,<wm,設(shè)有一棵一叉樹(shù)有m片葉子，分別帶有權(quán)值陰，叫,飛，…戶'滿此樹(shù)為帶權(quán)二叉樹(shù).例如:下邊是有葉結(jié)點(diǎn)露卜丹血分別帶有權(quán)7足,3的二叉樹(shù):丸帶權(quán)樹(shù)T的權(quán)WEh mW(T)=其中L(%)是標(biāo)有權(quán)為的葉結(jié)點(diǎn)的從根到該葉結(jié)點(diǎn)的路長(zhǎng).上例中：W(T1)=7X2+5X2+2X2+3X2=34W(T2)=3X2+7X3+5X3+2X1=44琳(4)=7X14-5X2+2X3+3X3=32由此看出W{T。是比較小的.Z G /.最優(yōu)樹(shù)：帶權(quán)樹(shù)中，權(quán)數(shù)最少的二叉樹(shù)?.畫(huà)最優(yōu)樹(shù)的算法一哈夫曼算法二(1冼將權(quán)按照升序排序，設(shè)為Wl3v/Y…分片⑵以叫和小為兒子結(jié)點(diǎn),構(gòu)造它們的父結(jié)點(diǎn)，且其權(quán)為M]+啊，并從權(quán)的序列中去掉W1和⑶叫+叫再與其余權(quán)一起排序.再?gòu)拇岁?duì)列中取出前面兩個(gè)權(quán)值為兒子結(jié)點(diǎn)，同⑵的方法構(gòu)造它們的父結(jié)點(diǎn).依此類(lèi)推，直至最后.即得到最優(yōu)樹(shù).例如，給定一組權(quán)23,5,7,11,1317,以23.構(gòu)造一棵最優(yōu)樹(shù).42.5824,34,4219,23,24,3417,17,1義工42.5824,34,4219,23,24,3417,17,1義工32411,13,17,17,19,237.10414347JM35,5,7/1,13,17/9,232*,7,11,13,17,19,23***后五章重點(diǎn)內(nèi)容（考題重點(diǎn)）：＜精華看完絕對(duì)不虧＞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à)法.用“?！北硎続中元素。.如果x^y,KxWy,則結(jié)點(diǎn)y要畫(huà)在結(jié)點(diǎn)x的上方。.如果、&,且y蓋住x,x與y之間連一直線。.一般先從最下層結(jié)點(diǎn)（全是射出的邊與之相連（不考慮環(huán)）），逐層向上畫(huà)，直到最上層結(jié)點(diǎn)（全是射入的邊與之相連）。（采用抓兩頭，帶中間的方法）判斷——格：看是否任意都有最小上界、最大下界；分配格：跟那倆個(gè)特別的格比較，沒(méi)有那樣的子格就是分配格；鏈一定是分配格有界格：有無(wú)最大最小元（1,0表示），有限個(gè)元素的格一定是有界格；有補(bǔ)格：看是否每個(gè)元素都有補(bǔ)元若有補(bǔ)元，補(bǔ)元唯一的是有界分配格!布爾格：分配、有補(bǔ)5、復(fù)合函數(shù)的性質(zhì)f:X—Y,g:Y』Z是兩個(gè)函數(shù)，則⑴如果f和g是滿射的，貝4g。f也是滿射的；⑵如果f和g是入射的，貝4g。f也是入射的；⑶如果f和g是雙射的，則gof也是雙射的⑴如果g。f是滿射的，則g是滿射的；⑵如果gof是入射的，貝If是入射的；⑶如果gof是雙射的，則f是入射的和g是滿射的6、完全圖的邊數(shù)無(wú)向完全圖：邊數(shù)為n(n-1)/2有向完全圖：邊數(shù)為2的n次方7、歐拉圖、H圖完全圖Kn,n為奇數(shù)時(shí)，完全圖既是歐拉圖又是H圖;8、證明子格證明從封閉性入手，若對(duì)V,A(取最小下界、最大上界運(yùn)算)運(yùn)算封閉貝為子格。9、證明子群第一步:證明非空集合；第二步:在集合中任取兩個(gè)進(jìn)行自定義的運(yùn)算，證明封閉性；第三步：任意取一個(gè)集合中的數(shù)a,證a逆屬于集合即證明可逆性。證明三點(diǎn)：自反、對(duì)稱(chēng)、傳遞11、證明同態(tài)、同構(gòu)（或者自同構(gòu)）第一步：證明￡僅）雙射，①先證入射（單射），②再證滿射，則為雙射第二步：證類(lèi)似如下式子成立4工］★巧尸 此式叫同態(tài)（同構(gòu)）關(guān)系式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ù)。定理1設(shè)G=＜KE＞為任意無(wú)向圖，丫=｛。,\…4｝,園=桁，則 廣￡d（4）=2m1hI證G中每條邊（包括環(huán)）均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m條邊共提供2旭度.定理2即==匕￡＞為任意有向圖，V=｛匕必\E\=m7貝U樣 M NZ4（與）=2%且工〃+（為）=工*（4）=rn1=1 r=l i=i13、布爾表達(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、A(G),k(G),”G),入(G),W(G),x(G)分別表示圖G的（最大度），（點(diǎn)連通度），（最小度），（邊連通度）（連通分支數(shù)）,（最小著色數(shù)）K（G）表示點(diǎn)連通度入（G）表示邊連通度d（u,v）表示最短兩點(diǎn)距離deg（v）表示度示最短兩點(diǎn)距離deg（v）表示度degi表示入度dego表示出度半群—