離散數(shù)學(xué)公式2233

.基本等值式1.雙重否定律A┐┐A2.冪等律AA∨A,AA∧A3.交換律A∨BB∨A，A∧BB∧A4.結(jié)合律(A∨B)∨CA∨(B∨C)5.分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)(A∧B)∧CA∧(B∧C)（∨對(duì)∧的分配律）（∧對(duì)∨的分配律）6.德·摩根律┐(A∨B)┐A∧┐┐(A∧B)┐A∨┐BB7.吸收律8.零律A∨(A∧B)A，A∧(A∨B)AA∨11,A∧00A∨0A，A∧1AA∨┐A19.同一律10.排中律11.矛盾律A∧┐A012.蘊(yùn)涵等值式A→B┐A∨B13.等價(jià)等值式AB(A→B)∧(B→A)14.假言易位15.等價(jià)否定等值式AB┐A┐B16.歸謬論(A→B)∧(A→┐B)┐AA→B┐B→┐A求給定公式范式的步驟(1)消去聯(lián)結(jié)詞→、(若存在)。(2)否定號(hào)的消去(利用雙重否定律(3)利用分配律)或內(nèi)移(利用德摩根律)。：利用∧對(duì)∨的分配律求析取范式，∨對(duì)∧的分配律求合取范式。推理定律--重言蘊(yùn)含式(1)A(A∨B)(2)(A∧B)A附加律化簡(jiǎn)律假言推理(3)(A→B)∧AB(4)(A→B)∧┐B┐A拒取式析取三段論假言三段論等價(jià)三段論構(gòu)造性二難(5)(A∨B)∧┐BA(6)(A→B)∧(B→C)(A→C)(7)(AB)∧(BC)(AC)(8)(A→B)∧(C→D)∧(A∨C)(B∨D)(A→B)∧(┐A→B)∧(A∨┐A)B構(gòu)造性二難(特殊形式)(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破壞性二難..設(shè)個(gè)體域?yàn)橛邢藜疍={a1,a2,…,an},則有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)（1）┐xA(x)x┐A(x)（2）┐xA(x)x┐A(x)x的公式，則設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B中不含x的出現(xiàn)，則（1）x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)（2）x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則（1）x(A(x)∧B(x))xA(x)∧xB(x)（2）x(A(x)∨B(x))xA(x)∨xB(x)全稱量詞“”對(duì)“∨”無(wú)分配律。存在量詞“”對(duì)“∧”無(wú)分配律。xA(x)xA(x)A(y)A(c)UI規(guī)則?；騏G規(guī)則。A(y)xA(x)A(c)xA(x)EG規(guī)則。xA(x)A(c)EI規(guī)則。..A∪B＝{x|x∈A∨x∈B}、A∩B＝{x|x∈A∧x∈B}A－B＝{x|x∈A∧xB}冪集P(A)＝{x|xA}對(duì)稱差集AB＝(A－B)∪(B－A)AB＝(A∪B)－(A∩B)絕對(duì)補(bǔ)集～A＝{x|xA}廣義并∪A＝{x|z(z∈A∧x∈z)}廣義交∩A＝{x|z(z∈A→x∈z)}設(shè)A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}則∪A＝{a,b,c,d,e,f}∪B＝{a}∪C＝a∪{c,d}∪＝∩A＝{a}∩B＝{a}∩C＝a∩{c,d}集合恒等式冪等律結(jié)合律A∪A＝AA∩A＝A(A∪B)∪C＝A∪(B∪C)A∪B＝B∪A(A∩B)∩C＝A∩(B∩C)A∩B＝B∩A交換律分配律A∪(B∩C)＝(A∪B)∩(A∪C)A∩(B∪C)＝(A∩B)∪(A∩C)同一律A∪＝AA∪E＝EA∩E＝AA∩＝零律..排中律A∪～矛盾律A∩～A＝吸收律A∪(A∩B)＝AA＝EA∩(A∪B)＝A德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)＝～B∩～～(B∩C)＝～B∪～～＝E～E＝CC雙重否定律～(～A)＝A集合運(yùn)算性質(zhì)的一些重要結(jié)果A∩BA，A∩BBAA∪B，BA∪BA－BAA－B＝A∩～BA∪B＝BABA∩B＝AA－B＝AB＝BA(AB)C＝A(BC)A＝AAA＝AB＝ACB＝C對(duì)偶(dual)式：一個(gè)集合表達(dá)式，如果只含有∩、∪、～、、E、＝、、，那么同時(shí)把∩與∪互換，把與E互換，把與互換，得到式子稱為原式的對(duì)偶式。有序?qū)?lt;x,y>具有以下性質(zhì)：（（2）<x,y>＝<u,v>的充分必要條件是笛卡兒積的符號(hào)化表示為A×B＝{<x,y>|x∈A∧y∈B}|A|=m,|B|=n,則|A×B|=mn。1）當(dāng)x≠y時(shí)，<x,y>≠<y,x>。x＝u且y＝v。如果笛卡兒積的運(yùn)算性質(zhì)(1)對(duì)任意集合A×＝,×A＝(2)一般的A×B≠B×A(3)笛卡兒積運(yùn)算(A×B)×C≠A×(B×C)(當(dāng)(4)笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即A，根據(jù)定義有說(shuō)，笛卡兒積運(yùn)算不滿足交換律，即(當(dāng)A≠∧B≠∧A≠B時(shí))不滿足結(jié)合律，即A≠∧B≠∧C≠時(shí))A×(B∪C)=(A×B)∪(A×C)A×(B∩C)=(A×B)∩(A×C)(5)AC∧BDA×BC×D(B∪C)×A=(B×A)∪(C×A)(B∩C)×A=(B×A)∩(C×A)常用的關(guān)系對(duì)任意集合A，定義全域關(guān)系EA={<x,y>|x∈A∧y∈A}=A×A恒等關(guān)系IA={<x,x>|x∈A}空關(guān)系..小于或等于關(guān)系：LA={<x,y>|x,y∈A∧x≤y}，其中AR。整除關(guān)系：DB={<x,y>|x,y∈B∧x整除y}，其中AZ*，Z*是非零整數(shù)集包含關(guān)系：R＝{<x,y>|x,y∈A∧xy}，其中A是集合族。關(guān)系矩陣和關(guān)系圖設(shè)A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，則R的關(guān)系矩陣和關(guān)系圖分別是11000011M0000R0100定義域domR＝{x|y(<x,y>∈R)}值域ranR＝{y|x(<x,y>∈R)}域fldR＝domR∪ranR例求R={<1,2>,<1,3>,<2,4>,<4,3>}的定義域、值域和域。解答domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}逆R-1＝{<x,y>|<y,x>∈R}右復(fù)合FG＝{<x,y>|t(<x,t>∈F∧<t,y>∈G)}限制R↑A={<x,y>|xRy∧x∈A}像R[A]=ran(R↑A)例設(shè)R＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}R↑{1}＝{<1,2>，<1,3>}R↑＝R↑{2,3}＝{<2,2>，<2,4>}，<3,2>}R[{1}]＝{2,3}R[]＝R[{3}]＝{2}設(shè)F是任意的關(guān)系，則(1)(F-1)-1＝F(2)domF-1＝ranF，ranF-1＝domF設(shè)F，G，H是任意的關(guān)系，則(1)(FG)H＝F(GH)(2)(FG)-1＝G-1F-1設(shè)R為A上的關(guān)系，則RIA＝IAR＝R設(shè)F，G，H是任意的關(guān)系，則(1)F(G∪H)＝FG∪FH(2)(G∪H)F＝GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF..設(shè)F為關(guān)系，A,B為集合，則(1)F↑(A∪B)＝F↑A∪F↑B(2)F[A∪B]＝F[A]∪F[B](3)F↑(A∩B)＝F↑A∩F↑B(4)F[A∩B]F[A]∩F[B]關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系，（1）R0＝{<x,x>|x∈A}＝IA（2）Rn+1＝RnRn為自然數(shù)，則R的n次冪定義為：冪運(yùn)算的性質(zhì)設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。設(shè)R是A上的關(guān)系，m,n∈N，則(1)RmRn＝Rm+n(2)(Rm)n＝Rmn設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(s<t)使得Rs=Rt，則(1)對(duì)任何k∈N有Rs+k=Rt+k(2)對(duì)任何k,i∈N有Rs+kp+i=Rs+i，其中p=t-s(3)令S={R0，R1，…，Rt-1}，則對(duì)于任意的q∈N有Rq∈S自反x(x∈A→<x,x>∈R)，反自反x(x∈A→<x,x>R)，對(duì)稱xy(x,y∈A∧<x,y>∈R→<y,x>∈R)反對(duì)稱xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，傳遞xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)關(guān)系性質(zhì)的等價(jià)描述設(shè)R為A上的關(guān)系，則（1）R在A上自反當(dāng)且僅當(dāng)IAR（2）R在A上反自反當(dāng)且僅當(dāng)R∩IA＝（3）R在A上對(duì)稱當(dāng)且僅當(dāng)R＝R-1（4）R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R-1IA（5）R在A上傳遞當(dāng)且僅當(dāng)RRR(1)若R1，R2是自反的和對(duì)稱的，則R1∪R2也是自反的和對(duì)稱的。(2)若R1和R2是傳遞的，則R1∩R2也是傳遞的。..關(guān)系性質(zhì)的特點(diǎn)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性集合表達(dá)式IARR∩＝IAR＝R-1R∩R-1IARRR關(guān)系矩陣主對(duì)角線元素主對(duì)角線元素全矩陣是對(duì)稱矩陣若rij＝1，且i≠j，對(duì)M2中1所在位M中相應(yīng)的全是1是0則rji＝0置，位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有每個(gè)頂點(diǎn)都沒(méi)有如果兩個(gè)頂點(diǎn)之如果兩點(diǎn)之間有如果頂點(diǎn)xi到xjxj到xk有)邊，則從xi到xk環(huán)環(huán)間有邊，一定是邊，一定是一條有有邊，一對(duì)方向相反的向邊(無(wú)雙向邊邊(無(wú)單邊)也有邊關(guān)系的性質(zhì)和運(yùn)算之間的關(guān)系自反性√√√×反自反性對(duì)稱性反對(duì)稱性傳遞性R1-1√√√√×√√√√×√√×√R1∩R2R1∪R2R1－R2√×××√×R1R2√閉包的構(gòu)造方法設(shè)R為A上的關(guān)系，則有（1）自反閉包r(R)＝R∪R0（2）對(duì)稱閉包s(R)＝R∪R-1（3）t(R)＝R∪R2∪R3∪…關(guān)系性質(zhì)與閉包運(yùn)算之間的聯(lián)系設(shè)R是非空集合（1）若R是自反的，則s(R)與t(R)也是自反的（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的（3）若R是傳遞的，則r(R)是傳遞的A上的關(guān)系，。。。..等價(jià)類的性質(zhì)設(shè)R是非空集合A上的等價(jià)關(guān)系，則（1）x∈A，[x]是A的非空子集。（2）x,y∈A，如果xRy，則[x]＝[y]。（3）x,y∈A，如果<x,y>R，則[x]與[y]不交。（4）∪{[x]|x∈A}＝A。偏序集中的特殊元素設(shè)<A，≤>為偏序集，BA，y∈B。稱y為B的最小元。x(x∈B→x≤y)成立，則稱y為B的最大元。稱y為B的極小元。（1）若x(x∈B→y≤x)成立，則（2）若（3）若（4）若x(x∈B∧x≤y→x＝y(tǒng))成立，則x(x∈B∧y≤x→x＝y(tǒng))成立，則稱y為B的極大元2436B最大元最小元極大元極小元12{2,3,6,12,24,36}無(wú)無(wú)624，362,3{6,12}{2,3,6}{6}1261266無(wú)662,366623B上界下界無(wú)上確界無(wú)下確界無(wú){2,3,6,12,24,36}無(wú){6,12}{2,3,6}{6}12,24,362,3,61266無(wú)66,12,24,36無(wú)6,12,24,36,2,3,6,6函數(shù)相等由定義可知，兩個(gè)函數(shù)F和G相等,一定滿足下面兩個(gè)條件：（1）domF＝domG（2）x∈domF＝domG，都有F(x)＝G(x)所有從A到B的函數(shù)的集合記作BA，讀作“B上A＝{1,2,3}，B＝{a,b}，求BA。BA＝{f0,f1,f2,f3,f4,f5,f6,f7}。其中A”，符號(hào)化表示為BA＝{f|f：A→B}。例：設(shè)f0＝{<1,a>,<2,a>,<3,a>}f2＝{<1,a>,<2,b>,<3,a>}f4＝{<1,b>,<2,a>,<3,a>}f6＝{<1,b>,<2,b>,<3,a>}f1＝{<1,a>,<2,a>,<3,b>}f3＝{<1,a>,<2,b>,<3,b>}f5＝{<1,b>,<2,a>,<3,b>}f7＝{<1,b>,<2,b>,<3,b>}設(shè)f:A→B，（1）若ranf＝B，則稱f:A→B是滿射(surjection)的。稱f:A→B是單射(injection)的。（2）若y∈ranf都存在唯一的x∈A使得f(x)＝y(tǒng)，則..（3）若f既是滿射又是單射的，則稱f:A→B是雙射(bijection)1a1aa1a1234bbb2b223ccd34c34cdd單射雙射函數(shù)滿射例：判斷下面函數(shù)是否為單射、滿射、雙射的，為什么?(1)f：R→R，f(x)=-x2+2x-1(3)f：R→Z，f(x)=x(2)f：Z+→R，f(x)=lnx，Z+為正整數(shù)集(4)f：R→R，f(x)=2x+1。解（1）f在x=1取得極大值0。既不是單射也不是滿射的。（2）f是單調(diào)上升的，是單射的，但不滿射。ranf={ln1,ln2,…}。（3）f是滿射的，但不是單射的，例如f(1.5)=f(1.2)=1。（4）f是滿射調(diào)函數(shù)并且ranf=R。、單射、雙射的，因?yàn)樗菃卫?1)給定無(wú)向圖G＝<V,E>，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(2)給定有向圖D=<V,E>，其中V＝{a,b,c,d}，E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。畫(huà)出G與D的圖形。鄰域：NG(v1)＝{v2，v5}后繼元集：Г+D(d)＝{c}先驅(qū)元集：Г-D(d)＝{a，c}閉鄰域：NG(v1)＝{v1，v2，v5}關(guān)聯(lián)集：IG(v1)＝{e1，e2，e3}鄰域：ND(d)＝{a，c}閉鄰域：ND(d)＝{a，c，d}出度：d+(a)＝4，入度：d-(a)＝1(環(huán)e1提供出度1，提供入度1)，d(a)＝4+1＝5?！鳎?，δ＝3，△+＝4(在a點(diǎn)達(dá)到)d(v1)＝4(注意，環(huán)提供2度)，△＝4，δ＝1，v4是懸掛頂點(diǎn)，e7是懸掛邊。度數(shù)列為4,4,2,1,3。δ+＝0(在b點(diǎn)達(dá)到)△-＝3(在b點(diǎn)達(dá)到)δ-＝1(在a和c點(diǎn)達(dá)到)按字母順序，度數(shù)列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2..設(shè)G＝<V,E>是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹(shù)。（3）G中無(wú)回路且m＝n1。（4）G是連通的且（5）G是連通的且G中任何邊均為橋。（6）G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。T中，有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹(shù)葉，試求樹(shù)葉數(shù)，并畫(huà)出滿足要（2）G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。m＝n1。例題已知無(wú)向樹(shù)求的非同構(gòu)的無(wú)向樹(shù)。解答設(shè)有x片樹(shù)葉，于是結(jié)點(diǎn)總數(shù)n＝1+2+x＝3+x由握手定理和樹(shù)的性質(zhì)m＝n1可知，2m＝2(n1)＝2×(2+x)＝1×3+2×2+x解出x＝3，故T有3片樹(shù)葉。故T的度數(shù)1、1、1、2、2、3。算法（避圈法(Kruskal)）G＝<V,E,W>有m條邊。不e1,e2,…,em。應(yīng)為求最小生成樹(shù)的(1)設(shè)n階無(wú)向連通將m條邊(2)取e1在T中。(3)依次檢查e2,…,em，若ej(j≥2)與已在(4)算法停止時(shí)得到的T為G的最小生成樹(shù)為止。示兩個(gè)圖中的帶權(quán)圖妨設(shè)G中沒(méi)有環(huán)（否則，可以將所有的環(huán)先刪去），按權(quán)從小到大排序：T中的邊不構(gòu)成回路，取ej也在T中，否則去棄ej。例：求下圖所最小生成樹(shù)。W(T1)＝6W(T2)＝12T是n(n≥2)階有向樹(shù)，(1)T為根樹(shù)—T中有一個(gè)頂點(diǎn)(2)樹(shù)根——入度為0的頂點(diǎn)(3)樹(shù)葉——入度為1，出度為0的頂點(diǎn)(4)內(nèi)點(diǎn)——入度為1，出度不為0的頂點(diǎn)(5)分支點(diǎn)——樹(shù)根與內(nèi)點(diǎn)的總(6)頂點(diǎn)v的層數(shù)——從樹(shù)根到v的通路(7)樹(shù)高——T中層數(shù)最大頂點(diǎn)的層數(shù)入度為0，其余頂點(diǎn)的入度均為1稱長(zhǎng)度..根樹(shù)的畫(huà)法：樹(shù)根放上方，省去所有有向邊上的箭頭。樹(shù)葉——8片內(nèi)點(diǎn)——6個(gè)分支點(diǎn)——7個(gè)高度——51、1、2、3、4、5的最優(yōu)樹(shù)。求帶權(quán)為W(T)=38中序行遍法：ba(fdg)ce前序行遍法：ab(c(dfg)e)后序行遍法：b((fgd)ec)a..├斷定符（公式在L中可證）R關(guān)系r相容關(guān)系╞滿足符（公式在E上有效，公式在E上可滿足）┐命題的“非”運(yùn)算R○S關(guān)系與關(guān)系的復(fù)合domf函數(shù)的定義域（前域）ranf函數(shù)的值域∧命題的“合取”（“與”）運(yùn)算∨命題的“析取”（“或”，“可兼或”）運(yùn)算→命題的“條件”運(yùn)算f:X→Yf是X到Y(jié)的函數(shù)GCD(x,y)x,y最大公約數(shù)LCM(x,y)x,y最小公倍數(shù)aH(Ha)H關(guān)于a的左（右）陪集Ker(f)同態(tài)映射f的核（或稱f同態(tài)核）[