命题逻辑中等价公式的证明方法探讨

On the Proof Methods of Propositional Equivalences in Propositional Logic

摘要: 命题公式是命题逻辑中的基本研究对象。判定两个命题公式是否逻辑等价是一个重要问题。本文结合例题讲解，对证明两个命题公式等价的方法进行了总结，共提出六种方法，并对各种方法进行了分析和探讨。

Abstract: Propositional formulas are the basic contents in propositional logic. It is an important problem to determine whether two propositional formulas are logically equivalent. The paper summarizes six methods about how to prove the equivalence of two propositional formulas by specific examples, and discusses the relations of these methods.

1. 引言

在离散数学 [1] [2] [3] 的教学中，命题逻辑是主要内容之一。命题是命题逻辑的最基本研究单位。命题用数学符号表示后称为命题公式。把所有的命题公式看成一个集合，命题公式的等价用集合论的语言说是一种“等价关系”。这种“等价关系”将所有命题公式按照是否等价划分成若干“等价类”，在同一个等价类中的命题公式都是等价的。也就是说，只要知道了“等价类”中的一个命题公式的性质，那么这个“等价类”中所有公式的性质就都清楚了。因此，在命题逻辑中，判定两个命题公式是否等价是一类基本题型。

离散数学中有大量的定义和定理，其解题方法中包含大量的方法和技巧 [4] [5] [6]。本文给出了证明命题公式等价的常用方法，这些方法涉及命题逻辑几乎所有内容，并将各部分内容有机联系在一起，这对我们理解和掌握命题逻辑及后续谓词逻辑的内容是非常有好处的。

2. 命题公式等价的相关概念

首先我们介绍一些基本的概念 [1] [2] [3]。若无特别指出，以下出现的 $P,Q,\cdots$ 均表示命题公式，T，F分别表示永真式和永假式。

定义1：给定两个命题公式P和Q，设 $P_1,P_2,\cdots ,P_n$ 为所有出现于P和Q中的原子变元，若给 $P_1,P_2,\cdots ,P_n$ 的任一组真值指派，P和Q的真值都相同，则称P和Q是等价的或逻辑相等。记作 $P\iff Q$。

由双条件式的定义，P和Q是等价的也相当于说公式 $P\leftrightarrow Q$ 是永真式。

3. 命题公式等价的证明方法

本文介绍证明两个命题公式等价的六种方法，它们分别是真值表法、等价代换法、利用双条件式的方法、利用主析取(合取)范式的方法、赋值法和利用对偶原理的方法。下面我们通过例子分别介绍这些方法。

方法1：真值表法

由命题公式等价的定义，如果我们可以证明两个命题公式的真值表是相同的，那么这两个命题公式一定是等价的。

例1：证明 $\left(P\leftrightarrow Q\right)\iff \left(P\to Q\right)\wedge \left(Q\to P\right)$。

证明列出真值表：

由上表可知 $P\leftrightarrow Q$ 与 $\left(P\to Q\right)\wedge \left(Q\to P\right)$ 的真值相同，所以等价。

真值表法列出了命题公式真值的所有可能情况，方法简单且直观，不易出错，对于简单命题公式的证明特别适用。但如果命题公式含有的命题变元的个数较多时，真值表法过于繁琐，不建议使用。

方法2：等价代换法

等价代换法就是利用一些常用的等价公式(如 $P\to Q\iff \neg P\vee Q,\neg \neg P\iff P$ )，通过等价代换来证明两个公式等价。在证明时，我们可以对一个命题公式进行等价代换得到另一个命题公式，也可以两个命题公式同时进行等价代换，化成同一个命题公式。这种方法对命题变元的个数没有要求，是较为普遍的一种方法。

例2：证明 $\left(P\to \left(Q\vee R\right)\right)\wedge \left(\neg P\vee \left(Q\leftrightarrow R\right)\right)\iff P\to \left(R\wedge \left(Q\vee \neg R\right)\right)$。

证明因为

$\begin{array}{l}\left(P\to \left(Q\vee R\right)\right)\wedge \left(\neg P\vee \left(Q\leftrightarrow R\right)\right)\\ \iff \left(\neg P\vee Q\vee R\right)\wedge \left(\neg P\vee \left(\left(Q\to R\right)\wedge \left(R\to Q\right)\right)\right)\\ \iff \neg P\vee \left(\left(Q\vee R\right)\wedge \left(\neg Q\vee R\right)\wedge \left(Q\vee \neg R\right)\right)\\ \iff \neg P\vee \left(R\wedge \left(Q\vee \neg R\right)\right)\\ \iff P\to \left(R\wedge \left(Q\vee \neg R\right)\right)\end{array}$

所以这两个命题公式是等价的。

方法3：利用主析取(合取)范式的方法

对于一个命题公式的主析取(合取)范式，如果将其命题变元的个数及出现次序固定后，则此公式的主析取(合取)范式是唯一的。因此，给定两个命题公式，如果它们的主析取(合取)范式是相同的，则它们一定等价。即证两命题公式等价的问题转化为求它们的主析取(合取)范式的问题。

求一个公式的主析取(合取)范式一般有两种方法：真值表法和等价代换法。因此该方法可以和方法1、方法2结合使用。

方法4：利用双条件式的方法

由命题公式等价的定义，要证 $P\iff Q$，只需证 $P\leftrightarrow Q$ 为永真式。从上面的分析我们看到，我们可以利用方法1、方法2或方法3证明 $P\leftrightarrow Q$ 为永真式。在这种方法中，我们从原命题公式P、Q构造出一个更大的命题公式 $P\leftrightarrow Q$，因此在方法上略繁琐。

方法5：赋值法

要证 $P\iff Q$，只需证 $P\Rightarrow Q$ 且 $Q\Rightarrow P$ 成立，即证 $P\to Q$ 且 $Q\to P$ 为永真式。从而将等价式的证明转化为永真式的证明。要证明一个公式与永真式等价，除了我们上面提到的4种方法可用外，我们还可以利用赋值法。也就是说要证 $P\to Q$ 为永真式，只要证明P的任意一个成真赋值都是Q的成真赋值，或者Q的任意一个成假赋值都是P的成假赋值。

例3：证明 $\left(P\to R\right)\wedge \left(Q\to R\right)\iff \left(P\vee Q\right)\to R$。

证明假设a是 $\left(P\to R\right)\wedge \left(Q\to R\right)$ 的任意一个成真赋值(记为 $a\left(\left(P\to R\right)\wedge \left(Q\to R\right)\right)=T$ )，则 $a\left(P\to R\right)=T$ 且 $a\left(Q\to R\right)=T$。此时，若 $a\left(R\right)=T$，则 $a\left(P\right)=a\left(Q\right)=T$ ；若 $a\left(R\right)=F$，则 $a\left(P\right)=a\left(Q\right)=F$。那么不论R的真值怎样，a是 $P\vee Q\to R$ 的成真赋值。

假设a是 $P\vee Q\to R$ 的任意一个成真赋值。若 $a\left(P\vee Q\right)=T$，则 $a\left(R\right)=T$，总有 $a\left(P\to R\right)=a\left(Q\to R\right)=T$ ；若 $a\left(P\vee Q\right)=F$，则 $a\left(P\right)=a\left(Q\right)=F$，就有 $a\left(P\to R\right)=a\left(Q\to R\right)=T$。所以 $a\left(\left(P\to R\right)\wedge \left(Q\to R\right)\right)=T$。

此解法部分的利用了真值表法和条件式的定义，因此比真值表法优越。如果公式较为复杂，用等价代换法求解过程较繁琐，则可用直接证明法求解。需要说明的是证明 $P\to Q$ 为永真式也可以利用推理理论中的CP规则，这里不再赘述。

方法6：利用对偶原理

所谓对偶原理是指如果两个命题公式是等价的，那么它们的对偶式也是等价的。利用对偶原理，两个命题公式等价的证明可以转化为它们的对偶式等价的证明。另外，如果我们已知一个等价式，则立即可得新的等价式，非常简便。这种方法有一定技巧性，我们要注意观察具有特殊性质的公式，如例题4。

例4：证明下面两个等价式

1) $\left(P\vee Q\right)\wedge \left(\neg P\wedge Q\right)\iff \neg P\wedge Q$ ；

2) $\neg \left(P\wedge Q\right)\to \left(\neg P\wedge Q\right)\iff \neg P\vee Q$。

证明：1) 利用等价代换，有

$\left(P\vee Q\right)\wedge \left(\neg P\wedge Q\right)\iff \left(P\wedge \left(\neg P\wedge Q\right)\right)\vee \left(Q\wedge \left(\neg P\wedge Q\right)\right)\iff \neg P\wedge Q$

2) 注意到2)式的右边 $\neg P\vee Q$ 恰好是1)式右边 $\neg P\wedge Q$ 的对偶式。而2)式左边

$\neg \left(P\wedge Q\right)\to \left(\neg P\wedge Q\right)\iff \left(P\wedge Q\right)\vee \left(\neg P\vee Q\right)$

恰好是1)式左边的对偶式。由对偶原理，2)式中两个命题公式等价。

4. 结论

以上我们总结了命题逻辑中等价公式的证明方法，并对各种方法进行了比较，它们既有区别也有联系。等价代换法是较为简捷的一种方法，一般的等价公式证明题我们可用这种方法。将等价代换法贯穿于除真值表法之外的各种方法之中，可使我们的证明更加简便。

基金项目

国家自然科学基金项目(11771279, 11801363)，上海海事大学文理学院重点课程建设项目(2018)。