離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)

離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)第一章命題邏輯一、典型考查點(diǎn)1、命題的判斷方法：陳述句真值唯一，特殊：反問(wèn)句也是命題。其它疑問(wèn)句、祈使句、感嘆句、悖論等皆不是。詳見(jiàn)教材P12、聯(lián)結(jié)詞運(yùn)算定律┐∧∨→記住特殊的：1∧11，0∨00，1→00，111，001詳見(jiàn)P53、命題符號(hào)化步驟：A劃分原子命題，找準(zhǔn)聯(lián)結(jié)詞。特殊自然語(yǔ)言：不但而且，雖然但是用∧，只有P才Q，應(yīng)為Q→P；除非P否則Q，應(yīng)為┐P→Q。B設(shè)出原子命題寫出符號(hào)化公式。詳見(jiàn)P54、公式的分類判定（重言式、矛盾式、可滿足式）方法：其一根據(jù)所有真值賦值情況，其二根據(jù)等價(jià)演算來(lái)判斷。詳見(jiàn)P95、真值表的構(gòu)造步驟：①命題變?cè)醋值湫蚺帕?，共?n個(gè)真值賦值。②對(duì)每個(gè)指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。③若公式較復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里層向外層展開(kāi))，最后列出所求公式的真值。詳見(jiàn)P8。6、基本概念：置換規(guī)則，P規(guī)則，T規(guī)則，詳見(jiàn)P24；合取范式，析取范式，詳見(jiàn)P15；小項(xiàng)詳見(jiàn)P16；大項(xiàng)詳見(jiàn)P18，最小聯(lián)結(jié)詞組詳見(jiàn)P157、等價(jià)式詳見(jiàn)P22表證明方法：①真值表完全相同②用等價(jià)演算③利用AB的充要條件是AB且BA。主要等價(jià)式：(1)雙否定：AA。(2)交換律：A∧BB∧A，A∨BB∨A，ABBA。3)結(jié)合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等冪律：A∧AA，A∨AA。(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互補(bǔ)律：A∧AF，(矛盾律)，A∨AT。(排中律)(11)條件式轉(zhuǎn)化律：A→BA∨B，A→BB→A。(12)雙條件式轉(zhuǎn)化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)8、蘊(yùn)含式詳見(jiàn)P23表證明方法：①前件真導(dǎo)后件真方法②后件假導(dǎo)前件假方法③真值表中，前件為真的行，后件也為真或者后件為假的行，前件也為假。④用定義，證AB，即證A→B是永真式。9、范式求法步驟：①使用命題定律，消去公式中除、和以外公式中出現(xiàn)的所有聯(lián)結(jié)詞；②使用(P)P和德·摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞都移到命題變?cè)?；③利用結(jié)合律、分配律等將公式化成析取范式或合取范式。10、主范式的求法重點(diǎn)步驟：(a)把給定公式化成析?。ê先。┓妒剑?b)刪除析取范式中所有為永假的簡(jiǎn)單合?。ㄎ鋈。┦?；(c)用等冪律化簡(jiǎn)簡(jiǎn)單合?。ㄎ鋈。┦街型幻}變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如P∧PP。(d)用同一律補(bǔ)進(jìn)簡(jiǎn)單合取（析?。┦街形闯霈F(xiàn)的所有命題變?cè)鏠，則PP∧（Q∨Q)或PP∨（Q∧Q)，并用分配律展開(kāi)之，將相同的簡(jiǎn)單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析?。ê先。┓妒健Ｗ⒁猓褐魑鋈》妒脚c主合取范式之間的聯(lián)系。例如：(PQ)Qm1m11、推理證明：重點(diǎn)方法：演算、演繹法（常用的格式）、反證法、CP規(guī)則即附加前提等。重點(diǎn)規(guī)則（主要蘊(yùn)含式）：(1)P∧QP化簡(jiǎn)(2)P∧QQ化簡(jiǎn)(3)PP∨Q附加(4)PP→Q變形附加(5)QP→Q變形附加(6)(P→Q)P變形化簡(jiǎn)(7)(P→Q)Q變形化簡(jiǎn)(8)P，(P→Q)Q假言推理(9)Q，(P→Q)P拒取式(10)P，(P∨Q)Q析取三段論(11)(P→Q)，(Q→R)P→R條件三段論(12)(PQ)，(QR)PR雙條件三段論文字證明推理三步：一命題符號(hào)化，二寫出前提和結(jié)論，三進(jìn)行證明。詳見(jiàn)P21二、強(qiáng)化練習(xí)1.命題的是()A.走，看電影去+y>0C2.下列式子為重言式的是()→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐(PQ) D.(P∨Q)(P→Q)3．下列為兩個(gè)命題變?cè)狿，Q的小項(xiàng)是（）A．P∧Q∧PB．P∨QC．P∧Q D．P∨P∨Q4．下列語(yǔ)句中是真命題的是（）A．我正在說(shuō)謊B．嚴(yán)禁吸煙C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的5．設(shè)P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為（）A．P∧QB．P∨QC．（PQ） D．（P∨Q）6．命題公式（P∧（P→Q））→Q是（）A．矛盾式B．蘊(yùn)含式C．重言式 D．等價(jià)式7．命題公式（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111C8．設(shè)P：他聰明，Q：他用功，命題“他雖聰明但不用功”的符號(hào)化正確的是（）A．P∧Q B．P∧QC．P→Q D．P∨Q9．下面聯(lián)結(jié)詞運(yùn)算不可交換的是（）A．∧ B．→C．∨ D．10下列命題公式不是重言式的是（）A．Q→（P∨Q） B．（P∧Q）→PC．（P∧Q）∧（P∨Q）D．（P→Q）（P∨Q）11.設(shè)命題變?cè)獮镻，Q，R，則小項(xiàng)m100=________，大項(xiàng)M010=________。12.置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以________，記為_(kāi)_______規(guī)則。13.請(qǐng)用聯(lián)結(jié)詞┐，∧表示聯(lián)結(jié)詞∨和聯(lián)結(jié)詞：________，________。14．兩個(gè)重言式的析取是________式，一個(gè)重言式與一個(gè)矛盾式的析取是________式。15．命題公式（PQ）→P的成真指派為_(kāi)_________，成假指派為_(kāi)_________。16.用等值演算求(P→Q)→R的主合取范式。17.列出(P→(Q∨R))(P→Q)的真值表。19．構(gòu)造命題公式（（P∧Q）→P）∨R的真值表。20．求下列公式的主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））21．構(gòu)造命題公式（）→PR的真值表。22．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。23.用推理方法證明：P∨Q，P→R，Q→S├R∨S。24．構(gòu)造下面推理的證明。如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。25．構(gòu)造下面推理的證明。只要A曾到過(guò)受害者房間并且11點(diǎn)以前沒(méi)離開(kāi)，A就犯了謀殺罪。A曾到過(guò)受害者房間。如果在11點(diǎn)以前離開(kāi)，看門人會(huì)看見(jiàn)他?？撮T人沒(méi)有看見(jiàn)他。所以A犯了謀殺罪。離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)第二章謂詞邏輯一、典型考查點(diǎn)1、基本概念：個(gè)體詞、個(gè)體域、謂詞、特性謂詞、轄域，詳見(jiàn)P27；前束范式詳見(jiàn)P362、謂詞符號(hào)化步驟：①正確理解給定命題。必要時(shí)把命題改敘，使其中每個(gè)原子命題、原子命題之間的關(guān)系能明顯表達(dá)出來(lái)。②把每個(gè)原子命題分解成個(gè)體、謂詞和量詞；在全總論域討論時(shí)，要給出特性謂詞。③找出恰當(dāng)量詞。應(yīng)注意全稱量詞(x)后跟條件式，存在量詞(x)后跟合取式。④用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來(lái)。詳見(jiàn)P303、謂詞公式類型的判定（永真式、永假式、可滿足式）方法：利用論域翻譯成自然語(yǔ)言后進(jìn)行判斷。詳見(jiàn)P344、自由變?cè)c約束變?cè)呐卸ǚ椒ǎ喊炊x，關(guān)鍵是要看它在A中是約束出現(xiàn)，還是自由出現(xiàn)，若與量詞的指導(dǎo)變?cè)嗤?，就是約束出現(xiàn)，不同就是自由出現(xiàn)。詳見(jiàn)P31。5、等價(jià)式(1)量詞否定等價(jià)式：(a)(x)A(x)A(b)(x)A(x)A(2)量詞轄域縮小或擴(kuò)大等價(jià)式(a)(x)(A(x)∧B)(x)A(x)∧B(b)(x)(A(x)∨B)(x)A(x)∨B(c)(x)(A(x)→B)(x)A(x)→B(d)(x)(B→A(x))B→(x)A(x)(e)(x)(A(x)∧B)(x)A(x)∧B(f)(x)(A(x)∨B)(x)A(x)∨B(g)(x)(A(x)→B)(x)A(x)→B(h)(x)(B→A(x))B→(x)A(x)。(3)量詞分配律等價(jià)式：(a)(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(b)(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)其中，A(x)，B(x)為有x自由出現(xiàn)的任何公式。詳見(jiàn)P34356、蘊(yùn)含式(a)(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))(b)(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(c)(x)(A(x)→B(x))(x)A(x)→(x)B(x)(d)(x)(A(x)→B(x))(x)A(x)→(x)B(x)其中，A(x)和B(x)為含有x自由出現(xiàn)的任意公式。詳見(jiàn)P356、前束范式方法：①把量詞全部通過(guò)等值演算化到整個(gè)謂詞公式的前面②把量詞前面的┐全部通過(guò)德摩根定律化到謂詞公式的內(nèi)部。詳見(jiàn)P367、推理：方法：演繹（常用格式）、反證法、CP規(guī)則即附加前提等。對(duì)于命題邏輯中的所有規(guī)則都可用。特殊規(guī)則：(1)量詞消去(簡(jiǎn)稱UI或US規(guī)則)(x)A(x)A(c)(x)A(x)A(y)(x)A(x)A(c)量詞產(chǎn)生規(guī)則(簡(jiǎn)稱EG或UG規(guī)則)A(c)(y)A(y)A(x)(y)A(y)詳見(jiàn)P38二、強(qiáng)化練習(xí)1.下列式子不是謂詞合式公式的是()A.(x)(P(x)→(x)(Q(x)∧A(x，y))) B.(x)∧(y)∨P(x，y)C.(x)P(x)→R(y) D.(x)P(x)∧Q(y，z)2.設(shè)個(gè)體域?yàn)閷?shí)數(shù)集，特定元素a=0，函數(shù)f(x，y)=x-y，特定謂詞F(x，y)為x<y，下列公式真值為真的是()A.(x)(y)F(x，f(f(x，y)，y))B.(x)(y)(┐F(f(x，y)，x))C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z)))D.(x)F(f(a，x)，a)3.對(duì)于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列說(shuō)法正確的是()是自由變?cè)?是約束變?cè)狢.(x)的轄域是P(x，y)∨Q(x，z) D.(x)的轄域是P(x，y)4.設(shè)論域?yàn)閧1，2}，與公式(x)┐A(X)等價(jià)的是()A.┐A(1)∨┐A(2) B.┐A(1)→┐(A2)C.┐A(1)∧┐A(2) D.A(1)→A(2)5．在公式（）F（x，y）→（y）G（x，y）中變?cè)獂是（）A．自由變?cè)?B．約束變?cè)狢．既是自由變?cè)质羌s束變?cè)?D．既不是自由變?cè)?，又不是約束變?cè)?．下列等價(jià)式不正確的是（）A． B．C． D．7．設(shè)A（x）:x是人，B（x）：x犯錯(cuò)誤，命題“沒(méi)有不犯錯(cuò)誤的人”符號(hào)化為（）A． B．B（x））C．D．B(x))二、填空題8.一個(gè)公式，如果量詞均在全式的________，其作用域延伸到整個(gè)公式的________，則該公式稱為前束范式。9．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的轄域?yàn)開(kāi)_______，x的轄域?yàn)開(kāi)_______。10．公式（）（F（x）→G(y)）→()(H(x))中的自由變?cè)獮開(kāi)________，約束變?cè)獮開(kāi)_________。三、綜合應(yīng)用題11．符號(hào)化下面命題，并構(gòu)造推理證明：人是要死的，蘇格拉底是人，所以蘇格拉底是要死的。離散數(shù)學(xué)復(fù)習(xí)第三章集合與函數(shù)一、典型考查點(diǎn)1、基本概念判斷：函數(shù)的入射、滿射、雙射及定理、復(fù)合運(yùn)算，詳見(jiàn)P72，73，75。冪集、差集、對(duì)稱差、笛卡爾積，詳見(jiàn)P46，47，43，49。全序關(guān)系，詳見(jiàn)P68.。方法：理解概念即可，按定義的步驟計(jì)算。2、關(guān)系的相關(guān)概念判斷：①特殊關(guān)系：若R=，為空關(guān)系；若R=AB，為全域關(guān)系。R={<x,x>|xA}為A上的恒等關(guān)系，記為IA。方法：根據(jù)定義判斷。②定義域:D(R)={x|(y)(xRy)}值域:R(R)={y|(x)(xRy)}域:F(R)=D(R)+R(R),方法：定義域就是關(guān)系R中第一位元素的集合，值域就是R中第二位元素的集合，域就是定義域并上值域。③表示方法：集合列舉法\關(guān)系矩陣\關(guān)系圖方法：根據(jù)題目條件，用列舉法寫出關(guān)系R，畫出關(guān)系圖（有向圖）或?qū)懗鲫P(guān)系矩陣。詳見(jiàn)P50,51,52.3、關(guān)系的性質(zhì)判斷：判斷方法如下：詳見(jiàn)P54R是A上關(guān)系自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義xxAxRxxA<x,x>RxRy→yRxxRy→<y,x>R除x=yxRyyRz→xRz矩陣特征主對(duì)角線全為1主對(duì)角線全為0沿對(duì)角線對(duì)稱沿主對(duì)角線不對(duì)稱圖特征每個(gè)頂點(diǎn)都有環(huán)每頂點(diǎn)都沒(méi)有環(huán)有邊則雙向邊若有邊，則是單向邊集合特征IARIAR=R-1=RIARIA4、關(guān)系的運(yùn)算：①關(guān)系的集合運(yùn)算，按集合的運(yùn)算規(guī)律即可：交、并、補(bǔ)、差、對(duì)稱差等。②復(fù)合運(yùn)算：按順序運(yùn)算，逆運(yùn)算，交換每個(gè)元的第一、二位元素的位置即<x,y>變<y,x>。③閉包運(yùn)算：即先判斷R本身是否具有自反（對(duì)稱、傳遞），若有，則自反（對(duì)稱、傳遞）閉包就是R本身，即r(R)=R(或s(R)=R,t(R)=R),若沒(méi)有，則增加R的元素，加到恰好滿足自反性為止，既不能多，也不少。詳見(jiàn)P555、等價(jià)關(guān)系和劃分的判斷及證明：①等價(jià)關(guān)系的證明：自反、對(duì)稱、傳遞三個(gè)性質(zhì)逐一驗(yàn)證。要注意給出的等價(jià)關(guān)系的條件的變通。②等價(jià)關(guān)系與劃分一一對(duì)應(yīng)，等價(jià)關(guān)系的等價(jià)類即為確定的劃分的分塊，即有關(guān)系的，劃在同一塊。劃分中凡在同一個(gè)分塊中的元，都寫成滿足關(guān)系的元，這樣寫出的關(guān)系R就是一個(gè)等價(jià)關(guān)系。6、相容關(guān)系和覆蓋的判斷：相容關(guān)系兩個(gè)性質(zhì)：自反和對(duì)稱，注意：相容關(guān)系圖的畫法省略了自反和對(duì)稱。覆蓋按定義判斷即可。詳見(jiàn)P617、偏序關(guān)系與哈斯圖：①基本概念：三個(gè)性質(zhì)：自反、反對(duì)稱和傳遞；可比，就是有關(guān)系，a≤bb≤a；蓋住，就是直接關(guān)系，中間沒(méi)有第三個(gè)元，即若a<b且不存在cA，使得a<c<b。②偏序關(guān)系與哈斯圖：畫圖注意四點(diǎn)：使用蓋住的聯(lián)系來(lái)表示，省略全部向上的箭頭，省略自反性的自環(huán)，省略了傳遞性。反之，由哈斯圖寫偏序關(guān)系也要注意這四點(diǎn)，除了直接的蓋住關(guān)系外，還有自反和傳遞也要寫出來(lái)。8、求偏序關(guān)系的特殊元：設(shè)<A,≤>為偏序集，BA，bB，①若(x)(xBb≤x)為真，則稱b為B的最小元。②若(x)(xBx≤b)為真，則稱b為B的最大元。③若(x)(bxx≤b)為真，則稱b為B的極小元。④若(x)(bxb≤x)為真，則稱b為B的極大元。根據(jù)定義判斷時(shí)，最?。ù螅┰c極?。ù螅┰怯袇^(qū)別的，最?。ù螅┰荁中最小（大）的元素，它與B中其他元素都可比；而極?。ù螅┰灰欢ㄅcB中元素都可比，只要沒(méi)有比它?。ù螅┑脑兀褪菢O?。ù螅┰?duì)于有窮集B，極?。ù螅┰欢ù嬖冢铱赡苡卸鄠€(gè)，但最?。ù螅┰灰欢ù嬖?，若存在則必唯一。若B中只有一個(gè)極?。ù螅┰瑒t它一定是B的最?。ù螅┰?。詳見(jiàn)P689、求上界下界上確界和下確界：設(shè)<A,≤>為偏序集，BA，bA，①若(x)(xBb≤x)為真，則稱b為B的下界。②若(x)(xBx≤b)為真，則稱b為B的上界。③若b是一下界且對(duì)每一個(gè)B的下界b’有b’≤b，則稱b為B的最大下界或下確界，記為glb。④若b是一上界且對(duì)每一個(gè)B的上界b’有b≤b’，則稱b為B的最小上界或上確界，記為lub。判斷時(shí)注意，上界下界上確界和下確界是A集合上來(lái)找的，B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。詳見(jiàn)P69二、強(qiáng)化練習(xí)1.設(shè)Z+是正整數(shù)集，f：Z+×Z+→Z+，f(n，m)=nm，則f()A.僅是入射B.僅是滿射C.是雙射D.不是函數(shù)]2.關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有自反性()A..D.3.設(shè)R1和R2是集合A上的相容關(guān)系，不是相容關(guān)系()4．集合A={1，2，…，10}上的關(guān)系R={<x，y>|x+y=10，x∈A，y∈A}，則R的性質(zhì)是（）A．自反的B．對(duì)稱的C．傳遞的、對(duì)稱的 D．反自反的、傳遞的5．若R和S是集合A上的兩個(gè)關(guān)系，則下述結(jié)論正確的是（）A．若R和S是自反的，則R∩S是自反的B．若R和S是對(duì)稱的，則RS是對(duì)稱的C．若R和S是反對(duì)稱的，則RS是反對(duì)稱的D．若R和S是傳遞的，則R∪S是傳遞的6．R={<1，4>，<2，3>，<3，1>，<4，3>}，則下列不是t（R）中元素的是（）A．<1，1>B．<1，2>C．<1，3>D．<1，4>7．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列選項(xiàng)正確的是（）A．1∈AB．{1，2，3}AC．{{4，5}}A D．∈A8．設(shè)M={x|f1(x)=0},N={x|f2(x)=0}，則方程f1(x)·f2(x)=0的解為（）A．M∩N B．M∪NC．MN D．M-N9．設(shè)A-B=，則有（）A．B= B．B≠C．AB D．AB10．A，B是集合，P（A），P（B）為其冪集，且A∩B=，則P(A)∩P(B)為（）A． B．{}C．{{}} D．{，{}}11．設(shè)A={1，2，3，4，5}，B={6，7，8，9，10}，以下關(guān)系是從A到B的入射函數(shù)的是A．f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B．f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C．f={<1,6>,<2,7>,<4,9>,<3,8>}D．f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}12．下面關(guān)于關(guān)系R的傳遞閉包t(R)的描述最確切的是（）A．t(R)是包含R的二元關(guān)系 B．t(R)是包含R的最小傳遞關(guān)系C．t(R)是包含R的一個(gè)傳遞關(guān)系 D．t(R)是任何包含R的傳遞關(guān)系13.設(shè)A={l，2，3，4}，A上的二元關(guān)系R={<1，2>，<3，4>，<4，3>}，S={<l，3>，<3，4>，<4，1>}，則R～S=________，(RS)-1=________。14．設(shè)N是自然數(shù)集合，f和g是N到N的函數(shù)，且f（n）=2n+1，g（n）=n2，那么復(fù)合函數(shù)（ff）（n）=________（gf）（n）=________。15．設(shè)復(fù)合函數(shù)gf是從A到C的函數(shù)，如果gf是滿射，那么________必是滿射，如果gf是入射，那么________必是入射。16．設(shè)A={1，2}，B={2，3}，則A-A=________，A-B=________。17．設(shè)A={1，2}，B={2，3}，則AA=__________，AB=__________。18．設(shè)A={1，2，3，4}上關(guān)系R={<1,2>,<2,4>,<3,3>,<1,3>}，則R的自反閉包r(R)=_________，對(duì)稱閉包S（R）=__________。19．設(shè)f:R→R,f(x)=x2-2,g:R→R,g(x)=x-1,那么復(fù)合函數(shù)=__________，=__________。20．設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)=__________。18．已知A={{}，{，1}}，B={{，1}，{1}}，計(jì)算A∪B，Aeq\o\ac(○,+)B，A的冪集P（A）。21．設(shè)A={a,b,c,d}，R={<a，b>，<a，d>，<b，c>，<c，a>，<d，a>}，求R的傳遞閉包。22.設(shè)A={2，3，6，12，24，36}，請(qǐng)畫出A上整除關(guān)系的哈斯圖，并給出子集{6，12，24，36}的下界、下確界、極大元、最大元。23．設(shè)A={1，2，3，4，6，8，12，24}，R為A上的整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元、最小元、極大元、極小元。24．若集合A={1，{2，3}}的冪集為P（A），集合B={{，2}，{2}}的冪集為P（B），求P(A)∩P(B)。25．X={1234}，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。（1）畫出R的關(guān)系圖；（2）寫出R的關(guān)系矩陣；（3）說(shuō)明R是否具有自反、反自反、對(duì)稱、傳遞性質(zhì)。26．設(shè)A={a,b,c},P(A)是A的冪集，R為A上的包含關(guān)系，試給出<P(A),R>的哈斯圖，并給出子集{{a,b},{a,c},{c}}的極大元、極小元、最大元、最小元。27．設(shè)R為N×N上的二元關(guān)系，對(duì)任意<a，b>,<c，d>∈N×N，<a，b>R<c，d>的充要條件是b=d，證明R為等價(jià)關(guān)系。28.設(shè)A={<a，b>|a，b∈Z+，Z+為整數(shù)集}，A上的關(guān)系R={<<a，b>,<c，d>>|ad=bc}，證明R是等價(jià)關(guān)系。29．R是集合A上自反和傳遞的關(guān)系，試證明：RR=R。離散數(shù)學(xué)復(fù)習(xí)第四章代數(shù)系統(tǒng)一、典型考查要點(diǎn)：1、運(yùn)算的判斷：方法：運(yùn)算滿足封閉性，即運(yùn)算后產(chǎn)生的象仍在同一個(gè)集合中。詳見(jiàn)P772、運(yùn)算性質(zhì)的判斷：運(yùn)算性質(zhì)：封閉、結(jié)合、交換、分配、冪等、吸收、消去方法：根據(jù)定義，在所討論的集中任取元素，符合定義即可。在運(yùn)算表中可以判斷：1）運(yùn)算具有封閉性，當(dāng)且僅當(dāng)運(yùn)算表中的每個(gè)元素都屬于A。2）運(yùn)算具有可交換性，當(dāng)且僅當(dāng)運(yùn)算表關(guān)于主對(duì)角線是對(duì)稱的。3）運(yùn)算具有等冪性，當(dāng)且僅當(dāng)運(yùn)算表的主對(duì)角線上的每一元素與它所在行（列）的表頭元素相同。詳見(jiàn)P793、代數(shù)系統(tǒng)中特殊元：么元（單位元）、零元、逆元判斷方法：根據(jù)定義，在所討論的集中找到特殊元，符合定義即可。在運(yùn)算表中可以判斷：1）A中關(guān)于運(yùn)算具有零元，當(dāng)且僅當(dāng)該元素所對(duì)應(yīng)的行和列中的元素都與該元素相同。2）A中關(guān)于運(yùn)算具有幺元，當(dāng)且僅當(dāng)該元素所對(duì)應(yīng)的行和列依次與運(yùn)算表的行和列相一致。3）設(shè)A中關(guān)于運(yùn)算具有幺元，a和b互逆，當(dāng)且僅當(dāng)位于a所在行和b所在列的元素及b所在行和a所在列的元素都是幺元。詳見(jiàn)P804、子代數(shù)的判定：關(guān)鍵兩個(gè)條件:BA,<B，>中的特殊元（么元或零元）與<A，>中相同。詳見(jiàn)P825、特殊代數(shù)系統(tǒng)判定：（G，）封閉廣群結(jié)合半群么元獨(dú)異點(diǎn)可逆群，根據(jù)定義，滿足條件即可。詳見(jiàn)P866、群的證明：方法：根據(jù)群的四個(gè)條件，逐一驗(yàn)證即可，注意：對(duì)于么元和逆元，先根據(jù)運(yùn)算特點(diǎn)解出么元和逆元，再驗(yàn)證。詳見(jiàn)P867、群的性質(zhì)：1、<G，⊙>是群∧|G|＞1<G，⊙>無(wú)零元。2、G，⊙>是群<G，⊙>中的唯一等冪元是幺元。3、群滿足消去律：b⊙a(bǔ)=c⊙a(bǔ)b=c4、給定群<G，⊙>，則a⊙x=b群中方程解是唯一的。5、<G，⊙>是群(a⊙b)-1=b-1⊙a(bǔ)-1詳見(jiàn)P878、子群及判定：三個(gè)判定定理根據(jù)已知條件選擇，給定群<G，⊙>及非空HG，則1、<H，⊙>是<G，⊙>的子群a⊙b∈H，a-1∈H2、<H，⊙>是<G，⊙>的子群(a)(b)(a，b∈H→a⊙b-1∈H)非空有限集H則a⊙b∈H9、特殊群的判斷：1、阿貝爾群即滿足交換律的群2、循環(huán)群即群中每個(gè)元都由某一個(gè)元的n次冪生成，這個(gè)元就是生成元。3、同余類整數(shù)加法，乘法，<Z，+m><Z，×m>構(gòu)成群：[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]10、環(huán)、整環(huán)、域之間的關(guān)系及判定：1、<R，+，·>，若①<R，+>是Abel群，②<R，·>是半群，③·對(duì)于+是可分配的，則稱<R，+，·>是環(huán)2、可交換含幺環(huán)<R，+，·>，且無(wú)零因子，則稱<R，+，·>為整環(huán)。3、可交換環(huán)<R，+，·>，若<R-{0}，·>為群，則稱<R，+，·>為域4、環(huán)、整環(huán)、域之間的關(guān)系：域一定是整環(huán)，整環(huán)一定是環(huán)，反之不成立。詳見(jiàn)P9311、格、子格、分配格、有補(bǔ)格的判定：1、格：即<A,≤>偏序集中，任意兩個(gè)元素都有最小上界和最大下界。2、子格：子集，運(yùn)算∨,∧封閉即可。3、分配格：含有五角格和鉆石格為子圖的都不是分配格，但鏈?zhǔn)欠峙涓瘛?、有補(bǔ)格：每個(gè)元素都至少有一個(gè)補(bǔ)元素的有界格。求補(bǔ)元時(shí)，滿足：a∨b=1(即全上界)，和a∧b=0(即全下界)詳見(jiàn)P97二、強(qiáng)化練習(xí)1.在整數(shù)集上，不是二元運(yùn)算()A.加法B.減法C.乘法D.除法2.設(shè)A是奇數(shù)集合，×為乘法運(yùn)算，則<A，×>是()A.半群B.群C.循環(huán)群D.交換群3.不滿足結(jié)合律是()*b=min(a，b)*b=max(a，b)*b=2(a+b) *b=2ab4．在N上，可結(jié)合的是（）A．a(chǎn)b=a-2bB．a(chǎn)b=min{a，b}C．a(chǎn)b=-a-bD．a(chǎn)b=|a-b|5．整環(huán)和域是（）A整環(huán)一定是域B域不一定是整環(huán)C域一定是整環(huán)D域一定不是整環(huán)6．設(shè)集合A={1，2，3，……，10}，A上是不封閉的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公約數(shù)D．x*y=LCM{x,y},即x,y的最小公倍數(shù)7．設(shè)H，K是群（G，）的子群，下面代數(shù)系統(tǒng)是（G，）的子群的是（）A．（H∩K，） B．（H∪K，）C．（K-H，） D．（H-K，）4．下列所示的哈斯圖所對(duì)應(yīng)的偏序集中能構(gòu)成格的是（）A．B．C． D．8.代數(shù)系統(tǒng)<A，*，>是整環(huán)，則<A，*>是________，<A，>是________，且無(wú)零因子。9.在實(shí)數(shù)集R上定義運(yùn)算ab=a+b+ab，則幺元為_(kāi)_______，元素2的逆元為_(kāi)_______。10．設(shè)S是非空有限集，代數(shù)系統(tǒng)<P（S），∪>中，其中P（S）為集合S的冪集，則P（S）對(duì)∪運(yùn)算的單位元是________，零元是________。11．在<Z6,eq\o\ac(○,+)>中，2的階是________。12．設(shè)<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤為整除關(guān)系，則3的補(bǔ)元是________。13．有理數(shù)集Q中的*運(yùn)算定義如下：a*b=a+b-ab，則*運(yùn)算的單位元是__________，設(shè)a有逆元，則其逆元a-1=__________。14．<Zn,>是一個(gè)群，其中Zn={0,1,2,……,n-1},xy=(x+y)modn，則在<Z6,>中，1的階是__________，4的階是__________。15．設(shè)H是形如的2×2階矩陣的集合，H中定義通常的矩陣乘法運(yùn)算。驗(yàn)證H是群，=。16．在整數(shù)集Z上定義：，證明：<Z，>是一個(gè)群。17．設(shè)H是G的有限子集，則<H，>是群<G，>的子群當(dāng)且僅當(dāng)<H，>是群<G，>的子代數(shù)。離散數(shù)學(xué)復(fù)習(xí)第五章圖論一、典型考查要點(diǎn)1、圖的基本概念：方法：度：點(diǎn)連接的邊的條數(shù)，自環(huán)算2度；生成子圖：點(diǎn)不減少，邊減少；完全圖：每個(gè)點(diǎn)都與余下的點(diǎn)有邊；同構(gòu)：兩個(gè)圖總可以畫成相同的。詳見(jiàn)P1102、握手定理：結(jié)點(diǎn)度數(shù)總和等于邊數(shù)的兩倍，即deg(v)=2|E|，用于邊點(diǎn)度之間的計(jì)算。3、路的兩個(gè)定理及證明：1、在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到vk存在一條路，則從結(jié)點(diǎn)vj到vk存在一條不多于n-1條邊的路。推論：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，若從結(jié)點(diǎn)vj到vk存在一條路，則必存在一條從vj到vk而邊數(shù)小于n的通路。詳見(jiàn)P1154、連通圖的判定及證明：1、無(wú)向連通圖：任意兩點(diǎn)都有路，即都走得通，只有一個(gè)連通分支。2、有向圖中：強(qiáng)連通，任意兩點(diǎn)都有路，即都走得通；弱連通，去掉方向后才連通；單側(cè)連通，每對(duì)點(diǎn)，只要一個(gè)點(diǎn)可達(dá)另一點(diǎn)。3、強(qiáng)連通的充要條件證明：一個(gè)有向圖是強(qiáng)連通的充分必要條件是G有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次。詳見(jiàn)P116-1175、邊割集、點(diǎn)割集的判定及證明：點(diǎn)割集：圖中去掉這些點(diǎn)及關(guān)聯(lián)的邊后，恰好不連通。定理：一個(gè)連通無(wú)向圖G中的結(jié)點(diǎn)v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和w，使得結(jié)點(diǎn)u和w的每一條路都通過(guò)v。邊割集：圖中去掉這些邊后，恰好不連通，連通分支變?yōu)?。定理：G的一條邊e不包含在G的回路中當(dāng)且僅當(dāng)e是G的割邊。詳見(jiàn)P116-1176、鄰接矩陣、可達(dá)矩陣的表示：鄰接矩陣：，表示圖中點(diǎn)與點(diǎn)的關(guān)系，可以利用它的Ak來(lái)求長(zhǎng)度為k的路的條數(shù)，即定理：設(shè)A為簡(jiǎn)單圖G的鄰接矩陣，則Ak中的i行j列元素akij等于G中聯(lián)結(jié)vi到vj的長(zhǎng)度為k的鏈(或路)的數(shù)目?？蛇_(dá)矩陣：可以利用它來(lái)判定連通性，全為1，就是連通的。詳見(jiàn)P117-1187、歐拉圖及應(yīng)用：歐拉路：邊遍行且只能一次的路，點(diǎn)可以重復(fù)。歐拉回路：邊遍行且只能一次的回路。判定：歐拉路存在當(dāng)且僅當(dāng)G連通，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。歐拉回路存在當(dāng)且僅當(dāng)G連通，并且所有點(diǎn)度數(shù)都為偶數(shù)。應(yīng)用到一筆畫問(wèn)題，即有沒(méi)有歐拉路。8、漢密爾頓圖及應(yīng)用：漢密爾頓路：點(diǎn)遍行且只能一次的路。漢密爾頓回路：點(diǎn)遍行且只能一次的回路。判定：1、必要條件：若圖有漢密爾頓回路，則V的每個(gè)非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的連通分支數(shù)?？梢岳眠@個(gè)必要條件來(lái)判定有些圖不是漢密爾頓圖。2、充分條件：圖G有n個(gè)點(diǎn)的簡(jiǎn)單圖,如果每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。若每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n,則存在漢密爾頓回路。3、應(yīng)用到網(wǎng)路連通、朋友開(kāi)會(huì)排座位等，就是先利用題目中的聯(lián)系，有關(guān)系就確定一條邊，構(gòu)造一個(gè)圖，找一條漢密爾頓路或漢密爾頓回路即可。詳見(jiàn)P1219、平面圖的判定：1、平面圖：畫在平面上，邊不相交叉。判定：平面圖不含與K3,3,或K5同胚的子圖。K3,3,K5及彼得森圖都不是平面圖。2、歐拉公式：n-m+r=2,計(jì)算邊點(diǎn)面之間的關(guān)系問(wèn)題。面的次數(shù)即圍著這個(gè)面的邊的條數(shù)，單獨(dú)的邊要算2次。必要條件：給定連通簡(jiǎn)單平面圖G=<V，E，>。若|V|≥3，則e≤3v-6。詳見(jiàn)P12510、樹的6個(gè)等價(jià)