谓词逻辑：量词与自然语句的形式化

本节导读

命题逻辑把「所有程序员都会写代码」整个看成一个 p，看不出「所有」和「程序员」的结构，也就无法推出「张三会写代码」。谓词逻辑把句子拆成个体、性质和数量，弥补了这个缺陷。

大纲这一单元列了六条，本节讲前三条：谓词与量词、复杂自然语句的形式化、否定型等值式与量词分配等值式；下一节讲前束范式、Skolem 标准形和推理。常见资料提到的「形式化语句」题，谓词逻辑是重头。学完你应该能写出带特性谓词、带两重量词的公式，能判断变元是约束还是自由出现，能在给定个体域上算出公式的真值。

个体词、谓词与量词

个体词表示研究的对象：个体常项用 a、b、c，个体变项用 x、y、z；个体变项的取值范围叫个体域（论域），不加说明时取全总个体域（宇宙间一切事物）。谓词表示个体的性质或个体之间的关系：F(x) 表示「x 是素数」是一元谓词，L(x, y) 表示「x 小于 y」是二元谓词。谓词填进具体的个体常项才成为命题，比如 L(2, 5) 是真命题。

量词有两个：全称量词 $\forall x$∀x 读作「对所有 x」，存在量词 $\exists x$∃x 读作「存在 x」「有的 x」。量词后面紧跟的那一部分公式是它的辖域，比如 $\forall x (F(x) \to G(x))$∀x(F(x)→G(x)) 中，$\forall x$∀x 的辖域是括号里的整个蕴涵式。

自然语句的形式化

用全总个体域时，要用特性谓词把讨论对象挑出来。规则只有两句：全称量词配蕴涵，存在量词配合取。设 M(x) 是特性谓词，P(x) 是要说的性质：

自然语句	公式
所有 M 都是 P	$\forall x (M(x) \to P(x))$∀x(M(x)→P(x))
有的 M 是 P	$\exists x (M(x) \land P(x))$∃x(M(x)∧P(x))
没有 M 是 P（所有 M 都不是 P）	$\forall x (M(x) \to \neg P(x))$∀x(M(x)→¬P(x))，等值于 $\neg \exists x (M(x) \land P(x))$¬∃x(M(x)∧P(x))
有的 M 不是 P（并非所有 M 都是 P）	$\exists x (M(x) \land \neg P(x))$∃x(M(x)∧¬P(x))，等值于 $\neg \forall x (M(x) \to P(x))$¬∀x(M(x)→P(x))

为什么全称要配蕴涵：$\forall x (M(x) \land P(x))$∀x(M(x)∧P(x)) 的意思是「一切事物都是 M 而且都是 P」，说过头了。为什么存在要配合取：$\exists x (M(x) \to P(x))$∃x(M(x)→P(x)) 只要有一个东西不是 M 就为真，什么也没说清楚。

带两个量词的句子，按「先外后内」逐层写。比如「每个整数都有比它大的整数」，设 I(x)：x 是整数，G(y, x)：y 大于 x，写成 $\forall x (I(x) \to \exists y (I(y) \land G(y, x)))$∀x(I(x)→∃y(I(y)∧G(y,x)))。量词的顺序不能随便换：$\forall x \exists y$∀x∃y 说的是「对每个 x 都能找到一个 y」，y 可以随 x 变；$\exists y \forall x$∃y∀x 说的是「有同一个 y 对所有 x 都成立」，要求强得多。同种量词之间可以交换，$\forall x \forall y \Leftrightarrow \forall y \forall x$∀x∀y⇔∀y∀x，$\exists x \exists y \Leftrightarrow \exists y \exists x$∃x∃y⇔∃y∃x。

约束变元与自由变元

在量词 $\forall x$∀x 或 $\exists x$∃x 辖域内出现的 x 叫约束出现，其他的出现叫自由出现。同一个字母可能在一个公式里既有约束出现又有自由出现，为了不混淆，有两条改名规则：

• 换名规则：把某个量词的约束变元连同它辖域里的所有约束出现，统一换成公式里没有出现过的字母；
• 代替规则：把某个自由变元的所有自由出现，统一换成公式里没有出现过的字母。

不含自由变元的公式叫闭式。闭式在给定解释下就是一个命题，有确定的真值；含自由变元的公式，还要再给自由变元赋值才有真值。

解释与真值

解释要给出个体域、个体常项和函数的含义、谓词的含义。个体域是有限集 $D = \{a_1, \ldots, a_n\}$D={a1​,…,an​} 时，量词可以展开：

$\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n), \qquad \exists x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)$∀xA(x)⇔A(a1​)∧A(a2​)∧⋯∧A(an​),∃xA(x)⇔A(a1​)∨A(a2​)∨⋯∨A(an​)

比如取 $D = \{1, 2, 3\}$D={1,2,3}：$\forall x \exists y (x + y = 4)$∀x∃y(x+y=4) 为真，因为 x 取 1、2、3 时分别有 y 取 3、2、1；$\exists y \forall x (x + y = 4)$∃y∀x(x+y=4) 为假，因为找不到一个 y 同时使三个等式成立。这一对公式就是「量词顺序不能换」最直观的例子。

在任何解释下都真的公式叫永真式（逻辑有效式），任何解释下都假的叫永假式，至少有一个解释使它为真的叫可满足式。命题逻辑的重言式代换进来得到的谓词公式（如 $F(x) \lor \neg F(x)$F(x)∨¬F(x)）都是永真式。

否定型等值式与量词分配等值式

类别	等值式（或只有一个方向的蕴涵式）
量词否定	$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$¬∀xA(x)⇔∃x¬A(x)；$\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$¬∃xA(x)⇔∀x¬A(x)
量词分配（等值）	$\forall x (A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x)$∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)；$\exists x (A(x) \lor B(x)) \Leftrightarrow \exists x A(x) \lor \exists x B(x)$∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)
只能单向	$\forall x A(x) \lor \forall x B(x) \Rightarrow \forall x (A(x) \lor B(x))$∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))；$\exists x (A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x)$∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)
辖域收缩与扩张（B 中不含 x）	$\forall x (A(x) \lor B) \Leftrightarrow \forall x A(x) \lor B$∀x(A(x)∨B)⇔∀xA(x)∨B；$\exists x (A(x) \land B) \Leftrightarrow \exists x A(x) \land B$∃x(A(x)∧B)⇔∃xA(x)∧B
量词在前件（B 中不含 x）	$\forall x (A(x) \to B) \Leftrightarrow \exists x A(x) \to B$∀x(A(x)→B)⇔∃xA(x)→B；$\exists x (A(x) \to B) \Leftrightarrow \forall x A(x) \to B$∃x(A(x)→B)⇔∀xA(x)→B
量词在后件（B 中不含 x）	$\forall x (B \to A(x)) \Leftrightarrow B \to \forall x A(x)$∀x(B→A(x))⇔B→∀xA(x)；$\exists x (B \to A(x)) \Leftrightarrow B \to \exists x A(x)$∃x(B→A(x))⇔B→∃xA(x)

量词否定可以记成「否定号穿过量词，量词换个样」。量词分配的口诀是「全称对合取，存在对析取」；反过来的两种只有单向蕴涵。比如个体域是某公司的员工，每人要么在上海办公、要么在杭州办公，两地都有人：「每人都在上海或杭州办公」为真，「所有人都在上海办公，或者所有人都在杭州办公」为假，所以全称对析取不能分配。量词在前件时会变成另一种量词，因为蕴涵的前件相当于带了一个否定。

易错提醒

• ❌ 「所有 M 都是 P」写成 $\forall x (M(x) \land P(x))$∀x(M(x)∧P(x))。✅ 写成 $\forall x (M(x) \to P(x))$∀x(M(x)→P(x))。因为合取的写法断言个体域里的一切都是 M。

• ❌ 「有的 M 是 P」写成 $\exists x (M(x) \to P(x))$∃x(M(x)→P(x))。✅ 写成 $\exists x (M(x) \land P(x))$∃x(M(x)∧P(x))。因为蕴涵式只要找到一个不是 M 的个体就为真。

• ❌ $\neg \forall x P(x)$¬∀xP(x) 等值于 $\forall x \neg P(x)$∀x¬P(x)。✅ 等值于 $\exists x \neg P(x)$∃x¬P(x)。因为「并非都是」只说明至少有一个不是。

• ❌ 把 $\forall x \exists y$∀x∃y 换成 $\exists y \forall x$∃y∀x。✅ 两者一般不等值，只有 $\exists y \forall x A(x, y) \Rightarrow \forall x \exists y A(x, y)$∃y∀xA(x,y)⇒∀x∃yA(x,y)。因为前者允许 y 随 x 变。

• ❌ 改名时只改了量词后面的字母，辖域里的约束出现没跟着改。✅ 量词和它辖域里的约束出现一起换成新字母。因为只改一处会把约束出现变成自由出现。

例题精讲

例题 1（形式化语句）

设 E(x)：x 是员工，T(x)：x 参加了培训，M(y)：y 是主管，R(y, x)：y 负责 x。把下面两句形式化：（1）并非所有员工都参加了培训；（2）每个员工都有负责他的主管。

答题要点示范：（1）$\neg \forall x (E(x) \to T(x))$¬∀x(E(x)→T(x))，等值于 $\exists x (E(x) \land \neg T(x))$∃x(E(x)∧¬T(x))；（2）$\forall x (E(x) \to \exists y (M(y) \land R(y, x)))$∀x(E(x)→∃y(M(y)∧R(y,x)))。

点评：（2）外层是全称、配蕴涵，内层是存在、配合取；主管可以因人而异，所以 $\exists y$∃y 写在 $\forall x$∀x 的里面。

例题 2（辖域与换名）

指出 $\forall x (F(x) \to \exists y G(x, y)) \land H(x, z)$∀x(F(x)→∃yG(x,y))∧H(x,z) 中各量词的辖域和变元的出现情况，并用换名规则改写，使每个字母只以一种身份出现。

答题要点示范：$\forall x$∀x 的辖域是 $F(x) \to \exists y G(x, y)$F(x)→∃yG(x,y)，$\exists y$∃y 的辖域是 $G(x, y)$G(x,y)；F、G 中的 x 和 G 中的 y 是约束出现，H 中的 x 和 z 是自由出现。把约束变元 x 换名为 u：$\forall u (F(u) \to \exists y G(u, y)) \land H(x, z)$∀u(F(u)→∃yG(u,y))∧H(x,z)。

点评：H 中的 x 不在 $\forall x$∀x 的辖域里，所以是自由出现；改名时它不跟着改。

例题 3（正误判断）

判断：$\exists x (A(x) \land B(x)) \Leftrightarrow \exists x A(x) \land \exists x B(x)$∃x(A(x)∧B(x))⇔∃xA(x)∧∃xB(x)。

答案：错误。反例：个体域是甲、乙两人，A(x) 表示 x 会弹琴，B(x) 表示 x 会唱歌；甲只会弹琴，乙只会唱歌。右边为真，左边为假。只有从左到右的单向蕴涵成立。

点评：判断等值式为错，给一个具体的个体域和谓词解释就是最好的理由。

本节小结

• 谓词表示性质或关系，量词有全称和存在两种，量词后面紧跟的部分是它的辖域。
• 形式化：全称配蕴涵，存在配合取；多重量词按先外后内写，$\forall x \exists y$∀x∃y 与 $\exists y \forall x$∃y∀x 不能互换。
• 约束出现在量词辖域内，其他是自由出现；换名规则改约束变元，代替规则改自由变元。
• 有限个体域上，全称展开成合取，存在展开成析取。
• 量词否定：否定号穿过量词、量词换样；量词分配：全称对合取，存在对析取，另外两种只有单向蕴涵。