谓词逻辑

命题逻辑将整个陈述视为不可分割的单位（命题），但我们在实际应用中常常需要讨论对象的性质或对象之间的关系。例如，"所有猫都是哺乳动物"或"存在大于100的素数"。命题逻辑无法直接表达"所有"或"存在"这样的概念，它只能将"所有猫都是哺乳动物"视为一个单独的黑箱命题。

谓词逻辑（Predicate Logic），也称为一阶逻辑（First-Order Logic），让我们能够"打开"这个黑箱。它引入了变量和量词，使我们能够一次性描述多个实例的情况，极大地扩展了逻辑的表达能力。

从命题到谓词

什么是谓词？

谓词（Predicate）是一个可以关于某些对象为真或为假的性质或关系。它通常用大写字母后跟括号表示，例如 $P(x)$ 可能表示"$x$ 是素数"或"$x$ 是哲学家"，具体含义取决于上下文。变量 $x$ 可以代表论域中的任意对象。

例子：

• 设 $M(x)$ 表示"$x$ 是会死的"，$H(x)$ 表示"$x$ 是人"
• 则"所有人都会死"可以用谓词逻辑表达，而命题逻辑无法直接做到这一点

谓词与命题的关系

谓词本身不是命题，因为它包含变量，真值不确定。但当我们将变量替换为具体的常量时，谓词就变成了命题。

例子：设 $P(x)$ 表示"$x$ 是素数"

• $P(2)$ 是命题，真值为真
• $P(4)$ 是命题，真值为假
• $P(x)$ 是谓词，真值取决于 $x$

谓词的元数

根据谓词所涉及的对象数量，可以分为：

一元谓词：描述单个对象的性质

$P(x): x \text{ 是学生}$

二元谓词：描述两个对象之间的关系

$R(x, y): x \text{ 爱 } y$

n元谓词：描述n个对象之间的关系

$B(x, y, z): x \text{ 在 } y \text{ 和 } z \text{ 之间}$

论域

论域（Domain of Discourse）是谓词逻辑中变量取值范围的集合，也称为个体域或全域。在进行逻辑推理时，必须明确论域是什么。

例子：

• 如果论域是自然数集 $\mathbb{N}$，则 $P(x)$ 中的 $x$ 只能取自然数
• 如果论域是全体人类，则 $H(x)$ 中的 $x$ 只能取人

选择合适的论域可以简化逻辑表达。例如，如果论域设为全体学生，则"所有学生都喜欢数学"可以简单表达为 $\forall x\, L(x)$，而不需要写 $\forall x\, (S(x) \rightarrow L(x))$。

量词

量词（Quantifier）是谓词逻辑引入的核心概念，用于表示"多少"或"哪些"元素满足某个谓词。

全称量词

全称量词（Universal Quantifier）记作 $\forall$，读作"对于所有"或"对于任意"。

$\forall x\, P(x)$

含义：对于论域中的每一个 $x$，$P(x)$ 都为真。

例子：

• 论域：所有动物
• $C(x)$：$x$ 是猫
• $M(x)$：$x$ 是哺乳动物
• $\forall x\, (C(x) \rightarrow M(x))$：所有猫都是哺乳动物

理解要点：全称量词通常与蕴含联结词配合使用。$\forall x\, (C(x) \rightarrow M(x))$ 的意思是：对于任意 $x$，如果 $x$ 是猫，那么 $x$ 是哺乳动物。这比 $\forall x\, (C(x) \land M(x))$ 更准确，后者表示"每个动物都是猫且是哺乳动物"，这显然是错误的。

存在量词

存在量词（Existential Quantifier）记作 $\exists$，读作"存在"或"至少存在一个"。

$\exists x\, P(x)$

含义：论域中至少存在一个 $x$ 使得 $P(x)$ 为真。

例子：

• 论域：自然数
• $P(x)$：$x$ 是素数
• $G(x)$：$x > 100$
• $\exists x\, (P(x) \land G(x))$：存在大于100的素数

理解要点：存在量词通常与合取联结词配合使用。$\exists x\, (P(x) \land G(x))$ 的意思是：存在一个 $x$，它既是素数又大于100。

量词的真值判断

全称量词的真值：

• 如果论域中每个元素都使 $P(x)$ 为真，则 $\forall x\, P(x)$ 为真
• 如果论域中至少有一个元素使 $P(x)$ 为假，则 $\forall x\, P(x)$ 为假

存在量词的真值：

• 如果论域中至少有一个元素使 $P(x)$ 为真，则 $\exists x\, P(x)$ 为真
• 如果论域中每个元素都使 $P(x)$ 为假，则 $\exists x\, P(x)$ 为假

有限论域的情形：如果论域是有限的，设为 $\{a_1, a_2, \ldots, a_n\}$，则：

$\forall x\, P(x) \equiv P(a_1) \land P(a_2) \land \cdots \land P(a_n)$

$\exists x\, P(x) \equiv P(a_1) \lor P(a_2) \lor \cdots \lor P(a_n)$

唯一存在量词

唯一存在量词记作 $\exists!$ 或 $\exists_1$，表示"恰好存在一个"。

$\exists! x\, P(x)$

含义：论域中恰好存在一个 $x$ 使得 $P(x)$ 为真。

展开形式：

$\exists! x\, P(x) \equiv \exists x\, \left(P(x) \land \forall y\, (P(y) \rightarrow y = x)\right)$

例子：$\exists! x\, (x \text{ 是中国的首都})$

这意味着：存在一个 $x$，$x$ 是中国的首都，并且对于所有 $y$，如果 $y$ 是中国的首都，则 $y = x$。

量词的否定

量词的否定是谓词逻辑中的一个重要技巧，德摩根律可以推广到量词上。

基本规则

$\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)$

$\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)$

直观理解：

• "不是所有 $x$ 都满足 $P$" 等价于 "存在某个 $x$ 不满足 $P$"
• "不存在满足 $P$ 的 $x$" 等价于 "所有 $x$ 都不满足 $P$"

应用例子

原命题：所有人都会死。

$\forall x\, (H(x) \rightarrow M(x))$

否定：不是所有人都会死（有人不会死）。

$\neg\forall x\, (H(x) \rightarrow M(x)) \equiv \exists x\, \neg(H(x) \rightarrow M(x)) \equiv \exists x\, (H(x) \land \neg M(x))$

即：存在一个人不会死。

原命题：存在大于100的素数。

$\exists x\, (P(x) \land x > 100)$

否定：不存在大于100的素数（所有素数都不超过100）。

$\neg\exists x\, (P(x) \land x > 100) \equiv \forall x\, \neg(P(x) \land x > 100) \equiv \forall x\, (P(x) \rightarrow x \leq 100)$

嵌套量词

当多个量词出现在同一个公式中时，就形成了嵌套量词。量词的顺序非常重要。

相同量词的嵌套

当嵌套的是相同类型的量词时，顺序可以交换。

$\forall x\, \forall y\, P(x, y) \equiv \forall y\, \forall x\, P(x, y)$

$\exists x\, \exists y\, P(x, y) \equiv \exists y\, \exists x\, P(x, y)$

例子：

• $\forall x\, \forall y\, (x + y = y + x)$：对于所有 $x$ 和 $y$，$x + y = y + x$
• 这与 $\forall y\, \forall x\, (x + y = y + x)$ 含义相同

不同量词的嵌套

当全称量词和存在量词嵌套时，顺序通常不能交换。

$\forall x\, \exists y\, P(x, y) \not\equiv \exists y\, \forall x\, P(x, y)$

例子：设 $L(x, y)$ 表示"$x$ 爱 $y$"

• $\forall x\, \exists y\, L(x, y)$：每个人都爱某个人（不同的人可能爱不同的人）
• $\exists y\, \forall x\, L(x, y)$：存在某个人被所有人爱（存在一个被所有人爱的人）

这两个命题的含义完全不同。前者几乎总是真的（每个人都有自己所爱的人），后者则很可能是假的（很难找到一个被所有人爱的人）。

数学例子：

• $\forall x\, \exists y\, (x + y = 0)$：对于每个实数 $x$，存在实数 $y$ 使得 $x + y = 0$
  • 这是真的，取 $y = -x$ 即可
• $\exists y\, \forall x\, (x + y = 0)$：存在实数 $y$，对于所有实数 $x$ 都有 $x + y = 0$
  • 这是假的，不可能有一个 $y$ 对所有 $x$ 都满足这个等式

嵌套量词的否定

对嵌套量词进行否定时，每个量词都要取反，顺序保持不变。

$\neg(\forall x\, \exists y\, P(x, y)) \equiv \exists x\, \forall y\, \neg P(x, y)$

$\neg(\exists x\, \forall y\, P(x, y)) \equiv \forall x\, \exists y\, \neg P(x, y)$

自然语言与谓词逻辑的翻译

将自然语言翻译为谓词逻辑是一项重要技能，需要准确识别量词和谓词的结构。

常见句型

自然语言	逻辑形式
所有 A 都是 B	$\forall x\, (A(x) \rightarrow B(x))$
有些 A 是 B	$\exists x\, (A(x) \land B(x))$
没有 A 是 B	$\forall x\, (A(x) \rightarrow \neg B(x))$ 或 $\neg\exists x\, (A(x) \land B(x))$
有些 A 不是 B	$\exists x\, (A(x) \land \neg B(x))$
并非所有 A 都是 B	$\exists x\, (A(x) \land \neg B(x))$

翻译例子

例子1："每辆汽车都有轮子。"

设论域为所有物体，$C(x)$：$x$ 是汽车，$W(x)$：$x$ 有轮子。

$\forall x\, (C(x) \rightarrow W(x))$

例子2："有些汽车没有轮子。"

$\exists x\, (C(x) \land \neg W(x))$

例子3："每个学生都至少选修了一门编程课。"

设 $S(x)$：$x$ 是学生，$P(y)$：$y$ 是编程课，$T(x, y)$：$x$ 选修了 $y$。

$\forall x\, (S(x) \rightarrow \exists y\, (P(y) \land T(x, y)))$

例子4："存在一个素数是偶数。"

设论域为自然数，$P(x)$：$x$ 是素数，$E(x)$：$x$ 是偶数。

$\exists x\, (P(x) \land E(x))$

这个命题是真的，因为 $x = 2$ 满足条件。

例子5："每个人都有恰好一个母亲。"

设 $M(x, y)$：$y$ 是 $x$ 的母亲。

$\forall x\, \exists! y\, M(x, y)$

展开形式：

$\forall x\, \exists y\, \left(M(x, y) \land \forall z\, (M(x, z) \rightarrow z = y)\right)$

关键词对照

自然语言关键词	逻辑表达
所有、每个、任意、一切	$\forall$
存在、有些、至少一个、有的	$\exists$
恰好一个、唯一	$\exists!$
如果...则...	$\rightarrow$（与全称量词配合）
并且、且	$\land$（与存在量词配合）

推理规则

谓词逻辑继承了命题逻辑的所有推理规则，并增加了处理量词的规则。

全称实例化（Universal Instantiation）

$\frac{\forall x\, P(x)}{\therefore P(c)}$

含义：如果对于所有 $x$，$P(x)$ 都为真，那么对于任意具体的 $c$，$P(c)$ 也为真。

例子：

• 前提：所有人都会死。$\forall x\, (H(x) \rightarrow M(x))$
• 结论：苏格拉底会死。$H(\text{苏格拉底}) \rightarrow M(\text{苏格拉底})$

全称推广（Universal Generalization）

$\frac{P(c) \text{（对任意 } c\text{）}}{\therefore \forall x\, P(x)}$

含义：如果对于任意选取的 $c$，$P(c)$ 都为真，则可以得出 $\forall x\, P(x)$。

注意：$c$ 必须是任意选取的，不能有任何特殊限制。

存在实例化（Existential Instantiation）

$\frac{\exists x\, P(x)}{\therefore P(c) \text{（对某个 } c\text{）}}$

含义：如果存在 $x$ 使得 $P(x)$ 为真，则可以引入一个常量 $c$ 表示这样的元素。

注意：$c$ 必须是一个新的常量符号，不能与之前使用过的常量冲突。

存在推广（Existential Generalization）

$\frac{P(c)}{\therefore \exists x\, P(x)}$

含义：如果某个具体的 $c$ 满足 $P(c)$，则存在 $x$ 使得 $P(x)$ 为真。

经典推理例子

三段论推理：

• 前提1：所有人都会死。$\forall x\, (H(x) \rightarrow M(x))$
• 前提2：苏格拉底是人。$H(\text{苏格拉底})$
• 结论：苏格拉底会死。$M(\text{苏格拉底})$

证明过程：

1. $\forall x\, (H(x) \rightarrow M(x))$ （前提）
2. $H(\text{苏格拉底}) \rightarrow M(\text{苏格拉底})$ （全称实例化，1）
3. $H(\text{苏格拉底})$ （前提）
4. $M(\text{苏格拉底})$ （假言推理，2，3）

前束范式

前束范式（Prenex Normal Form）是谓词逻辑公式的一种标准形式，其中所有量词都位于公式的最前面。

定义

一个谓词逻辑公式是前束范式，当且仅当它具有以下形式：

$Q_1 x_1\, Q_2 x_2\, \cdots Q_n x_n\, G$

其中 $Q_i$ 是 $\forall$ 或 $\exists$，$G$ 是不含任何量词的公式。$Q_1 x_1\, Q_2 x_2\, \cdots Q_n x_n$ 称为前束词，$G$ 称为母式。

转换步骤

1. 消除蕴含和双条件：$p \rightarrow q \equiv \neg p \lor q$
2. 将否定移到原子公式前（利用德摩根律和量词否定规则）
3. 重命名约束变量，避免变量名冲突
4. 将所有量词移到公式最前面

例子：将 $\forall x\, P(x) \rightarrow \exists x\, Q(x)$ 转换为前束范式

$\forall x\, P(x) \rightarrow \exists x\, Q(x)$ $\equiv \neg\forall x\, P(x) \lor \exists x\, Q(x)$ $\equiv \exists x\, \neg P(x) \lor \exists x\, Q(x)$ $\equiv \exists x\, (\neg P(x) \lor Q(x))$

应用实例

数据库查询

SQL 查询语言基于谓词逻辑。一个查询本质上就是找到满足某个谓词的所有元素。

SELECT * FROM Employees WHERE age > 30 AND department = 'Sales'

这相当于找到所有满足谓词 $(Age(x) > 30) \land (Dept(x) = \text{'Sales'})$ 的员工 $x$。

程序验证

在形式化验证中，程序的正确性用谓词逻辑描述。

例子：验证数组求和函数

// 前置条件: a 是长度为 n 的数组
// 后置条件: 返回值 = sum(a[0..n-1])
int sum(int[] a, int n) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s = s + a[i];
    }
    return s;
}

循环不变式（用谓词逻辑表示）： $\forall k\, (0 \leq k < i \rightarrow s = \sum_{j=0}^{k} a[j])$

数学证明

几乎所有数学定义和定理都用谓词逻辑表达。

极限的定义：$\lim_{x \to a} f(x) = L$

$\forall \varepsilon > 0\, \exists \delta > 0\, \forall x\, (0 < |x - a| < \delta \rightarrow |f(x) - L| < \varepsilon)$

这是一个典型的 $\forall \exists \forall$ 嵌套结构。

人工智能与知识表示

在专家系统和知识图谱中，知识用谓词逻辑表示。

例子：

• 规则：$\forall x\, (Cat(x) \rightarrow Mammal(x))$ （所有猫都是哺乳动物）
• 事实：$Cat(Tom)$ （Tom 是猫）
• 推理：$Mammal(Tom)$ （Tom 是哺乳动物）

常见误区

混淆量词类型

误区：认为"有些"和"所有"可以互换使用。

纠正："有些"用 $\exists$，"所有"用 $\forall$，含义完全不同。

全称量词使用合取

误区：将"所有猫都是哺乳动物"写成 $\forall x\, (C(x) \land M(x))$

纠正：应该写成 $\forall x\, (C(x) \rightarrow M(x))$。前者表示每个动物都是猫且是哺乳动物，这是错误的。

存在量词使用蕴含

误区：将"存在大于100的素数"写成 $\exists x\, (P(x) \rightarrow x > 100)$

纠正：应该写成 $\exists x\, (P(x) \land x > 100)$。使用蕴含时，如果 $P(x)$ 为假，整个蕴含就为真，这不符合原意。

忽略量词顺序

误区：认为 $\forall x\, \exists y\, P(x, y)$ 和 $\exists y\, \forall x\, P(x, y)$ 相同。

纠正：量词顺序不能随意交换，含义可能完全不同。

小结

本章介绍了谓词逻辑的核心概念：

• 谓词是关于对象的性质或关系，可以取真或假
• 量词（全称量词 $\forall$ 和存在量词 $\exists$）用于表达"所有"和"存在"
• 论域是变量取值范围的集合
• 量词否定遵循德摩根律的推广形式
• 嵌套量词的顺序通常不能交换
• 推理规则包括全称实例化、全称推广、存在实例化、存在推广

谓词逻辑是数学、计算机科学和人工智能中表达和推理的基本工具。下一章将学习集合论基础，为关系、函数和图论的学习打下基础。