離散數學復習材料第一章命題邏輯一、等價公式(真值表)`1)常用聯結詞：┐否定∨析取∧合取PTF┐PFPTTFFQTFTFP∨QPTTFFQTFTFP∧QTTTFTFFFT→：條件：雙條件當且僅當Q取值為F時P→Q為F，否則為TPTTFFQTFP→Q(┐P∨Q)PTTFFQTFPQTFTTTFFTTFTF★等價公式表(等值公式表常用的其它真值表)雙重否┐┐P<=>P定P∨P<=>P冪等律P∧P<=>P(P∧Q)∧R<=>P∧(Q∧R)(P∨Q)∨R<=>P∨(Q∨R)P∧Q<=>Q∧P結合律交換律分配律吸收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)離散數學復習材料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)當P→Q是一個重言式(永真式)稱P蘊含Q記做P=>Q★蘊含公式表：此表可以理解為子集=>全集)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對偶式與范式：性質：┐A(P1,P2…..Pn)<=>A*(┐P1,┐P2……┐Pn)A(┐P1,┐P2……┐Pn)<=>┐A*(P1,P2…..Pn)主析取范式：設命題公式A中含n個命題變項，如果A得析取范式中的簡單合取式全是小項，則稱該析取范式為A的主析取范式。(即A∨A2∨…..∨An形式)1例如：P,Q的小項是P∧Q,┐P∧Q,P∧┐Q,┐P∧┐Q(不能同時出現┐Q和Q)小項性質：a)每個(例如當P，Q，R全部為b)任意兩個c)全部小項析取值為范式的方法步驟a)劃歸為b)去除范式中的永假析取值項(例如P∧┐P)；c)重復d)對合取主合取小項當指派真值與編碼相同時，其值為T，否則全為F(共2n-1個)T的時候小項P∧Q∧R才為T，否則全部為F)小項合取值為FT找主析取析取范式；合取項和相同的變元合并；補沒有出現的命題變元，即添加(P∨┐P)式，應用分配律展開公式。中的簡單合析范式：設命題公式A中含n個命題變項，如果A得析取范式Page2of26離散數學復習材料式全是大項，則稱該析取范式為A的主析取范式。例如：P,Q的大項是P∨Q,┐P∨Q,P∨┐Q,┐P∨┐Q(不能同時出現┐Q和Q)大項性質：a)每個大項當指派真值與編碼相同時，其值為(例如當P，Q，R全部為F的時候大項b)任意兩個大項合取值為c)全部大項合取值為F，否則全為T(共2n-1個)P∨Q∨R才為F，否則全部為T)TT找主合取范式的方法步驟e)劃歸為合取范式；f)去除范式中的永真合取值項(例如P∨┐P)；g)重復析取項和相同的變元合并；h)對析取補沒有出現的命題變元，即添加(P∧┐P)式，應用分配律展開公式。主合取范式與主析取范式關系及整理技巧(以3個變元為例)小項┐P∧┐Q∧┐R┐P∧┐Q∧R┐P∧Q∧┐R┐P∧Q∧RP∧┐Q∧┐RP∧┐Q∧RP∧Q∧┐R解釋000001010011100101110111記法大項解釋記法M0M1M2M3M4M5M6M7mP∨Q∨RP∨Q∨┐R0000123mmm001010011100101110111P∨┐Q∨RP∨┐Q∨┐R┐P∨Q∨R┐P∨Q∨┐R┐P∨┐Q∨R┐P∨┐Q∨┐Rm4m5m6m7P∧Q∧R小項大項反過來合取范式∑(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)的編號次序，但是大項000求主合取范式過程按照上面的取值取反應該是小項的編碼是相反的，然后吧∧互換∨，因而住合取范式為：<=>(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)推理理論：(必考☆☆☆☆)☆直接證明：由一組前提，利用公認的推理規則，根據已知的等價和蘊含公式，有效的結論P規則：前提在推導過程中的任推演出何時候都可以引入使用Page3of26離散數學復習材料T規則：在推導中，如果有一個或多個公式、重言蘊含著公式S，則S可以引入推導中。常用蘊含式和等價(等值)式表：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☆實例直接證明：(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)傳遞關系(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)傳遞關系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即根據條件命題，通過利用蘊含表或等價表中的某些規則，將條件轉化為右值命題的過程，因此可能證明方式和過程不唯一。☆間接證明方法：把需要推導出的結論，取┐后，作為附加條件引入證明中，且最后證明結論是矛盾的。Page4of26離散數學復習材料(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：對于所有的客體變元(設S={x1,x2,…x})nx：對于一部分客體變元(全稱量詞：)1個)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）有限次的應用規則1)2)3)4)所得的公式都是合式公式xA和xA中，稱(作用變元)，稱☆約束變元x為指導變元A為相應量詞的轄域(作用域)，x稱為約束變元，x的出現稱為約束出現，A中其他出現的變元稱為自由出現(自由變元)。(x)(y)(A(x,y)∧B(y,z))∧(x)A(x,y)。和自由變元：在合式公式例子：約束約束約束自由約束自由n元謂詞：若P(x1,x2,…….,xn)，含有n個相互獨立的自由變元，對其中的k個變元進行約束，則稱之為n-k元謂詞。例子：(y)A(x,y,z)是二元謂詞，約束變元換名：(x)(P(x)→R(x,y))∧Q(x,y)(x)(P(x)→R(x,y))為一元謂詞，x約束變元，x換成z，即(z)(P(z)→R(z,y))∧Q(x,y)(不要出現與已有的(x)(y)A(x,y,z)則是一元謂詞。y為自由變元，且原式中x未對Q(x,y)約束。故而可以把約束變元重名)自由變元代入：y被z代入得到(x)(P(z)∧R(x,z))(不要出現與已有的重名)(x)(P(y)∧R(x,y))，自由變元Page5of26離散數學復習材料☆☆☆謂詞演算的等價式與蘊含式命題邏輯和謂詞邏輯存在相同的等價公式運算和蘊含運算(前邊等價式和蘊含運算皆起作用)例如：┐┐PPP∨PP┐┐P(x)P(x)P(x)∨P(x)P(x)因此可以證明下面一系列等價式和蘊含式(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未對Q有約束x未對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未對Q有約束x未對Q有約束x未對Q有約束x未對Q有約束x未對Q有約束x未對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是x的一個個體y是x的一個個體)(x)P(x)P(y)P(y)(x)P(x)(x)P(x)(x)P(x)上兩個式推導(x)PPx未對P有約束前束范式：設A為一謂詞公式，若A具有如下域延伸到公式的末尾(無自由變元)，稱A為前束范式。(x)(z)形式(x)(y)(z)(Q(x,y)→R(z))的形式，且開頭的作用例如：(x)P(x)∨Q(x)(y)P((y)∨Q(x)(x)P(x)→(x)Q(x)(x)(P(x)∨Q(x))☆☆☆謂詞演算的推理理論(必考)1)全稱制定規則US(x)P(x)P(c)2)全稱推廣規則UGP(x)(x)P(x)3)存在制定規則ESPage6of26離散數學復習材料(x)P(x)P(c)4)全稱制定規則EGP(c)(x)P(x)Page7of26離散數學復習材料第三章集合與關系集合的基本概念：外延性原理：兩個集合，當且僅當它們有相同的元素成員(無序，重復)，或者兩個集合互為子集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)}：設A={1,2,3}則(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}若有限集合A有n個元素，(A)有2n個元素冪集則冪集。集合的基本運算：1)交運算AA=AA=AE=AAB=BA(AB)C=A(BC)2)并運算AABBAB結合律：A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收律：A(AB)=AA(AB)=AAA=AAE=EA=AAB=BA(AB)C=A(BC)3)補運算：記做A—B，即S={x|(x∈A)∧(xB)}A={2,5,6}，B={1,2,4,16,7,8}A—B={5,6}設定E全集，~A記做絕對補集：~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)對稱差運算：設A，B兩個集合，A與B的對稱差集合S，其元素或屬于A，或屬于B，但不能同時屬于A,B。記做AB=(A—B)(B—A)={x|x∈A▽x∈B}(▽不可兼析、亦或運算)例如：E={1,2,3,4,5,6,7,8}A={1,2,5,6}B={2,5,7,8}AB={1,6,7,8}☆對稱差的幾個重要等式：8-of26離散數學復習材料AB=BAA=AAA=AB=(A—B)(B—A)=(A~B)(B~A)(AB)C=A(BC)一階邏輯等值式：設P，Q是一階邏輯中任意的兩公式，若P?Q為邏輯有效式，則稱P與Q是等值的，記作PQ，稱PQ為等值式。☆序偶：<x,y>=<u,v>當且僅當(x=u，y=v)☆笛卡爾積：設A和B為集合，用A中元素為第一元素，用B中元素為第二元素構成有序對A×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>}結論：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)當四個非空集合:幾個關鍵證明：9-of26離散數學復習材料10-of26離散數學復習材料二元關系的運算：二元關系：如果一個集合R為空集或者它的元素都是有序對，則稱集合R是一個二元關系。記做：<x,y>∈R或xRy否則<x,y>RR是二元關系，(1)R中所有有序對的第一元素構成的集合稱為二元關系的運算：設R的定義域domR={x|y(<x,y>∈R)}(2)R中所有有序對的第二元素構成的集合稱為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}特殊關系：(1)空關系：Φ(2)全域關系：E={<x,y>|x∈A∧y∈A}=A×AA(3)恒等關系：I={<x,x>|x∈A}A(4)小于等于關系：L={<x,y>|x,y∈A∧x≤y∈A},ARA(5)整除關系：R={<x,y>|x,y∈ψ∧xy},ψ是集合族二元關系的性質：(可以用矩陣或有向圖來表示二元關系)自反性：(x)(x∈X→xRx)例如實數關系的≤≥就是自反的(x≤x,x≥x)有向圖中的自環，矩陣中的對角線元素不為0對稱性：(x)(y)(x∈X∧y∈X∧xRy→yRx)有向圖中的兩個頂點相互指向，矩陣是對稱的傳遞性：(x)(y)(z)(x∈X∧y∈X∧z∈X∧xRy∧yRz→xRz)例如實數集合中的“≤”,“<”,“=”都是傳遞的反自反性：(x)(x∈X→<x,x>R)例如父子關系是反自反的(非自反的不一定是反自反的)例如：A={1,2,3}S={<1,1>,<1,2>,<3,2>,<2,3>,<3,3>}2∈A,但是<2,2>S因此S不是自反關系的1∈A,3∈A,但是<1,1><3,3>∈S，也不是反自反關系的反對稱性：(x)(y)(x∈X∧y∈X∧xRy∧yRx→x=y)11-of26離散數學復習材料例如實數關系的”≤”是反對稱的，””也是反對稱的(x)(y)(x∈X∧y∈X∧x≠y∧xRy→yRx)例如：A={1,2,3}，S={<1,1>,<2,2>,<3,3>}S既是對稱的也是反對稱的A={a,b,c}，S={<a,b>,<a,c>,<c,a>}S既不是對稱的也不是反對稱的☆判斷各類關系的方法：當且僅當關系矩陣上對角線元素都為非零(1)值是，其存在自反關系當且僅當關系矩陣是對稱的且在關系圖上，任意頂點有定向弧成對出現，其存在對稱關系當且僅當關系矩陣上對角線元素都為零，關系圖頂點無自回路，其存在反自反關系當且僅當關系矩陣主對角線不能同時為1，關系圖上兩個不同頂點定向弧不可能成對出現時，其存在反對稱關系特例：空關系是對稱的、可傳遞的、反對稱的全域關系A×A是自反的、對稱的、可傳遞的復合關系：設R是X到Y的關系，S是Y到Z的關系，則符合關系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>}推導出其它常用的幾個公式：(約定X集合，R是X的二元關系)R0=XR?R?R……?R記做R(m)mRm?R=Rm+11,x,yRuijij如上所述，關系可以以關系矩陣形式表達0,x,yRij同理可以知道R?S的矩陣MR?S(實際上是R矩陣與S矩陣相乘，且結果是非0即1)逆關系☆：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離散數學復習材料1）對于R是X的二元關系，若R是對稱的則：當且僅當：R=Rc充分性：R是對稱的,<x,y>∈R,則<y,x>∈R,又<y,x>∈R，所以R=R，cc必要性：若R=R,則<x,y>∈R=><x,y>∈R=><y,z>∈R,則R一定是對稱的cc2）對于R是X的二元關系，若R是反對稱的則：當且僅當：RRcIxR是反對稱的，<x,y>∈RR<x,y>∈R∧<x,y>∈R<x,y>∈R∧<y,x>∈RR的反對稱的，所以必有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的反對稱的充分性：cc由于Ixc必要性：若cccc★閉包關系(必考、重點)定義：R是非空集合A的關系，R的自反(對稱或傳遞)的閉包是A的關系R’：1)R’是自反的(對稱或傳遞2)RR’3)對于A上任何包含r(R)記為自反閉包)R的自反(對稱或傳遞)的關系R’’,有R’R’’s(R)記為對稱閉包t(R)記為傳遞閉包最小唯一結論：R的自反(對稱或傳遞)閉包是含有R的具有自反(對稱或傳遞)性質的關系，且是的，(對稱或傳遞補充序偶)的，則需要，使之變為具有自反(對稱或傳遞)如果R本身不是自反1)R是自反的則r(R)=R2)R是對稱的則s(R)=R滿足<x,x>∈R’,加上對角線元素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關系矩陣中的對稱元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>}比較復雜！！！需逐個推導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離散數學復習材料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)★集合劃分與覆.蓋設定一個集合A，把A的元素分塊成非空子集，使得每個元素至少屬于一個子集。A的~；(分塊之間不存在相同元素)，分塊集合稱為~；(空集不存在~)A的劃分方式多種，不同劃分方式下，各個子集交叉AB的集合稱為覆蓋：每個分塊構成的集合稱為劃分：每個元素僅僅屬于一個分塊交叉劃分：集合~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},{b},{c},239apmh,{e},{f}}Q3是A的最小劃分A的覆蓋)(子集元素交叉n個分組),Q是A的最大A的劃分(1個分組4劃分Q1,Q2中的子集{e,f}存在,稱交叉劃分定理：Q1iQ2j構成的集合也是A集合的一種劃分。定義：若Q1iQ2j，則稱Q1是Q的加細劃分個數:()2個元素2種本例不存在這個現象2定理：任何一個交叉劃分都是原來各自劃分的一種加細3個元素5種4個元素15種☆等價關系：(重點必考)等價關系自反的，對稱的和傳遞的，那么稱R是等價關系。：如果集合設R是A上的等價關系，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>}關系矩陣如下：關系圖如下：A上的二元關系R是x～y。例子：關系矩陣對角線元素全為1(關系圖自回路),R是自反的),R是對稱10010110的12關系矩陣對稱元素的值或為1/0(關系圖弧成對出現0110R也是傳遞的100143結論：R是自反的，對稱的和傳遞的R是等價關系等價類：設R是A上的等價關系，對任意的x∈A，令[a]R={x|x∈A,aRx}，稱[a]為關于aRR的~。另例：[a]且[a]RA顯然：R上例中：[1]=[4]R={1,4}R[2]R=[3]R={2,3}商集：集合A的等價關系R，等價類{[a]|a∈A}，稱作A關于R的集商記做A/R。R上例中：A/R={[1],[2]}另例中：X/R={[0]R,[1],[2]R}RRR14-of26離散數學復習材料幾個特例：全域關系R=A×A：即恒等關系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★偏序關系：(重點、必考)設R是集合A上的二元關系，如果R是自反的，反對稱的和傳遞的，那么稱R為A上的偏序，記作”≤”；稱序偶<A,R>為偏序集合。記做{A,”≤”}，典型的偏序集合“字典順序”例如：A={2,3,6,8}偏序關系“≤”={<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>}偏序關系“≤”={<x,y>|x是y的正倍數偏序關系的蓋住：滿足偏序關系，且在xy(x∈A,y)的條件下不存在z元素(z∈A)使得x“≤”z，且z“≤”y(即不存在中間元素)，則稱y蓋住x。86例如：上例中的COVA={<2,6>,<3,6><2,8>}哈斯圖(頂點圓圈表示自回路A的極大元{6,8}，極小元{2,3}；最大元無，最小元無蓋住則指直線連接)23再例子1：A={2,3,6,12,24,36}偏序關系“≤”={<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}；最大元無，最小元無鏈：<A,”≤”>是一個偏序集合，A子集中如果每兩個元素之間都有關系，稱為鏈，否則為反鏈哈斯圖畫法：231)圓圈表示帶有自回路的元素頂點；2)x≤y且xy，則x畫在y的下方；3)x≤y且xy，且在集A中不存在任何z∈A，使得z介于x與y之間，則x與y之間用一條直線連接。偏序的哈斯圖是唯一的證明蓋住也是唯一的再例子2：A={1,2,3,4,5,6,7,8,9}偏序關系”≤”={<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離散數學復習材料A的極大元{5,6,7,8,9}，極小元{1}；最大元無，最小元1再例子2的哈斯圖再例子3：A={a,b,c}偏序關系”≤”={<x,y>|xy}{A,”≤”}={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}COVA={,{a},{b},{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}；最大元無，最小元1幾個關鍵名詞設{A，“≤”}為一個偏序集合，BA，且(一)極大元：B的一個元素b是B的極大元，即B中找不到比當B=A的時候，哈斯圖的最頂層且無向上的連線的節點既是極大元；(二)極小元：當B=A的時候，(特特例：有b，如果B中沒有任何一個元素x，滿足b“≤”x，xb，且b“≤”x的元素則稱b還大的且滿足。特例：反之則是極小元。特例：哈斯圖的最下層且無向下的連線的節點既是極小元；些元素可能既是極大元也可能是極小元極大元和極小元之間無關的。)A的極大元{5,6,7,8,9}，極小元{2,3,5,7}；最大元無，最小元無{5,7}既是極大元也是極小元(三)最大元:BA，且B的一個元素b，如果B中任何一個元素x，有x“≤”b，則稱b是B的最16-of26離散數學復習材料大元(四)最小元:BA，且B的一個元素b，如果B中任何一個元素x，有b“≤”x，則稱b是B的最小元(特特例：最大元最小元唯一且屬于B(或者A)，且與B(或者A)任意元素有關系，且也可能沒有)極大元就是上面沒節點的極小元最大元最小元就是下面沒節點的就是所有節點的上面(有路徑能連下來(有路徑能)就是所有節點的下面連上去)上界：(五)BA，a∈A，且B的任意元素x,有x”≤”a，則稱a是B的上界，最小上界稱為上確x,有a”≤”x，則稱a是B的下界，最大下界稱為下確(下)確界界;下界：(六)BA，a∈A，且B的任意元素界；(特特例：上(下)界不一定存在,上(下)界不一(下)確界(小)元。)定唯一，但上若存在，必唯一。注意：上即某個偏序集的最大定義：任何一個偏序集合，假設它的每個非空子集存在最小元素，則稱為良序的，每個良序一定是全序集合。每個有限的全序集合必定是良序集合。17-of26離散數學復習材料第四章函數函數的性質：設f:AB，(1)若ranf=B，則稱f是滿射(到上)的。B中每個元素在A中有1個或多個象點：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是入射(一對一映射)的。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離散數學復習材料第五章代數結構(群、半群必考)★代數系統的引入定義：非空集合A定義的若干運算f,f,……f組成的系統成為代數系統；12n★代數系統運算特性封閉運算：若對給定的集合中的元素進行運算，產生的象點仍在該集合中x*y∈A)，則稱此集合在該運算的二元運算封閉性：設*是定義在A上的*在A上是封閉的運算若x*y=y*x則稱二元運算是可交換的(即x,y∈A都有作用下是封閉的二元運算，對于任意的x,y∈A,都有x*y∈A，則稱二元運算若(x*y)*z=x*(y*z),則稱是可結合的若*,Δ是二元運算,有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的每個元素均滿足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同理可以推導出<A，*>代數系統中θ≠e，否則A的元素唯一。[x=e*x=θ*x=e=θ可證明]逆元：設e是幺元，若a,b∈A，若b*a=e,稱為左逆元設e是幺元，若a,b∈A，若a*b=e,稱為右逆元若b既是左逆元又是右逆元，則稱為逆元，記做x的逆元x-1定理5-2.4：若<A,*>代數系統存在=逆元且唯一。[設xl,xr分別為x的左右逆元，唯一性：設x1,x2是x的逆元，則x=x1*e=x1*（x*x2）-1-1-1-11e幺元，每個元素都有左逆元，且*是可結合的，那么左逆元=右逆元∵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離散數學復習材料★半群封閉的、可結合的半群：代數系統<S,*>，其中S一個非空集合，*是S上的二元運算，且(若滿足交換律則成為交換半群)。若BS,*運算在封閉的，則<B,*>也是一個半群且是<S,*>的子半群。含有幺元的半群稱為獨異點(含幺半群)也記做<S,*,e>，“∪”和“∩”均滿足結合律和交換律，因此它們是可交換的半群*[(x*y)*z=x*(y*z)]，則稱<S,*>為一個半群B也是特例：運算若：<S,*>為獨異點(含幺半群)，則a,b∈S時均有逆元，則(a-1)-1=a(a*b)-1=b-1*a-1★群與子群封閉的、可結合的、群：若<G,*>是一個代數系統，G是非空集合，*是G的二元運算，若*是存在幺元它的逆元x-1，則稱<G,*>是一個群。若e的，且每個元素x∈G，都有G是有限個元素的個數(階)，記做|G|，若G無限個元素，則<G,*>是無限群。各類群的關系(包含關系)群的幾個特性：1)群<G,*>一定沒有相同的行(和列)θ*x=x*θ=θ≠e，零元2)群<G,*>不存在零元[即x∈G，θ不存在逆元，與群的定義矛盾，故...]3)群<G,*>,a,b∈G，必然存在一個x∈G，使得a*x=b，也必然存在一個y∈G，使得y*a=b。證明：證明：∵b=e*b=(a*a-1)*b=a*(a-1*b)∴x=a-1*b時滿足a*x=b唯一性證明：∵b=b*e=b*a-1*a=(b*a-1)*a∴y=b*a-1時滿足y*a=b唯一性證明：設另外的一個x滿足a*x0=b設另外的一個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={a,b,c,d},映射a->b,b->d,c->a,d->c,這個置換表示為：bdacG到G的雙射稱為G的一個置換abcd20-of26離散數學復習材料6)群<G,*>運算表置換的每一行或每一列都是G的元素的一個置換。7)代數系統<G,*>,a∈G,a*a=a則稱為等冪元，在群<G,*>,a∈G,a*a=a，則a=e是幺元，無其它元素是等冪的。8)SG，群<S,*>是<G,*>的子群，<G,*>的幺元e也是<S,*>的幺元。子群：SG，群<S,*>是<G,*>的子群，滿足三個條件：1)e是<G,*>的幺元，且e∈S2)a∈S且a-1∈S……幺元……逆元……封閉3)a,b∈S且a*b∈S特例1：當S={e}或者S=G的，則稱群<S,*>是<G,*>的平凡子群，其它的稱為真子群。特例2：SG，只要二元運算*在S是封閉，<S,*>也是<G,*>的子群。特例2證明：因為*在B是滿足封閉性，故b∈B,有b2∈B,b3∈B,b4∈B…..B是一個有限集，存在i,j（設i<j）bi=bj，bi=bi*bj-i，可知bj-i是幺元也在B集中。當j-i>1，bj-i=b*bj-i-1，bj-i-1∈B故bj-i-1是b的逆元。當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的幺元封閉因為：(b)=b∈B,則a*b=a*(b)∈B證畢。-1-1-1-1★阿貝爾群與循環群，G是非空集合，*是G的二元運算，若*是封閉的、是可阿貝爾群：若<G,*>是一個代數系統結合的、存在幺元e、且可交換的的，且每個元素x∈G，都有它的逆元x，則稱<G,*>是-1一個阿貝爾群。例如：G={1,2,3,4}F={f,f,f,f0123}1234f1234f212341234ff4(雙射置換f3)02341341241231234f是幺元，矩陣是對稱的，f，f3是互為逆元的，f，f1逆元是自己010(a*b)*(a*b)=(a*a)*(b*b)二元運算*是可交換的特殊群，成立的充要條件是：證明：充分性：即(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離散數學復習材料重要推論：阿貝爾群的特殊性質(a*b)-1=b-1*a-1=a-1*b-1循環群：若<G,*>是一個群，g∈G，且G中的每一個元素a，使得G中的任意元素都可以表示為g的形式。稱<G,*>循環群，g稱為生成元。n60就<{0是,60,120,240,300,180},*>的生成元，因此也是循環群60<{0,60,120,240,300,180},*>例如：重要推論：循環群必定是阿貝爾群。<G,*>是循環群，g是生成元(它生成了群),若存在一個正整數m，使得gm=e,則最小的那個正整數m稱為生成元g的周期，如不存在，則周期無窮大。第七章圖論☆圖的基本概念無向圖：是一個有序的二元組<V,E>，記作G，其中：(1)VФ稱為頂點集，其元素稱為頂點或頂點。(2)E為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。有向圖：是一個有序的二元組<V,E>,記作D,其中(1)V同無向圖。(2)E為邊集，它是笛卡爾積VV的多重子集，其元素稱為有向邊。設G=<V,E>是一個無向圖或有向圖。有限圖：若n階圖：若|V|=n，稱G為n階圖。零圖：若|E|=0，稱G為零圖,當|V|=1時，稱G為平凡圖。V,E是有限集，則稱G為有限圖。基圖：將有向圖變為無向圖得到的新圖，稱為有向圖的基圖。完全圖：每對頂點之間都有邊相連的圖，稱為完全圖。補圖：G，完全圖減去圖得到的圖是補圖。G’=<V,E-EG>V’=V，E’E稱之為生成子圖。子圖：G’=<E’,V’>且E’E,V’V,G’稱為G的子圖，若圖的同構：在用圖形表示圖時，由于頂點的位置不同，邊的形狀不同，同一個事物之間的關系可以用不同的圖表示，這樣的圖稱為圖同構。如一果個圖同構與它的補圖，則稱為自補圖。圖同構的必要單非充分條件：1)頂點數目相同；2)邊數相同；3)度數相同的結點數目相同；帶權圖：在處理有關圖的實際問題時，往往有值的存在，一般這個值成為權值，帶權值的圖稱為帶權圖或賦權圖。討論：定理7-1.1，任何圖中頂點度數之和是邊數的定理7-1.2，任何圖中度數為奇數的頂點必定是定理7-1.3，任何圖中頂點入度和是出度和；2倍；(環的度數增加2)偶數個；圖的最大度：△(G)=max{degv|v∈V(G)}22-of26離散數學復習材料圖的最小度：δ(G)=min{degv|v∈V(G)}n*(n1)*(1)nn條邊)(沒有自回路)定理7-1.4，無向圖是：條邊，有向圖是：2☆路與回路定理7-2.1：n個頂點的圖中，如果有vi到vk的一條路，則必存在不多于n-1條的路。連通圖：若無向圖是平凡圖，或圖中任意兩個頂點都是連通的，則稱G是連通圖。否則稱為非連通圖。設D是一個有向圖，如果D的基圖是連通圖，則稱D是弱連通圖，若D中任意兩個頂點至少一個可達另一個，則稱D是單向連通圖。若D中任意兩個頂點是相互可達的，則稱D是強連通圖。幾個概念：割點集：無向圖G=<V,E>是連通圖，V’V，G中刪去V’中所有頂點后，所得到的子圖是不連通的，而刪除了V’的任意一真子集后，所得到的子圖仍然是連通圖，則稱V’是G一個點割集，若V’只有一個點，則稱之為割點。定義k(G)=min{|V’||V’是G的點割集}為點的連通度，使得產生不連通圖而刪除的點的最小數目。0圖不連通1僅存在割點k(Kp)=p-1完全圖K刪除m<p-1個點仍然連通，但是刪除p-1個頂點之后變為平凡圖(|V|=1)p邊割集：無向圖G=<V,E>是連通圖，E’E，G中刪去E’中所有的邊之后得到的子圖不上連通圖，而刪除了E’的任意一真子集后，所得到的子圖仍然是連通圖，則稱E’是G一個邊割集，若E’只有一個邊，則稱之為割邊(橋)。0平凡圖和不連通圖定義λ(G)=min{|E’||E’是G的邊割集}為邊的連通度{v3,v5},{v2},{v6}為點割集{v2,v4}不是點割集，因為它的真子集{v2}已經是點割集了{v1,v6}不是點割集，因為它的真子集{v6}已經是點割集了{e3,e4}{e4,e5}{e1,e2,e3}{e1,e2,e4}{e9}等都是邊割集，其中{e9}是橋{e6,e7,e9}不是割集，因為它的真子集{e9}已是邊割集。{e6,e8,e1,e2,e5}也不是邊割集k(G)≤λ(G)≤δ(G)定理7-2.2：任意一個圖G有(點割集≤邊割集≤圖的最小度數)證明：1）若G是不連通的，則(G)=0，不等式成立；2）若G是連通的例如v6λ(G)<3δ(G)=31o：證明λ(G)≤δ(G)若G是一個平凡圖，則λ(G)=0≤δ(G)若G是非平凡圖，則λ(G)≤δ(G)因為每頂點的個邊割集包含在該頂點的關聯邊中2o：再證k(G)≤λ(G)若λ(G)=1，即G有一個割邊，則k(G)=1若λ(G)≥2，由定義可知，刪去λ(G)條邊G不連通，刪除λ(G)-1條邊G仍然是連通的。且至少在λ(G)上存在橋設為e=(u,v)。對λ(G)-1條邊中的每一條邊都選與取u,v不同的頂點，23-of26離散數學復習材料而把這些頂點刪除必定減少λ(G)-1條邊若這樣產生的圖不連通則k(G)≤λ(G)-1≤δ(G)是連通的，則e是橋，此時再刪去u或v產生了不連通的圖，故k(G)≤λ(G)由上述證明命題成立。定理7-2.3：v是割點的充要條件是存在u，w兩個頂點，使得u，w之間每條路都要經過v。定理7-2.4：有向圖是連通的當且僅當G中有一個回路它至少包含每個頂點一次。定理7-2.5：有向圖G=(V,E)每個頂點位于且只位于一個強分圖之內。圖矩陣☆鄰接矩陣：A(G)上的元素aijaij=0，vi和vj不存在直接到達的邊aij=1，vi和vj存在直接到達的邊矩陣P是鄰接矩陣。定理7-3.1：設A(G)是G的鄰接矩陣表示，A(G)l上的a的值是G中聯結v和v的長度為l路的數lijij目。圖的可達矩陣：pij=0，vi和vj不存在通路pij=1，vi和vj至少存在1條通路P是可達矩陣。P=A∨A2∨A3……∨An的最終結果將0映射為G=(V,E),|V|=n且G已經編號頂點V={v1,v2,……vn}，n×n的矩陣P=(pij)矩陣0，非0映射為1。關聯矩陣表示：(1)無向圖的關聯矩陣：設無向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，令mij為頂點v邊與的i關聯次數，則稱(m)nm為G的關聯矩陣。記為M(G)。ij(2)有向圖的關聯矩陣：設無向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，1vi是ej的始點vi與ej不關聯mij=0-1vi是ej的終點則稱(mij)nm為D的關聯矩陣。記M(D)。距離矩陣表示：dij=∞dii=0dij=k<vi,vj>=∞自環為0k使得aij(k)≠0☆歐拉圖與哈密頓圖歐拉圖：平凡