您好,欢迎访问三七文档
SpongeBobSquarePants11基本等值式1.双重否定律A┐┐A2.幂等律AA∨A,AA∧A3.交换律A∨BB∨A,A∧BB∧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∧┐A012.蕴涵等值式A→B┐A∨B13.等价等值式AB(A→B)∧(B→A)14.假言易位A→B┐B→┐A15.等价否定等值式AB┐A┐B16.归谬论(A→B)∧(A→┐B)┐A求给定公式范式的步骤(1)消去联结词→、(若存在)。(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。(3)利用分配律:利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。推理定律--重言蕴含式(1)A(A∨B)附加律(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)(AB)∧(BC)(AC)等价三段论(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)破坏性二难SpongeBobSquarePants222设个体域为有限集D={a1,a2,…,an},则有(1)xA(x)A(a1)∧A(a2)∧…∧A(an)(2)xA(x)A(a1)∨A(a2)∨…∨A(an)设A(x)是任意的含自由出现个体变项x的公式,则(1)┐xA(x)x┐A(x)(2)┐xA(x)x┐A(x)设A(x)是任意的含自由出现个体变项x的公式,B中不含x的出现,则(1)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)(2)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)设A(x),B(x)是任意的含自由出现个体变项x的公式,则(1)x(A(x)∧B(x))xA(x)∧xB(x)(2)x(A(x)∨B(x))xA(x)∨xB(x)全称量词“”对“∨”无分配律。存在量词“”对“∧”无分配律。UI规则。UG规则。EG规则。EI规则。A(c)xA(x)或A(y)xA(x)xA(x)A(y)xA(x)A(c)A(c)xA(x)SpongeBobSquarePants33A∪B={x|x∈A∨x∈B}、A∩B={x|x∈A∧x∈B}A-B={x|x∈A∧xB}幂集P(A)={x|xA}对称差集AB=(A-B)∪(B-A)AB=(A∪B)-(A∩B)绝对补集~A={x|xA}广义并∪A={x|z(z∈A∧x∈z)}广义交∩A={x|z(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}∪B={a}∪C=a∪{c,d}∪=∩A={a}∩B={a}∩C=a∩{c,d}集合恒等式幂等律A∪A=AA∩A=A结合律(A∪B)∪C=A∪(B∪C)(A∩B)∩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=A零律A∪E=EA∩=SpongeBobSquarePants444排中律A∪~A=E矛盾律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集合运算性质的一些重要结果A∩BA,A∩BBAA∪B,BA∪BA-BAA-B=A∩~BA∪B=BABA∩B=AA-B=AB=BA(AB)C=A(BC)A=AAA=AB=ACB=C对偶(dual)式:一个集合表达式,如果只含有∩、∪、~、、E、=、、,那么同时把∩与∪互换,把与E互换,把与互换,得到式子称为原式的对偶式。有序对x,y具有以下性质:(1)当x≠y时,x,y≠y,x。(2)x,y=u,v的充分必要条件是x=u且y=v。笛卡儿积的符号化表示为A×B={x,y|x∈A∧y∈B}如果|A|=m,|B|=n,则|A×B|=mn。笛卡儿积的运算性质(1)对任意集合A,根据定义有A×=,×A=(2)一般的说,笛卡儿积运算不满足交换律,即A×B≠B×A(当A≠∧B≠∧A≠B时)(3)笛卡儿积运算不满足结合律,即(A×B)×C≠A×(B×C)(当A≠∧B≠∧C≠时)(4)笛卡儿积运算对并和交运算满足分配律,即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常用的关系对任意集合A,定义全域关系EA={x,y|x∈A∧y∈A}=A×A恒等关系IA={x,x|x∈A}空关系SpongeBobSquarePants55小于或等于关系:LA={x,y|x,y∈A∧x≤y},其中AR。整除关系:DB={x,y|x,y∈B∧x整除y},其中AZ*,Z*是非零整数集包含关系:R={x,y|x,y∈A∧xy},其中A是集合族。关系矩阵和关系图设A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},则R的关系矩阵和关系图分别是定义域domR={x|y(x,y∈R)}值域ranR={y|x(x,y∈R)}域fldR=domR∪ranR例求R={1,2,1,3,2,4,4,3}的定义域、值域和域。解答domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}逆R-1={x,y|y,x∈R}右复合FG={x,y|t(x,t∈F∧t,y∈G)}限制R↑A={x,y|xRy∧x∈A}像R[A]=ran(R↑A)例设R={1,2,1,3,2,2,2,4,3,2}R↑{1}={1,2,1,3}R↑=R↑{2,3}={2,2,2,4},3,2}R[{1}]={2,3}R[]=R[{3}]={2}设F是任意的关系,则(1)(F-1)-1=F(2)domF-1=ranF,ranF-1=domF设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)-1=G-1F-1设R为A上的关系,则RIA=IAR=R设F,G,H是任意的关系,则(1)F(G∪H)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF0010000011000011MRSpongeBobSquarePants666设F为关系,A,B为集合,则(1)F↑(A∪B)=F↑A∪F↑B(2)F[A∪B]=F[A]∪F[B](3)F↑(A∩B)=F↑A∩F↑B(4)F[A∩B]F[A]∩F[B]关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为:(1)R0={x,x|x∈A}=IA(2)Rn+1=RnR幂运算的性质设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt。设R是A上的关系,m,n∈N,则(1)RmRn=Rm+n(2)(Rm)n=Rmn设R是A上的关系,若存在自然数s,t(st)使得Rs=Rt,则(1)对任何k∈N有Rs+k=Rt+k(2)对任何k,i∈N有Rs+kp+i=Rs+i,其中p=t-s(3)令S={R0,R1,…,Rt-1},则对于任意的q∈N有Rq∈S自反x(x∈A→x,x∈R),反自反x(x∈A→x,xR),对称xy(x,y∈A∧x,y∈R→y,x∈R)反对称xy(x,y∈A∧x,y∈R∧y,x∈R→x=y),传递xyz(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R)关系性质的等价描述设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R-1(4)R在A上反对称当且仅当R∩R-1IA(5)R在A上传递当且仅当RRR(1)若R1,R2是自反的和对称的,则R1∪R2也是自反的和对称的。(2)若R1和R2是传递的,则R1∩R2也是传递的。SpongeBobSquarePants77关系性质的特点自反性反自反性对称性反对称性传递性集合表达式IARR∩IA=R=R-1R∩R-1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij=1,且i≠j,则rji=0对M2中1所在位置,M中相应的位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,一定是一对方向相反的边(无单边)如果两点之间有边,一定是一条有向边(无双向边)如果顶点xi到xj有边,xj到xk有边,则从xi到xk也有边关系的性质和运算之间的关系自反性反自反性对称性反对称性传递性R1-1√√√√√R1∩R2√√√√√R1∪R2√√√××R1-R2×√√√×R1R2√××××闭包的构造方法设R为A上的关系,则有(1)自反闭包r(R)=R∪R0(2)对称闭包s(R)=R∪R-1(3)t(R)=R∪R2∪R3∪…关系性质与闭包运算之间的联系设R是非空集合A上的关系,(1)若R是自反的,则s(R)与t(R)也是自反的。(2)若R是对称的,则r(R)与t(R)也是对称的。(3)若R是传递的,则r(R)是传递的。SpongeBobSquarePants888等价类的性质设R是非空集合A上的等价关系,则(1)x∈A,[x]是A的非空子集。(2)x,y∈A,如果xRy,则[x]=[y]。(3)x,y∈A,如果x,yR,则[x]与[y]不交。(4)∪{[x]|x∈A}=A。偏序集中的特殊元素设A,≤为偏序集,BA,y∈B。(1)若x(x∈B→y≤x)成立,则称y为B的最小元。(2)若x(x∈B→x≤y)成立,则称y为B的最大元。(3)若x(x∈B∧x≤y→x=y)成立,则称y为B的极小元。(4)若x(x∈B∧y≤x→x=y)成立,则称y为B的极大元B上界下界上确界下确界{2,3,6,12,24,36}无无无无{6,12}12,24,362,3,6126{2,3,6}6,12,24,36无6无{6}6,12,24,36,2,3,6,66函数相等由定义可知,两个函数F和G相等,一定满足下面两个条件:(1)domF=domG(2)x∈domF=domG,都有F(x)=G(x)所有从A到B的函数的集合记作BA,读作“B上A”,符号化表示为BA={f|f:A→B}。例:设A={1,2,3},B={a,b},求BA。BA={f0,f1,f2,f3,f4,f5,f6,f7}。其中f0={1,a,2,a,3,a}f1={1,a,2,a,3,b}f2={1,a,2,b,
本文标题:离散数学公式
链接地址:https://www.777doc.com/doc-2755573 .html