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

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