離散數(shù)學公式

11基本等值式1.雙重否定律A┐┐A2.冪等律AA∨A,AA∧AABBAABB∧A4.結合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)5.分配律A∨(B∧C)(A∨B)∧(A∨C)(∨對∧的分配律)A∧(B∨C)(A∧B)∨(A∧C)(∧對∨的分配律)6.德·摩根律┐(A∨B)┐A∧┐B┐(A∧B)┐A∨┐B7.吸收律A∨(A∧B)A，A∧(A∨B)A8.零律A∨11,A∧009.同一律A∨0A，A∧1A10.排中律A∨┐A111.矛盾律A∧┐A0B13.等價等值式A一B(A→B)∧(B→A)A15.等價否定等值式A一B┐A一┐B16.歸謬論(A→B)∧(A→┐B)┐A求給定公式范式的步驟(1)消去聯(lián)結詞→、一(若存在)。2)否定號的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。簡律假言簡律假言推理拒取式析取三段論假言三段論等價三段論構造性二難構造性二難(特殊形式)2)(A∧B)A(3)(A→B)∧AB(4)(A→B)∧┐B┐A(5)(A∨B)∧┐BA(6)(A→B)∧(B→C)(A→C)(7)(A一B)∧(B一C)(A一C)(8)(A→B)∧(C→D)∧(A∨C)(B∨D)(A→B)∧(┐A→B)∧(A∨┐A)B(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破壞性二難BobSquarePantsBobSquarePants222(1)VxA(x)A(a1)∧A(a2)∧…∧A(an)(1)┐VxA(x)3x┐A(x)(2)┐3xA(x)Vx┐A(x)x(1)Vx(A(x)∨B)VxA(x)∨BVx(A(x)∧B)VxA(x)∧BVx(A(x)→B)3xA(x)→BVx(B→A(x))B→VxA(x)(2)3x(A(x)∨B)3xA(x)∨BxAxBxAx)∧B3x(A(x)→B)VxA(x)→BxBAxBxA(x)(1)Vx(A(x)∧B(x))VxA(x)∧VxB(x)(2)3x(A(x)∨B(x))3xA(x)∨3xB(x)V”無分配律。 A A(y)33A∪B＝{x|x∈A∨x∈B}A∩B＝{x|x∈A∧x∈B}對稱差集AB＝(A－B)∪(B－A)AB＝(A∪B)－(A∩B)絕對補集~A＝{x|x茫A}并∪A＝{x|3z(z∈A∧x∈z)}廣義交∩A＝{x|Vz(z∈A→x∈z)}A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}則∪A＝{a,b,c,d,e,f}集合恒等式冪等律A∪A＝AA∩A＝AABCABC)AB∩C＝A∩(B∩C)A∪B＝B∪AA∩B＝B∩A律A∪(B∩C)＝(A∪B)∩(A∪C)A∩(B∪C)＝(A∩B)∪(A∩C)A∪＝AA∩E＝AA∪E＝EBobSquarePants4BobSquarePants44排中律A∪~A＝E4矛盾律A∩~A＝吸收律A∪(A∩B)＝AA∩(A∪B)＝A德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)~(B∪C)＝~B∩~C~(B∩C)＝~B∪~C~＝E~E＝雙重否定律~(~A)＝A集合運算性質(zhì)的一些重要結果A∩BA，A∩BBAA∪B，BA∪BA－BAA－B＝A∩~BAB＝BA(AB)C＝A(BC)A＝AAB＝ACB＝Cxy<u,v>的充分必要條件是x＝u且y＝v。笛卡兒積的符號化表示為A×B＝{<x,y>|x∈A∧y∈B}Am|B|=n,則|A×B|=mn。笛卡兒積的運算性質(zhì)A×B≠B×A(當A≠∧B≠∧A≠B時)足結合律，即(A×B)×C≠A×(B×C)(當A≠∧B≠∧C≠時)A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)(5)AC∧BDA×BC×D的關系關系EA={<x,y>|x∈A∧y∈A}=A×A等關系IA={<x,x>|x∈A}空關系55R系矩陣和關系圖A,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，「1M=0R0L0100101000]00」domRx|3y(<x,y>∈R)}值域ranR＝{y|3x(<x,y>∈R)}域fldR＝domR∪ranR解答domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}BobSquarePants6BobSquarePants666(2)F[A∪B]＝F[A]∪F[B](4)F[A∩B]F[A]∩F[B]系的冪運算(1)R0＝{<x,x>|x∈A}＝IA(2)Rn+1＝Rn。R冪運算的性質(zhì)對稱VxVy(x,y∈A∧<x,y>∈R→<y,x>∈R)對稱VxVy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，VxVyVzxy,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)關系性質(zhì)的等價描述(1)R在A上自反當且僅當IAR(2)R在A上反自反當且僅當R∩IA＝(3)R在A上對稱當且僅當R＝R-1(4)R在A上反對稱當且僅當R∩R-1IA77系性質(zhì)的特點性性性遞性達式IAR主對角線元素主對角線元素全是對稱矩陣每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊，一定是一對方向相反的邊)如果兩點之間有雙向邊)邊關系的性質(zhì)和運算之間的關系性性性遞性√√√√√√√√√√√√√××R1－R2×√√√×√××××(1)自反閉包r(R)＝R∪R0(2)對稱閉包s(R)＝R∪R-1(3)t(R)＝R∪R2∪R3∪…關系性質(zhì)與閉包運算之間的聯(lián)系(1)若R是自反的，則s(R)與t(R)也是自反的。(2)若R是對稱的，則r(R)與t(R)也是對稱的。(3)若R是傳遞的，則r(R)是傳遞的。BobSquarePants8BobSquarePants88等價類的性質(zhì)8(1)Vx∈A，[x]是A的非空子集。(2)Vx,y∈A，如果xRy，則[x]＝[y]。(3)Vx,y∈A，如果<x,y>R，則[x]與[y]不交。(4)∪{[x]|x∈A}＝A。偏序集中的特殊元素(1)若Vx(x∈B→y≤x)成立，則稱y為B的最小元。(2)若Vx(x∈B→x≤y)成立，則稱y為B的最大元。Vx(x∈B∧x≤y→x＝y(tǒng))成立，則稱y為B的極小元。Vx(x∈B∧y≤x→x＝y(tǒng))成立，則稱y為B的極大元{2,3,6,12,24,36}2,3{6,12}1261266無62,36666632632{2,3,6}6,12,24,36無6無4,36,2,3,6,66(1)domF＝domG(2)Vx∈domF＝domG，都有F(x)＝G(x)BA＝{f0,f1,f2,f3,f4,f5,f6,f7}。其中f2＝{<1,a>,<2,b>,<3,a>}f4＝{<1,b>,<2,a>,<3,a>}f6＝{<1,b>,<2,b>,<3,a>}f3＝{<1,a>,<2,b>,<3,b>}f5＝{<1,b>,<2,a>,<3,b>}f7＝{<1,b>,<2,b>,<3,b>}設f:A→B，(1)若ranf＝B，則稱f:A→B是滿射(surjection)的。(2)若Vy∈ranf都存在唯一的x∈A使得f(x)＝y(tǒng)，則稱f:A→B是單射(injection)的。99(3)若f既是滿射又是單射的，則稱f:A→B是雙射(bijection)cI234cpI234abcpcI234bcpI23fRRfxxx(2)f：Z+→R，f(x)=lnx，Z+為正整數(shù)集解(1)f在x=1取得極大值0。既不是單射也不是滿射的。(2)f是單調(diào)上升的，是單射的，但不滿射。ranf={ln1,ln2,…}。(4)f是滿射、單射、雙射的，因為它是單調(diào)函數(shù)并且ranf=R。E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。鄰域：NG(v1)＝{v2，v5}da1＝5?！鳎?，δ＝3，BobSquarePantsBobSquarePantsG(2)G中任意兩個頂點之間存在唯一的路徑。(5)G是連通的且G中任何邊均為橋。G得圖中得到唯一的一個含新邊的圈。n＝1+2+x＝3+x)分支點——樹根與內(nèi)點的總稱7)樹高——T中層數(shù)最大頂點的層數(shù)樹葉——8片內(nèi)點——6個分支點——7個高度——5eBobSquarePantsBobSquarePantsR關系r相容關系R○R關系r相容關系R○S關系與關系的復合domf函數(shù)的定義域(前域)ranf函數(shù)的值域YGCD(x,y)x,y最大公約數(shù)LCM(x,y)x,y最小公倍數(shù)aH(Ha)H關于a的左(右)陪集Ker(f)同態(tài)映射f的核(或稱f同態(tài)核)d(u,v)點u與點v間的距離dvvGVE點集為V,邊集為E的圖W(G)圖G的連通分支數(shù)k(G)圖G的點連通度△(G)圖G的最大點度A(G)圖G的鄰接矩陣P(G)圖G的可達矩陣M(G)圖G的關聯(lián)矩陣C復數(shù)集N自然數(shù)集(包含0在內(nèi))N*正自然數(shù)集P素數(shù)集Q有理數(shù)集R實數(shù)集Z整數(shù)集Set集范疇Top拓撲空間范疇Ab交換群范疇Grp群范疇Mon單元半群范疇Ring有單位元的(結合)環(huán)范疇Rng環(huán)范疇CRng交換環(huán)范疇R-mod環(huán)R的左模范疇mod-R環(huán)R的右模范疇Field域范疇Poset偏序集范疇╞滿足符(公式在E上有效，公式在E上可滿足)┐命題的“非”運算→命題的“條件”運算?命題的“雙條件”運算的A<=>B命題A與B等價關系A=>B命題A與B的蘊涵關系A*公式A的對偶公式wff合式公式iff當且僅當↑命題的“與非”運算(“與非門”)↓命題的“或非”運算(“或非門”)□模態(tài)詞“必然”

模態(tài)詞“可能”φ空集∈屬于(?不屬于)P(A)集合A的冪集|A|集合A的點數(shù)R^2=R○R[R^n=R^(n-1)○R]關系R的“復合”?包含?(或下面