命题逻辑等值演算.ppt

两公式什么时候代表了同一个命题呢?抽象地看,两个公式在任何相同的赋值下有相同的真假时即代表了相同的命题。设公式A,B共同含有n个命题变项,可能对A或B有哑元,若A与B有相同的真值表,则说明在2n个赋值的每个赋值下,A与B的真值都相同。于是公式AB应为重言式。§、,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记作AB。说明注意与的区别。A或B中可能有哑元出现。p→q(┐p∨q)∨(┐r∧r)r为左边公式中的哑元。用真值表可以验证两个公式是否等值。 ┐(p∨q)与┐p∧┐q解答说明在用真值表法判断AB是否为重言式时,真值表的最后一列可以省略。(1)p→(q→r)与(p∧q)→r(2)(p→q)→r与(p∧q)→r解答等值不等值2、 A┐┐ AA∨A, AA∧ A∨BB∨A, A∧BB∧(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∨┐         A∨(A∧B)A,A∧(A∨B)        A∨11,A∧0          A∨0A,A∧1         A∨┐A    A∧┐A     A→B┐A∨    AB(A→B)∧(B→A)       A→B┐B→┐      AB┐A┐       (A→B)∧(A→┐B)┐A3、对偶原理一个逻辑等值式,如果只含有┐、∨、∧、0、1那么同时把∨和∧互换 把0和1互换得到的还是等值式。4、等值演算与置换规则各等值式都是用元语言符号书写的,其中A,B,C可以代表任意的公式,称这样的等值式为等值式模式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如,在蕴涵等值式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)。关于等值演算的说明等值演算的基础等值关系的性质:自反性:AA。对称性:若AB,则BA。传递性:若AB且BC,则AC。基本的等值式置换规则等值演算的应用证明两个公式等值判断公式类型解判定问题等值演算的应用举例证明两个公式等值(p→q)→r(p∨r)∧(┐q∨r)(p→q)→r(┐p∨q)→r (蕴含等值式、置换规则)┐(┐p∨q)∨r (蕴含等值式、置换规则)(p∧┐q)∨r (德摩根律、置换规则)(p∨r)∧(┐q∨r) (分配律、置换规则)说明也可以从右边开始演算因为每一步都用置换规则,故可不写出熟练后,基本等值式也可以不写出通常不用等值演算直接证明两个公式不等值解答