1、* * 1第一章 数理逻辑一 命题逻辑 命题及其表示法 联结词 命题公式与翻译 真值表与等价式 等价式与蕴含式 对偶与范式 推理理论二 谓词逻辑 谓词的概念与表示 命题函数与量词 谓词公式与翻译 变元的约束 谓词演算的等价式与蕴含式 前束范式 谓词演算的推理理论 本章 作业* * 2真值表与等价公式定义 1-4、 1 在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。例 1 构造 P Q 的真值表。 例 2 给出 (P Q) P 的真值表。例 3 给出 (P Q) ( P Q) 的真值表。 * * 3例 4 给出 (P Q)
2、( P Q) 的真值表。* * 4等价式和蕴涵式一、几个定义与定理定义 1-5、 1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 T，则称该命题公式为 重言式或永真公式 。定义 1-5、 2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 F，则称该命题公式为 矛盾式或永假公式 。定理 1-5、 1 任何两个重言式的合取或析取，仍然是一个 重言式 。 * * 5证明： 设 A和 B为两个重言式，则不论 A和 B的分量指派任何真值，总有 A为 T， B为 T，故 ABT,ABT。定理： 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一个重言式。证明：由于重言式
3、的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为 T。* * 6定义 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 为一个重言式。 等价式* * 7下表列出的命题定律，都可以用真值表予以验证 。10否定律9零律8同一律7德 摩根律6吸收律5分配律4交换律3结合律2幂等律1 对合律* *
4、8补充： 其它常用等价公式(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的子公式。* * 9定理 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条件的置换称为 等价置换（等价代换） 。* * 10例题 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下一节下一节
