離散數(shù)學公式[教資學習]

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) （對的分配律）A(BC) (AB)(AC) （對的分配律）6.德摩根律(AB) AB (AB) AB 7.吸收律A(AB) A，A(AB) A 8.零律A1 1,A0 0 9.同一律A0 A，A1 A 10.排中律AA 1 11.矛盾律AA 0 12.蘊涵等值式AB AB13.等價等值式AB (AB)(BA)14.假言易位AB BA15.等價否定等值式AB AB16.歸謬論(AB)(AB) A 求給定公式范

2、式的步驟 (1)消去聯(lián)結(jié)詞、(若存在)。(2)否定號的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。(3)利用分配律：利用對的分配律求析取范式，對的分配律求合取范式。推理定律-重言蘊含式(1) A (AB) 附加律(2) (AB) A 化簡律(3)(AB)A B 假言推理(4) (AB)B A 拒取式(5) (AB)B A 析取三段論 (6)(AB) (BC) (AC) 假言三段論(7)(AB) (BC) (A C) 等價三段論(8)(AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB)(AA) B 構(gòu)造性二難(特殊形式)(9)(AB)(CD)(BD) (AC) 破壞性二難 設(shè)個體域

3、為有限集D=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)個體變項x的公式，則（1）xA(x) $xA(x)（2）$xA(x) xA(x)設(shè)A(x)是任意的含自由出現(xiàn)個體變項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(BA(x) BxA(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)是

4、任意的含自由出現(xiàn)個體變項x的公式，則（1）x(A(x)B(x) xA(x)xB(x)（2）$x(A(x)B(x) $xA(x) $xB(x)全稱量詞“”對“”無分配律。存在量詞“$”對“”無分配律。UI規(guī)則。UG規(guī)則。EG規(guī)則。EI規(guī)則。ABx|xAxB 、ABx|xAxB ABx|xAxB 冪集 P(A)x | xA 對稱差集 AB(AB)(BA) AB(AB)(AB) 絕對補集 Ax|x A 廣義并 Ax | $z(zAxz) 廣義交 Ax | z(zAxz)設(shè) Aa,b,c,a,c,d,a,e,f Ba Ca,c,d則 Aa,b,c,d,e,f Ba Cac,d Aa Ba Cac,d集

5、合恒等式 冪等律 AAA AAA 結(jié)合律 (AB)CA(BC) (AB)CA(BC) 交換律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 同一律 AA 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 集合運算性質(zhì)的一些重要結(jié)果ABA，ABBAAB，BABABAABAB ABB AB ABA ABABBA (AB)CA(BC) AA AA ABAC BC 對偶(dual)式：一個集合表達式，

6、如果只含有、E、，那么同時把與互換，把與E互換，把與互換，得到式子稱為原式的對偶式。有序?qū)哂幸韵滦再|(zhì)： （1）當xy時，。 （2）的充分必要條件是xu且yv。 笛卡兒積的符號化表示為 AB|xAyB 如果|A|=m,|B|=n,則|AB|=mn。笛卡兒積的運算性質(zhì) (1)對任意集合A，根據(jù)定義有A, A(2)一般的說，笛卡兒積運算不滿足交換律，即ABBA (當 A B AB 時)(3)笛卡兒積運算不滿足結(jié)合律，即(AB)CA(BC)(當 A B C 時)(4)笛卡兒積運算對并和交運算滿足分配律，即A(BC)=(AB)(AC) (BC)A=(BA)(CA)A(BC)=(AB)(AC) (BC)

7、A=(BA)(CA)(5)AC BD AB CD常用的關(guān)系對任意集合A，定義全域關(guān)系 EA=|xAyA=AA 恒等關(guān)系 IA=|xA空關(guān)系 小于或等于關(guān)系：LA=|x,yAxy，其中 AR。整除關(guān)系：DB=|x,yBx整除y，其中 AZ* ，Z*是非零整數(shù)集包含關(guān)系：R|x,yAxy，其中 A是集合族。 關(guān)系矩陣和關(guān)系圖設(shè) A=1,2,3,4，R=,，則R的關(guān)系矩陣和關(guān)系圖分別是 定義域 dom R x | $y(R )值域 ran Ry | $ x(R)域 fld Rdom R ran R 例 求R=,的定義域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,3

8、,4 逆 R-1|R右復合 FG | $t(FG)限制 RA=|xRyxA 像 RA=ran(RA) 例 設(shè)R，R1， R R2,3， 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)(FG)HF(GH)(2)(FG)-1G-1 F-1設(shè)R為A上的關(guān)系，則R IAIA RR設(shè)F，G，H是任意的關(guān)系，則(1) F(GH)FGFH(2) (GH)FGFHF(3) F(GH)FGFH(4) (GH)FGFHF設(shè)F為關(guān)系，A,B為集合，則(1) F(AB)FAFB (2) FABFAFB (

9、3) F(AB)FAFB (4) FABFAFB 關(guān)系的冪運算設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：（1） R0|xAIA（2） Rn+1Rn R冪運算的性質(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(st)使得Rs=Rt，則(1) 對任何kN有 Rs+k=Rt+k(2) 對任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3) 令S=R0，R1，Rt-1，則對于任意的qN有 RqS自反 x(xAR)，反自反 x(xAR)，對稱 xy(x

10、,yARR)反對稱 xy(x,yARRx=y)，傳遞 xyz(x,y,zARRR)關(guān)系性質(zhì)的等價描述 設(shè)R為A上的關(guān)系，則（1）R在A上自反當且僅當 IA R（2）R在A上反自反當且僅當 RIA（3）R在A上對稱當且僅當 RR-1（4）R在A上反對稱當且僅當 RR-1 IA（5）R在A上傳遞當且僅當 RRR (1)若R1，R2是自反的和對稱的，則R1R2也是自反的和對稱的。(2)若R1和R2是傳遞的，則R1R2也是傳遞的。關(guān)系性質(zhì)的特點自反性反自反性對稱性反對稱性傳遞性集合表達式IA RRIARR-1RR-1 IARRR關(guān)系矩陣主對角線元素全是1主對角線元素全是0 矩陣是對稱矩陣 若rij1，

11、且ij，則rji0 對M2中1所在位置，M中相應的位置都是1 關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán) 如果兩個頂點之間有邊，一定是一對方向相反的邊(無單邊) 如果兩點之間有邊，一定是一條有向邊(無雙向邊) 如果頂點xi到xj有邊，xj到xk有邊，則從xi到xk也有邊 關(guān)系的性質(zhì)和運算之間的關(guān)系自反性反自反性對稱性反對稱性傳遞性R1-1R1R2R1R2R1R2R1 R2閉包的構(gòu)造方法設(shè)R為A上的關(guān)系，則有（1）自反閉包 r(R)RR0（2）對稱閉包 s(R)RR-1（3）t(R)RR2R3 關(guān)系性質(zhì)與閉包運算之間的聯(lián)系設(shè)R是非空集合A上的關(guān)系，（1）若R是自反的，則s(R)與t(R)也是自反的。（

12、2）若R是對稱的，則r(R)與t(R)也是對稱的。（3）若R是傳遞的，則r(R)是傳遞的。等價類的性質(zhì)設(shè)R是非空集合A上的等價關(guān)系，則（1）xA，x是A的非空子集。（2）x,yA，如果xRy，則xy。（3）x,yA，如果R，則x與y不交。（4）x|xAA。偏序集中的特殊元素設(shè)為偏序集，BA，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，362,36,121261262,3,6

13、6無62,366666363242126B上界下界上確界下確界2,3,6,12,24,36無無無無6,1212,24,362,3,61262,3,66,12,24,36無6無66,12,24,36,2,3,6,66函數(shù)相等由定義可知，兩個函數(shù)F和G相等, 一定滿足下面兩個條件：（1）dom Fdom G （2）xdom Fdom G，都有 F(x)G(x) 所有從A到B的函數(shù)的集合記作BA，讀作“B上A”，符號化表示為 BAf | f：AB 。例：設(shè)A1,2,3，Ba,b，求BA。 BA f0, f1, f2, f3, f4, f5, f6, f7 。其中 f 0, f 1, f 2, f 3

14、, f 4, f 5, f 6, f 7,設(shè)f:AB，（1）若ran fB，則稱f:AB是滿射(surjection)的。（2）若yran f 都存在唯一的xA使得f(x)y，則稱 f:AB是單射(injection)的。（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

15、+1。解（1）f 在x=1取得極大值0。既不是單射也不是滿射的。（2）f 是單調(diào)上升的，是單射的，但不滿射。ran f=ln1, ln2, 。（3）f 是滿射的， 但不是單射的，例如f(1.5)=f(1.2)=1。（4）f 是滿射、單射、雙射的，因為它是單調(diào)函數(shù)并且ran f=R。例：(1) 給定無向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖D=，其中 Va,b,c,d， E,。 畫出G與D的圖形。 鄰域：NG(v1) v2，v5 后繼元集：+D(d ) c

16、閉鄰域：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是懸掛頂點，e7是懸掛邊。 d(a)4+15。5，3， +4 (在a點達到)度數(shù)列為4,4,2,1,3。 +0(在b點達到) -3(在b點達到)-1(在a和c點達到) 按字母順序，度數(shù)列：5,3,3,3 出度列：4,0,2,1 入度列：1,3,1,2設(shè)G是n階m條邊的無向圖，則下面各命題是等價的：（1）

17、G是樹。 （2）G中任意兩個頂點之間存在唯一的路徑。（3）G中無回路且mn-1。 （4）G是連通的且mn-1。（5）G是連通的且G中任何邊均為橋。（6）G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。例題 已知無向樹T中，有1個3度頂點，2個2度頂點，其余頂點全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹。 解答 設(shè)有x片樹葉，于是結(jié)點總數(shù)n1+2+x3+x 由握手定理和樹的性質(zhì)mn-1可知，2m2(n-1)2(2+x) 13+22+x解出x3，故T有3片樹葉。故T的度數(shù)應為1、1、1、2、2、3。求最小生成樹的算法（避圈法(Kruskal)）(1)設(shè)n階無向連通帶權(quán)圖G有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)算法停止時得到的T為G的最小生成樹為止。例：求下圖所示兩個圖中的最小生成樹。 W(T1)6 W(T2)12 T是n(n2)階有向樹，(1) T