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

1、基本等值式1.雙重否定律AnnA幕等律交換律結(jié)合律分配律AAVA,AAAAAVBBVA,AABBAA(AVB)VCAV(BVC)AV(BAC)(AVB)A(AVC)AA(BVC)(AAB)V(AAC)（AAB）ACAA（BAC）（V對A的分配律）（A對V的分配律）德摩根律吸收律&零律9.同一律排中律矛盾律n(AVB)nAAnBn(AAB)nAVnBAV(AAB)A,AA(AVB)AAV11,AA00AV0A,AA1AAVnA1AAnA012.蘊涵等值式ABnAVB等價等值式等價等值式假言易位AoB(AB)A(BA)ABnBnA15.等價否定等值式AoBnAonB附加律附加律化簡律假言推理拒取式

2、析取三段論假言三段論等價三段論構(gòu)造性二難構(gòu)造性二難（特殊形式）16.歸謬論(AB)A(AnB)nA求給定公式范式的步驟（1）消去聯(lián)結(jié)詞一、o（若存在）。（2）否定號的消去（利用雙重否定律）或內(nèi)移（利用德摩根律）。（3）利用分配律：利用A對V的分配律求析取范式，V對A的分配律求合取范式。推理定律-重言蘊含式A,(AVB)(AAB),A(AB)AA,B(AB)AnB,nA(5)(AVB)AnB,A(AB)A(BC),(AC)(AoB)A(BoC),(AoC)(AB)A(CD)A(AVC),(BVD)(AB)A(nAB)A(AVnA),B(9)(AB)A(CD)A(nBVnD)，(nAVnC)破壞性

3、二難檢小項極天項公式成真賦值名稱公式成假賦值名稱1pAnq00叱pVq00%npAq01pVlq01-pAnq101pVq10pAq111pVnq11極小項公式極小項公式成真賦值名稱1pA|qA|r000噸1pAlqAr001IDnpAqAnr0101pAqAr011m3pAnqA-|r100ULQpAlqAr101n)5pAqAnr110mgpAqAr111IDT極大項公式成假賦值名稱pVqVr000MopVqVlr001MipViqVr010m2pVnqVlr011m31pVqVr100m41pVqVlr101m51pVnWr110m61pVnqVlr111My設(shè)個體域為有限集D=al,a

4、2,.,an,則有xA(x)oA(a1)AA(a2)A.AA(an),xA(x)oA(a1)VA(a2)V.VA(an)設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，則qxA(x)o,xqA(x)q,xA(x)oxqA(x)設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，B中不含x的出現(xiàn)，則(1)x(A(x)VB)oxA(x)VBx(A(x)AB)oxA(x)ABx(A(x)fB)o,xA(x)fBx(BfA(x)oBfxA(x)(2),x(A(x)VB)o,xA(x)VB,x(A(x)AB)o,xA(x)ABoxA(x)fB,x(BfA(x)oBf,xA(x)設(shè)A(x),B(x)是任意的含自由

5、出現(xiàn)個體變項x的公式，則x(A(x)AB(x)oxA(x)AxB(x),x(A(x)VB(x)o,xA(x)V,xB(x)全稱量詞“”對“V”無分配律。存在量詞“,”對“A”無分配律。UI規(guī)則。UG規(guī)則。EG規(guī)則。UI規(guī)則。UG規(guī)則。EG規(guī)則。A(y)iA(c)A(y)xA(x)A(c),xA(x)ei規(guī)貝yei規(guī)貝y。A(c)AUB=xlxGAVxBAnB=xlxGAAxBAB=xlxWAAxB幕集P(A)=xlxcA對稱差集A,B=(A-B)U(B-A)A,B=(AUB)-(AnB)絕對補集A=xlxA廣義并UA=xl3z(zWAAxWz)廣義交nA=xlz(zWAxWz)設(shè)A=a,b,c

6、,a,c,d,a,e,fB=aC=a,c,d則UA=a,b,c,d,e,fUB=aUC=aUc,dU0=0nA=anB=anc=anc,d集合恒等式幕等律結(jié)合律交換律AUA=幕等律結(jié)合律交換律AUA=AAnA=A(AUB)UC=AU(BUC)AUB=BUA(AnB)nc=An(Bnc)AnB=BnA分配律AU(BAC)=(AUB)A(AUC)AA(BUC)=(AAB)U(AAC)同一律AU=AAAE=A零律AUE=EAA=排中律AUA=E矛盾律AAA=吸收律AU(AAB)=AAA(AUB)=A德摩根律A(BUC)=(AB)A(AC)A(BAC)=(AB)U(AC)(BUC)=BAC(BAC)=

7、BUC=EE=雙重否定律(A)=A集合運算性質(zhì)的一些重要結(jié)果AABcA,AABcBAcAUB,BcAUBA-BcAAB=AABAUB=B,A匸B,AAB=A,AB=AB=BA(AB)C=A(BC)A3=AAA=AB=ACB=C對偶(dual)式：一個集合表達式，如果只含有A、U、E、=、匸、，那么同時把A與U互換，把與E互換，把匸與互換，得到式子稱為原式的對偶式。有序?qū)哂幸韵滦再|(zhì)：(1)當xMy時，vx,yMvy,x。(2)=的充分必要條件是x=u且y=v。笛卡兒積的符號化表示為AXB=lxGAAyB如果IAI=m,IBI=n,則IAXBl=mn。笛卡兒積的運算性質(zhì)對任意集合A,根據(jù)定義有A

8、X=,XA=般的說，笛卡兒積運算不滿足交換律，即AXBHBXA(當AMAB工AAHB時)笛卡兒積運算不滿足結(jié)合律，即(AXB)XCMAX(BXC)(當AMABMACM時)笛卡兒積運算對并和交運算滿足分配律，即AX(BUC)=(AXB)U(AXC)(BUC)XA=(BXA)U(CXA)AX(BAC)=(AXB)A(AXC)(BAC)XA=(BXA)A(CXA)AcCABcDAXB匸CXD常用的關(guān)系對任意集合A,定義全域關(guān)系EA=vx,ylx丘AAy丘A=AXA恒等關(guān)系IA=vx,xlxWA空關(guān)系小于或等于關(guān)系：LA=vx,ylx,yWAAxWy,其中AcRo整除關(guān)系：DB=vx,ylx,yWBA

9、x整除y,其中AcZ*,Z*是非零整數(shù)集包含關(guān)系：Rc=lx,yWAAxcy,其中A是集合族。關(guān)系矩陣和關(guān)系圖設(shè)A=1,2,3,4設(shè)A=1,2,3,4,R=vl,l,vl,2,v2,3,v2,4,v4,2,則R的關(guān)系矩陣和關(guān)系圖分別是定義域domR定義域domR=值域ranR=y|域fldR=domRx|,y(vx,yWR),x(WR)UranR例求R=v1,2,v1,3,v2,4,v4,3的定義域、值域和域。解答domR=1,2,4ranR=2,3,4fldR=1,2,3,4逆R-1=|WR右復(fù)合FoG=|,t(vx,tWFAvt,yWG)限制RfA=|xRyAxWA像RA=ran(RfA)

10、例設(shè)R=,Rf1=,Rf=Rf2,3=,v2,4,R1=2,3R=R3=2設(shè)F是任意的關(guān)系，則(F-1)-1=FdomF-1=ranF,ranF-1=domF設(shè)F,G,H是任意的關(guān)系，則(FOG)OH=FO(GH)(FOG)-1=G-1oF-1設(shè)R為A上的關(guān)系，則RoIA=IA。R=R設(shè)F,G,H是任意的關(guān)系，則FO(GUH)=FGUFOH(GUH)OF=GOFUHOFFO(GHH)cFOGnFOH(GnH)OFcGOFnHOF設(shè)F為關(guān)系，A,B為集合，則Ff(AUB)=FfAUFfBFAUB=FAUFBFf(AHB)=FfAHFfBFAHBFAnFB關(guān)系的幕運算設(shè)R為A上的關(guān)系，n為自然數(shù)，

11、則R的n次幕定義為：RO=vx,xlxWA=IARn+1=Rn。R幕運算的性質(zhì)設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。設(shè)R是A上的關(guān)系，m,nWN,貝V(1)RmRn=Rm+n(2)(Rm)n=Rmn設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(sWR),反自反,x(xWAvx,x笑R),對稱,x,y(x,y丘AAvx,yWRvy,xWR)反對稱,x,y(x,yWAAWRAWRx=y),傳遞,x,y,z(x,y,zWAAWRAvy,zWRWR)關(guān)系性質(zhì)的等價描述設(shè)R為A上的關(guān)系，則R在A上自反當且僅當IARR在A上反自反當且僅當RnIA=R在A上對稱當且僅當R=R-1R在A上

12、反對稱當且僅當RnR-1IAR在A上傳遞當且僅當RRR(1)若R1,R2是自反的和對稱的，則R1UR2也是自反的和對稱的。若R1和R2是傳遞的，則R1nR2也是傳遞的。關(guān)系性質(zhì)的特點自反性反自反性對稱性關(guān)系性質(zhì)的特點自反性反自反性對稱性反對稱性傳遞性集合表達式IARRnIA=R=R-1RnR-1IARRR關(guān)系矩陣主對角線元主對角線元素矩陣是對稱矩若rij=1,且i對M2中1所素全是1全是0陣工j,則rji=0在位置，M中相應(yīng)的位置都是1關(guān)系圖每個頂點都每個頂點都沒如果兩個頂點如果兩點之間如果頂點關(guān)系圖每個頂點都每個頂點都沒如果兩個頂點如果兩點之間如果頂點Xi到有環(huán)有環(huán)之間有邊，一有邊，一定是x

13、j有邊，xj到定是一對方向一條有向邊(無xk有邊，則從相反的邊(無雙向邊)xi到xk也有邊有環(huán)有環(huán)單邊)自反性反自反性R1-1自反性反自反性R1-1VVR1HR2VVR1UR2VVR1-R2XVR1R2VX關(guān)系的性質(zhì)和運算之間的關(guān)系對稱性反對稱性傳遞性VVVVVVVXXVVXXXX閉包的構(gòu)造方法設(shè)R為A上的關(guān)系，則有自反閉包r(R)=RURO對稱閉包s(R)=RUR-lt(R)=RUR2UR3U.關(guān)系性質(zhì)與閉包運算之間的聯(lián)系設(shè)R是非空集合A上的關(guān)系，若R是自反的，則s(R)與t(R)也是自反的。若R是對稱的，則r(R)與上(只)也是對稱的。若R是傳遞的，則r(R)是傳遞的。等價類的性質(zhì)設(shè)R是非

14、空集合A上的等價關(guān)系，則VxGA，x是A的非空子集。Vx,yWA,如果xRy，貝9x=y。Vx,yWA，如果vx,y,R，則x與y不交。UxlxA=Ao偏序集中的特殊元素設(shè)vA,W為偏序集，BcA，yWB。(1)若Vx(xWBfyWx)成立，則稱y為B的最小元。若x(xWBfxWy)成立，則稱y為B的最大元。若x(xWBAxWyfx=y)成立，則稱y為B的極小元。最大元最小元極大元極小元若x(xWBAyWxfx=y)成立，則稱y為B的極大元最大元最小元極大元極小元122,3,6,12,24,36無2636,122,3,661266B上界下界上確界下確界2,3,6,12,24,36無無無無6,1

15、212,24,362,3,61262,3,66,12,24,36無6無66,12,24,36,2,3,6,662436B無24,362,36126無62,3666函數(shù)相等由定義可知，兩個函數(shù)F和G相等，一定滿足下面兩個條件:(1)domF=domG(2)xdomF=domG,都有F(x)=G(x)所有從A到B的函數(shù)的集合記作BA,讀作“B上A”，符號化表示為BA=fIf：A-B。例：設(shè)A=1,2,3，B=a,b，求BA。BA=f0,fl,f2,f3,f4,f5,f6,f7。其中f0=,v2,a,v3,af1=,v2,a,v3,bf2=,v2,b,v3,af3=,v2,b,v3,bf4=,f5=

16、,f6=,f7=,設(shè)fiAB,(1)右ranf=B，則稱f.AB是滿射(surjection)的。若yWranf都存在唯一的xA使得f(x)=y，則稱f.AB是單射(injection)的。若f既是滿射又是單射的，則稱f.AB是雙射(bijection)1a2a1a2a1b3b2c4c3d4單射雙射例：判斷下面函數(shù)是否為單射、滿射、雙射的,a1a1b2b2c3c3d4d函數(shù)滿射為什么？(1)f：RfR,f(x)=-x2+2x-1(2)f：Z+fR,fx)=lnx,Z+為正整數(shù)集f：RfZ,fx)=x(4)f：RfR,fx)=2x+1。解(1)f在x=1取得極大值0。既不是單射也不是滿射的。f是

17、單調(diào)上升的，是單射的，但不滿射。ranf=ln1,ln2,。f是滿射的，但不是單射的，例如f(1.5)=f(1.2)=l。f是滿射、單射、雙射的，因為它是單調(diào)函數(shù)并且ranf=R。例：給定無向圖G=vV,E,其中V=v1,v2,v3,v4,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)給定有向圖D=vV,E，其中V=a,b,c,d,E=va,a,va,b,va,b,va,d,vc,d,vd,c,vc,b。畫出G與D的圖形。鄰域：NG(v1)鄰域：NG(v1)=v2,v5閉鄰域：NG(v1)=v1,v2,v5關(guān)聯(lián)集

18、：IG(v1)=e1,e2,e3d(v1)=4(注意，環(huán)提供2度)，=4,5=1,v4是懸掛頂點，e7是懸掛邊。度數(shù)列為4,4,2,1,3。后繼元集：r+D(d)=c先驅(qū)元集：r-D(d)=a,c鄰域：ND(d)=a,c閉鄰域：ND(d)=a,c,d出度：d+(a)=4,入度：d-(a)=1(環(huán)e1提供出度1,提供入度1),d(a)=4+1=5o=5,5=3,+=4(在a點達到)5+=0(在b點達到)-=3(在b點達到)5-=1(在a和c點達到)按字母順序，度數(shù)列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2設(shè)G=是n階m條邊的無向圖，則下面各命題是等價的：(1)G是樹。(2)G中任意兩個頂點之間存在唯一的路徑。(3)G中無回路且m=n，1。(4)G是連通的且m=n，1。G是連通的且G中任何邊均為橋。G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一