离散数学-命题逻辑2.ppt

第一章 数理逻辑,一 命题逻辑命题及其表示法联结词命题公式与翻译真值表与等价式等价式与蕴含式对偶与范式推理理论,二 谓词逻辑谓词的概念与表示命题函数与量词谓词公式与翻译变元的约束谓词演算的等价式与蕴含式前束范式谓词演算的推理理论本章作业,真值表与等价公式,定义1-4、1 在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。例 1 构造 P Q 的真值表。例 2 给出(P Q)P 的真值表。例 3 给出(P Q)(P Q)的真值表。,例 4 给出(P Q)(P Q)的真值表。,等价式和蕴涵式,一、几个定义与定理 定义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是等价的或逻辑相等。记作A B。例 5 证明 P Q(P Q)(Q P)定理：设A、B为两个命题公式，AB当且仅当A B 为一个重言式。,等价式,下表列出的命题定律，都可以用真值表予以验证。,补充：其它常用等价公式(1)P Q P Q(2)P Q(P Q)(Q P)P Q(3)(P Q)(P Q)P(归缪论)(4)P Q Q P(逆反式)我们称Q P 为逆换式，称 P Q为反换式定义1-4、3 如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。,定理1-4、1 设X是合式公式A的子公式，若X Y，如果将A中的X用Y来置换，所得到的公式B与公式A等价，即A B。证明：因为在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下，其真值亦必相同，故A B。注：满足定理1-4、1条件的置换称为等价置换（等价代换）。,例题7 证明Q(P(P Q)Q P 例题8 证明(PQ)(PQ)P 例题9 证明 P(QR)Q(P R)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，则P Q 为重言式，因为 PQ(PQ)(QP)故PQ 为T且QP 为T，即PQ，QP 成立。反之，若PQ 且QP，则 PQ 为T且QP 为T，因此P Q 为T，P Q 是重言式，即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 为T，则必须P为F，故P 为T。证法2 假定P 为F，则P为T。A）：若Q为F，则PQ 为F，Q(PQ)为F。B）：若Q为T，则Q 为F，Q(PQ)为F。所以Q(PQ)P 成立。,