资源描述:
《命题逻辑的等值和推理演算.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第二章命题逻辑的等值和推理演算推理形式和推理演算是数理逻辑研究的基本内容推理过程是从前提出发,根据所规定的规则来推导出结论的过程重言式是重要的逻辑规律,正确的推理形式,等值式都是重言式。本章对命题等值和推理演算进行讨论,是以语义的观点进行的非形式的描述,不仅直观且容易理解,也便于实际问题的逻辑描述和推理。严格的形式化的讨论见第三章所建立的公理系统。2.1等值定理若把初等数学里的+、-、×、÷等运算符看作是数与数之间的联结词,那么由这些联结词所表达的代数式之间,可建立许多等值式如下:x2-y2=(x+y)(x-y)(x+y)2=x2+2xy+y2sin2x+cos2
2、x=1……在命题逻辑里也同样可建立一些重要的等值式。2.1.1等值的定义给定两个命题公式A和B,而P1…Pn是出现于A和B中的所有命题变项,那么公式A和B共有2n个解释,若对其中的任一解释,公式A和B的真值都相等,就称A和B是等值的(或等价的)。记作A=B或AB。显然,可以根据真值表来判明任何两个公式是否是等值的。例1:证明(P∧P)∨Q=Q证明:画出(P∧P)∨Q与Q的真值表可看出等式是成立的。例2:证明P∨P=Q∨Q证明:画出P∨P,Q∨Q的真值表,可看出它们是等值的,而且它们都是重言式。从例1、2还可说明,两个公式等值并不要求它们一定含有相同的命
3、题变项。若仅在等式一端的公式里有变项P出现,那么等式两端的公式其真值均与P无关。例1中公式(P∨P)∨Q与Q的真值都同P无关,例2中P∨P,Q∨Q都是重言式,它们的真值也都与P、Q无关。2.1.2等值定理定理对公式A和B,A=B的充分必要条件是AB是重言式。若AB为重言式(A、B不一定都是简单命题,可能是由简单命题P1,…,Pn构成的对A,B的一个解释,指的是对P1,…,Pn的一组具体的真值设定),则在任一解释下A和B都只能有相同的真值,这就是定理的意思。证明若AB是重言式,即在任一解释下,AB的真值都为T。依AB的定义只有在A、B有相同的值时,才有
4、AB=T。于是在任一解释下,A和B都有相同的真值,从而有A=B。反过来,若有A=B,即在任一解释下A和B都有相同的真值,依AB的定义,AB只有为真,从而AB是重言式。有了这个等值定理,证明两个公式等值,只要证明由这两个公式构成的双条件式是重言式即可。不要将“=”视作联结词,在合式公式定义里没有“=”出现。A=B是表示公式A与B的一种关系。这种关系具有三个性质:1.自反性A=A。2.对称性若A=B则B=A。3.传递性若A=B,B=C则A=C。这三条性质体现了“=”的实质含义。2.2等值公式2.2.1基本的等值公式(命题定律)1.双重否定律P=P2.结合律(
5、P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)(PQ)R=P(QR)3.交换律P∨Q=Q∨PP∧Q=Q∧PPQ=QP4.分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)P(QR)=(PQ)(PR)5.等幂律(恒等律)P∨P=PP∧P=PPP=TPP=T6.吸收律P∨(P∧Q)=PP∧(P∨Q)=P7.摩根律(P∨Q)=P∧Q(P∧Q)=P∨Q对蕴涵词、双条件词作否定有(PQ)=P∧Q(PQ)=PQ=PQ=(P∧Q)∨(P∧Q)8.同一律P∨F=PP∧T=PTP
6、=PTP=P还有PF=PFP=P9.零律P∨T=TP∧F=F还有PT=TFP=T10.补余律P∨P=TP∧P=F还有PP=PPP=PPP=F所有这些公式,都可使用直值表加以验证。Venn图若使用Venn图也容易理解这些等值式,这种图是将P、Q理解为某总体论域上的子集合,而规定P∧Q为两集合的公共部分(交集合),P∨Q为两集合的全部(并集合),P为总体论域(如矩形域)中P的余集。从Venn图因P∧Q较P来得“小”,P∨Q较P来得“大”,从而有P∨(P∧Q)=PP∧(P∨Q)=P对这些等式使用自然用语加以说明,将有助于理解。如P表示张三
7、是学生,Q表示李四是工人,那么(P∨Q)就表示并非“张三是学生或者李四是工人”。这相当于说,“张三不是学生而且李四也不是工人”,即可由P∧Q表示,从而有(P∨Q)=P∧Q。2.2.2若干常用的等值公式由于人们对、∨、∧更为熟悉,常将含有和的公式化成仅含有、∨、∧的公式。这也是证明和理解含有,的公式的一般方法。公式11-18是等值演算中经常使用的,也该掌握它们,特别是能直观地解释它们的成立。11.PQ=P∨Q通常对PQ进行运算时,不如用P∨Q来得方便。而且以P∨Q表示PQ帮助我们理解如果P则Q的逻辑含义。问题是这种表示也有缺点,