《离散数学公式》由会员分享，可在线阅读，更多相关《离散数学公式（11页珍藏版）》请在金锄头文库上搜索。
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) 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)消去联结词、(若存在)。(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。(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) 构造性二难 (AB)(AB)(AA) B 构造性二难(特殊形式)(9)(AB)(CD)(BD) (AC) 破坏性二难 设个体域
3、为有限集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) $xA(x)（2）$xA(x) xA(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(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)设A(x)，B(x)是
4、任意的含自由出现个体变项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规则。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)设 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 结合律 (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 集合运算性质的一些重要结果ABA，ABBAAB，BABABAABAB ABB AB ABA ABABBA (AB)CA(BC) AA AA ABAC BC 对偶(dual)式：一个集合表达式，
6、如果只含有、E、，那么同时把与互换，把与E互换，把与互换，得到式子称为原式的对偶式。有序对具有以下性质： （1）当xy时，。 （2）的充分必要条件是xu且yv。 笛卡儿积的符号化表示为 AB|xAyB 如果|A|=m,|B|=n,则|AB|=mn。笛卡儿积的运算性质 (1)对任意集合A，根据定义有A, A(2)一般的说，笛卡儿积运算不满足交换律，即ABBA (当 A B AB 时)(3)笛卡儿积运算不满足结合律，即(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常用的关系对任意集合A，定义全域关系 EA=|xAyA=AA 恒等关系 IA=|xA空关系 小于或等于关系：LA=|x,yAxy，其中 AR。整除关系：DB=|x,yBx整除y，其中 AZ* ，Z*是非零整数集包含关系：R|x,yAxy，其中 A是集合族。 关系矩阵和关系图设 A=1,2,3,4，R=,，则R的关系矩阵和关系图分别是 定义域 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) 例 设R，R1， R R2,3， R12,3 R R32设F是任意的关系，则 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F 设F，G，H是任意的关系，则(1)(FG)HF(GH)(2)(FG)-1G-1 F-1设R为A上的关系，则R IAIA RR设F，G，H是任意的关系，则(1) F(GH)FGFH(2) (GH)FGFHF(3) F(GH)FGFH(4) (GH)FGFHF设F为关系，A,B为集合，则(1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABFAFB 关系的幂运算设R为A上的关系，n为自然数，则R的n次幂定义为：（1） R0|xAIA（2） Rn+1Rn R幂运算的性质设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。设R是A上的关系，m,nN，则(1)Rm RnRm+n (2)(Rm)nRmn设R是A上的关系，若存在自然数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
