1.2 真值表与逻辑等价

这一节把命题公式变成可以逐步计算的对象。一旦原子命题固定下来， 真值表就可以通过检查所有可能的真假指派，判断一个复合公式到底是真是假。

这件事听起来很机械，但数学意义非常清楚：如果一个公式只涉及 $n$ 个命题变量，那么就只有 $2^n$ 种真假配置。真值表正是把全部情况列出来， 因此不会漏掉隐藏情形。

真值表记录的是什么

定义

真值表

命题公式 $\varphi$ 的 真值表，会列出 $\varphi$ 中所有变量的每一种 真假指派，并记录 $\varphi$ 在每一行的真假值。

例如，如果公式只涉及 $P$ 和 $Q$，那么共有四行：

$$(T,T), \quad (T,F), \quad (F,T), \quad (F,F).$$

所以真值表不只是一个表格，而是一份完整的分类讨论。

逐行建立真值表的程序

一张可靠的真值表必须有清楚的行次序和列次序。若有 $n$ 个原子变量，就列出 $2^n$ 行，并从头到尾保持同一个次序。例如三个变量可以依次列为 TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF。然后每一个子公式增加一列，先算 最内层的连接词，最后才算整条公式。没有这些中间列，最后一列就很难检查。

例题

分步建立 $(A ∨ B) → C$

先计算 $A ∨ B$，再把这一列作为蕴含式的前件：

$A$	$B$	$C$	$A ∨ B$	$(A ∨ B) → C$
T	T	T	T	T
T	T	F	T	F
T	F	T	T	T
T	F	F	T	F
F	T	T	T	T
F	T	F	T	F
F	F	T	F	T
F	F	F	F	T

最后一列只在已经算出的前件为真而 $C$ 为假时为假。这里有三个独立变量，所以表有 八行。

嵌套蕴含也要遵守同一原则。在 $A → (B → A)$ 中，先计算内部的 $B → A$。按 $TT, TF, FT, FF$ 的次序，它的四个值是 $T, T, F, T$；再计算外层蕴含，得到 $T, T, T, T$。所以该公式是永真式。即使 $A$ 出现两次，也不能跳过内部列； 每次出现的作用范围由它所属的连接词决定。

定理

每个赋值确定一个最终真值

对原子命题指定一个真假赋值后，递归的真值规则会为每个良构布尔公式确定唯一的值。 因此，行次序相同且计算正确的两张表必须有相同的最终列。若结果不同，说明解析或计算 出了错误，而不是同一个公式有两个真值。

一个最重要的等价式

例题

为什么 $P \to Q$ 与 $\neg P \lor Q$ 表达同一件事

考虑公式 $P \to Q$ 与 $\neg P \lor Q$。

$P$	$Q$	$\neg P$	$P \to Q$	$\neg P \lor Q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

最后两列逐行完全一致。

因此

$$P \to Q \equiv \neg P \lor Q.$$

这个等价式在初等逻辑里非常重要。它说明了蕴含式只会在“前件真、 后件假”的那一行失败。

逻辑等价

定义

逻辑等价

如果两个公式 $\varphi$ 和 $\psi$ 在所有变量指派之下都得到相同真假值， 就说它们 逻辑等价，记作

$$\varphi \equiv \psi.$$

逻辑等价比“恰好在某个例子里一样”强得多。它表示两个公式实际上定义了同一个 truth function。

这里需要特别注意，不要把下面两种记号混为一谈：

• $\varphi \leftrightarrow \psi$ 是一个新的 Boolean 公式；
• $\varphi \equiv \psi$ 是一个关于两个公式的陈述。

两者有关，但并不是同一个东西。

定理

等价与双条件

两个公式 $\varphi$ 与 $\psi$ 逻辑等价，当且仅当

$$\varphi \leftrightarrow \psi$$

是一个永真式。

因此双条件可以拿来做检验：如果它的最后一列全部都是真，那么这两个公式就在 每一行都一致。

永真式、矛盾式与偶然式

定义

三种基本类型

设 $\varphi$ 是一个命题公式。

• 如果 $\varphi$ 在每一行都真，它就是 永真式。
• 如果 $\varphi$ 在每一行都假，它就是 矛盾式。
• 如果 $\varphi$ 有些行真、有些行假，它就是 偶然式。

标准例子是：

$$P \lor \neg P$$

它是永真式；而

$$P \land \neg P$$

则是矛盾式。

这个区分很重要，因为很多简短的逻辑论证，本质上就是证明某个公式总是真的， 或者总是假的。

第二个例题

例题

用真值表检验 De Morgan 定律

我们检验

$$\neg(P \lor Q) \equiv (\neg P) \land (\neg Q).$$

$P$	$Q$	$P \lor Q$	$\neg(P \lor Q)$	$\neg P$	$\neg Q$	$(\neg P) \land (\neg Q)$
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

第四列和第七列逐行一致，所以这两个公式逻辑等价。

这个例子说明了真值表的典型用途：它不只是用来算某一个公式，更是用来证明 一条等价律。

把论证化成一个真值表列

定理

检验有限命题推论

对前提 $P_1,\ldots,P_n$ 和结论 $Q$，其中 $n\ge1$，论证有效当且仅当

$$(P_1\land\cdots\land P_n)\to Q$$

是永真式。这个蕴含式恰好在全部前提真而结论假时为假，这正是反模型。含有假前提的行不能否定论证的有效性。

例题

比较两组前提

以前提 $P\to Q,P$ 推出 $Q$，检验式为 $((P\to Q)\land P)\to Q$。两个前提同时为真的唯一一行是 $P=T,Q=T$，该行结论也真；其余各行的外层前件为假，外层蕴含式仍真。若改以前提 $P\to Q,Q$ 推出 $P$，检验式就在 $P=F,Q=T$ 处失败。改变前提就是改变所检验的论证。

例题

替换等价的内部部分

在 $R\land(P\to Q)$ 中，以 $\neg P\lor Q$ 替换 $P\to Q$。对任意赋值，两个内部表达式真值相同，与同一个 $R$ 合取后的结果也相同。因此 $R\land(P\to Q)\equiv R\land(\neg P\lor Q)$；外层连接词及其作用域保持不变。

受控的改写过程

前面介绍的等价式还提供了一套可审查的改写方法。先把每个双条件替换成 $(P → Q) ∧ (Q → P)$，再用 $P → Q ≡ ¬P ∨ Q$ 替换所有蕴含；用德摩根律把 否定向内推进；消去双重否定；需要重新分组时使用分配律。例如：

$$¬(P → (Q ∧ R)) \equiv ¬(¬P ∨ (Q ∧ R)) \equiv P ∧ ¬(Q ∧ R) \equiv P ∧ (¬Q ∨ ¬R).$$

每一行都用逻辑等价式替换，因此最后一列的真假值保持不变。这样做的价值在于让 只有 $¬$、$∧$、$∨$ 的子公式更加显眼，便于建立中间列。这些等价式支持改写， 但它们并没有免除检查原公式作用范围的要求。这里把只用 $¬$、$∧$、$∨$，且每个 $¬$ 直接作用于原子命题的形式称为否定范式；它是便于造表的目标，不是把所有证明 都化成改写。

例题

等价与蕴含不是一回事

$P ∧ Q$ 与 $P$ 不等价：当 $P = T,\,Q = F$ 时，前者为假而后者为真。不过，论证 “$P ∧ Q$，所以 $P$”是有效的，因为不存在前提真而结论假的一行。对应的检验式 $(P ∧ Q) → P$ 是永真式。因此，等价要求两个方向的每一列都相同，而推论只要求 不存在被禁止的前提真、结论假的一行。

用表格回答不同类型的问题

同一张表可以回答不同问题，但读取方式必须对应题目。要判断一个公式的类型，只看它 自己的最后一列：全真是永真式，全假是矛盾式，真假都有是偶然式。要判断两个公式是否 等价，就把两条最后列逐行比较。要判断一个论证是否有效，则只圈出全部前提为真的行， 再看这些行的结论；前提为假的行不会构成反模型。

因此，做题时应先在纸上写出“公式类型”“公式等价”或“论证有效性”中的目标，再 决定要比较哪一列。一个表格可能包含足够信息，但错误的读取问题仍然会得到错误结论。

交换律、结合律与分配律

下面这些真值表等价式适合在改写公式时使用：

$$A \land B \equiv B \land A,\qquad A \lor B \equiv B \lor A$$ $$A \land (B \land C) \equiv (A \land B) \land C,\qquad A \lor (B \lor C) \equiv (A \lor B) \lor C$$ $$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C),\qquad A \land (B \lor C) \equiv (A \land B) \lor (A \land C).$$

交换律允许交换两个运算对象。结合律允许在重复使用同一个连接词时改变括号。 分配律则会改变连接词结构，产生展开步骤。例如：

$$R \lor (P \land Q) \equiv (R \lor P) \land (R \lor Q).$$

在更大的公式中使用这个步骤时，先找出完整的左侧模式，用右侧模式替换，再继续 计算新的子公式。每一行的最终真假值都保持不变，因为上面每个式子都是由真值表 验证的等价式。

从真值表的模式到逻辑恒等式

交换律双条件是永真式：

$(A → B) ∨ (B → A)$ 也是永真式。当 $A$ 真而 $B$ 假时， $B → A$ 为真；当 $A$ 假而 $B$ 真时，$A → B$ 为真；当真假相同时，两个蕴含式都真。

以下两个双条件在每一行的值相同：

因此 $A ↔ B ≡ ¬A ↔ ¬B$。这是关于两个公式的陈述，不是说 $↔$ 和 $≡$ 是同一个 连接词。

例题

完整计算 $(P ∧ Q) → P$

$(P ∧ Q) → P$ 的完整表如下：

$P$	$Q$	$P ∧ Q$	$(P ∧ Q) → P$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

最后一列全真，所以它是永真式，论证“$P ∧ Q$，所以 $P$”有效；这不表示 $P ∧ Q$ 与 $P$ 等价，它们在 $P = T,\,Q = F$ 时仍然不同。

双条件的否定与循环蕴含

$P ↔ Q$ 的否定恰好在两个值不同时为真：

$$\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q).$$

这是列出双条件为假的两行后得到的“互异”条件。

对于循环蕴含，应避免使用有歧义的链式记号。三个蕴含 $A → B$、$B → C$、 $C → A$ 迫使三个原子命题的真假值一致，因此精确的等价条件是

$$(A \leftrightarrow B) \land (B \leftrightarrow C).$$

这个显式合取写出了需要的两个双条件；不能把 $A ↔ B ↔ C$ 默认为三元连接词。

为什么这一节以后还重要

真值表不是逻辑课程的终点，但它训练了两个之后一直会用到的习惯：

• 把语法和意义分开处理；
• 检查“所有情况”，而不是只看一两个例子。

以后学习量词、集合与证明时，这种完整分类讨论的要求会以更成熟的形式再次出现。

常见错误

常见错误

只对上一两行并不够

如果两个公式只是在某一行，甚至几行里一致，都不足以证明等价。 等价要求的是所有可能指派全部一致。

常见错误

不要把 $\leftrightarrow$ 和 $\equiv$ 当成同一个记号

$\varphi \leftrightarrow \psi$ 是放进真值表里计算的公式。 $\varphi \equiv \psi$ 则是说两个公式定义同一个 truth function 的陈述。

读到这里，试一试

小检查

思考检查

如果一个公式涉及三个命题变量，真值表需要多少行？

用真假配置数量的规则回答。

解答 · 答案

需要 $2^3 = 8$ 行，因为三个变量都可以各自独立取真或假。

思考检查

为什么 $P \lor \neg P$ 是永真式？

逐行说明，不要只背结论。

解答 · 答案

如果 $P$ 真，那么 $P \lor \neg P$ 因为左边真而成立；如果 $P$ 假， 那么 $\neg P$ 真，所以析取仍然成立。每一行都是真，因此它是永真式。

思考检查

$P \land Q$ 与 $P \lor Q$ 是否逻辑等价？

指出至少一行让它们表现不同。

解答 · 答案

不是。例如当 $P = T$、$Q = F$ 时，有 $P \land Q = F$， 但 $P \lor Q = T$。它们在这一行不同，所以不等价。

继续学习量词

这一页直接承接 1.1 命题逻辑，并且为 1.3 量词与否定 做准备。