命题逻辑等值演算课件.ppt

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

1、主要内容等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集可满足性问题与消解法第二章命题逻辑等值演算1两公式什么时候代表了同一个命题呢？抽象地看,它们的真假取值完全相同时即代表了相同的命题.设公式A,B共同含有n个命题变项,可能A或B有哑元,若A与B有相同的真值表,则说明在2n次方个赋值的每个赋值下,A与B的真值都相同.于是等价式AB应为重言式.2.1等值式22.1等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：

2、定义中，A,B,均为元语言符号A或B中可能有哑元出现.例如(pq)((pq)(rr))r为左边公式的哑元.用真值表可检查两个公式是否等值请验证：p(qr)(pq)rp(qr)不与(pq)r等值3定义中给出的符号不是联结词符,它是用来说明A与B等值（AB是重言式）的一种记法,因而是元语言符号.此记号在下文中频繁出现,千万不要将它与混为一谈,同时也要注意它与一般等号=的区别.判断等值式有如下方法：1.真值表2.等值演算3.范式4用真值表判断公式的等值例1判断下面两个

3、公式是否等值：        ┐(p∨q)与┐p∧┐q解:用真值表法判断┐(p∨q)(┐p∧┐q)是否为重言式.此等价式的真值表如表1所示,从表中可知它是重言式,因而┐(p∨q)与┐p∧┐q等值,即┐(p∨q)(┐p∧┐q).5表1(p∨q)(┐p∧┐q)的真值表6等值式例题例2判断下列各组公式是否等值:(1)p(qr)与(pq)r111111011111110111011101000001010011100101110111(pq)rp(qr)qrpqrpq00000011

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

5、(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A9基本等值式零律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特别提示：必须牢记这16组等值式，这是继续学习的基础10等值演算与置换规则1.等值演算——由已知的等值式推演出新的等值式的

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

7、则注意：用等值演算不能直接证明两个公式不等值12证明两个公式不等值例3证明p(qr)与(pq)r不等值证方法一真值表法,见例1(2)方法二观察法.观察到000,010是左边的成真赋值，是右边的成假赋值方法三先用等值演算化简公式，然后再观察p(qr)pqr(pq)r(pq)r(pq)r更容易看出前面的两个赋值分别是左边的成真赋值和右边的成假赋值等值演算的应用举例13判断公式类型:A为矛盾式当且仅当A0A为重言式当且仅当A1例4用等值演算法判断下列公式的类型(

8、1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)等值演算的应用举例解(1)q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）矛盾式14判断公式类型(2)(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1重言式(3)((pq)(pq))