1、1.3 命题公式间的逻辑等价关系 1.3.1 基本概念1.3.2 替换定理1.3.3 代入定理1.3.4 逻辑等价变换1.3.5 联结词归约与范式 1.3.1 基本概念 定义 1 设 , 是两个命题公式。如果对于 与 的合成变元组 (即这两个公式所有不同命题变元合在一起 )的任意指派 ，均有 () = ()则称 与 逻辑等价 ，也称永真等价或同真假。记为 。判断两个命题公式逻辑等价的第一种方法是使用真值表。先将 与 的合成变元组的各种指派和 与 在各种指派下的真假值写在同一张表上，然后检验 与 的相应位置上的真值是否相同。例如，利用真值表即可验证命题公式 PQ与命题公式 P(PQ)逻辑等价。
2、P P 双重否定律PP P , PP P 幂等律(PQ)R P(QR)(PQ)R P(QR) 结合律PQ QP , PQ QP 交换律P(QR) (PQ)(PR)P(QR) (PQ)(PR) 分配律(PQ) PQ(PQ) PQ De Morgan律PF P , PT P 同一律PT T , PF F 零律PP T , PP F 否定律PQ PQPQ (PQ)(QP) 联结词归约基本逻辑等价式请用真值表验证各个逻辑等价公式研究两个命题公式之间逻辑等价关系的方法之二是利用命题公式的永真性。定理 1 设 , 为命题公式， 当且仅当 为永真公式。命题公式间的逻辑等价关系具有：1) 自反性： ；2) 对
3、称性：若 ，则 ；3) 传递性：若 且 ，则 。应当指出的是，两个命题公式逻辑等价与两个命题公式相等是有所区别的。前者是指结果相同，后者是指形式相同 (当然结果必相同 )。因此相等比逻辑等价的要求更高。以后仍用 “ ”表示相等。1.3.2 替换定理 定义 2 设 命题公式， 是命题公式 的一部分且 是命题公式，则称 是 的子命题公式。定义 3 设 是命题公式，若将 的子命题公式 用另一命题公式 替换，则称替换后产生的命题公式 是 关于 替换为 的结果。利用替换，可以将原有的命题公式改造成新的命题公式。例如，命题公式 P(P(PQ)关于 P(PQ)替换为 PQ的结果为P(PQ) 。替换定理 设
4、是 关于 替换为 的结果。如果 ，则 。引理 设 1, 2, 1, 2均为命题公式。若 1 1 , 2 2 , 则1) 1 1 2) 1 2 1 2 3) 1 2 1 2 4) 1 2 1 2 5) 1 2 1 2 证： 3）设 1, 2, 1, 2的合成变元组为 (P1 , P2, , P n) 。对于该合成变元组的任一指派 ，由条件 1 1 , 2 2 有1() = 1() 2() = 2() 于是有 1() 2() = 1() 2() 由于 (1 2)() = 1() 2() (1 2)() = 1() 2() 于是有 (1 2)() = (1 2)() 由指派的任意性和逻辑等价的定义知
5、有 1 2 1 2 。替换定理 设 是 关于 替换为 的结果。如果 ，则 。证：对 中除 之外的联结词个数 k 进行归纳证明。当 k = 0 时， 为下述两种形式之一。1) = P (P是命题变元 )， 2) = 对于 1) 根据 的定义可知，此时 = P。于是有 = = P ，当然有 。对于 2) 有 = = 。设当 kn 时，结论成立。下证当 k = n 时，结论也成立。事实上，按照命题公式的定义可知， 必呈下述形式之一。1, 1 2 , 1 2 , 1 2 , 1 2 仅以 1 2 为例进行证明。由于 是 关于 替换为 的结果，而且只是对 中 以外的联结词进行归纳，即 12中的 不是 中
6、的联结词。因此， 必呈 12的形式，其中 1,2分别是 1, 2关于 替换为 的结果。又由于 1, 2中除 之外的联结词的个数必然小于 n。于是按照归纳假设可知，有1 1 2 2 再由引理知，有 1 2 1 2 , 即 。 1.3.3 代入定理 代入是通过已有的永真公式推出更多的永真公式的一种有效途径。例如，是否可由 PP 是永真公式而直接推断出 PQ PQ 是永真公式。这就是代入定理所要回答的问题。定义 4 设 为命题公式， P是中的命题变元， 是任一命题公式。如果将中 P的所有出现均用命题公式 代替，则称代替后所得到的命题公式为 关于 P代入为 的结果，简称 的代入实例，记为 /P。例 =
7、 (P(PQ)Q， = PQ，代入 P后 则有/P = (PQ)(PQ)Q)Q代入定理 设 为命题公式， P是 中的命题变元。如果 是永真公式，那么对任意命题公式 ，有 /P为永真公式。证 令 = /P。设 的变元组为 (P1, P2, , Pn)， 的变元组为(Q1,Q2, , Q m)。于是 的变元组应为(Q1,Q2,Q m,P1,P2,P n)于是 的变元组的任何指派 = (Q10,Q20,Q m0,P10,P20,P n0)必确定了 的一个指派1 = (Q10,Q20,Q m0)令 P 0 = (1) ，于是得到 的一个完全指派2 = (P 0, P10, P20, , P n0)注意
8、到 是将 中 P 的所有出现均用 代替，于是有() = (2)而 是永真公式，于是有 (2) = T ，即有 () = T 。由指派的任意性和永真公式的定义知 为永真公式。由于代入定理的引入，获得永真公式的手段就更加丰富了。由代入定理知，每一个永真公式都是一族永真公式的代表。例如，由 (P(PQ)Q 是永真公式可推知所有形如 () 的命题公式均为永真公式。因此，每个永真公式中的命题变元都可以理解为子命题公式的形式。将代入定理运用于命题公式之间的逻辑等价，可以得到如下结论。推论 设 , 是命题公式。若 ，则 /P /P 。证 由条件知 ，由定理 1知 是永真公式。根据代入定理有 /P/P 是永真公式。再由定理 1知/P /P 。利用这个推论，可将上节给出的基本逻辑等价式中的命题变元理解为命题公式。例如， PQ QP 可理解为 等等 。
