命题逻辑的等值和推理演算2

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

1、第二章命题逻辑的等值和推理演算内容：推理形式和推理演算是数理逻辑研究的基本内容。推理演算要用正确的推理：推理形式由前提和结论经蕴涵词联接而成。我们关注正确的推理形式。正确的推理形式可由逻辑关系符表达。非形式描述：本章对命题等值和推理演算进行的讨论，是以语义的观点进行的非形式的描述。等值演算(考察逻辑关系符)：1)等值定理、公式2)由真值表写命题公式(由T写、由F写)3)联结词的完备集(由个别联结词表示所有联结词的问题)4)对偶式(命题公式的对偶性)5)范式(命题公式的统一标准)推理演算(考察逻辑关系符)：1)推理形式(正确推理形式的表示)2)基本推理公式(各种三段论及五种证明方法)3)推理演算

2、(证明推理公式的第六种方法，使用推理规则)4)归结推理法(证明推理公式的第七种方法，常用反证法)2.1.1等值的定义等值的定义：给定两个命题公式A和B,而P1…Pn是出现于A和B中的所有命题变项,那么公式A和B共有2n个解释,若对其中的任一解释,公式A和B的真值都相等,就称A和B是等值的(或等价的)。记作A=B或AB。注意逻辑关系词2.1等值定理例1:证明(P∧P)∨Q=Q证明:画出(P∧P)∨Q与Q的真值表可看出等式是成立的。例2:证明P∨P=Q∨Q证明:画出P∨P,Q∨Q的真值表,可看出它们是等值的,而且它们都是重言式。等值定义补充说明：两个公式等值并不要求它们一定含有相同

3、的命题变项。若仅在等式一端的公式里有变项P出现,那么等式两端的公式其真值均与P无关。例1中公式(P∨P)∨Q与Q的真值都同P无关,例2中P∨P,Q∨Q都是重言式,它们的真值也都与P、Q无关。2.1.2等值定理定理2.1.1对公式A和B,A=B的充分必要条件是AB是重言式。即任意解释下，A和B都有相同的真值。证明：定理中的两部分都与上一行等同。“＝”作为逻辑关系符是一种等价关系A=B是表示公式A与B的一种关系。这种关系具有三个性质:1.自反性A=A。2.对称性若A=B则B=A。3.传递性若A=B,B=C则A=C。这三条性质体现了“＝”的实质含义。2.2等值公式(真值表验证，Venn图

4、理解)2.2.1基本的等值公式(特别注意蓝色字)1.双重否定律P=P2.结合律(P∨Q)∨R=P∨(Q∨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

5、∧Q)∨(P∧Q)8.同一律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图实例1.P∨(P∧Q)=P2.P∧(P∨Q)=P3.(P∨Q)=P∧QVenn图可以用来理解集合间、命题逻辑中、部分信息量间的一些关系。2.2.2若干常用的等值公式等值演算中，由于人们对、

6、∨、∧更为熟悉，常将含有和的公式化成仅含有、∨、∧的公式。这也是证明和理解含有，的公式的一般方法。但后面的推理演算中，更希望见到和.12.逆否定理PQ=QP11.PQ=P∨Q13.前提合并P(QR)=(P∧Q)R17.前提交换P(QR)=Q(PR)18.另一种前提合并(PR)∧(QR)=(P∨Q)R14.从取真来描述双条件词PQ=(P∧Q)∨(P∧Q)15.从取假来描述双条件词PQ=(P∨Q)∧(P∨Q)16.从蕴涵词描述双条件词PQ=(PQ)∧(QP)2.2.3置换规则(注意与代入规则p8的区别)置换定义：对公式A的子公式,用与

7、之等值的公式来代换便称置换。置换规则：将公式A的子公式置换后，A化为公式B,必有A=B。置换与代入是有区别的：代入规则要求操作重言式、对所有同一命题变元都作代换2.2.4等值演算举例例1:证明(P∧(Q∧R))∨(Q∧R)∨(P∧R)=R证明:左端=(P∧(Q∧R))∨((Q∨P)∧R)(分配律)=((P∧Q)∧R))∨((Q∨P)∧R)(结合律)=((P∨Q)∧R)∨((Q∨P)∧