离散数学之等值演算.ppt

**等值式定义若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式说明:定义中,A,B,均为元语言符号,,在(pq)((pq)(rr))中,:p(qr)(pq)rp(qr)(pq)r*基本等值式双重否定律:AA等幂律:AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC)*基本等值式(续)德·摩根律:(AB)AB(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,A1A排中律:AA1矛盾律:AA0*基本等值式(续)蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学****的基础*等值演算与置换规则等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)等值演算的基础:(1)等值关系的性质:自反、对称、传递(2)基本的等值式(3)置换规则*应用举例——证明两个公式等值例1证明p(qr)(pq)r证p(qr)p(qr)(蕴涵等值式,置换规则)(pq)r(结合律,置换规则)(pq)r(德摩根律,置换规则)(pq)r(蕴涵等值式,置换规则)说明:也可以从右边开始演算(请做一遍)因为每一步都用置换规则,故可不写出熟练后,基本等值式也可以不写出*应用举例——证明两个公式不等值例2证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,(自己证),010等是左边的的成真赋值,,再观察.*应用举例——判断公式类型例3用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)(蕴涵等值式)q(pq)(德摩根律)p(qq)(交换律,结合律)p0(矛盾律)0(零律)由最后一步可知,该式为矛盾式.*例3(续)(2)(pq)(qp)解(pq)(qp)(pq)(qp)(蕴涵等值式)(pq)(pq)(交换律)1由最后一步可知,:最后一步为什么等值于1?