离散数学第2章-命题逻辑等值演算

CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen1离散数学DiscreteMathematicsCHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen2第二章命题逻辑等值演算ChapterTwoPropositionLogicCHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen32.1等值式2.2析取范式与合取范式2.3联结词的完备集等值式定义基本等值式等值演算（置换规则）简单析取（合取）式极大（小）项（主）析（合）取范式真值函数联结词完备集2.4可满足性问题与消解法第二章内容CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen4设公式Ａ、Ｂ中总共含有命题变项p1,p2,…pn，但Ａ或Ｂ并不全含有这些变项。如果某个变项未在公式Ａ中出现，则称该变项为Ａ的哑元。同样可定义Ｂ的哑元。在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内，即将Ａ、Ｂ都看成含所有p1,p2,…pn的命题公式，如果在所有2n个赋值下，Ａ与Ｂ的真值相同，则ＡＢ为重言式。哑元CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen5定义2.1设A,B是两个命题公式，若A,B构成的等价式A↔B为重言式，则称A与B是等值的,记为A⇔B。例2.1判断公式┐(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等值。110111101001011001001001定义CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen6(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)→r.110111110111111111000111由真值表可见，p→(q→r)⇔(p∧q)→r,例2.2判断下列两组公式是否等值：CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen7当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为等值式模式，通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下：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⇔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等值式模式CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen88.零律：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等值式模式（续）CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen9利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后所得的公式。若B⇔A,则Φ(B)⇔Φ(A)。等值演算CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen10例如，对公式(p→q)→r,如果用┐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)为简便起见,以后凡用到置换规则时,均不必标出。(蕴含等值式，置换规则）(蕴含等值式，置换规则）(德摩根律，置换规则）(分配律，置换规则）等值演算-例子CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen11例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.3CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen12证明：(p→q)→r⇔p→(q→r）.方法三:记A=(p→q)→r,B=p→(q→r)。先将A,B等值演算化成易于观察真值的公式，再进行判断。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的成真赋值。方法二：观察法。(p→q)→r⇔p→(q→r)。证方法一：真值表法。故(蕴含等值式)(蕴含等值式)(德摩根律)(蕴含等值式)(结合律)例24CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen13(1)（p→q)∧p→q;(2)┐(p→(p∨q))∧r;(3)p∧(((p∨q)∧┐p)→q).解:(1)（p→q)∧p→q⇔(┐p∨q)∧p→q⇔┐((┐p∨q)∧p)∨q⇔(┐(┐p∨q)∨┐p)∨q⇔((p∧┐q)∨┐p)∨q⇔((p∨┐p)∧(┐q∨┐p))∨q⇔(1∧(┐q∨┐p))∨q⇔(┐q∨┐p)∨q⇔(┐q∨q)∨┐p⇔1∨┐p⇔1故(p→q)∧p→q是重言式。用等值演算判断下列公式的类型(蕴含等值式)(蕴含等值式)(德摩根律)(德摩根律)(分配律)(排中律)(同一律）(交换律，结合律）（排中律）（零律）例2.5CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen14(2)┐(p→(p∨q))∧r⇔┐(┐p∨p∨q)∧r⇔(p∧┐p∧┐q)∧r⇔(0∧┐q)∧r⇔0∧r⇔0故┐(p→(p∨q))∧r是矛盾式。(蕴含等值式，结合律）(德摩根律）(矛盾律）(零律)(零律）例2.5（续）CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen15(3)p∧(((p∨q)∧┐p)→q)⇔p∧(┐((p∨q)∧┐p)∨q)(蕴含等值式)⇔p∧(┐((p∧┐p)∨(q∧┐p))∨q)(分配律)⇔p∧(┐(0∨(q∧┐p))∨q)(矛盾律)⇔p∧(┐(q∧┐p))∨q)(同一律)⇔p∧((┐q∨p)∨q)(德摩根律，双重否定律)⇔p∧((┐q∨q)∨p)(交换律，结合律)⇔p∧(1∨p)（排中律）⇔p∧1（零律）⇔p（同一律）可见，（3）中公式不是重言式，因为00，01都是成假赋值；它也不是矛盾式，因为10，11都是其成真赋值，故它是可满足式。例2.5（续）CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen16例2.6在某次研讨会的休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授不是上海人，也不是杭州人。听完3人的判断，王教授笑着说，他们3人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？解：设命题p,q,r分别表示：王教授是苏州、上海、杭州人。则p,q,r中必有一个真命题，两个假命题。要通过逻辑演算将真命题找出来。设：甲的判断为：A1=┐p∧q;乙的判断为：A2=p∧┐q;丙的判断为：A3=┐q∧r。例2.6CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen17那么甲的判断全对：B1=A1=┐p∧q甲的判断对一半：B2=((┐p∧┐q)∨(p∧q))甲的判断全错：B3=p∧┐q乙的判断全对：C1=A2=p∧┐q乙的判断对一半：C2=((p∧q)∨(┐p∧┐q))乙的判断全错：C3=┐p∧q丙的判断全对：D1=A3=┐q∧┐r丙的判断对一半：D2=((q∧┐r)∨(┐q∧r))丙的判断全错：D3=q∧r由王教授所说E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3)∨(B2∧C3∧D1)∨(B3∧C1∧D2)∨(B3∧C2∧D1)为真命题.例2.6（续）CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen18B1∧C2∧D3=(┐p∧q)∧((p∧q)∨(┐p∧┐q))∧(q∧r)((┐p∧q∧┐q∧r)∨(┐p∧q∧p∧r)0B1∧C3∧D2=(┐p∧q)∧(┐p∧q)∧((q∧┐r)∨(┐q∧r))(┐p∧q∧┐r)∨(┐p∧q∧┐q∧┐r)┐p∧q∧┐rB2∧C1∧D3=((┐p∧┐q)∨(p∧q))∧(p∧┐q)∧(q∧r)(┐p∧p∧p∧┐q∧q∧r)∨(p∧q∧┐q∧r)0类似可得B2∧C3∧D10,B3∧C1∧D2p∧┐q∧r,B3∧C2∧D10于是，由同一律可知E(┐p∧q∧┐r)∨(p∧┐q∧r)但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命题，即p∧┐q∧r0。于是E┐p∧q∧┐r为真命题，因而必有p,r为假命题，q为真命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。例2.6（续）CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen19定义2.2命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式；仅由有限个文字构成的合取式称作简单合取式。§2.2析取范式与合取范式例如：p;┐p;q∨┐q;p∨┐q;┐p∨┐q∨r都是简单析取式.p;┐p;q∧q;┐p∧┐q∧r;┐p∧p∧r都是简单合取式。注：单个文字既是简单析取式又是简单合取式。定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定式。CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen20例如：(p∧┐q)∨(┐q∧┐r)∨r是一个析取范式，而(p∨q∨r)∧(┐p∨┐q)∧r是一个合取范式。注：单个文字既是简单析取式又是简单合取式。因此形如┐p∧q∧r的公式既是由一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。类似地，形如p∨┐q∨r的公式既可看成析取范式也可看成合取范式。定义2.3由有限个简单合取式构成的析取式称为析取范式；由有限个简单析取式构成的合取式成为合取范式；析取范式与合取范式统称为范式。定义CHAPTERTWO3/29/20205:26PMDiscreteMath.,ChenChen21析取范式的一般形式：A⇔A1A2…An,其中Ai(i=1,…,n)是简单合