命题逻辑等值演算.ppt

《命题逻辑等值演算.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章命题逻辑等值演算主要内容等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集可满足性问题与消解法12.1等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式.几点说明：定义中，A,B,均为元语言符号.不是一个新的联结词.A或B中可能有哑元出现.例如(pq)((pq)(rr))r为左边公式的哑元.用真值表可检查两个公式是否等值.2等值式例题例1判断下列各组公式是否等值:(1)p(qr)与(pq)r111111011111110111011101000001010011

2、100101110111(pq)rp(qr)qrpqrpq00000011结论:p(qr)(pq)r3等值式例题(2)p(qr)与(pq)r010111011111110111011101000001010011100101110111(pq)rp(qr)qrpqrpq11110011结论:p(qr)与(pq)r不等值4基本等值式双重否定律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

3、C),A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A5基本等值式零律A11,A00同一律A0A,A1A排中律AA1矛盾律AA0蕴涵等值式ABAB假言易位ABBA等价等值式AB(AB)(BA)等价否定等值式ABAB归谬论(AB)(AB)A6基本等值式说明上述等值式都是用元语言符号书写的，其中的A，B，C可以代表任意的公式，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体等值式。例如：

4、A＝p,B=q时,pqpqA=pqr,B=pq时，(pqr)(pq)(pqr)(pq)7对偶式在给定的命题公式A中，将联结词换成，将换成，若有特殊变元0和1亦相互取代，所得公式A*称为A的对偶式。反演规则：设A和A*是对偶式，p1,p2,…,pn是出现在A和A*中的原子变元，则A(p1,p2,…,pn)A*(p1,p2,…,pn)因为：AB(AB),AB(AB)对偶规则：如果AB,则A*B*。8等值演算与置换规则1.等值演算由已知的等值式推演出新的等值式的过程.2.置换规则设(A)是含公式

5、A的命题公式，(B)是用公式B置换(A)中所有的A后得到的命题公式，若BA，则(B)(A).3.等值演算的基础：基本的等值式置换规则等值关系的性质：自反性、对称性、传递性9等值演算的应用举例证明两个公式等值例2证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）p(qr)（蕴涵等值式，置换规则）(pq)r（结合律）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式）今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值10证明两个公式不等值例3证明p(qr)与(pq)r不

6、等值证：方法一真值表法.见例1(2)方法二观察法.观察到000,010是左边的成真赋值，是右边的成假赋值方法三先用等值演算化简公式，然后再观察.p(qr)pqr(pq)r(pq)r(pq)r看出000,010分别是左边的成真赋值和右边的成假赋值.等值演算的应用举例11判断公式类型:A为矛盾式当且仅当A0A为重言式当且仅当A1例4用等值演算法判断下列公式的类型(1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)等值演算的应用举例12判断公式类型解(1)q(pq)q(pq)（蕴

7、涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）矛盾式13判断公式类型(2)(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1重言式14判断公式类型(3)((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）可满足式152.2析取范式与合取范式定义2.2(1)文字——命题变项及其否定的总称(2)简单析取式——有限个文字构成的析取式p,q,pq,pqr,…(3