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

1、基本等值式1.雙重否定律A Û A2.冪等律A Û AA,A Û AA 3.交換律AB Û BA，AB Û BA4.結(jié)合律(AB)C Û A(BC) (AB)C Û A(BC) 5.分配律        A(BC) Û (AB)(AC) （對(duì)的分配律）A(BC) Û (AB)(AC) （對(duì)的分配律）6.德·摩根律     (AB) Û AB (AB) 

2、19; AB 7.吸收律        A(AB) Û A，A(AB) Û A 8.零律     A1 Û 1,A0 Û 0 9.同一律        A0 Û A，A1 Û A 10.排中律       AA Û 1 11.矛盾律 

3、60;AA Û 0 12.蘊(yùn)涵等值式   AB Û AB13.等價(jià)等值式   A«B Û (AB)(BA)14.假言易位     AB Û BA15.等價(jià)否定等值式     A«B Û A«B16.歸謬論      (AB)(AB) Û A 求給定公式范式的步驟 (1)消去聯(lián)結(jié)詞、

4、1;(若存在)。(2)否定號(hào)的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。(3)利用分配律：利用對(duì)的分配律求析取范式，對(duì)的分配律求合取范式。推理定律-重言蘊(yùn)含式(1) A Þ (AB)                          附加律(2) (AB) Þ A       

5、;                     化簡(jiǎn)律(3) (AB)A Þ B                          &

6、#160; 假言推理(4) (AB)B Þ A                         拒取式(5) (AB)B Þ A                     

7、      析取三段論 (6) (AB) (BC) Þ (AC)                  假言三段論(7) (A«B) (B«C) Þ (A « C) 等價(jià)三段論(8) (AB)(CD)(AC) Þ(BD)          構(gòu)造性二難 &

8、#160; (AB)(AB)(AA) Þ B       構(gòu)造性二難(特殊形式)(9)(AB)(CD)(BD) Þ(AC)破壞性二難 設(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)x的公式，則（1）"xA(x) Û $xA(x)（2）$xA(x) Û "xA(x)設(shè)A(x)是任意的含自由出現(xiàn)

9、個(gè)體變項(xiàng)x的公式，B中不含x的出現(xiàn)，則（1） "x(A(x)B) Û "xA(x)B"x(A(x)B) Û "xA(x)B"x(A(x)B) Û $xA(x)B"x(BA(x) Û B"xA(x)（2） $x(A(x)B) Û $xA(x)B$x(A(x)B) Û $xA(x)B$x(A(x)B) Û "xA(x)B$x(BA(x) Û B$xA(x)設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則（1）"x(A(x

10、)B(x) Û "xA(x)"xB(x)（2）$x(A(x)B(x) Û $xA(x) $xB(x)全稱量詞“"”對(duì)“”無(wú)分配律。存在量詞“$”對(duì)“”無(wú)分配律。UI規(guī)則。UG規(guī)則。EG規(guī)則。EI規(guī)則。ABx|xAxB 、ABx|xAxB ABx|xAxÏB 冪集 P(A)x | xÍA 對(duì)稱差集 AÅB(AB)(BA) AÅB(AB)(AB) 絕對(duì)補(bǔ)集 Ax|x Ï A 廣義并 Ax | $z(zAxz) 廣義交 Ax | "z(zAxz)設(shè) Aa,b,c,a,c,d,a,e,f Ba

11、 Ca,c,d則 Aa,b,c,d,e,f Ba Cac,d ÆÆ Aa Ba Cac,d集合恒等式 冪等律 AAA AAA 結(jié)合律 (AB)CA(BC) (AB)CA(BC) 交換律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 同一律 AÆA AEA 零律 AEE AÆÆ 排中律 AAE 矛盾律 AAÆ 吸收律 A(AB)A A(AB)A 德摩根律 A(BC)(AB)(AC) A(BC)(AB)(AC) (BC)BC (BC)BC ÆE EÆ 雙重否定律 (A)A 集合運(yùn)算

12、性質(zhì)的一些重要結(jié)果ABÍA，ABÍBAÍAB，BÍABABÍAABAB ABB Û AÍB Û ABA Û ABÆAÅBBÅA (AÅB)ÅCAÅ(BÅC) AÆÅA AÅAÆ AÅBAÅC Þ BC 對(duì)偶(dual)式：一個(gè)集合表達(dá)式，如果只含有、Æ、E、Í、Ê，那么同時(shí)把與互換，把Æ與E互換，把Í與Ê互換

13、，得到式子稱為原式的對(duì)偶式。有序?qū)?lt;x,y>具有以下性質(zhì)： （1）當(dāng)xy時(shí)，<x,y><y,x>。 （2）<x,y><u,v>的充分必要條件是xu且yv。 笛卡兒積的符號(hào)化表示為 A×B<x,y>|xAyB 如果|A|=m,|B|=n,則|A×B|=mn。笛卡兒積的運(yùn)算性質(zhì) (1)對(duì)任意集合A，根據(jù)定義有A×ÆÆ, Æ×AÆ(2)一般的說，笛卡兒積運(yùn)算不滿足交換律，即A×BB×A (當(dāng) AÆ BÆ AB

14、時(shí))(3)笛卡兒積運(yùn)算不滿足結(jié)合律，即(A×B)×CA×(B×C)(當(dāng) AÆ BÆ CÆ 時(shí))(4)笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即A×(BC)=(A×B)(A×C) (BC)×A=(B×A)(C×A)A×(BC)=(A×B)(A×C) (BC)×A=(B×A)(C×A)(5)AÍC BÍD Þ A×B Í C×D常用的關(guān)系對(duì)任意集合A，定義

15、全域關(guān)系 EA=<x,y>|xAyA=A×A 恒等關(guān)系 IA=<x,x>|xA空關(guān)系 Æ小于或等于關(guān)系：LA=<x,y>|x,yAxy，其中 AÍR。整除關(guān)系：DB=<x,y>|x,yBx整除y，其中 AÍZ* ，Z*是非零整數(shù)集包含關(guān)系：RÍ<x,y>|x,yAxÍy，其中 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)系圖分

16、別是 定義域 dom R x | $y(<x,y>R )值域 ran Ry | $ x(<x,y>R)域 fld Rdom R ran R 例 求R=<1,2>,<1,3>,<2,4>,<4,3>的定義域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,3,4 逆 R-1<x,y>|<y,x>R右復(fù)合 F°G<x,y> | $t(<x,t>F<t,y>G)限制 RA=<x,y>|xRyxA 像 RA=ran(RA

17、) 例 設(shè)R<1,2>，<1,3>，<2,2>，<2,4>，<3,2>R1<1,2>，<1,3> RÆ Æ R2,3<2,2>，<2,4>，<3,2> R12,3 RÆ Æ R32設(shè)F是任意的關(guān)系，則 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F 設(shè)F，G，H是任意的關(guān)系，則(1)(F°G)°HF°(G°H)(2)(F°G)-1G-1 ° F

18、-1設(shè)R為A上的關(guān)系，則R ° IAIA° RR設(shè)F，G，H是任意的關(guān)系，則(1) F°(GH)F°GF°H(2) (GH)°FG°FH°F(3) F°(GH)ÍF°GF°H(4) (GH)°FÍG°FH°F設(shè)F為關(guān)系，A,B為集合，則(1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABÍFAFB 關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：（1） R0<x,x

19、>|xAIA（2） Rn+1Rn ° R冪運(yùn)算的性質(zhì)設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。設(shè)R是A上的關(guān)系，m,nN，則(1)Rm ° RnRm+n (2)(Rm)nRmn設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(s<t)使得Rs=Rt，則(1) 對(duì)任何kN有 Rs+k=Rt+k(2) 對(duì)任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3) 令S=R0，R1，Rt-1，則對(duì)于任意的qN有 RqS自反 "x(xA<x,x>R)，反自反 "x(xA<x,x>ÏR)，對(duì)稱 &quo

20、t;x"y(x,yA<x,y>R<y,x>R)反對(duì)稱 "x"y(x,yA<x,y>R<y,x>Rx=y)，傳遞 "x"y"z(x,y,zA<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) IA Í R（2）R在A上反自反當(dāng)且僅當(dāng) RIAÆ（3）R在A上對(duì)稱當(dāng)且僅當(dāng) RR-1（4）R在A上反對(duì)稱當(dāng)且僅當(dāng) RR-1 Í IA（5）R在A上傳遞當(dāng)且僅當(dāng) R°R&#

21、205;R (1)若R1，R2是自反的和對(duì)稱的，則R1R2也是自反的和對(duì)稱的。(2)若R1和R2是傳遞的，則R1R2也是傳遞的。關(guān)系性質(zhì)的特點(diǎn) 自反性反自反性對(duì)稱性反對(duì)稱性傳遞性集合表達(dá)式IA Í RRIAÆRR-1RR-1 Í IAR°RÍR關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0 矩陣是對(duì)稱矩陣 若rij1，且ij，則rji0 對(duì)M2中1所在位置，M中相應(yīng)的位置都是1 關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán) 如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊(無(wú)單邊) 如果兩點(diǎn)之間有邊，一定是一條有向邊(無(wú)雙向邊) 如果頂點(diǎn)xi到xj

22、有邊，xj到xk有邊，則從xi到xk也有邊 關(guān)系的性質(zhì)和運(yùn)算之間的關(guān)系 自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R1-1R1R2R1R2××R1R2××R1 ° R2××××閉包的構(gòu)造方法設(shè)R為A上的關(guān)系，則有（1）自反閉包 r(R)RR0（2）對(duì)稱閉包 s(R)RR-1（3）t(R)RR2R3 關(guān)系性質(zhì)與閉包運(yùn)算之間的聯(lián)系設(shè)R是非空集合A上的關(guān)系，（1）若R是自反的，則s(R)與t(R)也是自反的。（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。（3）若R是傳遞的，則r(R)是傳遞的。等價(jià)類的性

23、質(zhì)設(shè)R是非空集合A上的等價(jià)關(guān)系，則（1）"xA，x是A的非空子集。（2）"x,yA，如果xRy，則xy。（3）"x,yA，如果<x,y>ÏR，則x與y不交。（4）x|xAA。偏序集中的特殊元素設(shè)<A，>為偏序集，BÍA，yB。（1）若"x(xByx)成立，則稱y為B的最小元。（2）若"x(xBxy)成立，則稱y為B的最大元。（3）若"x(xBxyxy)成立，則稱y為B的極小元。（4）若"x(xByxxy)成立，則稱y為B的極大元B最大元最小元極大元極小元2,3,6,12,24,36

24、 無(wú)無(wú) 24，36 2,3 6,12 126  12 62,3,6 6無(wú) 6 2,3 6 66 66 363242126B上界下界上確界下確界2,3,6,12,24,36 無(wú) 無(wú) 無(wú)無(wú) 6,12 12,24,362,3,6 12  62,3,6 6,12,24,36無(wú) 6 無(wú) 6 6,12,24,36,2,3,6,6&

25、#160;6 函數(shù)相等由定義可知，兩個(gè)函數(shù)F和G相等, 一定滿足下面兩個(gè)條件：（1）dom Fdom G （2）"xdom Fdom G，都有 F(x)G(x) 所有從A到B的函數(shù)的集合記作BA，讀作“B上A”，符號(hào)化表示為 BAf | f：AB 。例：設(shè)A1,2,3，Ba,b，求BA。 BA f0, f1, f2, f3, f4, f5, f6, f7 。其中 f 0<1,a>,<2,a>,<3,a> f 1<1,a>,<2,a>,<3,b> f 2<1,a>,<2,b>,&l

26、t;3,a> f 3<1,a>,<2,b>,<3,b> f 4<1,b>,<2,a>,<3,a> f 5<1,b>,<2,a>,<3,b> f 6<1,b>,<2,b>,<3,a> f 7<1,b>,<2,b>,<3,b>設(shè)f:AB，（1）若ran fB，則稱f:AB是滿射(surjection)的。（2）若"yran f 都存在唯一的xA使得f(x)y，則稱 f:AB是單射(injection)的。

27、（3）若f 既是滿射又是單射的，則稱f:AB是雙射(bijection) abc1234 abc1234d abc1234d abc123d單射 雙射 函數(shù) 滿射例：判斷下面函數(shù)是否為單射、滿射、雙射的，為什么?(1) f：RR，f(x)= -x2+2x-1 (2) f：Z+R，f(x)=ln x，Z+為正整數(shù)集(3) f：RZ，f(x)=ëxû (4) f：RR，f(x)=2x+1。解（1）f 在x=1取得極大值0。既不是單射也不是滿射的。（2）f 是單調(diào)上升的，是單射的，但不滿射。ran f=ln1, ln2, 。（3）f 是滿射的， 但不是單射的，例如f(1.5)=f

28、(1.2)=1。（4）f 是滿射、單射、雙射的，因?yàn)樗菃握{(diào)函數(shù)并且ran f=R。例：(1) 給定無(wú)向圖G<V,E>，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖D=<V,E>，其中 Va,b,c,d， E<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>。 畫出G與D的圖形。 鄰域：NG(v1) v2，v5 后繼元集：+D(

29、d ) c閉鄰域：NG(v1) v1，v2，v5 先驅(qū)元集：-D(d ) a，c關(guān)聯(lián)集：IG(v1) e1，e2，e3 鄰域： ND(d ) a，c 閉鄰域：ND(d ) a，c，dd(v1)4(注意，環(huán)提供2度)， 出度：d+(a)4，入度：d-(a)1 4，1， (環(huán)e1提供出度1，提供入度1)，v4是懸掛頂點(diǎn)，e7是懸掛邊。 d(a)4+15。5，3， +4 (在a點(diǎn)達(dá)到)度數(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ú)向

30、圖，則下面各命題是等價(jià)的：（1）G是樹。 （2）G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。（3）G中無(wú)回路且mn-1。 （4）G是連通的且mn-1。（5）G是連通的且G中任何邊均為橋。（6）G中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。例題 已知無(wú)向樹T中，有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無(wú)向樹。 解答 設(shè)有x片樹葉，于是結(jié)點(diǎn)總數(shù)n1+2+x3+x 由握手定理和樹的性質(zhì)mn-1可知，2m2(n-1)2×(2+x) 1×3+2×2+x解出x3，故T有3片樹葉。故T的度數(shù)應(yīng)為1、1

31、、1、2、2、3。求最小生成樹的算法（避圈法(Kruskal)）(1)設(shè)n階無(wú)向連通帶權(quán)圖G<V,E,W>有m條邊。不妨設(shè)G中沒有環(huán)（否則，可以將所有的環(huán)先刪去），將m條邊按權(quán)從小到大排序：e1,e2,em。(2)取e1在T中。(3)依次檢查e2,em ，若ej(j2)與已在T中的邊不構(gòu)成回路，取ej也在T中，否則棄去ej。(4)算法停止時(shí)得到的T為G的最小生成樹為止。例：求下圖所示兩個(gè)圖中的最小生成樹。 W(T1)6 W(T2)12 T是n(n2)階有向樹，(1) T為根樹 T中有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度均為1(2) 樹根入度為0的頂點(diǎn)(3) 樹葉入度為1，出度為0的頂點(diǎn)(4) 內(nèi)點(diǎn)入度為1，出度不為0的頂點(diǎn)(5) 分支點(diǎn)樹根與內(nèi)點(diǎn)的總稱(6) 頂點(diǎn)v的層數(shù)從樹根到v的通路長(zhǎng)度(7) 樹高T中層數(shù)最大頂點(diǎn)的層數(shù)根樹的畫法：樹根放上方，省去所有有向邊上的箭頭。 樹葉8片 內(nèi)點(diǎn) 6個(gè) 分支點(diǎn) 7個(gè) 高度 5求帶權(quán)為1、1、2、3、4、5的最優(yōu)樹。W(T)