离散数学-命题逻辑2

第一章数理逻辑,一命题逻辑命题及其表示法联结词命题公式与翻译真值表与等价式等价式与蕴含式对偶与范式推理理论,二谓词逻辑谓词的概念与表示命题函数与量词谓词公式与翻译变元的约束谓词演算的等价式与蕴含式前束范式谓词演算的推理理论本章作业,真值表与等价公式,定义1-4、1在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。例1构造PQ的真值表。例2给出(PQ)P的真值表。例3给出(PQ)(PQ)的真值表。,例4给出(PQ)(PQ)的真值表。,等价式和蕴涵式,一、几个定义与定理定义1-5、1给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。定义1-5、2给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。定理1-5、1任何两个重言式的合取或析取，仍然是一个重言式。,证明：设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故ABT,ABT。定理：一个重言式，对同一分量都用任何合式公式置换，其结果仍为一个重言式。证明：由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T。,定义1-4、2给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB。例5证明PQ(PQ)(QP)定理：设A、B为两个命题公式，AB当且仅当AB为一个重言式。,等价式,下表列出的命题定律，都可以用真值表予以验证。,补充：其它常用等价公式(1)PQPQ(2)PQ(PQ)(QP)PQ(3)(PQ)(PQ)P(归缪论)(4)PQQP(逆反式)我们称QP为逆换式，称PQ为反换式定义1-4、3如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。,定理1-4、1设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，所得到的公式B与公式A等价，即AB。证明：因为在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下，其真值亦必相同，故AB。注：满足定理1-4、1条件的置换称为等价置换（等价代换）。,例题7证明Q(P(PQ)QP例题8证明(PQ)(PQ)P例题9证明P(QR)Q(PR)R(QP)例题10证明(PQ)(P(QR)(PQ)(PR)T,下一节,例7证明设A：因为故B：即例8证明,例9证明又，,例10证明原式左边,例1解,例2解,例3解,例4解,例5解:,定义：当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ。注意：区别条件与蕴含，同时，二者存在联系.定理：设P，Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。证明：若PQ，则PQ为重言式，因为PQ(PQ)(QP)故PQ为T且QP为T，即PQ，QP成立。反之，若PQ且QP，则PQ为T且QP为T，因此PQ为T，PQ是重言式，即PQ。证毕。,蕴含式,二、蕴含有下面几个常用的性质：（1）设A、B、C为合式公式，若AB且A是重言式，则B必是重言式。（2）若AB，BC，则AC，即蕴含关系是传递的。（3）若AB且AC，那么A(BC)（4）若AB且CB，则ACB,三、下表所列各蕴含式都可推理证明。,重言式、等价式与蕴涵式的证明：例题1证明(PS)R)(PS)R)为重言式。例题2证明(PQ)(PQ)例题3推证Q(PQ)P,BACK,例题1证明因为PPT，如以(PS)R)置换P即得(PS)R)(PS)R)T例题2证明由上节例题4表可知，(PQ)(PQ)为重言式，故根据定理1-5、3：(PQ)(PQ),例题3证法1假定Q(PQ)为T，则Q为T，且(PQ)为T。由Q为F，PQ