一-2命题逻辑等值演算.ppt

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

1、第2章命题逻辑等值演算本章的主要内容等值式与基本的等值式等值演算与置换规则析取范式与合取范式、主析取范式与主合取范式本章与后续各章的关系是第一章的抽象与延伸是后续各章的现行准备第一节等值式基本问题：基本要求：教学重点：教学重点：1.等值的基本概念2.等值的判断（真值表法、等值代换法）3.置换规则4.等值演算的应用1.熟练掌握等值式的概念及置换规则2.熟练应用等值式及置换规则进行等值演算3.掌握等值演算的应用等值演算、置换规则等值演算等值的基本概念等值的判断（演算）真值表法公式代换法等值演算的应用等值式？两公式什么时候代表了同一个命题呢？●抽象地看，它们的真假取值完全相同时即代表了相同的命题。

2、◆设公式A,B共同含有n个命题变项，可能对A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。一、等值式定义2.1：设A,B是两个命题公式，若A,B构成的等价式AB为重言式，则称A与B是等值的，记作AB。说明定义中,A,B,都是元语言符号。A或B中可能有哑元出现。p→q(┐p∨q)∨(┐r∧r)r为左边公式中的哑元。用真值表可以验证两个公式是否等值。一、基本概念注意：符号和所表达的含义完全不同。前者表示A和B之间的关系，后者表示A和B之间的运算。例题例2.1判断下面两个公式是否等值┐(p∨q)与┐p∧┐q解答说

3、明在用真值表法判断AB是否为重言式时，真值表的最后一列可以省略。等值例题例题2.2判断下列各组公式是否等值(1)p→(q→r)与(p∧q)→r(2)(p→q)→r与(p∧q)→r解答等值不等值二、基本等值式（等值式模式）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

4、∧B)A，A∧(A∨B)A基本等值式8.零律A∨11,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三、对偶原理一个逻辑等值式，如果只含有┐、∨、∧、0、1那么同时把∨和∧互换把0和1互换得到的还是等值式。四、等值演算与置换规则等值式模式：各等值式都是用元语言符号书写的，其中A,B,C可以代表任意的公式，称这样的等值式为等值式模式。代入实例：

5、每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式A→B┐A∨B中，取A=p，B=q时，得等值式p→q┐p∨q取A=p∨q∨r，B=p∧q时，得等值式(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)这些具体的等值式都被称为原来的等值式模式的代入实例。等值演算：由已知的等值式推演出另外一些等值式的过程为等值演算。置换规则：设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若BA，则Φ(B)Φ(A)。五、关于等值演算1.等值演算的基础等值关系的性质：自反性：AA。对称性：若AB，则BA。传递性：若AB且BC

6、，则AC。基本的等值式置换规则2.等值演算的应用证明两个公式等值判断公式类型解判定问题两点说明：等值演算的应用举例证明两个公式等值(p→q)→r(p∨r)∧(┐q∨r)(p→q)→r(┐p∨q)→r（蕴含等值式、置换规则）┐(┐p∨q)∨r（蕴含等值式、置换规则）(p∧┐q)∨r（德摩根律、置换规则）(p∨r)∧(┐q∨r)（分配律、置换规则）说明也可以从右边开始演算因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出通常不用等值演算直接证明两个公式不等值解答例题例2.3用等值演算法验证等值式(p∨q)→r(p→r)∧(q→r)(p→r)∧(q→r)(┐p∨r)∧

7、(┐q∨r)(蕴含等值式)(┐p∧┐q)∨r(分配律)┐(p∨q)∨r(德摩根律)(p∨q)→r(蕴含等值式)解答例题例2.4证明：(p→q)→r与p→(q→r)不等值方法一、真值表法。方法二、观察法。易知，010是(p→q)→r的成假赋值，而010是p→(q→r)的成真赋值，所以原不等值式成立。方法三、通过等值演算化成容易观察真值的情况，再进行判断。A=(p→q)→r(┐p∨q)→r（蕴涵等值式）