命题逻辑等值演算.ppt

DiscreteMathematicsDate1DiscreteMath.,ChenChen第二章命题逻辑等值演算ChapterTwoPropositionLogicDate2DiscreteMath.,(置换规则)简单析取(合取)式极大(小)项(主)析(合).,ChenChen设公式A、B中总共含有命题变项p1,p2,…pn,但A或B并不全含有这些变项。如果某个变项未在公式A中出现,则称该变项为A的哑元。同样可定义B的哑元。在讨论A与B是否有相同的真值表时,应将哑元考虑在内,即将A、B都看成含所有p1,p2,…pn的命题公式,如果在所有2n个赋值下,A与B的真值相同,则AB为重言式。哑元Date4DiscreteMath.,,B是两个命题公式,若A,B构成的等价式A↔B为重言式,则称A与B是等值的,记为A⇔B。┐(p∨q)与┐p∧┐q是否等值。解:用真值表法判断,如下:pq┐p┐qp∨q┐(p∨q)┐p∧┐q┐(p∨q)↔(┐p∧┐q)00011011注:A与B等值当且仅当A与B的真值表相同。因此,检验A与B是否等值,也可通过检查A与B的真值表是否相同来实现。从表中可见,┐(p∨q)与┐p∨┐q等值。1101111010010**********定义Date5DiscreteMath.,ChenChen(1)p→(q→r)与(p∧q)→r;(2)(p→q)→r与(p∧q)→r。解:所给的4个公式的真值表如下:pqrp→(q→r)(p∧q)→r(p→q)→r000001010011100101110111但(p→q)→r⇔(p∧q)→**********由真值表可见,p→(q→r)⇔(p∧q)→r,:Date6DiscreteMath.,ChenChen当命题公式中变项较多时,用上述方法判断两个公式是否等值计算量很大。为此,人们将一组经检验为正确的等值式作为等值式模式,通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下::A⇔┐(┐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等值式模式Date7DiscreteMath.,: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)⇔┐A等值式模式(续)Date8DiscreteMath.,ChenChen利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设Φ(A)是含公式A的命题公式,Φ(B)是用公式B置换了Φ(A)中所有的A后所得的公式。若B⇔A,则Φ(B)⇔Φ(A)。等值演算Date9DiscreteMath.,ChenChen例如,对公式(p→q)→r,如果用┐p∨q置换其中的p→q,则得(┐p∨q)→→q⇔┐p∨q,故(p→q)→r⇔(┐p∨q)→r。类似地,可进行如下等值演算:(p→q)→r⇔(┐p∨q)→r⇔┐(┐p∨q)∨r⇔(p∧┐q)∨r⇔(p∨r)∧(┐q∨r)为简便起见,以后凡用到置换规则时,均不必标出。(蕴含等值式,置换规则)(蕴含等值式,置换规则)(德摩根律,置换规则)(分配律,置换规则)等值演算-例子Date10DiscreteMath.,ChenChen