资源描述：
《离散数学第2章-命题逻辑等值演算课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学DiscreteMathematics9/2/20211DiscreteMath.,ChenChen第二章命题逻辑等值演算ChapterTwoPropositionLogic9/2/20212DiscreteMath.,ChenChen2.1等值式2.2析取范式与合取范式2.3联结词的完备集等值式定义基本等值式等值演算（置换规则）简单析取（合取）式极大（小）项（主）析（合）取范式真值函数联结词完备集2.4可满足性问题与消解法第二章内容9/2/20213DiscreteMath.,ChenChen设公式Ａ、Ｂ中总共含有命题变项p1,p2
2、,…pn，但Ａ或Ｂ并不全含有这些变项。如果某个变项未在公式Ａ中出现，则称该变项为Ａ的哑元。同样可定义Ｂ的哑元。在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内，即将Ａ、Ｂ都看成含所有p1,p2,…pn的命题公式，如果在所有2n个赋值下，Ａ与Ｂ的真值相同，则ＡＢ为重言式。哑元9/2/20214DiscreteMath.,ChenChen定义2.1设A,B是两个命题公式，若A,B构成的等价式A↔B为重言式，则称A与B是等值的,记为A⇔B。例2.1判断公式┐(p∨q)与┐p∧┐q是否等值。解：用真值表法判断,如下：pq┐p┐qp∨q┐(p∨q)
3、┐p∧┐q┐(p∨q)↔(┐p∧┐q)00011011注：A与B等值当且仅当A与B的真值表相同。因此，检验A与B是否等值，也可通过检查A与B的真值表是否相同来实现。从表中可见，┐(p∨q)与┐p∨┐q等值。110111101001011001001001定义9/2/20215DiscreteMath.,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∧
4、q)→r.110111110111111111000111由真值表可见，p→(q→r)⇔(p∧q)→r,例2.2判断下列两组公式是否等值：9/2/20216DiscreteMath.,ChenChen当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为等值式模式，通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下：1.双重否定律：A⇔┐(┐A)2.幂等律：A⇔A∨A,A⇔A∧A3.交换律:A∨B⇔B∨A,A∧B⇔B∧A4.结合律:(A∨B)∨C⇔A∨(B∨C),(A∧B)∧C⇔
5、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)⇔A等值式模式9/2/20217DiscreteMath.,ChenChen8.零律：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→
6、B⇔┐B→┐A15.等价否定等值式:A↔B⇔┐A↔┐B16.归谬论:(A→B)∧(A→┐B)⇔┐A等值式模式（续）9/2/20218DiscreteMath.,ChenChen利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后所得的公式。若B⇔A,则Φ(B)⇔Φ(A)。等值演算9/2/20219DiscreteMath.,ChenChen例如，对公式(p→q)→r,如果用┐
7、p∨q置换其中的p→q,则得(┐p∨q)→r.由于p→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)为简便起见,以后凡用到置换规则时,均不必标出。(蕴含等值式，置换规则）(蕴含等值式，置换规则）(德摩根律，置换规则）(分配律，置换规则）等值演算-例子9/2/202110DiscreteMath.,ChenChen例2.3用等值演算证明:(p∨q)→r⇔(p→r)∧(q→r)注：用等值演算证明等值式时，既可以从左向右推
8、演，也可以从右向左推演。证：(p→r)∧(q→r)⇔(┐p∨r)∧(┐q∨r)⇔(┐p∧┐q)∨r⇔┐(p∨q)∨r⇔(p∨q)→r(蕴含等值式)(分配律)(德摩根
