1、离散数学许雷（数学与信息科学学院）邮箱： ）电话： 180802219261.3 命题公式的等值式定义 1: 给定两个命题公式 A和 B，设P1 ,P2 , ,Pn为出现于 A和 B中的所有原子变元 ,若给 P1 , P2 , ,Pn任一组真值指派 , A和 B的真值都相同 ,则称 A和 B是等价的或逻辑相等 .记作A B。1.3 命题公式的等值式注 : (1) “ ”不是逻辑联结词 .(2)命题公式之间的逻辑相等关系具有 ：自反性： A A ；对称性：若 A B，则 B A；传递性：若 A B且 B C，则 A C。1.3 命题公式的等值式证明公式等价的方法：1. 真值表法 2. 等值演算法
2、1. 真值表法 例 1. 111 1111 0110 1110 0 Q QP PP Q 1.3 命题公式的等值式例 2. 证明 : PQ (PQ) (QP)P Q PQ QP PQ (PQ) (QP)0 00 11 01 11.3 命题公式的等值式例 2. 证明 : PQ (PQ) (QP)P Q PQ QP PQ (PQ) (QP)0 0 1 1 1 10 1 0 0 1 01 0 0 1 0 01 1 1 1 1 11.3 命题公式的等值式例 3： 判断公式 P(QR)、 (P Q)R是否等价P Q R P Q QR P(QR) (P Q)R0 0 0 0 10 0 1 0 10 1 0
3、0 00 1 1 0 11 0 0 0 11 0 1 0 11 1 0 1 01 1 1 1 11.3 命题公式的等值式P Q R P Q QR P(QR) (P Q)R0 0 0 0 1 1 10 0 1 0 1 1 10 1 0 0 0 1 10 1 1 0 1 1 11 0 0 0 1 1 11 0 1 0 1 1 11 1 0 1 0 0 01 1 1 1 1 1 1例 3： 判断公式 P(QR)、 (P Q)R是否等价1.3 命题公式的等值式2. 等值演算法 (Equivalent Calculation) 等值演算中使用的一条重要规则： 置换规则定义 2 (子公式 )： 如果 X是 wff A的一部分 ,且X本身也是 wff，则称 X是 A的子公式。例如 ,P(PQ)为 Q (P(PQ)的子公式。1.3 命题公式的等值式(置换定理 Axiom of rePlacement)设 X是 wff A的子 wff，若 XY，则若将 A中的 X用 Y来置换，所得公式 B与 A等价，即AB。证： 因为对变元的任一指派 ,X与 Y真值相同，所以 Y取代 X后，公式 B与公式 A对变元的任一指派真值也相同 ,所以 AB。
