《离散数学公式54166》由会员分享,可在线阅读,更多相关《离散数学公式54166(12页珍藏版)》请在金锄头文库上搜索。
1、11SpongeBob SquarePants基本等值式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 AB
2、16.归谬论(AB)(AB) A 求给定公式范式的步骤 (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)(
3、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)是任意的含自由出现个体变项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
4、(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规则。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
5、 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) 同一律 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
6、 BC 对偶(dual)式:一个集合表达式,如果只含有、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)(
7、CA)A(BC)=(AB)(AC) (BC)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
8、 ran R2,3,4 fld R1,2,3,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