(第2讲)命题逻辑.ppt

1.2.1命题公式的一些基本概念,例考虑：G1：(PQ)P；G2：(PQ)P；G3：()(PQ),解：下面分别列出公式G1、G2、G3的真值表。,1的真值表：,2的真值表：,一、命题公式的分类,G3的真值表：,公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值,定义,公式G1称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G3称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G2称为可满足的，如果它不是永假的。,从上述定义可知三种特殊公式之间的关系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式。可满足式的否定不一定为不可满足式(即为永假式)。,列出下列公式的真值表，并验证其是否是永真公式。(1)(PQ)(PQ)；(2)(PQ)P)Q。(3).P(QR)解：、的真值表如下：,例1,(1)、(2)的真值表如下：,例1,公式（1）、（2）都是永真公式,（3）的真值表为：,例（续）,公式（3）是可满足公式。,(1)永真式的否定是矛盾式,矛盾式的否定是永真式,所以研究其一就可以了。(2)永真式的合取,析取,蕴含,等值等都是重言式。这样,由简单的永真式可推出复杂的永真式。(3)永真式中有许多非常有用的恒等式和永真蕴含式（类似于我们说的公理）。,永真式在数理逻辑的研究中占有特殊且重要的地位。,永真式的代入规则一永真式中某个命题变元出现的每一处均代入以同一公式后,所得的仍是永真式。,例如PP为永真式,以RQ代P得(RQ)(RQ)1,仍正确。它的思想就如同在代数中,若x2-y2=(x+y)(x-y)则(a+b)2-(mn)2=(a+b+mn)(a+b-mn)是一样的。,这条规则之所以正确是由于永真式之值不依赖于变元的值的缘故。,考察命题公式：PQ与PQPQ它们的真值表如下：,两个命题公式,如果有相同的真值表,则称它们是逻辑等价命题。以上两个命题因后两列的真假值完全一致,所以它们是逻辑等价命题。,二、命题公式的相等的概念,设A:A(P1,P2,Pn),B:B(P1,P2,Pn)是两个命题公式,这里Pi(i=1,2,n)不一定在两公式中同时出现。如果AB是重言式,则A与B对任何指派都有相同的真值。记为AB,叫做逻辑恒等式,读做“A恒等于B”。,恒等式,设A，B为两命题公式，由定义判断A与B是否逻辑等价应判断AB是否为重言式，若的真值表最后一列全为1，则AB重言式，因而AB。若A，B的真值表是完全相同的，则AB。,考察命题公式：PQ与PQPQ它们的真值表如下：,PQPQPQ,首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价（即GH），则计算机通过“计算”公式GH是否是永真公式，而得出结论。,“”与“”的区别,由于“”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性GG；（2）对称性若GH，则HG；（3）传递性若GH，HS，则GS。这三条性质体现了“”的实质含义。,常用的逻辑恒等式,1.双重否定律,2.等幂律,3.交换律,4.结合律,5.分配律,常用的逻辑恒等式,6.德.摩根律,7.吸收律,8.零律,9.同一律,10.排中律,11.矛盾律,12.蕴涵等值式,13.等价等值式,14.假言易位,15.等价否定等值式,16.归缪论,替换规则(RuleofReplacement)设有恒等式AB,若在公式C中出现A的地方,替换以B(不必每一处)而得到公式D,则CD。如果A是命题公式C中完整的一部分,且A本身是复合公式,则称A是C的子公式,规则中“公式C中出现A”意指“A是C的子公式”。这条规则的正确性是由于在公式C和D中,除替换部分外均相同,但对任一指派,A和B的真值相同,所以C和D的真值也相同,故CD。,证明PQQPQ,证：PQQQPQE4(QP)(QQ)E9(QP)1E20和替换规则QPE19PQE4,证明(PQ)(QR)PQR证(PQ)(QR)(PQ)(QR)E14和替换规则(PQ)(QR)E14PQ(QR)E10、E1和替换规则(PQQ)R)E6PQR例（a）和替换规则,定理1设A和A*是对偶式。P1,P2,Pn是出现于A和A*中的所有命题变元，于是A(P1,P2,Pn)A*(P1,P2,Pn),例,A*(P,Q,R)(P)(QR),所以,A(P,Q,R)A*(P,Q,R),A(P，Q，R)PQR,A(P，Q，R)(PQR),(P)(QR),(P)(QR),A*(P,Q,R)P(QR),三、命题公式的对偶原理,定理2若AB,且A、B为命题变元P1,P2,.,Pn及联结词、构成的公式,则A*B*。此定理常称为对偶原理。,A(P1P2,Pn)B(P1,P2,Pn),永真。,故A(P1,P2,Pn)B(P1,P2,Pn),永真。由定理1得,A*(P1,P2,Pn)B*(P1,P2,Pn),得A