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

1、命題的判斷方法：陳述句真值唯一，特殊：反問句也是命題。其它疑問句、祈使句、感嘆句、悖論等皆不是。詳2、聯(lián)結(jié)詞運算定律┐∧∨→記住特殊的：1∧11，0∨00，1→00，111，001詳見P53、命題符號化步驟：A劃分原子命題，找準聯(lián)結(jié)詞。特殊自然語言：不但而且，雖然但是用∧，只有P才Q，應(yīng)為Q→P；除非P否則Q，應(yīng)為┐P→Q。B設(shè)出原子命題寫出符號化公式。詳見P54、公式的分類判定（重言式、矛盾式、可滿足式）方法：其一根據(jù)所有真值賦值情況，其二根據(jù)等價演算來判斷。詳見P95、真值表的構(gòu)造步驟：①命題變元按字典序排列，共有2n個真值賦值。②大到小順序列出。③若公式較復(fù)雜，可先列出各子公式的真值(若有括號，則應(yīng)從里層向外層展開式的真值。詳見P8。對每個指派，以二進制數(shù)從小到大或從)，最后列出所求公6、基本概念：置換規(guī)則，P規(guī)則，T規(guī)則，詳見P24；合取范式，析取范式，詳見P15；小項詳見P16；大項詳見P18，最小聯(lián)結(jié)詞組詳見P157、等價式詳見P22表1.6.2證明方法：①真值表完全相同主要等價式：(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②用等價演算③利用AB的充要條件是AB且BA。A∨B，A→BB→A。(12)雙條件式轉(zhuǎn)化8、蘊含式詳見P23表1.6.3證明方法：①前件真導(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)用同一律補進簡單合?。ㄎ鋈。┦街形闯霈F(xiàn)的所有命題變元，如Q，則PP∧（Q∨Q)或PP∨（Q∧Q)，并用分配律展開之，將相同的簡單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析?。ê先。┓妒?。注意：主析取范式與主合取范式之間的聯(lián)系。例如：(PQ)Qm1m3M0M2，即剩下的編碼就是另一個主范式的編碼，因此，求主范式，哪一個簡單易求，就先求哪個，然后對應(yīng)出所求結(jié)果。詳見P1611、推理證明：重點方法：演算、演繹法（常用的格式）、反證法、CP規(guī)則即附加前提等。重點規(guī)則（主要蘊含式）：(1)P∧QP化簡(2)P∧QQ化簡(3)PP∨Q附加(6)(P→Q)P變形化簡(7)(P→Q)Q變形化簡(8)P，(P→Q)Q假言推理P，(P∨Q)Q析取三段論(11)(P→Q)，(Q→R)P→R條件三段論(12)(PQ)，(QR)PR雙條件三段論步：一命題符號化，二寫出前提和結(jié)論，三進行證明。詳見P21(4)PP→Q變形附加(5)QP→Q變形…1.命題的是()A.走，看電影去+y>0C.空集是任意2.下列式子為重言式的是(→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐(P3．下列為兩個命題變元P，Q的小項是（）集合的真子集D.你明天能來嗎)D.(P∨Q)(P→Q)A．P∧Q∧PB．P∨QC．P∧QD．P∨P∨Q4．下列語句中是真命題的是（）A．我正在說謊B．嚴禁吸煙C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的C．（PQ）6．命題公式（P∧（P→Q））→Q是（）A．矛盾式B．蘊含式C．重言式D．等價式7．命題公式（P∧Q）→R的成真指派是（）B．001，011，101，110，111C．全體指派D．無“他雖聰明但不用功”的確的是（）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．求下列公式的21．構(gòu)造命題公式（PQQR）→PR的真值表。22．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））23.用推理方法證明：P∨Q，P→R，Q→S├R∨S。24．構(gòu)造下面推理的小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當小趙去看電影時，小李也去。25．構(gòu)造下面推理的A曾到過受害者房間并且11點以前沒離開，A就犯了謀殺罪。A曾到過受害者房間。11點以前離開，看門人會看見他?？撮T人沒有看見他。所以A犯了謀殺罪。證明。如果證明。只要如果在，離散數(shù)學(xué)復(fù)習(xí)要點第二章謂詞邏輯一、典型考查點1、基本概念：個體詞、個體域、謂詞、特性謂詞、轄域，詳見P27；前2、謂詞符號化步驟：①正確理解給定命題。把命題改敘，使其中每個原子命題、原子命題表達出來。②把每個原子命題分解成個體、謂詞和量詞；在全總論域討論時，要給出特性謂詞。③找出恰當注意全稱量詞(x)后跟條件式，存在量詞(x)后跟合取式。④用恰當?shù)穆?lián)結(jié)詞把給定命題表示出來。詳見P303、謂詞公式類型的判定（永真式、永假式、可滿足式）方法：利用論域翻譯成自然語言后進行判斷。詳見P34束范式詳見P36必要時之間的關(guān)系能明顯量詞。應(yīng)4、自由變元與約束變元的判定方法：按定義，關(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)量詞轄域縮小或擴大等價式((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)(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、前束范式方法：①把量詞全部通過等值演算化到整個謂詞公式的前面②把量詞前面的┐全部通過德摩根定律化到謂詞公式的內(nèi)部。詳見P36~A.(x)(P(x)→(x)(Q(x)∧A(x，y)))B.(x)∧(y)∨P(x，y))@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．在公式（x）F（x，y）→（y）G（x，y）中變元x是（）A．自由變元B．約束變元C．既是自由變元，又是約束變元D．既不是自由變元，又不是約束變元6．下列等價式不正確的是（）A．x(P(x)Q(x))xP(x)xQ(x)B．x(P(x)Q(x))xP(x)xQ(x)C．x(P(x)Q(x))xP(x)xQ(x)D．x(P(x)Q)xP(x)Q7．設(shè)A（x）:x是人，B（x）：x，誤命題“沒有不犯錯的誤人”符號化為（）A．x(A(x)B(x))B．x(A(x)B（x））C．x(A(x)B(x))D．x(A(x)B(x))—二、填空題8.一個公式，如果量詞均在全式的________，其作用域延伸到整個公式的________，則該公式稱為前束范式。9．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的轄域為________，x的轄域為________。10．公式（x）（F（x）→G(y)）→(y)(H(x)L(x,y,z))中的自由變元為_________，約束變元為__________。三、綜合應(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上的恒等系，記為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)系矩陣\關(guān)系圖方法：根據(jù)題目條件，用列舉法寫出關(guān)系R，畫出關(guān)系圖（有向圖）或?qū)懗鲫P(guān)系矩陣。詳見P50,51,52.3、關(guān)系的性質(zhì)判斷：判斷方法如下：詳見P54R是A上關(guān)系…自反性反自反性對稱性傳遞性反對稱性xA<x,x>xxAxRxxRy→yRxxRy→<y,x>R除x=yxRyyRz→xRz定義R沿對角線對、主對角線全為1主對角線全為0沿主對角線不對稱矩陣特征稱:有邊則雙向若有邊，則是單向邊圖特征每個頂點都有環(huán)每頂點都沒有邊環(huán)IAR=集合特征IARR-1=R】RIAIA4、關(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)系與劃分一一對應(yīng)，等價關(guān)系的等價類即為確定的劃分的分塊，即有關(guān)系的，劃在同一塊。劃分中凡在同一個分塊中的元，都寫成滿足關(guān)系的元，這樣寫出的關(guān)系R就是一個等價關(guān)系。逐一驗證。要注意給出的等價關(guān)系6、相容關(guān)系和覆蓋的判斷：相容關(guān)系兩個性質(zhì)：自反和對稱，注意：相容關(guān)系圖的畫法省略了自反和對稱。覆蓋按定義判斷即可。詳見P617、偏序關(guān)系與哈斯圖直接關(guān)系，中間沒有第三個元，即若a<b且不存在cA，使得a<c<b。②偏序關(guān)系與哈斯圖住的聯(lián)系來表示，省略全部向上的箭頭，省略自反性的自環(huán)，省略了傳遞性。反之，由哈斯圖寫偏序關(guān)系也要注意這四點，除了直接的蓋住關(guān)系外，還有自反和傳遞也要寫出來。：①基本概念：三個性質(zhì)：自反、反對稱和傳遞；可比，就是有關(guān)系，a≤bb≤a；蓋住，就是：畫圖注意四點：使用蓋<A,≤>為偏序集，BA，bB，①若(x)(xBb≤x)為真，則稱b為B的最小元。②若(x)(xBx≤b)為真，則稱b為B的最大元。③若(x)(bxx≤b)為真，則稱b為B的極小元。·④若根據(jù)定義判斷時，最?。ù螅┰c極?。ù螅┰怯袇^(qū)別的，最小（大）元是B中最?。ù螅┑脑兀cB中其他元素都可比；而極?。ù螅┰灰欢ㄅcB中元素都可比，只要沒有比它?。ù螅┑脑?，它就是極小（大）元。對于B，極?。ù螅┰欢ù嬖冢钚。ù螅┰灰欢ù嬖冢鬊中只有一個極?。ù螅┰?，則它一定是B的最?。ù螅┰Ｔ斠奝689、求上界下界上確界和下確界：設(shè)<A,≤>為偏序集，BA，bA，①若(x)(xBb≤x)為真，則稱②若(x)(xBx≤b)為真，則稱b為B的上界。③若b是一下界且對每一個B的下界b’有b’≤b，則稱b為B的最大下界或下確界，記為glb。④若b是一上界且對每一個B的上界b’有b≤b’，則稱b為B的最小上界或上確界，記為lub。有窮集且可能有多個，存在則必唯一。若b為B的下界。判斷時注意，上界下界上確界和下確界是A集合上來找的，B的上界，下界，最小上界，最大下界都可能不存在。若下界是唯一的。詳見P691.設(shè)Z+是正整數(shù)集，f：Z+×Z+→Z+，f(n，m)=nm，則f()A.僅是入射B.僅是滿射C.是雙射D.不是函數(shù))1011000011013.設(shè)R1和R2是集合A上的相容關(guān)系，4．集合A={1，2，…，10}上的關(guān)系R={<x，y>|x+y=10，x∈A，y∈A}，則A．自反的B．對稱的C．傳遞的、對稱的D．反自反的、5．若R和S是集合A上的兩個關(guān)系，則下述結(jié)論正確的是（）A．若R和S是自反的，則R∩S是自反的B．若C．若R和S是反對稱的，則RS是反對稱的D．若R和S是傳遞的，則2CR的性質(zhì)是（）RS是對稱的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}}AD．∈A8．設(shè)A．M∩N9．設(shè)A-B=，則有（）A．B=10．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)系A(chǔ)．t(R)是包含R的二元關(guān)系B．t(R)是包含R的最小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的傳遞閉包t(R)的描述最確切的是（）傳遞關(guān)系R～S=________，f（n）=2n+1，g（n）=n2，那么復(fù)合函數(shù)（ff）（n）=________gf是從A到C的函數(shù)，如果gf是滿射，那么________必是滿射，如果gf是入射，那么________-16．設(shè)A={1，2}，B={2，3}，則A-A=________，A-B=________。AA=__________，AB=__________。R的自反閉包r(R)=_________，對稱閉包S（R）=__________。gfx=__________，()()=__________。19．設(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，A○+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)系。）A上自反和傳遞的關(guān)系，試證明：RR=R。29．R是集合離散數(shù)學(xué)復(fù)習(xí)第四章代數(shù)系統(tǒng)一、典型考查要點：1、運算的2、運算性質(zhì)的取元素，符合定義即可。在運算運算具有可交換性，當且僅當運算表關(guān)于主對角線是對稱的。的每一元素與它所在行（列）的表頭元素相同。詳見P793、代數(shù)系統(tǒng)中特殊元：么元（單位元）、零元、逆元判斷方法：根據(jù)定義，在所討論的集中可。在運算表中可以判斷：1）A中關(guān)于運算具有零元，當且僅當該元素所對應(yīng)的行和列中的元素都與該元素相同。2）A中關(guān)于運算具有幺元，當且僅當該元素所對應(yīng)的行和列依次與運算表的行和列相一致。3）設(shè)A中關(guān)于運算幺元，a和b互逆，當且僅當位于a所在行和b所在列的元素及b所在行和a所在列的元素都是幺元。詳見P804、子判定：關(guān)鍵兩個條件:BA,<B，判斷：方法：運算滿足封閉性，即運算后產(chǎn)生的象仍在同一個集合中。詳見P77等、吸收、消去方法：根據(jù)定義，在所討論的集中表中可以判斷：1）運算具有當且僅當運算表中的每個元素都屬于A。2）3）運算具有當且僅當運算表的主對角線上判斷：運算性質(zhì)：封閉、結(jié)合、交換、分配、冪任封閉性，等冪性，找到特殊元，符合定義即具有封閉廣群結(jié)合半群么元獨異點可逆群，根據(jù)定義，滿足條件即可。詳>中的特殊元（么元或零元）與<A，>中相同。詳見P82代數(shù)的5、特殊代數(shù)系統(tǒng)判定：（G，）見P86/6、群的證明：方法：根據(jù)群的四個條件，逐一驗證即可，注意：對于么元和逆元，先根據(jù)運算特點解出么元和逆元，>是群∧|G|＞1<G，⊙>是群<G，⊙>中的唯一等冪元是幺元。3、群>是群(a⊙b)-1=b-1⊙a-1滿足消去律：b⊙a=c⊙ab=c4、給定群5、<G，⊙詳見P878、子群及判定：三個判定定理根據(jù)已知條件選擇，給定群⊙b∈H，a-1∈H2、<H，⊙>是<G，⊙>的子群(a)(b)(a，b∈H→a⊙b-1∈H)非空有限集9、特殊群的判斷：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)、1、<R，+，·>，若①<R，+>是Abel群，②<R，·>是半群，③·對于+是可分配的，則稱<R，+，·>是環(huán)2、可交換<R，+，·>，且無零因子，則稱<R，+，·>為整環(huán)。3、可交換環(huán)<R，+，·>，若<R-{0}，·>為群，則稱<R，+，·>為域4、環(huán)、整環(huán)、立。詳見P9311、格、子格、分配格、有1、格：即最小上界和最大下界。2、子格：子集，運算∨,∧封閉即可。3、分配格：含有五角格和鉆石格為子圖的都不是分配格，但鏈是分配格。4、有補格：每個元素都至少有一個補元素的有界格。求補元時，滿足：a∨b=1(即全上界)，和a∧b=0(即全下界)詳見P97>及非空1、<H，⊙>是<G，⊙>的子群aH則a⊙b∈H生成元。域之間的關(guān)系及判定：含幺環(huán)域之間的關(guān)系：域一定是整環(huán)，整環(huán)一定是環(huán)，反之不成補格的判定：<A,≤>偏集序中，任意兩個元素都有,二、強化練習(xí)1.在整數(shù)集上，不是二元運算2.設(shè)A是奇數(shù)集合，×為乘法運算，則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域一定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ù)()A.加法B.減法C.乘法D.除法<A，×>是()A.半群B.群C.循環(huán)群D.交換群(不是整環(huán)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．8.代數(shù)系統(tǒng)<A，*，9.在實數(shù)集R上定義運算ab=a+b+ab，則幺元為________，元素2的逆元為________。10．設(shè)S是非空有限集，代數(shù)系統(tǒng)<P（S），∪>中，其中P（S）為集合S的冪集，則P（S）對∪運算的單位元是________，零元是________。11．在<Z6,○+>中，2的階是________。12．設(shè)<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤為整B．C．D．<A，*>是________，<A，>是整環(huán)，則>是________，且無零因子。除關(guān)系，則3的補元是________?！?3．有理數(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的階是__________。111101xxx0101。15．設(shè)H是形如的2×2階矩陣的集合，H中定義通常的矩陣乘法運算。驗證H是群，=abab2,a,bZ16．在整數(shù)集Z上定義：，證明：<Z，>是一個群。>的子代數(shù)。17．設(shè)H是G的有限子集，則<H，>是群<G，>的子群當且僅當<H，>是群<G，離散數(shù)學(xué)復(fù)習(xí)第五章圖論一、典型考查要點1、圖的基本概念：方法：度：點連接的邊的條數(shù)，自環(huán)算2度；生成子圖：點不減少，邊減少；完全圖：每個點都與余下的點有邊；同構(gòu)：兩個圖總可以畫成相同的。詳見P110·2、握手定3、路的兩個定一條不多于n-1條邊的vk而邊數(shù)小于n的通路。詳見P1154、連通圖的1、無向連通圖：走得通，有只一個連通分支。2、有向圖中：強連通，弱連通，去掉方向后才連通；單側(cè)連通，每對點，要只一個點可達另一點。3、強連件證明：一個有強連通的充分必要條件是G有一個回路，它至少包含每個次。詳見P116-1175、邊割集、點割集的割集：圖中去掉這些點及關(guān)聯(lián)的邊后，恰好不連通。定G中的結(jié)點v是割點的充分必要條件是存在兩個u和w，使得結(jié)點u和w的每一條過v。邊割集：圖中去掉這些邊后，恰好不連通，連通分支變?yōu)?。定G的一條邊e不包含在G的回路中當且僅當e是G的割邊。詳見P116-117理：結(jié)點度數(shù)總和等于邊數(shù)的兩倍，即deg(v)=2|E|，用于邊點度n個結(jié)點的圖中，如vj到vk存在一條n個結(jié)點的圖中，vj到vk存在一條之間的計算。理及證明：1、在一個具有果從結(jié)點路，則從結(jié)點vj到vk存在路。推論：在一個具有若從結(jié)點路，則必存在一條從vj到判定及證明：任意兩點都有路，即都任意兩點都有路，即都走得通；通的充要條向圖是結(jié)點一判定及證明：點理：一個連通無向圖結(jié)點路都通理：1viviadjvaij0jnadjvorij6、鄰接矩陣、可達矩陣的表示：鄰接矩陣：j，表示圖中點與點的關(guān)系，可以利用它的Ak來求長度為k的路的條數(shù)，即定理：設(shè)A為簡單圖G的鄰接矩陣，則Ak中的i行j列元素akij等于G中聯(lián)結(jié)vi到vj的長1路ij從v到v不存在路可以Pij0度為k的鏈(或路)的數(shù)詳見P117-1187、歐拉圖及應(yīng)用：歐拉路：邊遍行且只能一次的路，點可以G連通，且有零個或兩個奇數(shù)度結(jié)點。歐拉回路存在當且僅當筆畫問題，即有沒有歐拉路。8、漢密爾頓圖及應(yīng)用：漢密爾頓路：點遍行且只能一次的路。件：若圖有漢密爾頓回路，則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、平面圖：畫在平面上，邊不相交叉。判定：平面圖不得森圖都不是平面圖。2、歐拉公式：n-m+r=2,計算邊點面之間的關(guān)系問題。面的次數(shù)即圍著這個面的邊的條數(shù)，單獨2次。必要條件：給定連通簡單平面圖G=<V，E，>。若|V|≥3，則e≤3v-6。詳見P125利用它來判定連通性，全為1，就是連通的。目?？蛇_矩陣：重復(fù)。歐拉回路：邊遍行且只能一次的回路。判定：歐拉路存在當且僅當G連通，并且所有點度數(shù)都為偶數(shù)。應(yīng)用到一漢密爾頓回路：點遍行且只能一次的回路。判定：1、必要條利若每一判定：含與K3,3,或K5同胚的子圖。K3,3,K5及彼的邊要算…10、樹的6個等價定義：回路(5)連通，但刪去任一邊后就不連通詳見P128(1)無回路的連通圖(2)無回路且e=v-1(3)連通且e=v-1(4)無回路，但增加一邊后得到且僅得一個(6)每一對結(jié)點間有且僅有一條通利用e=v-1和握手定理計算邊點的數(shù)目。路。11、最小生成樹：連通圖中權(quán)之各最小的生成樹，利用避圈法：