第二章命题逻辑等值演算.ppt

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

1、第二章命题逻辑等值演算2.1等值式设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。如何判断哪些公式具有相同的真值？定义2.1设A,B式两个命题公式，若A,B构成的等价式AB为重言式，则称A与B是等值的，记作AB.（是元语言符号）例1.7中公式p→q和(┐p∨q)∧((p∧r)→p)的真值表相同，所以它们是等值的。即：p→q(┐p∨q)∧((p∧r)→p)判断等值式有如下方法：1.真值表2.等值演算3.范

2、式例2.1判断下面两个公式是否等值：┐(p∨q)与┐p∧┐q解:用真值表法判断┐(p∨q)(┐p∧┐q)是否为重言式。从表中可知它是重言式，即┐(p∨q)(┐p∧┐q)例2.2判断下列各组公式是否等值：(1)p→(q→r)与(p∧q)→r(2)(p→q)→r与(p∧q)→rp→(q→r)(p∧q)→r(p→q)→r(p∧q)→r用真值表法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。根

3、据已知的等值式推演出另外一些等值式的过程，称为等值演算。16组重要的等值式:1.双重否定律A┐┐A2.幂等律AA∨A,AA∧A3.交换律A∨BB∨A，A∧BB∧A4.结合律(A∨B)∨CA∨(B∨C)       (A∧B)∧CA∧(B∧C)5.分配律  ∨对∧的分配律A∨(B∧C)(A∨B)∧(A∨C)  ∧对∨的分配律A∧(B∨C)(A∧B)∨(A∧C)6.德摩根律   ┐(A∨B)┐A∧┐B，┐(A∧B)┐A∨┐B7.吸收律A∨(A∧B)A，A∧(A∨B)A8.零律A∨11,

4、A∧009.同一律A∨0A，A∧1A10.排中律A∨┐A111.矛盾律A∧┐A012.蕴涵等值式A→B┐A∨B13.等价等值式(AB)(A→B)∧(B→A)14.假言易位A→B┐B→┐A15.等价否定等值式AB┐A┐B16.归谬论(A→B)∧(A→┐B)┐A由于A,B,C可以代表任意的公式，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式中，取A=p，B=q时，得等值式p→q┐p∨q当取A=p∨q∨r，B=p∧q时，得等值式(p∨q∨r)→(

5、p∧q)┐(p∨q∨r)∨(p∧q)这些具体的等值式都被称为原来的等值式模式的代入实例。置换规则设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若BA，则Φ(B)Φ(A).例如：(p→q)→r(┐p∨q)→r（蕴含等值式、置换规则）AB┐(┐p∨q)∨r（蕴含等值式、置换规则）(p∧┐q)∨r（得摩根律、置换规则）(p∨r)∧(┐q∨r)（分配律、置换规则）公式之间的等值关系具有自反性AA对称性若AB，则BA传递性若AB，BC，则AC所以上述演算中得

6、到的公式彼此之间都是等值的。在演算的每一步都用到了置换规则，因而在以下的演算中，置换规则均不标出。等值演算的用途：(1)验证等值式例2.3用等值演算法验证等值式：(p∨q)→r(p→r)∧(q→r)证:可以从左边开始演算，也可以从右边开始演算。现在从右边开始演算。(p→r)∧(q→r)（┐p∨r)∧(┐q∨r)(┐p∧┐q)∨r┐(p∨q)∨r(p∨q)→r一般情况下，不能用等值演算法直接验证两个公式不等值。例2.4证明：(p→q)→rp→(q→r)证：方法一：真值表法。方法二：观察法。易知，010是(p→

7、q)→r的成假赋值，而010是p→(q→r)的成真赋值，所以原不等值式成立。方法三：设A=(p→q)→r,B=p→(q→r)A=(p→q)→r(┐p∨q)→r┐(┐p∨q)∨r(p∧┐q)∨rB=p→(q→r)┐p∨(┐q∨r)┐p∨┐q∨r容易观察到，000，010是A的成假赋值，而它们是B的成真赋值。(2)将命题公式化简及判断公式类型例2.5用等值演算法判断下列公式的类型。永真式(pq)pq(┐pq)pq┐((┐pq)p)q(┐(┐pq)┐p)q((p┐q)┐p)q

8、((p┐p)(┐q┐p))q(1(┐q┐p))q(┐q┐p)q(┐qq)┐p1┐p1矛盾式(2)┐(p(pq))r┐(┐ppq)r(p┐p┐q)r0r0最后结果说明(3)中公式不是重言式，00，01都是成假赋值，并且也不是矛盾式，因为10，11都是成真赋值。(3)p(