離散數(shù)學公式17727

1、基本等值式1.雙重否定律A Û A2.冪等律A Û AA,A Û AA 3.交換律AB Û BA，AB Û BA4.結合律(AB)C Û A(BC) (AB)C Û A(BC) 5.分配律        A(BC) Û (AB)(AC) （對的分配律）A(BC) Û (AB)(AC) （對的分配律）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.蘊涵等值式   AB Û AB13.等價等值式   A«B Û (AB)(BA)14.假言易位     AB Û BA15.等價否定等值式      A«B Û A«B16.歸謬論      (AB)(AB) Û A 求給定公式范式的步驟 (1)消去聯(lián)結

4、詞、«(若存在)。(2)否定號的消去(利用雙重否定律)或內移(利用德摩根律)。(3)利用分配律：利用對的分配律求析取范式，對的分配律求合取范式。推理定律-重言蘊含式(1) A Þ (AB)                          附加律(2) (AB) Þ A      

5、;                      化簡律(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) 等價三段論(8) (AB)(CD)(AC) Þ(BD)          構

8、造性二難  (AB)(AB)(AA) Þ B       構造性二難(特殊形式)(9)(AB)(CD)(BD) Þ(AC) 破壞性二難 設個體域為有限集D=a1,a2,an,則有（1）"xA(x) Û A(a1)A(a2)A(an) （2）$xA(x) Û A(a1)A(a2)A(an)   設A(x)是任意的含自由出現(xiàn)個體變項x的公式，則（1）"xA(x) Û $xA(x)（2）$xA(x) Û "xA(x)設A(x)是任意

9、的含自由出現(xiàn)個體變項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)設A(x)，B(x)是任意的含自由出現(xiàn)個體變項x的公式，則（1）"

10、;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|xAxÏB 冪集 P(A)x | xÍA 對稱差集 AÅB(AB)(BA) AÅB(AB)(AB) 絕對補集 Ax|x Ï A 廣義并 Ax | $z(zAxz) 廣義交 Ax | "z(zAxz)設 Aa,b,c,a,c,d,a,

11、e,f Ba Ca,c,d則 Aa,b,c,d,e,f Ba Cac,d ÆÆ Aa Ba Cac,d集合恒等式 冪等律 AAA AAA 結合律 (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)

12、A 集合運算性質的一些重要結果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 對偶(dual)式：一個集合表達式，如果只含有、Æ、E、Í、Ê，那么同時把與互換，把Æ與E互換，把Í與&#

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

14、8; AB 時)(3)笛卡兒積運算不滿足結合律，即(A×B)×CA×(B×C)(當 AÆ BÆ CÆ 時)(4)笛卡兒積運算對并和交運算滿足分配律，即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常用的關系對任意

15、集合A，定義全域關系 EA=<x,y>|xAyA=A×A 恒等關系 IA=<x,x>|xA空關系 Æ小于或等于關系：LA=<x,y>|x,yAxy，其中 AÍR。整除關系：DB=<x,y>|x,yBx整除y，其中 AÍZ* ，Z*是非零整數(shù)集包含關系：RÍ<x,y>|x,yAxÍy，其中 A是集合族。 關系矩陣和關系圖設 A=1,2,3,4，R=<1,1>,<1,2>,<2,3>,<2,4>,<4,2>，則R的關系矩

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°G<x,y> | $t(<x,t>F<t,y>G)限制 RA=<x,y>|xRyxA 像 RA=

17、ran(RA) 例 設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設F是任意的關系，則 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F 設F，G，H是任意的關系，則(1)(F°G)°HF°(G°H)(2)(F°G)-1G-1 &#

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

19、lt;x,x>|xAIA（2） Rn+1Rn ° R冪運算的性質設A為n元集，R是A上的關系，則存在自然數(shù)s和t,使得Rs=Rt。設R是A上的關系，m,nN，則(1)Rm ° RnRm+n (2)(Rm)nRmn設R是A上的關系，若存在自然數(shù)s,t(s<t)使得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(xA<x,x>R)，反自反 "x(xA<x,x>ÏR)，對

20、稱 "x"y(x,yA<x,y>R<y,x>R)反對稱 "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)關系性質的等價描述 設R為A上的關系，則（1）R在A上自反當且僅當 IA Í R（2）R在A上反自反當且僅當 RIAÆ（3）R在A上對稱當且僅當 RR-1（4）R在A上反對稱當且僅當 RR-1 Í IA（5）R在A上傳遞當且僅當 R

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

22、點xi到xj有邊，xj到xk有邊，則從xi到xk也有邊 關系的性質和運算之間的關系 自反性反自反性對稱性反對稱性傳遞性R1-1R1R2R1R2××R1R2××R1 ° R2××××閉包的構造方法設R為A上的關系，則有（1）自反閉包 r(R)RR0（2）對稱閉包 s(R)RR-1（3）t(R)RR2R3 關系性質與閉包運算之間的聯(lián)系設R是非空集合A上的關系，（1）若R是自反的，則s(R)與t(R)也是自反的。（2）若R是對稱的，則r(R)與t(R)也是對稱的。（3）若R是傳遞的，則r(R)是傳遞的

23、。等價類的性質設R是非空集合A上的等價關系，則（1）"xA，x是A的非空子集。（2）"x,yA，如果xRy，則xy。（3）"x,yA，如果<x,y>ÏR，則x與y不交。（4）x|xAA。偏序集中的特殊元素設<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、,24,36 無無 24，36 2,3 6,12 126  12 62,3,6 6無 6 2,3 6 66 66 363242126B上界下界上確界下確界2,3,6,12,24,36 無 無 無無 6,12 12,24,362,3,6 12  62,3,6 6,12,24,36無 6 無 6 6,12,24,36,2,

25、3,6,6 6 函數(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 。例：設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&

26、gt;,<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>設f:AB，（1）若ran fB，則稱f:AB是滿射(surjection)的。（2）若"yran f 都存在唯一的xA使得f(x)y，則稱 f:AB是單射(inject

27、ion)的。（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 是單調上升的，是單射的，但不滿射。ran f=ln1, ln2, 。（3）f 是滿射的， 但不是單射的，例如f(

28、1.5)=f(1.2)=1。（4）f 是滿射、單射、雙射的，因為它是單調函數(shù)并且ran f=R。例：(1) 給定無向圖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(d ) c閉鄰域：NG(v1) v1，v2，v5 先驅元集：-D(d ) a，c關聯(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是