3 逻辑公式

令人惊讶的是, 人们竟然能理解说话中的时候产生的歧义. 比如这些例子:

• “你可以吃蛋糕, 或者你可以吃冰淇淋.”
• “如果猪会飞, 那么你的账户不会被黑客入侵.”
• “如果你能解决我们提出的任何问题, 那么你会得到这门课程的A.”
• “每个美国人都有一个梦想.”

这些句子都在说啥？你可以同时吃蛋糕和冰淇淋, 还是只能选择一种甜点？猪不会飞, 所以第二个句子是否说明了你账户是安全的？如果你能解决我们提出的一些问题, 你能在这门课上得到A吗？如果你不能解决任何一个问题, 这是否意味着你不能得到A？最后一句是否意味着所有美国人都有相同的梦想——比如拥有一栋房子——还是不同的美国人有不同的梦想——比如, Eric的梦想是设计一个非常牛逼的应用, Tom的梦想是成为网球冠军, Elbert的梦想能够唱歌…?

在日常对话中, 一些不确定性是可以容忍的. 但当我们需要精确地表达想法时——比如在数学和编程中——日常语言中的歧义可能会成为一个真正的问题. 如果我们不确定句子的确切含义, 就不能做出精确的论证. 因此, 在我们开始研究数学之前, 我们需要探讨如何谈论数学的问题.

为了绕过英语的歧义, 数学家设计了一种特殊的语言来谈论逻辑关系. 这种语言主要使用普通英语单词和短语, 如“或(or)”, “意味着(implies)”和“对于所有(forall)”. 但数学家赋予这些词精确和无歧义的定义, 这些定义与常用用法不符.

令人惊讶的是, 在学习逻辑的过程中, 我们将遇到计算机科学中最重要的一个开放问题——一个其解决方案可能改变世界的问题.

3.1 命题

在英语中, 我们可以用诸如“非”, “与”, “或”, “意味着”和“如果-那么”之类的词来修改、组合和关联命题. 例如, 我们可以将三个命题组合成如下一个命题:

如果所有人都是凡人, 并且所有希腊人都是人类, 那么所有希腊人都是凡人.

在接下来的内容中, 我们将不太关心命题的内部——无论它们涉及数学还是希腊人的死亡率——而是关心命题是如何组合和关联的. 因此, 我们经常会用变量 \(P\) 和 \(Q\) 来代替具体的命题, 如“所有人都是凡人”和“2 + 3 = 5”. 理解的是这些命题变量, 像命题一样, 可以取值 \(T\)（真）和 \(F\)（假）. 命题变量也被称为布尔变量, 以其发明者, 19世纪数学家乔治·布尔（George Boole）命名.

3.1.1 非(NOT), 与(AND), 或(OR)

数学家使用“非”, “与”和“或”来表示改变或组合命题的操作. 这些特殊词语的精确定义可以用真值表来表示. 例如, 如果 \(P\) 是一个命题, 那么“非(\(P\))”也是一个命题, 并且“非(\(P\))”的真值由 \(P\) 的真值决定, 如下表所示:

\[ \begin{array}{|c|c|} \hline P & \text{非}(P) \\ \hline T & F \\ F & T \\ \hline \end{array} \]

表的第一行表示, 当命题 \(P\) 为真时, 命题“非(\(P\))”为假. 第二行表示, 当 \(P\) 为假时, “非(\(P\))”为真. 这大概是你所期望的结果.

一般来说, 真值表表示命题在变量的每个可能的真值组合下的真/假值. 例如, 命题“\(P\) 与 \(Q\)”的真值表有四行, 因为两个变量的真值有四种组合:

\[ \begin{array}{|c|c|c|} \hline P & Q & P \text{ 与 } Q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \\ \hline \end{array} \]

根据这个表, 命题“\(P \text{ 与 } Q\)”只有在 \(P\) 和 \(Q\) 都为真时才为真. 这大概是你通常对“与”这个词的理解方式.

在“\(P \text{ 或 } Q\)”的真值表中有一个细微差别:

\[ \begin{array}{|c|c|c|} \hline P & Q & P \text{ 或 } Q \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array} \]

这个表的第一行表示, 即使 \(P\) 和 \(Q\) 都为真, “\(P \text{ 或 } Q\)”也是为真的. 这并不总是日常语言中“或”的预期含义, 但这是数学写作中的标准定义. 所以, 如果一个数学家说, “你可以吃蛋糕, 或者你可以吃冰淇淋,”他的意思是你可能两者都可以吃.

如果你想排除同时吃蛋糕和冰淇淋的可能性, 你应该用互斥或操作（XOR）将它们组合起来:

\[ \begin{array}{|c|c|c|} \hline P & Q & P \text{ XOR } Q \\ \hline T & T & F \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{array} \]

3.1.2 当且仅当(IFF)

当且仅当的英语为 if and only if, 简写为IFF. 命题“\(P\) 当且仅当 \(Q\)”断言 \(P\) 和 \(Q\) 具有相同的真值. 要么两者都为真, 要么两者都为假.

\[ \begin{array}{|c|c|c|} \hline P & Q & P \text{ IFF } Q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \hline \end{array} \]

例如, 以下这个命题对于每个实数 \(x\) 都成立:

\[ x^2 - 4 \geq 0 \quad \text{IFF} \quad |x| \geq 2. \]

对于某些 \(x\) 的值, 两个不等式都成立. 对于其他 \(x\) 的值, 两个不等式都不成立. 但在每种情况下, 上述命题整体来看是真的.

3.1.3 意味着(蕴含, implies)

“意味着”是含义最不直观的. 我们常说: “如果P, 那么Q”. 这里是它的真值表, 第四列被标记出来以便下文引用.

\[ \begin{array}{|c|c|c|c|} \hline P & Q & P \text{ implies } Q & \text{Label} \\ \hline T & T & T & (\text{tt}) \\ T & F & F & (\text{tf}) \\ F & T & T & (\text{ft}) \\ F & F & T & (\text{ff}) \\ \hline \end{array} \]

可以用以下文字来总结蕴含的真值表:

一个蕴含在 "如果" 部分为假或 "那么" 部分为真时才为真.

这句话值得记住: 大量数学文本都是具有”如果…那么…“的形式的！

让我们试验一下这个定义. 例如, 以下命题是对还是错？

如果哥德巴赫猜想是真的, 那么 \(x^2 \geq 0\) 对于每个实数 \(x\) 都成立.

我们已经提到没有人知道哥德巴赫猜想（命题 1.1.6）是真的还是假的. 但这并不妨碍我们回答这个问题！这个命题的形式是 \(P \text{ implies } Q\), 其中假设 \(P\) 是“哥德巴赫猜想是真的”, 结论 \(Q\) 是“\(x^2 \geq 0\) 对于每个实数 \(x\) 都成立”. 因为结论显然是真的, 我们处于真值表的（tt）或（ft）行. 无论哪种情况, 命题作为一个整体是真的！

现在让我们找出我们原始例子之一的真值:

如果猪会飞, 那么你的账户不会被黑客入侵.

不用管猪, 我们只需要确定这个命题是真还是假. 猪不会飞, 所以我们处于真值表的（ft）或（ff）行. 在这两种情况下, 命题都是真的！

假设为假的情况

这种数学惯例——蕴含作为一个整体被认为是真的, 当它的假设为假时——与在常见情况下蕴含应该在其假设和结论之间具有某种因果关系的情况形成对比.

例如, 我们可以同意——或者至少希望——以下陈述是真的:

如果你遵循安全协议, 那么你的账户不会被黑客入侵.

我们认为这个蕴含是没有问题的, 因为安全协议和账户被黑客入侵之间有明确的因果关系.

另一方面, 陈述:

如果猪会飞, 那么你的账户不会被黑客入侵,

通常会被认为是假的——或者至少是荒谬的——因为猪的航空学与您的账户安全无关. 但在数学上, 这个蕴含被认为是真的.

重要的是要接受这样一个事实: 数学蕴含忽略了因果关系. 这使它们比因果蕴含要简单得多, 但仍然有用. 为了说明这一点, 假设我们有一个系统规范, 其中包括一系列, 例如十二条规则:

如果系统传感器处于状态1, 那么系统执行动作1. 如果系统传感器处于状态2, 那么系统执行动作2. …… 如果系统传感器处于状态12, 那么系统执行动作12.

令 \(C_i\) 为系统传感器处于状态 \(i\) 的命题, \(A_i\) 为系统执行动作 \(i\) 的命题, 规范可以更简洁地用逻辑公式表示为

\[ \begin{align*} C_1 \text{ implies } A_1, \\ C_2 \text{ implies } A_2, \\ \vdots \\ C_{12} \text{ implies } A_{12} \end{align*} \]

现在, 可以将系统遵循规范的命题通过将这些公式结合起来并用 AND 连接成一个单一的逻辑公式:

\[ [C_1 \text{ implies } A_1] \text{ AND } [C_2 \text{ implies } A_2] \text{ AND } \cdots \text{ AND } [C_{12} \text{ implies } A_{12}]. \tag{3.1} \]

例如, 假设只有状态 \(C_2\) 和 \(C_5\) 是真的, 系统会执行指定的动作 \(A_2\) 和 \(A_5\). 所以在这种情况下, 系统的行为符合规范. 符合规范, 我们希望公式 (3.1) 成立. 蕴含 \(C_2 \text{ implies } A_2\) 和 \(C_5 \text{ implies } A_5\) 都是真的, 因为它们的假设和结论都是真实的. 但是, 为了使 (3.1) 成立, 我们需要所有其他的蕴含都是真的, 而所有这些蕴含的假设都是假的. 这正是数学蕴含规则所实现的.

3.2 计算机程序中的命题逻辑

命题和逻辑连接词在计算机程序中随处可见. 例如, 考虑以下代码片段, 这可以是 C、C++ 或 Java:

if ( x > 0 || (x <= 0 && y > 100) )
  // (进一步的指令)

Java 使用符号 || 表示“或”, 符号 && 表示“与”. 只有在 if 后面的命题为真时, 才会执行进一步的指令. 仔细检查, 这个大表达式是由两个更简单的命题构建的. 设 \(A\) 为命题“\(x > 0\)”, \(B\) 为命题“\(y > 100\)”. 那么我们可以将条件重写为:

\[ A \text{ OR } (\text{NOT}(A) \text{ AND } B). \tag{3.2} \]

3.2.1 真值表计算

真值表计算揭示了更复杂的表达式 (3.2) 始终具有与 \(A \text{ OR } B\) 相同的真值:

\[ A \text{ OR } B. \tag{3.3} \]

我们从仅包含 \(A\) 和 \(B\) 真值的表开始:

\[ \begin{array}{|c|c|c|c|} \hline A & B & A \text{ OR } (\text{NOT}(A) \text{ AND } B) & A \text{ OR } B \\ \hline T & T & & \\ T & F & & \\ F & T & & \\ F & F & & \\ \hline \end{array} \]

这些值足以填充另外两列:

\[ \begin{array}{cc|ccccc|c}A & B & A & \text { OR } & (\operatorname{NOT}(A) & \text { AND } & B) & A \text { OR } B \\\hline \mathbf{T} & \mathbf{T} & & & \mathbf{F} & & & \mathbf{T} \\\mathbf{T} & \mathbf{F} & & & \mathbf{F} & & & \mathbf{T} \\\mathbf{F} & \mathbf{T} & & & \mathbf{T} & & & \mathbf{T} \\\mathbf{F} & \mathbf{F} & & & \mathbf{T} & & & \mathbf{F}\end{array} \]

现在我们有了填充 AND 列所需的值:

\[ \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\operatorname{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & & \mathbf{F} & \mathbf{F} & & \mathbf{T} \\ \mathbf{T} & \mathbf{F} & & & \mathbf{F} & \mathbf{F} & \\ \mathbf{F} & \mathbf{T} & & & \mathbf{T} & \mathbf{T} & & \mathbf{T} \\ \mathbf{F} & \mathbf{F} & & & \mathbf{T} & \mathbf{F} & & \mathbf{F} \end{array} \]

这为我们提供了填充第一个 OR 列的剩余值:

\[ \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\operatorname{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & \mathbf{T} & \mathbf{F} & \mathbf{F} & & \mathbf{T} \\ \mathbf{T} & \mathbf{F} & & \mathbf{T} & \mathbf{F} & \mathbf{F} & & \mathbf{T} \\ \mathbf{F} & \mathbf{T} & & \mathbf{T} & \mathbf{T} & \mathbf{T} & & \mathbf{T} \\ \mathbf{F} & \mathbf{F} & & \mathbf{F} & \mathbf{T} & \mathbf{F} & & \mathbf{F} \end{array} \]

真值总是匹配的表达式称为等价表达式. 由于两个表达式的真值表中的强调列相同, 它们是等价的. 因此, 我们可以通过用等价的更简单的表达式替换复杂的表达式来简化代码片段, 而不会改变程序的行为:

if ( x > 0 || y > 100 )
  // (进一步的指令)

(3.2) 和 (3.3) 的等价性也可以通过分类讨论来确认:

• \(A\) 为真. 形式为 \((T \text{ OR 任何})\) 的表达式等价于 \(T\). 由于 (3.2) 和 (3.3) 在这种情况下都是这种形式, 所以它们具有相同的真值, 即 \(T\).

• \(A\) 为假. 形式为 \((F \text{ OR 任何})\) 的表达式将具有与任何相同的真值. 由于 \(A\) 为假, (3.3) 具有与 \(B\) 相同的真值.

形式为 \((T \text{ AND 任何})\) 的表达式等价于任何, 就像 \((F \text{ OR 任何})\) 一样. 因此, 在这种情况下, \(A \text{ OR } (\text{NOT}(A) \text{ AND } B)\) 等价于 \((\text{NOT}(A) \text{ AND } B)\), 反过来又等价于 \(B\).

因此, 在这种情况下, (3.2) 和 (3.3) 都将具有相同的真值, 即 \(B\) 的值.

简化逻辑表达式在计算机科学中具有实际的重要性. 像上面这样的程序中的表达式简化可以使程序更容易阅读和理解. 简化的程序也可能运行得更快, 因为它们需要更少的操作. 在硬件中, 简化表达式可以减少芯片上逻辑门的数量, 因为数字电路可以用逻辑公式描述（见问题 3.6 和 3.7）. 最小化逻辑公式对应于减少电路中的门数量. 减少门的好处是潜在的巨大: 门更少的芯片更小, 消耗更少的功率, 具有更低的缺陷率, 并且制造成本更低.

3.2.2 简化的符号

Java 使用符号 && 和 || 代替 AND 和 OR. 电路设计师使用“·”和“+”, 并实际上将 AND 视为乘积, 将 OR 视为和. 数学家使用其他符号, 如下表所示.

English	Symbolic Notation
\(\text{NOT}(P)\)	\(\neg P\) (或 \(P\))
\(P \text{ AND } Q\)	\(P \land Q\)
\(P \text{ OR } Q\)	\(P \lor Q\)
\(P \text{ implies } Q\)	\(P \rightarrow Q\)
if \(P\) then \(Q\)	\(P \rightarrow Q\)
\(P \text{ IFF } Q\)	\(P \leftrightarrow Q\)
\(P \text{ XOR } Q\)	\(P \oplus Q\)

例如, 使用这种符号, “如果 \(P \text{ AND NOT}(Q)\), 那么 \(R\)”可以写成:

\[ (P \land \neg Q) \rightarrow R. \]

这样的数学符号虽然简洁但令人摸不着头脑. 像“AND”和“OR”这样的词更容易记住, 不会与数字操作混淆. 我们将继续使用 \(\bar P\) 作为 \(\text{NOT}(P)\) 的简写, 但除了这个例外, 我们基本上坚持使用这些词——我们的一行不够长了.

3.3 等价性和有效性

3.3.1 蕴含与逆否命题

这两个句子说的是同一件事吗？

• 如果我饿了, 那么我会脾气暴躁.
• 如果我不脾气暴躁, 那么我不饿.

我们可以通过将这两个句子重新表述为命题逻辑来解决这个问题. 设 \(P\) 为命题“我饿了”, \(Q\) 为命题“我脾气暴躁”. 第一个句子说“\(P \text{ implies } Q\)”, 第二个句子说“\(\text{NOT}(Q) \text{ implies } \text{NOT}(P)\)”. 我们可以通过真值表比较这两个命题:

\[ \begin{array}{|c|c|c|c|} \hline P & Q & (P \text{ implies } Q) & (\text{NOT}(Q) \text{ implies } \text{NOT}(P)) \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \\ \hline \end{array} \]

当然, 突出显示的列显示了这两个命题的真值是相同的. 形式为“\(\text{NOT}(Q) \text{ implies } \text{NOT}(P)\)”的命题称为“\(P \text{ implies } Q\)”的逆否命题. 真值表显示, 蕴含及其逆否命题是等价的——它们只是不同的说法.

相比之下, “\(P \text{ implies } Q\)”的逆命题是“\(Q \text{ implies } P\)”. 我们示例的逆命题是:

• 如果我脾气暴躁, 那么我饿了.

这听起来是一个相当不同的主张, 真值表也证实了这一怀疑:

\[ \begin{array}{|c|c|c|c|} \hline P & Q & P \text{ implies } Q & Q \text{ implies } P \\ \hline T & T & T & T \\ T & F & F & T \\ F & T & T & F \\ F & F & T & T \\ \hline \end{array} \]

现在, 突出显示的列在第二行和第三行中不同, 这表明蕴含通常不等同于其逆命题.

最后一个关系: 蕴含及其逆命题一起等价于一个当且仅当命题, 具体来说, 这两个命题一起. 例如,

• 如果我脾气暴躁, 那么我饿了, 如果我饿了, 那么我脾气暴躁.

等同于单个命题:

• 当且仅当我饿了时, 我脾气暴躁.

我们可以再次用真值表验证这一点:

\[ \begin{array}{|c|c|c|c|c|} \hline P & Q & (P \text{ implies } Q) \text{ AND } (Q \text{ implies } P) & P \text{ IFF } Q \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & F & F \\ F & F & T & T \\ \hline \end{array} \]

第四列给出的真值与第六列给出的真值相同, 这证实了蕴含的 AND 等价于 IFF 命题.

3.3.2 有效性和可满足性

一个有效的公式是一个总是真实的公式, 无论其变量的真值是什么. 最简单的例子是

\[ P \text{ OR } \text{NOT}(P). \]

你可以将有效公式视为捕捉基本逻辑真理的公式. 例如, 我们认为理所当然的蕴含属性是, 如果一个命题蕴含第二个命题, 第二个命题蕴含第三个命题, 那么第一个命题蕴含第三个命题. 以下有效公式证实了这个蕴含属性的真实性:

\[ [(P \text{ implies } Q) \text{ AND } (Q \text{ implies } R)] \text{ implies } (P \text{ implies } R). \]

公式的等价性实际上是有效性的特例. 即, 当公式 \(F\) 和 \(G\) 等价时, 当且仅当命题 \((F \text{ IFF } G)\) 有效. 例如, 表达式 (3.3) 和 (3.2) 的等价性意味着

\[ (A \text{ OR } B) \text{ IFF } (A \text{ OR } (\text{NOT}(A) \text{ AND } B)) \]

是有效的. 当然, 有效性也可以视为等价性的一个方面. 即, 一个公式当且仅当等价于 \(T\) 时才是有效的.

一个可满足的公式是一个有时可以为真的公式, 即存在某种变量真值赋值使其为真. 可满足性的一个例子是, 当存在一组系统规范时, 系统设计者的工作是设计一个遵循所有规范的系统. 这意味着所有规范的 AND 都必须是可满足的, 否则设计师的工作将是不可能的（见问题 3.16）.

有效性和可满足性之间也存在密切关系: 一个命题 \(P\) 是可满足的, 当且仅当其否定 \(\text{NOT}(P)\) 不是有效的.

3.4 命题的代数

3.4.1 正规形式的命题

每个命题公式都等价于“积之和”或析取范式（DNF）.

更准确地说, 一个命题变量 \(A\) 或其否定 \(\overline{A}\) 称为文字, 涉及不同变量的文字的 AND 称为AND 子句. 例如,

\[ A \text{ AND } \overline{B} \text{ AND } C \]

是一个 AND 子句, 但 \(A \text{ AND } B \text{ AND } \overline{B} \text{ AND } C\) 不是, 因为 \(B\) 出现了两次. 最后, DNF 是 AND 子句的 OR, 例如:

\[ (A \text{ AND } B) \text{ OR } (A \text{ AND } C). \tag{3.4} \]

你可以直接从真值表中读取任何命题公式的 DNF. 例如, 公式

\[ A \text{ AND } (B \text{ OR } C) \tag{3.5} \]

的真值表如下:

\[ \begin{array}{|c|c|c|c|c|} \hline A & B & C & A \text{ AND } (B \text{ OR } C) & A \text{ OR } B \\ \hline T & T & T & T & T \\ T & T & F & T & T \\ T & F & T & T & T \\ T & F & F & F & T \\ F & T & T & F & T \\ F & T & F & F & T \\ F & F & T & F & T \\ F & F & F & F & F \\ \hline \end{array} \]

公式 (3.5) 在第一行中为真, 当 \(A\)、\(B\) 和 \(C\) 都为真时, 即 \(A \text{ AND } B \text{ AND } C\) 为真. 它在第二行中也为真, 当 \(A \text{ AND } B \text{ AND } \overline{C}\) 为真时, 第三行也为真, 当 \(A \text{ AND } \overline{B} \text{ AND } C\) 为真时, 仅此而已. 所以 (3.5) 正好在以下情况为真:

\[ (A \text{ AND } B \text{ AND } C) \text{ OR } (A \text{ AND } B \text{ AND } \overline{C}) \text{ OR } (A \text{ AND } \overline{B} \text{ AND } C). \tag{3.6} \]

表达式 (3.6) 是一个 DNF, 其中每个 AND 子句实际上包括了所有变量的一个文字. 我们称这样的公式为完整 DNF.

DNF 公式通常可以简化为更小的 DNF. 例如, DNF (3.6) 进一步简化为上述的等价 DNF (3.4).

对真值表的 F 项应用相同的推理, 可以得到任何公式的合取范式（CNF）——即 OR 子句的 AND, 其中 OR 子句是来自不同变量的文字的 OR. 例如, 公式 (3.5) 在真值表 (3.4.1) 的第四行中为假, 即 \(A\) 为真, \(B\) 为假, \(C\) 为假. 但这正是 OR 子句 \(\overline{A} \text{ OR } B \text{ OR } C\) 为假的一行！同样, (3.5) 在第五行中为假, 这正是 OR 子句 \(\overline{A} \text{ OR } B \text{ OR } \overline{C}\) 为假的一行！这意味着 (3.5) 为假时, 这两个 OR 子句的 AND 为假. 继续这种方式处理其余三行 (3.5) 为假的情况, 我们得到一个等价于 (3.5) 的 CNF, 即

\[ (\overline{A} \text{ OR } B \text{ OR } C) \text{ AND } (\overline{A} \text{ OR } B \text{ OR } \overline{C}) \text{ AND } (\overline{A} \text{ OR } \overline{B} \text{ OR } C) \text{ AND } (\overline{A} \text{ OR } \overline{B} \text{ OR } \overline{C}). \]

再次, 每个 OR 子句包含了所有变量的一个文字, 即它是一个完整 CNF.

上述方法可应用于任何真值表, 这意味着

定理3.4.1

每个命题公式都等价于一个完整析取范式和一个完整合取范式.

3.4.2 证明等价性

通过真值表检查等价性或有效性很快就会失效: 一个具有 \(n\) 个变量的命题其真值表有 \(2^n\) 行, 因此检查一个命题所需的努力随着变量数量的增加呈指数级增长. 对于一个具有30个变量的命题来说, 这已经超过十亿行了！

另一种有时有帮助的方法是使用代数来证明等价性. 一个命题公式中可能会出现许多不同的操作符, 因此一个有用的第一步是去掉所有操作符, 只保留三个: AND、OR和NOT. 这很容易, 因为每个操作符都等价于仅使用这三个操作符的简单公式. 例如, \(A \text{ implies } B\) 等价于 \(\text{NOT}(A) \text{ OR } B\). 定义公式的剩余操作符只使用 \(Q \text{ AND } R\) 和 NOT 留给问题 3.17.

我们下面列出了一些等价公理, 用符号“\(\leftrightarrow\)”表示等价公式. 这些公理很重要, 因为它们是证明等价性的所有需求. 我们将从 AND 的一些等价性开始, 这些等价性看起来像数量乘法的熟悉公式:

\[ A \text{ AND } B \leftrightarrow B \text{ AND } A \tag{3.7} \]

\[ (A \text{ AND } B) \text{ AND } C \leftrightarrow A \text{ AND } (B \text{ AND } C) \tag{3.8} \]

\[ T \text{ AND } A \leftrightarrow A \quad (\text{identity for AND}) \\ F \text{ AND } A \leftrightarrow F \quad (\text{zero for AND}) \]

\[ A \text{ AND } (B \text{ OR } C) \leftrightarrow (A \text{ AND } B) \text{ OR } (A \text{ AND } C) \tag{3.9} \]

公式 (3.8) 证明了写 \(A \text{ AND } B \text{ AND } C\) 而不指定它是括号化为 \(A \text{ AND } (B \text{ AND } C)\) 或 \(A \text{ AND } (B \text{ AND } C)\) 是合理的. 两种插入括号的方法产生等价公式.

与数字的算术规则不同, 还有一个“和”对“积”的分配律:

\[ A \text{ OR } (B \text{ AND } C) \leftrightarrow (A \text{ OR } B) \text{ AND } (A \text{ OR } C) \tag{3.10} \]

另外还有三条公理与以往数字的性质不同:

\[ A \text{ AND } A \leftrightarrow A \quad (\text{idempotence for AND}) \]

\[ A \text{ AND } \overline{A} \leftrightarrow F \quad (\text{contradiction for AND}) \tag{3.11} \]

\[ \text{NOT}(\text{NOT}(A)) \leftrightarrow A \quad (\text{double negation}) \tag{3.12} \]

对于 OR 也有一组对应的等价性, 这里不再列出, 除了有效性规则 (3.13):

\[ A \text{ OR } \overline{A} \leftrightarrow T \quad (\text{validity for OR}) \tag{3.13} \]

最后, 还有德摩根定律解释了如何分配 AND 和 OR 上的 NOT:

\[ \text{NOT}(A \text{ AND } B) \leftrightarrow \overline{A} \text{ OR } \overline{B} \quad (\text{De Morgan for AND}) \tag{3.14} \]

\[ \text{NOT}(A \text{ OR } B) \leftrightarrow \overline{A} \text{ AND } \overline{B} \quad (\text{De Morgan for OR}) \tag{3.15} \]

所有这些公理都可以通过真值表轻松验证.

这些公理是将任何公式转换为完整 DNF 所需的全部. 我们可以通过将它们应用到公式 (3.5) 的否定来说明它们的工作原理:

\[ \operatorname{NOT}((A \text { AND } B) \text { OR }(A \text { AND } C)) \text {. } \tag{3.16} \]

我们从应用德摩根律的“or”(3.15)到(3.16)开始, 将“not”进一步引入公式. 这给出

\[ \text{NOT}(A \text{ AND } B) \text{ AND } \text{NOT}(A \text{ AND } C) \]

现在对两个最内层的“and”应用德摩根律(3.14), 得到

\[ (A \text{ OR } B) \text{ AND } (A \text{ OR } C) \tag{3.17} \]

此时“not”仅适用于变量, 我们不再需要德摩根律.

现在我们将反复应用(3.9), 即“and”对“or”的分配律, 将(3.17)转化为DNF. 首先, 我们将

\[ (A \text{ OR } B) \]

分配到“and”上, 得到

\[ ((A \text{ OR } B) \text{ AND } A) \text{ OR } ((A \text{ OR } B) \text{ AND } C) \]

使用“and”两侧的分配律, 我们得到

\[ ((A \text{ AND } A) \text{ OR } (B \text{ AND } A)) \text{ OR } ((A \text{ AND } C) \text{ OR } (B \text{ AND } C)) \]

顺便说一下, 我们在这里隐式地使用了交换律(3.7)来证明从右侧分配一个“and”. 现在应用等幂性来去除A的重复出现, 我们得到

\[ (A \text{ OR } (B \text{ AND } A)) \text{ OR } ((A \text{ AND } C) \text{ OR } (B \text{ AND } C)) \]

QOR的结合律现在允许去掉括号, 得到(3.16)的DNF:

\[ A \text{ OR } (B \text{ AND } A) \text{ OR } (A \text{ AND } C) \text{ OR } (B \text{ AND } C) \]

(3.18)

倒数第二步是将这个DNF转换为完全DNF. 这可以对每个“and”-子句分别进行. 我们将通过第二个“and”-子句\((B \text{ AND } A)\)来说明如何操作. 这个子句需要提到C才能成为完全形式. 为了引入C, 我们使用“or”的有效性和“and”的恒等式来得出结论:

\[ (B \text{ AND } A) \leftrightarrow (B \text{ AND } A) \text{ AND } (C \text{ OR } \text{NOT}(C)) \]

现在将\((B \text{ AND } A)\)分配到\((C \text{ OR } \text{NOT}(C))\)上, 得到完全DNF

\[ (B \text{ AND } A \text{ AND } C) \text{ OR } (B \text{ AND } A \text{ AND } \text{NOT}(C)) \]

对(3.18)中的其他“and”-子句做同样的操作, 最终得到(3.5)的完全DNF:

\[ (A \text{ AND } B \text{ AND } C) \text{ OR } (A \text{ AND } B \text{ AND } \text{NOT}(C)) \text{ OR } (A \text{ AND } \text{NOT}(B) \text{ AND } C) \text{ OR } (A \text{ AND } \text{NOT}(B) \text{ AND } \text{NOT}(C)) \text{ OR } (\text{NOT}(A) \text{ AND } B \text{ AND } C) \text{ OR } (\text{NOT}(A) \text{ AND } B \text{ AND } \text{NOT}(C)) \text{ OR } (\text{NOT}(A) \text{ AND } \text{NOT}(B) \text{ AND } C) \text{ OR } (\text{NOT}(A) \text{ AND } \text{NOT}(B) \text{ AND } \text{NOT}(C)) \]

最后一步是使用交换律对“and”-子句中的变量进行排序, 然后对“and”-子句本身进行排序, 最后应用“or”-等幂性来删除重复的“and”-子句. 这最终得到一个无重复的排序完全DNF, 称为规范DNF:

\[ (A \text{ AND } \text{NOT}(B) \text{ AND } C) \text{ OR } (A \text{ AND } B \text{ AND } C) \text{ OR } (A \text{ AND } \text{NOT}(B) \text{ AND } \text{NOT}(C)) \text{ OR } (A \text{ AND } B \text{ AND } \text{NOT}(C)) \text{ OR } (\text{NOT}(A) \text{ AND } B \text{ AND } \text{NOT}(C)) \]

这个例子说明了应用上述公理到任何给定命题公式以推导等价规范DNF的一般策略. 这证明了:

定理 3.4.2

使用上述等价关系, 任何命题公式都可以被证明等价于规范形式.

这与等价有什么关系呢？很简单: 要证明两个公式等价, 可以将它们都转换为包含至少一个公式中出现的变量集合的规范形式——称之为联合变量. 如果两个公式等价于相同的规范形式, 那么这两个公式当然等价. 反之, 我们从真值表读取的完全析取范式实际上得到了规范形式. 因此, 如果两个公式等价, 它们将在联合变量上的真值表相同, 因此它们将具有相同的规范形式. 这证明了

定理3.4.3 (命题等价公理的完备性).

两个命题公式当且仅当它们可以使用上述等价公理证明等价时才等价.

注意, 可以使用CNF而不是DNF规范形式来采取相同的方法.

这些公理的好处在于, 它们允许一些巧妙的等价证明, 而这可能比真值表法要省力得多. 此外, 上述定理向我们保证, 这些公理保证提供每个等价性的证明, 这对于本节来说是一个很好的总结.

但是我们不想误导你: 使用规范形式本质上是真值表的副本. 没有理由期望等价的代数证明比转换为规范形式更容易, 这意味着代数证明一般不会比使用真值表更容易.

3.6 谓词公式

3.6.1 量词

“for all”符号 \(\forall\) 已经在第1.1节中出现过. 例如, 谓词

“\(x^2 \geq 0\)”

在\(x\)为实数时总是为真. 即,

\[ \forall x \in \mathbb{R}. x^2 \geq 0 \]

是一个真命题. 另一方面, 谓词

“\(5x^2 - 7 = 0\)”

仅在某些情况下为真；具体来说, 当\(x = \pm \sqrt{7/5}\)时. 有一个“存在”符号 ∃ 表示谓词对于至少一个对象为真, 但不一定对所有对象都为真. 因此,

\[ \exists x \in \mathbb{R}. 5x^2 - 7 = 0 \]

是真命题, 而

\[ \forall x \in \mathbb{R}. 5x^2 - 7 = 0 \]

不是真命题.

有几种方法可以表达“总是为真”和“有时为真”的概念. 下表给出了左侧的一般格式和右侧使用这些格式的具体示例. 你可以预期在数学写作中看到这样的短语数百次！

总是为真

抽象表示	例子
对所有 \(x \in D\), \(P(x)\) 为真.	对所有 \(x \in \mathbb{R}\), \(x^2 \geq 0\).
\(P(x)\) 对集合 \(D\) 中的每个 \(x\) 都为真.	\(x^2 \geq 0\) 对每个 \(x \in \mathbb{R}\) 都为真.

有时为真

抽象表达	具体例子
存在一个 \(x \in D\) 使得 \(P(x)\) 为真.	存在一个 \(x \in \mathbb{R}\) 使得 \(5x^2 - 7 = 0\).
\(P(x)\) 对集合 \(D\) 中的某些 \(x\) 为真.	\(5x^2 - 7 = 0\) 对某些 \(x \in \mathbb{R}\) 为真.
\(P(x)\) 对集合 \(D\) 中的至少一个 \(x\) 为真.	\(5x^2 - 7 = 0\) 对至少一个 \(x \in \mathbb{R}\) 为真.

这些句子都“量化”了谓词为真的频率. 具体来说, 断言一个谓词总是为真被称为全称量词, 而断言一个谓词有时为真被称为存在量词. 有时英文句子在量词的表述方面并不明确:

如果你能解决我们提出的任何问题, 那么你将获得这门课程的A. (3.19)

短语“你能解决我们提出的任何问题”可以合理地解释为全称量化或存在量化:

你能解决我们提出的每一个问题, (3.20)

或者

你能解决我们提出的至少一个问题. (3.21)

为了精确起见, 设Probs是我们提出的问题的集合, Solves(x)是谓词“你能解决问题$x$”, $G$是命题“你获得这门课程的A”. 然后对(3.19)的两种不同解释可以写成如下形式:

对于(3.20)而言,

\[ (\forall x \in \text{Probs}. \text{Solves}(x)) \implies G, \]

对于(3.21)而言,

\[ (\exists x \in \text{Probs}. \text{Solves}(x)) \implies G, \]

3.6.2 混合量词

许多数学陈述涉及多个量词. 例如, 我们已经描述了哥德巴赫猜想: 每个大于2的偶数都是两个素数之和.

让我们详细写出来确定量词:

对于每个大于2的偶数\(n\), 存在素数\(p\)和\(q\)使得\(n = p + q\).

设Evens为大于2的偶数的集合, Primes为素数的集合. 然后我们可以用逻辑符号表示哥德巴赫猜想如下:

\[ \forall n \in \text{Evens} \exists p \in \text{Primes} \exists q \in \text{Primes}. n = p + q \]

3.6.3 量词的顺序

交换不同种类的量词（存在量词或全称量词）的顺序通常会改变命题的含义. 例如, 让我们回到最初的一个有歧义的陈述:

“每个美国人都有一个梦想.”

这个句子是有歧义的, 因为量词的顺序不明确. 设\(A\)为美国人的集合, \(D\)为梦想的集合, 并定义谓词\(H(a, d)\)表示“美国人\(a\)有梦想\(d\). ”现在, 这个句子可以意味着每个美国人都有一个共同的梦想——比如拥有自己的房子:

\[ \exists d \in D \forall a \in A. H(a, d) \]

或者它可以意味着每个美国人都有一个个人的梦想:

\[ \forall a \in A \exists d \in D. H(a, d) \]

例如, 有些美国人可能梦想和平退休, 而其他人梦想在他们活着的时候继续从事他们的职业, 还有一些人梦想着如此富有以至于他们不需要考虑工作.

在哥德巴赫猜想中交换量词会产生明显错误的命题, 即每个大于2的偶数都是相同的两个素数之和:

\[ \exists p \in \text{Primes} \exists q \in \text{Primes} \forall n \in \text{Evens}. n = p + q \]

3.6.4 同一论域上的变量

当公式中的所有变量都被理解为取自同一非空集合\(D\)的值时, 通常省略对\(D\)的提及. 例如, 不写\(\forall x \in D \exists y \in D. Q(x, y)\), 而写\(\forall x \exists y. Q(x, y)\). 未命名的非空集合\(x\)和\(y\)所在的范围被称为公式的论域, 或简称域.

很容易安排所有变量在一个域上取值. 例如, 哥德巴赫猜想可以表达为所有变量在域\(\mathbb{N}\)上取值:

\[ \forall n. n \in \text{Evens} \implies (\exists p \exists q. p \in \text{Primes} \text{ AND } q \in \text{Primes} \text{ AND } n = p + q) \]

3.6.5 否定量词

两种量词之间存在简单的关系. 以下两个句子表示相同的意思:

• 并非每个人都喜欢冰淇淋.
• 有人不喜欢冰淇淋.

这些句子的等价性是谓词公式之间一般等价关系的一个实例:

\[ \text{NOT}(\forall x. P(x)) \text{ 等价于 } \exists x. \text{NOT}(P(x)) \tag{3.22} \]

同样, 这些句子表示相同的意思:

• 没有人喜欢被嘲笑.
• 每个人都不喜欢被嘲笑.

相应的谓词公式等价性是

\[ \text{NOT}(\exists x. P(x)) \text{ 等价于 } \forall x. \text{NOT}(P(x)) \tag{3.23} \]

注意, 等价性(3.23)直接由否定等价性(3.22)的两边得出.

一般原理是: 将“not”移到“\(\exists\)”的另一侧会将其变为“\(\forall\)”, 反之亦然.

这些等价性被称为德摩根量词律, 因为它们可以理解为将德摩根律应用于命题公式的无限序列的“and”和“or”. 例如, 我们可以通过以下方式解释(3.22):

假设论域是\(\{d_0, d_1, \ldots, d_n, \ldots\}\). 那么\(\exists x. \text{NOT}(P(x))\)的意思与以下无限“or”相同:

\[ \text{NOT}(P(d_0)) \text{ OR } \text{NOT}(P(d_1)) \text{ OR } \cdots \text{ OR } \text{NOT}(P(d_n)) \text{ OR } \cdots \tag{3.24} \]

将德摩根律应用于此无限“or”得到等价公式

\[ \text{NOT}[P(d_0) \text{ AND } P(d_1) \text{ AND } \cdots \text{ AND } P(d_n) \text{ AND } \cdots] \tag{3.25} \]

但是(3.25)的意思与

\[ \text{NOT}[\forall x. P(x)] \]

相同. 这解释了为什么\(\exists x. \text{NOT}(P(x))\)的意思与\(\text{NOT}[\forall x. P(x)]\)相同, 这也证实了(3.22).

3.6.6 谓词公式的有效性

有效性的概念扩展到谓词公式, 但是要有效, 一个公式现在必须无论论域是什么, 无论其变量取代论域, 无论其谓词变量的解释为何, 都必须求值为真. 例如, 等价性(3.22)给出了否定全称量词的规则, 这意味着以下公式是有效的:

\[ \text{NOT}(\forall x. P(x)) \text{ 当且仅当 } \exists x. \text{NOT}(P(x)) \tag{3.26} \]

另一个有用的有效断言例子是

\[ \exists x \forall y. P(x, y) \implies \forall y \exists x. P(x, y) \tag{3.27} \]

这是为什么这是有效的解释:

设\(D\)为变量的域, \(P_0\)为\(D\)上的某些二元谓词. 我们需要证明, 如果

\[ \exists x \in D. \forall y \in D. P_0(x, y) \tag{3.28} \]

在此解释下成立, 那么

\[ \forall y \in D. \exists x \in D. P_0(x, y) \tag{3.29} \]

也是成立的.

因此假设(3.28)为真. 根据\(\exists\)的定义, 这意味着某个元素\(d_0 \in D\)具有属性

\[ \forall y \in D. P_0(d_0, y) \]

根据\(\forall\)的定义, 这意味着

\[ P_0(d_0, d) \]

对于所有\(d \in D\)都为真. 因此给定任何\(d \in D\), 存在\(D\)中的一个元素, 即\(d_0\), 使得\(P_0(d_0, d)\)为真. 但这正是(3.29)的意思, 所以我们已经证明了(3.29)在此解释下成立, 如所需的那样.

我们希望这作为解释是有帮助的, 但我们并不真正想称其为“证明”. 问题在于对于像(3.27)这样基本的东西, 很难看出可以使用哪些更基本的公理来证明它. 上述解释所做的只是将逻辑公式(3.27)翻译成英文, 然后通过“for all”和“there exists”的意义作为依据.

与(3.27)相对, 公式

\[ \forall y \exists x. P(x, y) \implies \exists x \forall y. P(x, y) \tag{3.30} \]

是不成立的. 我们可以通过描述一种解释来证明这一点, 其中假设\(\forall y \exists x. P(x, y)\)为真, 但结论\(\exists x \forall y. P(x, y)\)不为真. 例如, 设论域为整数, \(P(x, y)\)表示\(x > y\). 那么假设会是真的, 因为给定\(y\)的值, 我们可以选择\(x\)的值为\(n + 1\), 例如. 但在这种解释下, 结论断言存在一个大于所有整数的整数, 这显然是错误的. 这种使断言成为假的解释称为该断言的反例.