第二章命题逻辑等值和推理演算ppt课件.ppt

《第二章命题逻辑等值和推理演算ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章命题逻辑的等值和推理演算推理形式和推理演算是数理逻辑研究的基本内容推理形式是由前提和结论经蕴涵词联结而成的推理过程是从前提出发，根据所规定的规则来推导出结论的过程重言式是重要的逻辑规律，正确的推理形式、等值式都是重言式本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式的描述，不仅直观且容易理解，也便于实际问题的逻辑描述和推理。严格的形式化的讨论见第三章所建立的公理系统。等值演算(考察逻辑关系符⇔(=))等值定理、公式联结词的完备集(由个别联结词表示所有联结词的问题)对偶式(命题公式的对偶性)范式(命题公式的统一标准)由真值表写命题公式

2、(由T写、由F写)推理演算(考察逻辑关系符⇒)推理形式(正确推理形式的表示)基本推理公式(各种三段论及五种证明方法)推理演算(证明推理公式的第六种方法，使用推理规则)归结推理法(证明推理公式的第七种方法，常用反证法)2.1等值定理若把初等数学里的＋、－、×、÷等运算符看作是数与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下：x2－y2=(x＋y)(x－y)(x＋y)2=x2＋2xy＋y2sin2x＋cos2x=1……在命题逻辑里也同样可建立一些重要的等值式2.1.1等值的定义给定两个命题公式A和B,而P1…Pn是出现于A和B

3、中的所有命题变项,那么公式A和B共有2n个解释,若对其中的任一解释,公式A和B的真值都相等,就称A和B是等值的(或等价的)。记作A=B或AB显然，可以根据真值表来判明任何两个公式是否是等值的例1:证明(P∧P)∨Q=Q证明:画出(P∧P)∨Q与Q的真值表可看出等式是成立的。例2:证明P∨P=Q∨Q证明:画出P∨P,Q∨Q的真值表,可看出它们是等值的,而且它们都是重言式。从例1、2还可说明,两个公式等值并不一定要求它们一定含有相同的命题变项若仅在等式一端的公式里有变项P出现,那么等式两端的公式其真值均与P无关。例1中公式(P∧P)∨Q与

4、Q的真值都同P无关例2中P∨P,Q∨Q都是重言式,它们的真值也都与P、Q无关。说明2.1.2等值定理定理对公式A和B,A=B的充分必要条件是AB是重言式。A、B不一定都是简单命题,可能是由简单命题P1,…,Pn构成的.对A,B的一个解释,指的是对P1,…,Pn的一组具体的真值设定.若AB为重言式,则在任一解释下A和B都只能有相同的真值,这就是定理的意思。证明若AB是重言式,即在任一解释下,AB的真值都为T依AB的定义只有在A、B有相同的值时,才有AB=T。于是在任一解释下,A和B都有相同的真值,从而有A=B。反过来，若有A=B,即在任

5、一解释下A和B都有相同的真值,依AB的定义,AB只有为真,从而AB是重言式。注：根据该等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可“＝”作为逻辑关系符是一种等价关系不要将“＝”视作联结词，在合式公式定义里没有“＝”出现A=B是表示公式A与B的一种关系。这种关系具有三个性质:1.自反性A=A2.对称性若A=B,则B=A3.传递性若A=B,B=C,则A=C这三条性质体现了“＝”的实质含义。2.2等值公式2.2.1基本的等值公式(命题定律,P和Q是任意的命题公式)1.双重否定律P=P2.结合律(P∨Q)∨R=P∨(Q

6、∨R)(P∧Q)∧R=P∧(Q∧R)(PQ)R=P(QR)注:所有这些公式，都可使用真值表加以验证3.交换律P∨Q=Q∨PP∧Q=Q∧PPQ=QP4.分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)P(QR)=(PQ)(PR)5.等幂律(恒等律)P∨P=PP∧P=PPP=TPP=T6.吸收律P∨(P∧Q)=PP∧(P∨Q)=P7.摩根律(P∨Q)=P∧Q(P∧Q)=P∨Q对蕴涵词、双条件词作否定有(PQ)=P∧Q(PQ)=PQ=PQ=(P∧Q)∨(P∧Q)8

7、.同一律P∨F=PP∧T=PTP=PTP=P还有PF=PFP=P9.零律P∨T=TP∧F=F还有PT=TFP=T10.补余律P∨P=TP∧P=F还有PP=PPP=PPP=FVenn图(理解等式)将P、Q理解为某总体论域上的子集合，并规定：P∧Q为两集合的公共部分(交集合)P∨Q为两集合的全部(并集合)P为总体论域(如矩形域)中P的余集Venn图(理解等式)从Venn图，因P∧Q较P来得“小”,P∨Q较P来得“大”，从而有P∨(P∧Q)=PP∧(P∨Q)=P理解等式:Venn图，自然语言(P∨Q)=P∧QVen

8、n图(理解集合间、命题逻辑中、部分信息量间的一些关系)对这些等式使用自然用语加以说明，将有助于理解如P表示张