2.2 真值表、蕴含与等价

第 2.1 节已经教会我们：给定原子命题的真值后，可以计算复合命题。但是，一组真值只描述一个可能世界。要可靠地比较公式，就必须检查全部可能赋值。真值表正是组织这种完整检查的工具。

本节会建立三个互相衔接的工具：

• 真值表枚举所有可能输入世界；

• 蕴含表示一项条件承诺，并指出它在什么情况下被违反；

• 逻辑等价比较完整真值列，而不是比较表达式表面写法。

按固定规律构造全部输入行

假设表达式中有两个原子命题 $p$、$q$。每个命题都有两个可能真值，因此共有

种赋值。常用的行顺序是

观察变化规律：$p$ 列变化较慢，$q$ 列变化较快。如果有三个原子命题 $p,q,r$，就有 $2^3=8$ 行。第一列连续四行为真，第二列每两行变化一次，最后一列每行变化一次。这个计数与第 1 章幂集中的“独立二选一”思路完全相同。

要为下面的表达式构造真值表，

不要试图一步算出整个公式。先为每个必要的子表达式建立一列：

把第 2 行当作一次计算轨迹：$p=\mathrm{T}$ 且 $q=\mathrm{F}$，所以 $p\lor q=\mathrm{T}$，$\neg q=\mathrm{T}$，最终合取为真。其他各行都使用完全相同的局部规则。

可以采用下面的可靠流程：

1. 列出所有原子命题；

2. 若原子命题有 $n$ 个，就构造全部 $2^n$ 行输入；

3. 先为最小的子表达式添加列；

4. 从内向外计算，直到得到完整表达式的列；

5. 输出与上一行不同的位置最容易出错，要重点复查。

蕴含是一项承诺，不表示因果关系

蕴含（implication）

读作“如果 $p$，那么 $q$”。$p$ 叫作前提（hypothesis 或 antecedent），$q$ 叫作结论（conclusion 或 consequent）。

考虑一条文件安全策略：

> 如果文件属于机密文件，那么该文件必须加密。

令 $p$ 表示“文件是机密文件”，$q$ 表示“文件已经加密”。只有当文件是机密文件却没有加密时，策略才被违反。因此真值表为

最后两行常让初学者感到意外。蕴含并没有说“只有机密文件才能加密”。它只承诺：当 $p$ 为真时，$q$ 必须发生。当 $p$ 为假时，这项特定承诺没有被违反。

由此可以得到一个有用的等价式：

符号 $\equiv$ 表示“在每一种赋值下都具有相同真值”。$\neg p\lor q$ 只有在 $\neg p$ 为假且 $q$ 为假时才为假，也就是 $p=\mathrm{T}$、$q=\mathrm{F}$ 时。它与蕴含恰好在同一行失败。

巡逻模拟把条件语句变成可能被违反的规则。请给四个世界全部分类。重点不只是找到失败货舱，还要解释另外三个货舱为什么不构成这项承诺的反例。

与原命题相关的条件语句不能随意互换

从 $p\to q$ 出发，可以构造三条相关语句：

原命题与逆否命题逻辑等价；逆命题与否命题彼此等价，但它们通常不等价于原命题。

回到文件策略。“如果机密，那么加密”的逆命题是“如果加密，那么机密”。这不一定成立，因为公开文件也可以加密。只要找到一个加密的公开文件，就足以推翻逆命题。

逆否命题是“如果没有加密，那么不是机密文件”。它从失败条件的方向重新表达同一策略：若原策略得到遵守，未加密文件就不可能是机密文件。

不要只凭语序接受这些等价关系。接下来会用真值表列进行完整检验。

逻辑等价要求在每个可能世界中都相同

若两个复合命题在每一种赋值下都具有相同真值，就称它们逻辑等价（logically equivalent），记作

这里的 $P$、$Q$ 可以代表完整复合表达式。检验等价的步骤是：

1. 把两个表达式放在同一张真值表中；

2. 分别计算它们的最终列；

3. 逐行比较两个最终列；

4. 只有每一行都相同，才能宣布逻辑等价。

例如，第 1 章出现的德摩根律可以写成

第 4 列和第 7 列分别表示等价式左右两边。它们每一行都相同，因此等价关系成立。

如果两列哪怕只有一行不同，这一行就是逻辑等价的反例（counterexample）。反例是一组具体赋值，它使一个表达式为真、另一个表达式为假。

永真式、矛盾式与可满足的变化情况

最终真值列还可以告诉我们表达式属于哪一类：

• 永真式（tautology）在每一行都为真。

• 矛盾式（contradiction）在每一行都为假。

• 偶然式（contingency）在某些行为真、另一些行为假。

例如，

是永真式，因为 $p$ 与它的否定必有一个为真。而

是矛盾式，因为同一次赋值中，$p$ 不可能既真又假。$p\land q$ 则是偶然式，它的真值会随输入行改变。

双条件（biconditional）

读作“$p$ 当且仅当 $q$”。只有 $p$、$q$ 真值相同时，它才为真。双条件也可以理解为同时要求两个方向：

扫描仪把最终真值列当作四位指纹。先寻找指纹完全相同的表达式，再故意选择一对不同表达式并定位第一行反例。这两种操作同样重要：证明等价必须检查全部行，证明不等价只需一行。

通向下一节

当公式只含少量固定命题时，真值表非常有效。但很多陈述讨论的是“集合中的每个对象”或“是否存在具有某种性质的对象”。第 2.3 节会回到开放语句 $P(x)$，用谓词与量词精确定义“对所有”和“存在”。