離散數(shù)學(xué)部分概念和公式總結(jié)(精簡(jiǎn)版)2232

離散數(shù)學(xué)復(fù)習(xí)材料第一章命題邏輯一、等價(jià)公式(真值表)`1)常用聯(lián)結(jié)詞：┐否定∨析取∧合取PTF┐PFPTTFFQTFTFP∨QPTTFFQTFTFP∧QTTTFTFFFT→：條件：雙條件當(dāng)且僅當(dāng)Q取值為F時(shí)P→Q為F，否則為T(mén)PTTFFQTFP→Q(┐P∨Q)PTTFFQTFPQTFTTTFFTTFTF★等價(jià)公式表(等值公式表常用的其它真值表)雙重否┐┐P<=>P定P∨P<=>P冪等律P∧P<=>P(P∧Q)∧R<=>P∧(Q∧R)(P∨Q)∨R<=>P∨(Q∨R)P∧Q<=>Q∧P結(jié)合律交換律分配律吸收P∨Q<=>Q∨PP∧(Q∨R)<=>(P∧Q)∨(P∧R)P∨(Q∧R)<=>(P∨Q)∧(P∨R)P∨(P∧Q)<=>PP∧(P∨Q)<=>P┐(P∧Q)<=>┐P∨┐Q┐(P∨Q)<=>┐P∧┐QP∨F<=>P德摩根同一律P∧T<=>PP∨T<=>T零律P∧F<=>FP∨┐P<=>T否定律P∧┐P<=>FPage1of26P→Q<=>┐P∨QPQ<=>(P→Q)∧(Q→P)離散數(shù)學(xué)復(fù)習(xí)材料PQ<=>QPPQ<=>(P∧Q)∨(┐P∧┐Q)┐(PQ)<=>P┐QR∨(P∨┐P)<=>T常用的其它真值表命題公式的類型：(1)若A在它的各種賦值下均取值為真，則稱R∧(P∧┐P)<=>FA為重言式或永真式。P→Q<=>┐Q→┐PA為┐(P→Q)<=>P∧┐Q(2)若A在它的賦值下取值均為假，則稱矛盾式或永假式。(P→Q)∧(P→┐Q)<=>┐PP→(Q→R)<=>(P∧Q)→R(3)若A至少存在一組賦值是成真賦值，則A是可滿足式。(PQ)R<=>P(QR)當(dāng)P→Q是一個(gè)重言式(永真式)稱P蘊(yùn)含Q記做P=>Q★蘊(yùn)含公式表：此表可以理解為子集=>全集)1P∧Q=>P2P∧Q=>Q3P=>P∨Q4┐P=>P→Q5Q=>P→Q6┐(P→Q)=>P7┐(P→Q)=>┐Q8P∧(P→Q)=>Q9┐Q∧(P→Q)=>┐P┐P∧(P∨Q)=>Q(P→Q)∧(Q→R)=>P→R(PQ)∧(QR)=>PR(P∨Q)∧(P→S)∧(Q→R)=>R(P→Q)∧(R→S)=>(P∧R)→(Q∧S)1011121314對(duì)偶式與范式：性質(zhì)：┐A(P1,P2…..Pn)<=>A*(┐P1,┐P2……┐Pn)A(┐P1,┐P2……┐Pn)<=>┐A*(P1,P2…..Pn)主析取范式：設(shè)命題公式A中含n個(gè)命題變項(xiàng)，如果A得析取范式中的簡(jiǎn)單合取式全是小項(xiàng)，則稱該析取范式為A的主析取范式。(即A∨A2∨…..∨An形式)1例如：P,Q的小項(xiàng)是P∧Q,┐P∧Q,P∧┐Q,┐P∧┐Q(不能同時(shí)出現(xiàn)┐Q和Q)小項(xiàng)性質(zhì)：a)每個(gè)(例如當(dāng)P，Q，R全部為b)任意兩個(gè)c)全部小項(xiàng)析取值為范式的方法步驟a)劃歸為b)去除范式中的永假析取值項(xiàng)(例如P∧┐P)；c)重復(fù)d)對(duì)合取主合取小項(xiàng)當(dāng)指派真值與編碼相同時(shí)，其值為T(mén)，否則全為F(共2n-1個(gè))T的時(shí)候小項(xiàng)P∧Q∧R才為T(mén)，否則全部為F)小項(xiàng)合取值為FT找主析取析取范式；合取項(xiàng)和相同的變?cè)喜?；補(bǔ)沒(méi)有出現(xiàn)的命題變?cè)?，即添?P∨┐P)式，應(yīng)用分配律展開(kāi)公式。中的簡(jiǎn)單合析范式：設(shè)命題公式A中含n個(gè)命題變項(xiàng)，如果A得析取范式Page2of26離散數(shù)學(xué)復(fù)習(xí)材料式全是大項(xiàng)，則稱該析取范式為A的主析取范式。例如：P,Q的大項(xiàng)是P∨Q,┐P∨Q,P∨┐Q,┐P∨┐Q(不能同時(shí)出現(xiàn)┐Q和Q)大項(xiàng)性質(zhì)：a)每個(gè)大項(xiàng)當(dāng)指派真值與編碼相同時(shí)，其值為(例如當(dāng)P，Q，R全部為F的時(shí)候大項(xiàng)b)任意兩個(gè)大項(xiàng)合取值為c)全部大項(xiàng)合取值為F，否則全為T(mén)(共2n-1個(gè))P∨Q∨R才為F，否則全部為T(mén))TT找主合取范式的方法步驟e)劃歸為合取范式；f)去除范式中的永真合取值項(xiàng)(例如P∨┐P)；g)重復(fù)析取項(xiàng)和相同的變?cè)喜?；h)對(duì)析取補(bǔ)沒(méi)有出現(xiàn)的命題變?cè)刺砑?P∧┐P)式，應(yīng)用分配律展開(kāi)公式。主合取范式與主析取范式關(guān)系及整理技巧(以3個(gè)變?cè)獮槔?小項(xiàng)┐P∧┐Q∧┐R┐P∧┐Q∧R┐P∧Q∧┐R┐P∧Q∧RP∧┐Q∧┐RP∧┐Q∧RP∧Q∧┐R解釋000001010011100101110111記法大項(xiàng)解釋記法M0M1M2M3M4M5M6M7mP∨Q∨RP∨Q∨┐R0000123mmm001010011100101110111P∨┐Q∨RP∨┐Q∨┐R┐P∨Q∨R┐P∨Q∨┐R┐P∨┐Q∨R┐P∨┐Q∨┐Rm4m5m6m7P∧Q∧R小項(xiàng)大項(xiàng)反過(guò)來(lái)合取范式∑(m1,m3,m5,m6,m7)<==>析取范式∏(M0,M2,M4)例如：(P∨(Q∧R))→(P∧Q∧R)主析取范式和主合取范式<=>┐(P∨(Q∧R))∨(P∧Q∧R)<=>(┐P∧┐(Q∧R))∨(P∧Q∧R)<=>(┐P∧┐Q)∨(┐P∧┐R)∨(P∧Q∧R)<=>(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)∨(┐P∧Q∧┐R)∨(┐P∧┐Q∧┐R)∨(P∧Q∧R)001000010111<=>(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(P∧Q∧R)主析取范式000001010111(011,100,101,110)的編號(hào)次序，但是大項(xiàng)000求主合取范式過(guò)程按照上面的取值取反應(yīng)該是小項(xiàng)的編碼是相反的，然后吧∧互換∨，因而住合取范式為：<=>(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)推理理論：(必考☆☆☆☆)☆直接證明：由一組前提，利用公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)和蘊(yùn)含公式，有效的結(jié)論P(yáng)規(guī)則：前提在推導(dǎo)過(guò)程中的任推演出何時(shí)候都可以引入使用Page3of26離散數(shù)學(xué)復(fù)習(xí)材料T規(guī)則：在推導(dǎo)中，如果有一個(gè)或多個(gè)公式、重言蘊(yùn)含著公式S，則S可以引入推導(dǎo)中。常用蘊(yùn)含式和等價(jià)(等值)式表：I1P∧Q=>PI2P∧Q=>QI3P=>P∨QI4Q=>P∨QI5┐P=>P→QI6Q=>P→QI7┐(P→Q)=>PI8┐(P→Q)=>┐QI9P,Q=>P∧QE1E2E3E4E5E6E7E8E9┐┐P<=>PP∧Q<=>Q∧PP∨Q<=>Q∨P(P∧Q)∧R<=>P∧(Q∧R)(P∨Q)∨R<=>P∨(Q∨R)P∧(Q∨R)<=>(P∧Q)∨(P∧R)P∨(Q∧R)<=>(P∨Q)∧(P∨R)┐(P∧Q)<=>┐P∨┐Q┐(P∨Q)<=>┐P∧┐QI10┐P,P∨Q=>QI11P,P→Q=>QE10P∧P<=>PE11P∨P<=>PI12┐Q,P→Q=>┐PI13P→Q,Q→R=>P→RI14P∨Q,P→R,Q→R=>RI15P→Q=>(P∨R)→(Q∨R)I16P→Q=>(P∧R)→(Q∧R)E12R∨(P∧┐P)<=>RE13R∧(P∨┐P)<=>RE14R∨(P∨┐P)<=>TE15R∧(P∧┐P)<=>FE16P→Q<=>┐P∨QE17┐(P→Q)<=>P∧┐QE18P→Q<=>┐Q→┐PE19P→(Q→R)<=>(P∧Q)→RE20PQ<=>(P→Q)∧(Q→P)E21PQ<=>(P∧Q)∧(┐P∧┐Q)E22┐(PQ)<=>P┐Q☆實(shí)例直接證明：(P∨Q)∧(P→R)∧(Q→S)=>S∨RP∨Q，Q→R，P→S，┐S=>R∧(P∨Q)證明：證明：(1)┐S(1)P∨Q(2)┐P→Q(3)Q→S(4)┐P→S(5)┐S→P(6)P→RP（已知條件）PT(1)E(P∨Q<=>┐P→Q)P（已知條件）(2)P→S(3)┐PPT(1)(2)EPT(2)(3)I(┐P→Q,Q→S=>┐P→S)傳遞關(guān)系(4)P∨QT(4)E(┐P→S<=>P∨S<=>S∨P<=>┐S→P）(5)┐P∧QT(3)(4)ET(5)IPP（已知條件）T(5)(6)I(┐S→P,P→R)傳遞關(guān)系T(7)I(6)Q(7)┐S→R(8)S∨R(7)Q→R(8)RT(6)(7)I(9)R∧(P∨Q)T(4)(8)I即根據(jù)條件命題，通過(guò)利用蘊(yùn)含表或等價(jià)表中的某些規(guī)則，將條件轉(zhuǎn)化為右值命題的過(guò)程，因此可能證明方式和過(guò)程不唯一?！铋g接證明方法：把需要推導(dǎo)出的結(jié)論，取┐后，作為附加條件引入證明中，且最后證明結(jié)論是矛盾的。Page4of26離散數(shù)學(xué)復(fù)習(xí)材料(P∨Q)∧(P→R)∧(Q→S)=>S∨RP∨Q，Q→R，P→S，┐S=>R∧(P∨Q)證明：證明：(1)┐(R∧(P∨Q))(2)P∨Q(1)┐(S∨R)(2)┐S∧┐R(3)P∨QP(附加條件)P(附加條件)T(1)EPP(用了2次)P(3)P→S(4)┐P→QT(3)P(4)┐SP(5)Q→S(5)┐PT(3)(4)ET(2)(5)ET(6)I(6)┐P→ST(4)(5)IT(6)ET(7)IT(8)IP(6)┐P∧Q(7)Q(7)┐S→P(8)(┐S∧┐R)→(P∧┐R)(9)P∧┐R(8)Q→R(9)RPT(7)(8)ET(2)(9)(10)P→R(10)R∧(P∨Q)(11)┐(R∧(P∨Q))∧(R∧(P∨Q))矛盾T(1)(10)(11)┐P∨R(12)┐(P∧┐R)T(10)ET(11)E(13)┐(P∧┐R)∧(P∧┐R)矛盾T(9)(12)I第二章謂詞邏輯☆量詞：(x)P(x)P(x)1∧P(x2)…∧P(x)nx：對(duì)于所有的客體變?cè)?設(shè)S={x1,x2,…x})nx：對(duì)于一部分客體變?cè)?全稱量詞：)1個(gè))x)P(x)P(x)P(x)…P(x∨∨n存在量詞：合式公式：(至少是121）原子謂詞公式是合式公式；2）若A是合式公式，則┐A也是合式公式；3）若A，B都是合式公式，則，A∧B，A∨B，A→B，AB都是合式公式；4）若A是合式公式，則(x)A，(x)A都是合式公式；5）有限次的應(yīng)用規(guī)則1)2)3)4)所得的公式都是合式公式xA和xA中，稱(作用變?cè)?，稱☆約束變?cè)獂為指導(dǎo)變?cè)狝為相應(yīng)量詞的轄域(作用域)，x稱為約束變?cè)瑇的出現(xiàn)稱為約束出現(xiàn)，A中其他出現(xiàn)的變?cè)Q為自由出現(xiàn)(自由變?cè)?。(x)(y)(A(x,y)∧B(y,z))∧(x)A(x,y)。和自由變?cè)涸诤鲜焦嚼樱杭s束約束約束自由約束自由n元謂詞：若P(x1,x2,…….,xn)，含有n個(gè)相互獨(dú)立的自由變?cè)瑢?duì)其中的k個(gè)變?cè)M(jìn)行約束，則稱之為n-k元謂詞。例子：(y)A(x,y,z)是二元謂詞，約束變?cè)獡Q名：(x)(P(x)→R(x,y))∧Q(x,y)(x)(P(x)→R(x,y))為一元謂詞，x約束變?cè)?，x換成z，即(z)(P(z)→R(z,y))∧Q(x,y)(不要出現(xiàn)與已有的(x)(y)A(x,y,z)則是一元謂詞。y為自由變?cè)?，且原式中x未對(duì)Q(x,y)約束。故而可以把約束變?cè)孛?自由變?cè)耄簓被z代入得到(x)(P(z)∧R(x,z))(不要出現(xiàn)與已有的重名)(x)(P(y)∧R(x,y))，自由變?cè)狿age5of26離散數(shù)學(xué)復(fù)習(xí)材料☆☆☆謂詞演算的等價(jià)式與蘊(yùn)含式命題邏輯和謂詞邏輯存在相同的等價(jià)公式運(yùn)算和蘊(yùn)含運(yùn)算(前邊等價(jià)式和蘊(yùn)含運(yùn)算皆起作用)例如：┐┐PPP∨PP┐┐P(x)P(x)P(x)∨P(x)P(x)因此可以證明下面一系列等價(jià)式和蘊(yùn)含式(x)(P(x)∨Q(x))(x)(P(x))∨(x)(Q(x))(x)(P(x)∧Q(x))(x)(P(x))∧(x)(Q(x))┐(x)P(x)(x)┐P(x)┐(x)P(x)(x)┐P(x)(x)(P(x)∨Q)((x)P(x))∨Q(x)(P(x)∧Q)((x)P(x))∧QE23242526272829EEEEEEx未對(duì)Q有約束x未對(duì)Q有約束(x)(P(x)→Q(x))(x)P(x)→(x)Q(x)(x)(P(x)∧Q)((x)P(x))∧Q(x)(P(x)∨Q)((x)P(x))∨Q(x)P(x)→Q(x)(P(x)→Q)(x)P(x)→Q(x)(P(x)→Q)Q→(x)P(x)(x)(Q→P(x))Q→(x)P(x)(x)(Q→P(x))x未對(duì)Q有約束x未對(duì)Q有約束x未對(duì)Q有約束x未對(duì)Q有約束x未對(duì)Q有約束x未對(duì)Q有約束EEEE30313233☆(x)P(x)∨(x)Q(x)(x)(P(x)∨Q(x))(x)(P(x)∧Q(x))(x)P(x)∧(x)Q(x)(x)P(x)→(x)Q(x)(x)(P(x)→Q(x))(x)(P(x)Q(x))(x)P(x)(x)Q(x)I17I18I19☆☆其它的量詞添加和除去重言式(永真式y(tǒng)是x的一個(gè)個(gè)體y是x的一個(gè)個(gè)體)(x)P(x)P(y)P(y)(x)P(x)(x)P(x)(x)P(x)上兩個(gè)式推導(dǎo)(x)PPx未對(duì)P有約束前束范式：設(shè)A為一謂詞公式，若A具有如下域延伸到公式的末尾(無(wú)自由變?cè)?，稱A為前束范式。(x)(z)形式(x)(y)(z)(Q(x,y)→R(z))的形式，且開(kāi)頭的作用例如：(x)P(x)∨Q(x)(y)P((y)∨Q(x)(x)P(x)→(x)Q(x)(x)(P(x)∨Q(x))☆☆☆謂詞演算的推理理論(必考)1)全稱制定規(guī)則US(x)P(x)P(c)2)全稱推廣規(guī)則UGP(x)(x)P(x)3)存在制定規(guī)則ESPage6of26離散數(shù)學(xué)復(fù)習(xí)材料(x)P(x)P(c)4)全稱制定規(guī)則EGP(c)(x)P(x)Page7of26離散數(shù)學(xué)復(fù)習(xí)材料第三章集合與關(guān)系集合的基本概念：外延性原理：兩個(gè)集合，當(dāng)且僅當(dāng)它們有相同的元素成員(無(wú)序，重復(fù))，或者兩個(gè)集合互為子集AB(x)(x∈A→x∈B)AA(AB)∧(BC)AC真子集：AB(x)(x∈A→x∈B)∧(x(x∈B∧xA)空集：={x|P(x)∧┐P(x)}A(空集屬于任意集合)≠{}，∈{}全集E：E={x|P(x)∨┐P(x)}：設(shè)A={1,2,3}則(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}若有限集合A有n個(gè)元素，(A)有2n個(gè)元素冪集則冪集。集合的基本運(yùn)算：1)交運(yùn)算AA=AA=AE=AAB=BA(AB)C=A(BC)2)并運(yùn)算AABBAB結(jié)合律：A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收律：A(AB)=AA(AB)=AAA=AAE=EA=AAB=BA(AB)C=A(BC)3)補(bǔ)運(yùn)算：記做A—B，即S={x|(x∈A)∧(xB)}A={2,5,6}，B={1,2,4,16,7,8}A—B={5,6}設(shè)定E全集，~A記做絕對(duì)補(bǔ)集：~A=E—A例如：~B~A(B-A)A=B~(~A)=A~E=A~A=EA~A=德摩根：~(AB)=~A~B~(AB)=~A~B若AB則有重要公式：A—B=A~B~=EA—B=A—(AB)=A~(AB)=(A~A)(A~B)A(B—C)=(AB)—(AC)A—(B∪C)=(A~B)(A~C)=(A—B)∩(A—C)A—(B∩C)=(A—B)(A—C)4)對(duì)稱差運(yùn)算：設(shè)A，B兩個(gè)集合，A與B的對(duì)稱差集合S，其元素或?qū)儆贏，或?qū)儆贐，但不能同時(shí)屬于A,B。記做AB=(A—B)(B—A)={x|x∈A▽x∈B}(▽不可兼析、亦或運(yùn)算)例如：E={1,2,3,4,5,6,7,8}A={1,2,5,6}B={2,5,7,8}AB={1,6,7,8}☆對(duì)稱差的幾個(gè)重要等式：8-of26離散數(shù)學(xué)復(fù)習(xí)材料AB=BAA=AAA=AB=(A—B)(B—A)=(A~B)(B~A)(AB)C=A(BC)一階邏輯等值式：設(shè)P，Q是一階邏輯中任意的兩公式，若P?Q為邏輯有效式，則稱P與Q是等值的，記作PQ，稱PQ為等值式。☆序偶：<x,y>=<u,v>當(dāng)且僅當(dāng)(x=u，y=v)☆笛卡爾積：設(shè)A和B為集合，用A中元素為第一元素，用B中元素為第二元素構(gòu)成有序?qū)×B={<x,y>|(x∈A)∧(y∈B)}組成的集合稱為A和B的笛卡爾積，記為A×B。例如：A={x,y}B={1,2,3}A×B={<x,1>,<x,2>,<x,3>,<y,1>,<y,2>,<y,3>}B×A={<1,x>,<1,y>,<2,x>,<2,y>,<3,x>,<3,y>}結(jié)論：A×BB×A(A×B)×CA×(B×C)(注<<x,y>,z><x,<y,z>>)同理：A×(BC)=(A×B)(A×C)A×(BC)=(A×B)(A×C)(AB)×C=(A×C)(B×C)(AB)×C=(A×C)(B×C)A×BC×D(AC，BD)當(dāng)四個(gè)非空集合:幾個(gè)關(guān)鍵證明：9-of26離散數(shù)學(xué)復(fù)習(xí)材料10-of26離散數(shù)學(xué)復(fù)習(xí)材料二元關(guān)系的運(yùn)算：二元關(guān)系：如果一個(gè)集合R為空集或者它的元素都是有序?qū)?，則稱集合R是一個(gè)二元關(guān)系。記做：<x,y>∈R或xRy否則<x,y>RR是二元關(guān)系，(1)R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為二元關(guān)系的運(yùn)算：設(shè)R的定義域domR={x|y(<x,y>∈R)}(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域ranR={y|x(<x,y>∈R)}(3)R的定義域和值域的并集稱為R的域fldR=domRranR：H={<1,2>,<1,4>,<2,4>,<3,4>}例如domH={1,2,3}ranH={2,4}fldH={1,2,3,4}特殊關(guān)系：(1)空關(guān)系：Φ(2)全域關(guān)系：E={<x,y>|x∈A∧y∈A}=A×AA(3)恒等關(guān)系：I={<x,x>|x∈A}A(4)小于等于關(guān)系：L={<x,y>|x,y∈A∧x≤y∈A},ARA(5)整除關(guān)系：R={<x,y>|x,y∈ψ∧xy},ψ是集合族二元關(guān)系的性質(zhì)：(可以用矩陣或有向圖來(lái)表示二元關(guān)系)自反性：(x)(x∈X→xRx)例如實(shí)數(shù)關(guān)系的≤≥就是自反的(x≤x,x≥x)有向圖中的自環(huán)，矩陣中的對(duì)角線元素不為0對(duì)稱性：(x)(y)(x∈X∧y∈X∧xRy→yRx)有向圖中的兩個(gè)頂點(diǎn)相互指向，矩陣是對(duì)稱的傳遞性：(x)(y)(z)(x∈X∧y∈X∧z∈X∧xRy∧yRz→xRz)例如實(shí)數(shù)集合中的“≤”,“<”,“=”都是傳遞的反自反性：(x)(x∈X→<x,x>R)例如父子關(guān)系是反自反的(非自反的不一定是反自反的)例如：A={1,2,3}S={<1,1>,<1,2>,<3,2>,<2,3>,<3,3>}2∈A,但是<2,2>S因此S不是自反關(guān)系的1∈A,3∈A,但是<1,1><3,3>∈S，也不是反自反關(guān)系的反對(duì)稱性：(x)(y)(x∈X∧y∈X∧xRy∧yRx→x=y)11-of26離散數(shù)學(xué)復(fù)習(xí)材料例如實(shí)數(shù)關(guān)系的”≤”是反對(duì)稱的，””也是反對(duì)稱的(x)(y)(x∈X∧y∈X∧x≠y∧xRy→yRx)例如：A={1,2,3}，S={<1,1>,<2,2>,<3,3>}S既是對(duì)稱的也是反對(duì)稱的A={a,b,c}，S={<a,b>,<a,c>,<c,a>}S既不是對(duì)稱的也不是反對(duì)稱的☆判斷各類關(guān)系的方法：當(dāng)且僅當(dāng)關(guān)系矩陣上對(duì)角線元素都為非零(1)值是，其存在自反關(guān)系當(dāng)且僅當(dāng)關(guān)系矩陣是對(duì)稱的且在關(guān)系圖上，任意頂點(diǎn)有定向弧成對(duì)出現(xiàn)，其存在對(duì)稱關(guān)系當(dāng)且僅當(dāng)關(guān)系矩陣上對(duì)角線元素都為零，關(guān)系圖頂點(diǎn)無(wú)自回路，其存在反自反關(guān)系當(dāng)且僅當(dāng)關(guān)系矩陣主對(duì)角線不能同時(shí)為1，關(guān)系圖上兩個(gè)不同頂點(diǎn)定向弧不可能成對(duì)出現(xiàn)時(shí)，其存在反對(duì)稱關(guān)系特例：空關(guān)系是對(duì)稱的、可傳遞的、反對(duì)稱的全域關(guān)系A(chǔ)×A是自反的、對(duì)稱的、可傳遞的復(fù)合關(guān)系：設(shè)R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則符合關(guān)系R?S表示為R?S={<x,z>|x∈X∧z∈Z∧(y)(y∈Y∧<x,y>∈R∧<y,z>∈S)R={<1,2>,<3,4>,<2,2>}X={a,b,c}R={<a,b,><b,c>,<c,a>}S={<4,2>,<2,5>,<3,1>,<1,3>}則：則：R?R=R2={<a,c>,<b,c>,<c,b>}R?S={<1,5>,<3,2>,<2,5>}S?R={<4,2>,<3,2>,<1,4>}IR?R?R=R3={<a,a>,<b,b>,<c,c>}=x(R?S)?R={<3,2>}R?(S?R)={<3,2>}R?R={<1,2>,<2,2>}R?R?R={<1,2>,<2,2>}S?S={<4,5>,<3,3>,<1,1>}推導(dǎo)出其它常用的幾個(gè)公式：(約定X集合，R是X的二元關(guān)系)R0=XR?R?R……?R記做R(m)mRm?R=Rm+11,x,yRuijij如上所述，關(guān)系可以以關(guān)系矩陣形式表達(dá)0,x,yRij同理可以知道R?S的矩陣MR?S(實(shí)際上是R矩陣與S矩陣相乘，且結(jié)果是非0即1)逆關(guān)系☆：R={<y,x>|<x,y>∈R},例如：R={<1,a>,<3,b>,<2,c>}則R={<a,1>,<b,3>,<c,2>}c證明(R?S)?Rc(Rc)c=R=Sccc(R1R2)c=R1cRc<z,x>∈(R?S)c<x,z>∈(R?S)(y)(y∈Y∧<x,y>∈R∧<y,z>∈S)(y)(y∈Y∧<y,x>∈Rc∧<z,y>∈Sc)<z,x>Sc?Rc2(RR)c=R1cRc(R)cRc(RABR)122(A×B)c=B×A(R1—R2)c=R1c—Rc證畢2(R?S)=S?Rcc定理3-7.3c12-of26離散數(shù)學(xué)復(fù)習(xí)材料1）對(duì)于R是X的二元關(guān)系，若R是對(duì)稱的則：當(dāng)且僅當(dāng)：R=Rc充分性：R是對(duì)稱的,<x,y>∈R,則<y,x>∈R,又<y,x>∈R，所以R=R，cc必要性：若R=R,則<x,y>∈R=><x,y>∈R=><y,z>∈R,則R一定是對(duì)稱的cc2）對(duì)于R是X的二元關(guān)系，若R是反對(duì)稱的則：當(dāng)且僅當(dāng)：RRcIxR是反對(duì)稱的，<x,y>∈RR<x,y>∈R∧<x,y>∈R<x,y>∈R∧<y,x>∈RR的反對(duì)稱的，所以必有x=y，故RRRRIx，則<x,y>∈RR有<x,y>∈Ix，所以有x=y又<x,y>∈RR則<x,y>∈R且<x,y>∈R<x,y>∈R且<y,x>∈R，又有x=y所以R的反對(duì)稱的充分性：cc由于Ixc必要性：若cccc★閉包關(guān)系(必考、重點(diǎn))定義：R是非空集合A的關(guān)系，R的自反(對(duì)稱或傳遞)的閉包是A的關(guān)系R’：1)R’是自反的(對(duì)稱或傳遞2)RR’3)對(duì)于A上任何包含r(R)記為自反閉包)R的自反(對(duì)稱或傳遞)的關(guān)系R’’,有R’R’’s(R)記為對(duì)稱閉包t(R)記為傳遞閉包最小唯一結(jié)論：R的自反(對(duì)稱或傳遞)閉包是含有R的具有自反(對(duì)稱或傳遞)性質(zhì)的關(guān)系，且是的，(對(duì)稱或傳遞補(bǔ)充序偶)的，則需要，使之變?yōu)榫哂凶苑?對(duì)稱或傳遞)如果R本身不是自反1)R是自反的則r(R)=R2)R是對(duì)稱的則s(R)=R滿足<x,x>∈R’,加上對(duì)角線元素3)R是傳遞的則t(R)=R例子：A={a,b,c}R={<a,b>,<b,c>,<c,a>}r(R)={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}滿足<x,y>∈R’∧<y,x>∈R’，加r(R)=RIA關(guān)系矩陣中的對(duì)稱元R素cs(R)={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}=RRc()ss(R)s(RRc)(RR)(RR)(RRc)s(R)ccct(R)={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,<b,b>,<c,c>}比較復(fù)雜！?。⌒柚饌€(gè)推導(dǎo)R+=t(R)Rii1定理3-8.61)rs(R)=sr(R)rs(R)sr(R)=s(RIx)=(RIx)(RIx)c=(RIx)(RcIxc)=Ix(RRc)=2)R*=rt(R)=tr(R)itr(R)t(IR)(IR)i(IRj)XXXi1i1j1RjIRiIIi()()tRrtRXXXi1j113i-1of26離散數(shù)學(xué)復(fù)習(xí)材料3)st(R)ts(R)Rs(R)t(R)ts(R)st(R)sts(R)∴sts(R)=ts(R)(ts(R))c∵st(R)ts(R)(ts(R))cst(R)ts(R)★集合劃分與覆.蓋設(shè)定一個(gè)集合A，把A的元素分塊成非空子集，使得每個(gè)元素至少屬于一個(gè)子集。A的~；(分塊之間不存在相同元素)，分塊集合稱為~；(空集不存在~)A的劃分方式多種，不同劃分方式下，各個(gè)子集交叉AB的集合稱為覆蓋：每個(gè)分塊構(gòu)成的集合稱為劃分：每個(gè)元素僅僅屬于一個(gè)分塊交叉劃分：集合~ij例如：A={a,b,c,d,e,f}S1={{a,b},{b,c,d},{d,e,f}}S2={{a},{b,c,d},{d,e,f}}S1,S2稱為Q1={{a,b},{c,d},{e,f}}Q2={{a},{b,c,d},{e,f}}Q1,Q2,Q3,Q4稱為Q3={{a,b,c,d,e,f}}Q3={{a},,{c},p1xdh5l,{e},{f}}Q3是A的最小劃分A的覆蓋)(子集元素交叉n個(gè)分組),Q是A的最大A的劃分(1個(gè)分組4劃分Q1,Q2中的子集{e,f}存在,稱交叉劃分定理：Q1iQ2j構(gòu)成的集合也是A集合的一種劃分。定義：若Q1iQ2j，則稱Q1是Q的加細(xì)劃分個(gè)數(shù):()2個(gè)元素2種本例不存在這個(gè)現(xiàn)象2定理：任何一個(gè)交叉劃分都是原來(lái)各自劃分的一種加細(xì)3個(gè)元素5種4個(gè)元素15種☆等價(jià)關(guān)系：(重點(diǎn)必考)等價(jià)關(guān)系自反的，對(duì)稱的和傳遞的，那么稱R是等價(jià)關(guān)系。：如果集合設(shè)R是A上的等價(jià)關(guān)系，x,y是A的任意元素，記作A={1,2,3,4}R={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}關(guān)系矩陣如下：關(guān)系圖如下：A上的二元關(guān)系R是x～y。例子：關(guān)系矩陣對(duì)角線元素全為1(關(guān)系圖自回路),R是自反的),R是對(duì)稱10010110的12關(guān)系矩陣對(duì)稱元素的值或?yàn)?/0(關(guān)系圖弧成對(duì)出現(xiàn)0110R也是傳遞的100143結(jié)論：R是自反的，對(duì)稱的和傳遞的R是等價(jià)關(guān)系等價(jià)類：設(shè)R是A上的等價(jià)關(guān)系，對(duì)任意的x∈A，令[a]R={x|x∈A,aRx}，稱[a]為關(guān)于aRR的~。另例：[a]且[a]RA顯然：R上例中：[1]=[4]R={1,4}R[2]R=[3]R={2,3}商集：集合A的等價(jià)關(guān)系R，等價(jià)類{[a]|a∈A}，稱作A關(guān)于R的集商記做A/R。R上例中：A/R={[1],[2]}另例中：X/R={[0]R,[1],[2]R}RRR14-of26離散數(shù)學(xué)復(fù)習(xí)材料幾個(gè)特例：全域關(guān)系R=A×A：即恒等關(guān)系R=IA：A/R={[x]R|x∈A}={[x1]R∧[x2]R……∧[xn]R},形成最大劃分[x]=A,A/R={[x]|x∈A},|A/R|=1，形成了最小劃分RR★偏序關(guān)系：(重點(diǎn)、必考)設(shè)R是集合A上的二元關(guān)系，如果R是自反的，反對(duì)稱的和傳遞的，那么稱R為A上的偏序，記作”≤”；稱序偶<A,R>為偏序集合。記做{A,”≤”}，典型的偏序集合“字典順序”例如：A={2,3,6,8}偏序關(guān)系“≤”={<x,y>|x整除y},{A,≤}={<2,2>,<3,3>,<6,6>,<8,8>,<2,6>,<3,6><2,8>}}{A,≤}={<2,2>,<3,3>,<6,6>,<8,8>,<6,2>,<6,3><8,2>}偏序關(guān)系“≤”={<x,y>|x是y的正倍數(shù)偏序關(guān)系的蓋?。簼M足偏序關(guān)系，且在xy(x∈A,y)的條件下不存在z元素(z∈A)使得x“≤”z，且z“≤”y(即不存在中間元素)，則稱y蓋住x。86例如：上例中的COVA={<2,6>,<3,6><2,8>}哈斯圖(頂點(diǎn)圓圈表示自回路A的極大元{6,8}，極小元{2,3}；最大元無(wú)，最小元無(wú)蓋住則指直線連接)23再例子1：A={2,3,6,12,24,36}偏序關(guān)系“≤”={<x,y>|x整除y}{A,”≤”}={<2,2><3,3><6,6><12,12><24,24><36,36><2,6><2,12><2,24><2,36><3,6><3,12><3,2364><3,36><6,12><6,24><6,36><12,24><12,36>}24哈斯圖COVA={<2,6>,<3,6>,<6,12>,<12,24>,<12,36>}126A的極大元{24,36}，極小元{2,3}；最大元無(wú)，最小元無(wú)鏈：<A,”≤”>是一個(gè)偏序集合，A子集中如果每?jī)蓚€(gè)元素之間都有關(guān)系，稱為鏈，否則為反鏈哈斯圖畫(huà)法：231)圓圈表示帶有自回路的元素頂點(diǎn)；2)x≤y且xy，則x畫(huà)在y的下方；3)x≤y且xy，且在集A中不存在任何z∈A，使得z介于x與y之間，則x與y之間用一條直線連接。偏序的哈斯圖是唯一的證明蓋住也是唯一的再例子2：A={1,2,3,4,5,6,7,8,9}偏序關(guān)系”≤”={<x,y>|x整除y}864321{A,”≤”}={省略}COVA={<1,2>,<1,3>,<1,5><1,7>,<2,4>,<2,6>,9<3,6>,<3,9><4,8>}7515-of26離散數(shù)學(xué)復(fù)習(xí)材料A的極大元{5,6,7,8,9}，極小元{1}；最大元無(wú)，最小元1再例子2的哈斯圖再例子3：A={a,b,c}偏序關(guān)系”≤”={<x,y>|xy}{A,”≤”}={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}COVA={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}A的極大元{{a,b,c}}，極小元{}；最大元{a.b,c}，最小元其它類似的例子：再例子3的哈斯圖A的極大元{24}，極小元{1}；最大元24，最小元1A的極大元{7,8,9,10,11,12}，極小元{1}；最大元無(wú)，最小元1幾個(gè)關(guān)鍵名詞設(shè){A，“≤”}為一個(gè)偏序集合，BA，且(一)極大元：B的一個(gè)元素b是B的極大元，即B中找不到比當(dāng)B=A的時(shí)候，哈斯圖的最頂層且無(wú)向上的連線的節(jié)點(diǎn)既是極大元；(二)極小元：當(dāng)B=A的時(shí)候，(特特例：有b，如果B中沒(méi)有任何一個(gè)元素x，滿足b“≤”x，xb，且b“≤”x的元素則稱b還大的且滿足。特例：反之則是極小元。特例：哈斯圖的最下層且無(wú)向下的連線的節(jié)點(diǎn)既是極小元；些元素可能既是極大元也可能是極小元極大元和極小元之間無(wú)關(guān)的。)A的極大元{5,6,7,8,9}，極小元{2,3,5,7}；最大元無(wú)，最小元無(wú){5,7}既是極大元也是極小元(三)最大元:BA，且B的一個(gè)元素b，如果B中任何一個(gè)元素x，有x“≤”b，則稱b是B的最16-of26離散數(shù)學(xué)復(fù)習(xí)材料大元(四)最小元:BA，且B的一個(gè)元素b，如果B中任何一個(gè)元素x，有b“≤”x，則稱b是B的最小元(特特例：最大元最小元唯一且屬于B(或者A)，且與B(或者A)任意元素有關(guān)系，且也可能沒(méi)有)極大元就是上面沒(méi)節(jié)點(diǎn)的極小元最大元最小元就是下面沒(méi)節(jié)點(diǎn)的就是所有節(jié)點(diǎn)的上面(有路徑能連下來(lái)(有路徑能)就是所有節(jié)點(diǎn)的下面連上去)上界：(五)BA，a∈A，且B的任意元素x,有x”≤”a，則稱a是B的上界，最小上界稱為上確x,有a”≤”x，則稱a是B的下界，最大下界稱為下確(下)確界界;下界：(六)BA，a∈A，且B的任意元素界；(特特例：上(下)界不一定存在,上(下)界不一(下)確界(小)元。)定唯一，但上若存在，必唯一。注意：上即某個(gè)偏序集的最大定義：任何一個(gè)偏序集合，假設(shè)它的每個(gè)非空子集存在最小元素，則稱為良序的，每個(gè)良序一定是全序集合。每個(gè)有限的全序集合必定是良序集合。17-of26離散數(shù)學(xué)復(fù)習(xí)材料第四章函數(shù)函數(shù)的性質(zhì)：設(shè)f:AB，(1)若ranf=B，則稱f是滿射(到上)的。B中每個(gè)元素在A中有1個(gè)或多個(gè)象點(diǎn)：A={a,b,c,d}B={1,2,3}若：AB，有f(a)=1,f(b)=2,f(c)=3,f(d)=3;這是滿射f(2)若yranf都存在唯一的xA使得f(x)=y,則稱f是入射(一對(duì)一映射)的。A={a,b}B={1,2,6}若：AB，有f(a)=1,f(b)=2,這是入射f(3)若f既是滿射又是入射的，則稱f是雙射(——到上)的。[a,b]={x|a≤x≤b}，令f:[0,1]→[a,b]，f(x)=(b-a)x+a,這是雙射aaaαβγαβγαβγbcbcbcδεδεdededeδζ入射滿射滿射、入射雙射18-of26離散數(shù)學(xué)復(fù)習(xí)材料第五章代數(shù)結(jié)構(gòu)(群、半群必考)★代數(shù)系統(tǒng)的引入定義：非空集合A定義的若干運(yùn)算f,f,……f組成的系統(tǒng)成為代數(shù)系統(tǒng)；12n★代數(shù)系統(tǒng)運(yùn)算特性封閉運(yùn)算：若對(duì)給定的集合中的元素進(jìn)行運(yùn)算，產(chǎn)生的象點(diǎn)仍在該集合中x*y∈A)，則稱此集合在該運(yùn)算的二元運(yùn)算封閉性：設(shè)*是定義在A上的*在A上是封閉的運(yùn)算若x*y=y*x則稱二元運(yùn)算是可交換的(即x,y∈A都有作用下是封閉的二元運(yùn)算，對(duì)于任意的x,y∈A,都有x*y∈A，則稱二元運(yùn)算若(x*y)*z=x*(y*z),則稱是可結(jié)合的若*,Δ是二元運(yùn)算,有x,y,z∈A,x*(yΔz)=(x*y)Δ(x*z),(yΔz)*x=(y*x)Δ(z*x),則稱為若x*(xΔy)=x，xΔ(x*y)=x滿足吸收律可分配的若x∈A的每個(gè)元素均滿足x*x=x,則稱為是等冪的,即x=x;(如和)若只是存在x∈A滿足nx*x=x,稱為冪等元素幺元：若e*x=x,稱為左幺元l若x*er=x,稱為右幺元若el*x=x*er=x,稱為幺元，若e=e=e，則稱幺元是唯一的。lr零元：若θ*x=θl,稱為左零元l若x*θr=θr,稱為右零元若θl*x=x*θr=θ,稱為零元，若θ=θ=θ，則稱零元是唯一的。lr同理可以推導(dǎo)出<A，*>代數(shù)系統(tǒng)中θ≠e，否則A的元素唯一。[x=e*x=θ*x=e=θ可證明]逆元：設(shè)e是幺元，若a,b∈A，若b*a=e,稱為左逆元設(shè)e是幺元，若a,b∈A，若a*b=e,稱為右逆元若b既是左逆元又是右逆元，則稱為逆元，記做x的逆元x-1定理5-2.4：若<A,*>代數(shù)系統(tǒng)存在=逆元且唯一。[設(shè)xl,xr分別為x的左右逆元，唯一性：設(shè)x1,x2是x的逆元，則x=x1*e=x1*（x*x2）-1-1-1-11e幺元，每個(gè)元素都有左逆元，且*是可結(jié)合的，那么左逆元=右逆元∵xl*x=e,x*xr=e；∴xl*x=x*xr=e,xl*x*xr=(xl*x)*xr=e*xr=xr;=（x1-1*x）*x2-1=e*x2-1=x另∴xl*x*xr=xl*(x*xr)=xl*e=xl,-1-1-12因此逆元是唯一的∴xr=xl]定理可推出(x)=x,e=e，零元不存在逆元?。?！-1-1-119-of26離散數(shù)學(xué)復(fù)習(xí)材料★半群封閉的、可結(jié)合的半群：代數(shù)系統(tǒng)<S,*>，其中S一個(gè)非空集合，*是S上的二元運(yùn)算，且(若滿足交換律則成為交換半群)。若BS,*運(yùn)算在封閉的，則<B,*>也是一個(gè)半群且是<S,*>的子半群。含有幺元的半群稱為獨(dú)異點(diǎn)(含幺半群)也記做<S,*,e>，“∪”和“∩”均滿足結(jié)合律和交換律，因此它們是可交換的半群*[(x*y)*z=x*(y*z)]，則稱<S,*>為一個(gè)半群B也是特例：運(yùn)算若：<S,*>為獨(dú)異點(diǎn)(含幺半群)，則a,b∈S時(shí)均有逆元，則(a-1)-1=a(a*b)-1=b-1*a-1★群與子群封閉的、可結(jié)合的、群：若<G,*>是一個(gè)代數(shù)系統(tǒng)，G是非空集合，*是G的二元運(yùn)算，若*是存在幺元它的逆元x-1，則稱<G,*>是一個(gè)群。若e的，且每個(gè)元素x∈G，都有G是有限個(gè)元素的個(gè)數(shù)(階)，記做|G|，若G無(wú)限個(gè)元素，則<G,*>是無(wú)限群。各類群的關(guān)系(包含關(guān)系)群的幾個(gè)特性：1)群<G,*>一定沒(méi)有相同的行(和列)θ*x=x*θ=θ≠e，零元2)群<G,*>不存在零元[即x∈G，θ不存在逆元，與群的定義矛盾，故...]3)群<G,*>,a,b∈G，必然存在一個(gè)x∈G，使得a*x=b，也必然存在一個(gè)y∈G，使得y*a=b。證明：證明：∵b=e*b=(a*a-1)*b=a*(a-1*b)∴x=a-1*b時(shí)滿足a*x=b唯一性證明：∵b=b*e=b*a-1*a=(b*a-1)*a∴y=b*a-1時(shí)滿足y*a=b唯一性證明：設(shè)另外的一個(gè)x滿足a*x0=b設(shè)另外的一個(gè)y滿足y0*a=b00∵a*x=b,a*x0=b即a*x=a*x0∵y*a=b,y0*a=b即y*a=y0*a∴a-1*a*x=a-1*a*x0=>e*x=e*x0=>x=x0∴y*a-1*a=y0*a-1*a=>e*y=e*y0=>y=y04)群<G,*>,a,b,c∈G，若a*b=a*c或者b*a=c*a，則必有b=c。[加上a-1消去兩邊證明]5)群<G,*>,G是一個(gè)非空集合，例如G={a,b,c,d},映射a->b,b->d,c->a,d->c,這個(gè)置換表示為：bdacG到G的雙射稱為G的一個(gè)置換abcd20-of26離散數(shù)學(xué)復(fù)習(xí)材料6)群<G,*>運(yùn)算表置換的每一行或每一列都是G的元素的一個(gè)置換。7)代數(shù)系統(tǒng)<G,*>,a∈G,a*a=a則稱為等冪元，在群<G,*>,a∈G,a*a=a，則a=e是幺元，無(wú)其它元素是等冪的。8)SG，群<S,*>是<G,*>的子群，<G,*>的幺元e也是<S,*>的幺元。子群：SG，群<S,*>是<G,*>的子群，滿足三個(gè)條件：1)e是<G,*>的幺元，且e∈S2)a∈S且a-1∈S……幺元……逆元……封閉3)a,b∈S且a*b∈S特例1：當(dāng)S={e}或者S=G的，則稱群<S,*>是<G,*>的平凡子群，其它的稱為真子群。特例2：SG，只要二元運(yùn)算*在S是封閉，<S,*>也是<G,*>的子群。特例2證明：因?yàn)?在B是滿足封閉性，故b∈B,有b2∈B,b3∈B,b4∈B…..B是一個(gè)有限集，存在i,j（設(shè)i<j）bi=bj，bi=bi*bj-i，可知bj-i是幺元也在B集中。當(dāng)j-i>1，bj-i=b*bj-i-1，bj-i-1∈B故bj-i-1是b的逆元。當(dāng)j-i=1，bi=bi*b,b是幺元b∈B，也是逆元。因此<B,*>是子群特殊定理(證明子群的方法)：定理5.4-8<G,*>是群，B是G的非空子集，若a,b∈B,且a*b-1∈B,<B,*>也是<G,*>的子群。1)a*b-1∈B=>a*a-1∈B,即e∈B幺元2)a*b-1∈B=>e*a-1∈B,即a-1∈B逆元3)a*b-1∈B=>b-1∈B是b的幺元封閉因?yàn)椋?b)=b∈B,則a*b=a*(b)∈B證畢。-1-1-1-1★阿貝爾群與循環(huán)群，G是非空集合，*是G的二元運(yùn)算，若*是封閉的、是可阿貝爾群：若<G,*>是一個(gè)代數(shù)系統(tǒng)結(jié)合的、存在幺元e、且可交換的的，且每個(gè)元素x∈G，都有它的逆元x，則稱<G,*>是-1一個(gè)阿貝爾群。例如：G={1,2,3,4}F={f,f,f,f0123}1234f1234f212341234ff4(雙射置換f3)02341341241231234f是幺元，矩陣是對(duì)稱的，f，f3是互為逆元的，f，f1逆元是自己010(a*b)*(a*b)=(a*a)*(b*b)二元運(yùn)算*是可交換的特殊群，成立的充要條件是：證明：充分性：即(a*b)*(a*b)=(a*a)*(b*b)=>a*b=b*a=><G,*>是阿貝爾群∵(a*a)*(b*b)=a*(a*b)*b且(a*b)*(a*b)∴a*(a*b)*b=a*(b*a)*b=>a*b=b*a∴<G,*>是阿貝爾群必要性：<G,*>是阿貝爾群∵<G,*>是阿貝爾群(支持可交換∴a,b∈G,有a*b=b*a=>(a*b)*(a*b)=(a*a)*(b*b))(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)21-of26離散數(shù)學(xué)復(fù)習(xí)材料重要推論：阿貝爾群的特殊性質(zhì)(a*b)-1=b-1*a-1=a-1*b-1循環(huán)群：若<G,*>是一個(gè)群，g∈G，且G中的每一個(gè)元素a，使得G中的任意元素都可以表示為g的形式。稱<G,*>循環(huán)群，g稱為生成元。n60就<{0是,60,120,240,300,180},*>的生成元，因此也是循環(huán)群60<{0,60,120,240,300,180},*>例如：重要推論：循環(huán)群必定是阿貝爾群。<G,*>是循環(huán)群，g是生成元(它生成了群),若存在一個(gè)正整數(shù)m，使得gm=e,則最小的那個(gè)正整數(shù)m稱為生成元g的周期，如不存在，則周期無(wú)窮大。第七章圖論☆圖的基本概念無(wú)向圖：是一個(gè)有序的二元組<V,E>，記作G，其中：(1)VФ稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或頂點(diǎn)。(2)E為邊集，它是無(wú)序積V&V的多重子集，其元素稱為無(wú)向邊，簡(jiǎn)稱邊。有向圖：是一個(gè)有序的二元組<V,E>,記作D,其中(1)V同無(wú)向圖。(2)E為邊集，它是笛卡爾積VV的多重子集，其元素稱為有向邊。設(shè)G=<V,E>是一個(gè)無(wú)向圖或有向圖。有限圖：若n階圖：若|V|=n，稱G為n階圖。零圖：若|E|=0，稱G為零圖,當(dāng)|V|=1時(shí)，稱G為平凡圖。V,E是有限集，則稱G為有限圖?；鶊D：將有向圖變?yōu)闊o(wú)向圖得到的新圖，稱為有向圖的基圖。完全圖：每對(duì)頂點(diǎn)之間都有邊相連的圖，稱為完全圖。補(bǔ)圖：G，完全圖減去圖得到的圖是補(bǔ)圖。G’=<V,E-EG>V’=V，E’E稱之為生成子圖。子圖：G’=<E’,V’>且E’E,V’V,G’稱為G的子圖，若圖的同構(gòu)：在用圖形表示圖時(shí)，由于頂點(diǎn)的位置不同，邊的形狀不同，同一個(gè)事物之間的關(guān)系可以用不同的圖表示，這樣的圖稱為圖同構(gòu)。如一果個(gè)圖同構(gòu)與它的補(bǔ)圖，則稱為自補(bǔ)圖。圖同構(gòu)的必要單非充分條件：1)頂點(diǎn)數(shù)目相同；2)邊數(shù)相同；3)度數(shù)相同的結(jié)點(diǎn)數(shù)目相同；帶權(quán)圖：在處理有關(guān)圖的實(shí)際問(wèn)題時(shí)，往往有值的存在，一般這個(gè)值成為權(quán)值，帶權(quán)值的圖稱為帶權(quán)圖或賦權(quán)圖。討論：定理7-1.1，任何圖中頂點(diǎn)度數(shù)之和是邊數(shù)的定理7-1.2，任何圖中度數(shù)為奇數(shù)的頂點(diǎn)必定是定理7-1.3，任何圖中頂點(diǎn)入度和是出度和；2倍；(環(huán)的度數(shù)增加2)偶數(shù)個(gè)；圖的最大度：△(G)=max{degv|v∈V(G)}22-of26離散數(shù)學(xué)復(fù)習(xí)材料圖的最小度：δ(G)=min{degv|v∈V(G)}n*(n1)*(1)nn條邊)(沒(méi)有自回路)定理7-1.4，無(wú)向圖是：條邊，有向圖是：2☆路與回路定理7-2.1：n個(gè)頂點(diǎn)的圖中，如果有vi到vk的一條路，則必存在不多于n-1條的路。連通圖：若無(wú)向圖是平凡圖，或圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖。否則稱為非連通圖。設(shè)D是一個(gè)有向圖，如果D的基圖是連通圖，則稱D是弱連通圖，若D中任意兩個(gè)頂點(diǎn)至少一個(gè)可達(dá)另一個(gè)，則稱D是單向連通圖。若D中任意兩個(gè)頂點(diǎn)是相互可達(dá)的，則稱D是強(qiáng)連通圖。幾個(gè)概念：割點(diǎn)集：無(wú)向圖G=<V,E>是連通圖，V’V，G中刪去V’中所有頂點(diǎn)后，所得到的子圖是不連通的，而刪除了V’的任意一真子集后，所得到的子圖仍然是連通圖，則稱V’是G一個(gè)點(diǎn)割集，若V’只有一個(gè)點(diǎn)，則稱之為割點(diǎn)。定義k(G)=min{|V’||V’是G的點(diǎn)割集}為點(diǎn)的連通度，使得產(chǎn)生不連通圖而刪除的點(diǎn)的最小數(shù)目。0圖不連通1僅存在割點(diǎn)k(Kp)=p-1完全圖K刪除m<p-1個(gè)點(diǎn)仍然連通，但是刪除p-1個(gè)頂點(diǎn)之后變?yōu)槠椒矆D(|V|=1)p邊割集：無(wú)向圖G=<V,E>是連通圖，E’E，G中刪去E’中所有的邊之后得到的子圖不上連通圖，而刪除了E’的任意一真子集后，所得到的子圖仍然是連通圖，則稱E’是G一個(gè)邊割集，若E’只有一個(gè)邊，則稱之為割邊(橋)。0平凡圖和不連通圖定義λ(G)=min{|E’||E’是G的邊割集}為邊的連通度{v3,v5},{v2},{v6}為點(diǎn)割集{v2,v4}不是點(diǎn)割集，因?yàn)樗恼孀蛹瘂v2}已經(jīng)是點(diǎn)割集了{(lán)v1,v6}不是點(diǎn)割集，因?yàn)樗恼孀蛹瘂v6}已經(jīng)是點(diǎn)割集了{(lán)e3,e4}{e4,e5}{e1,e2,e3}{e1,e2,e4}{e9}等都是邊割集，其中{e9}是橋{e6,e7,e9}不是割集，因?yàn)樗恼孀蛹瘂e9}已是邊割集。{e6,e8,e1,e2,e5}也不是邊割集k(G)≤λ(G)≤δ(G)定理7-2.2：任意一個(gè)圖G有(點(diǎn)割集≤邊割集≤圖的最小度數(shù))證明：1）若G是不連通的，則(G)=0，不等式成立；2）若G是連通的例如v6λ(G)<3δ(G)=31o：證明λ(G)≤δ(G)若G是一個(gè)平凡圖，則λ(G)=0≤δ(G)若G是非平凡圖，則λ(G)≤δ(G)因?yàn)槊宽旤c(diǎn)的個(gè)邊割集包含在該頂點(diǎn)的關(guān)聯(lián)邊中2o：再證k(G)≤λ(G)若λ(G)=1，即G有一個(gè)割邊，則k(G)=1若λ(G)≥2，由定義可知，刪去λ(G)條邊G不連通，刪除λ(G)-1條邊G仍然是連通的。且至少在λ(G)上存在橋設(shè)為e=(u,v)。對(duì)λ(G)-1條邊中的每一條邊都選與取u,v不同的頂點(diǎn)，23-of26離散數(shù)學(xué)復(fù)習(xí)材料而把這些頂點(diǎn)刪除必定減少λ(G)-1條邊若這樣產(chǎn)生的圖不連通則k(G)≤λ(G)-1≤δ(G)是連通的，則e是橋，此時(shí)再刪去u或v產(chǎn)生了不連通的圖，故k(G)≤λ(G)由上述證明命題成立。定理7-2.3：v是割點(diǎn)的充要條件是存在u，w兩個(gè)頂點(diǎn)，使得u，w之間每條路都要經(jīng)過(guò)v。定理7-2.4：有向圖是連通的當(dāng)且僅當(dāng)G中有一個(gè)回路它至少包含每個(gè)頂點(diǎn)一次。定理7-2.5：有向圖G=(V,E)每個(gè)頂點(diǎn)位于且只位于一個(gè)強(qiáng)分圖之內(nèi)。圖矩陣☆鄰接矩陣：A(G)上的元素aijaij=0，vi和vj不存在直接到達(dá)的邊aij=1，vi和vj存在直接到達(dá)的邊矩陣P是鄰接矩陣。定理7-3.1：設(shè)A(G)是G的鄰接矩陣表示，A(G)l上的a的值是G中聯(lián)結(jié)v和v的長(zhǎng)度為l路的數(shù)lijij目。圖的可達(dá)矩陣：pij=0，vi和vj不存在通路pij=1，vi和vj至少存在1條通路P是可達(dá)矩陣。P=A∨A2∨A3……∨An的最終結(jié)果將0映射為G=(V,E),|V|=n且G已經(jīng)編號(hào)頂點(diǎn)V={v1,v2,……vn}，n×n的矩陣P=(pij)矩陣0，非0映射為1。關(guān)聯(lián)矩陣表示：(1)無(wú)向圖的關(guān)聯(lián)矩陣：設(shè)無(wú)向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，令mij為頂點(diǎn)v邊與的i關(guān)聯(lián)次數(shù)，則稱(m)nm為G的關(guān)聯(lián)矩陣。記為M(G)。ij(2)有向圖的關(guān)聯(lián)矩陣：設(shè)無(wú)向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，1vi是ej的始點(diǎn)vi與ej不關(guān)聯(lián)mij=0-1vi是ej的終點(diǎn)則稱(mij)nm為D的關(guān)聯(lián)矩陣。記M(D)。距離矩陣表示：dij=∞dii=0dij=k<vi,vj>=∞自環(huán)為0k使得aij(k)≠0☆歐拉圖與哈密頓圖歐拉圖：平凡