谓词逻辑

一、谓词逻辑的基本概念

1.1 个体词

定义：在原子命题中，可以独立存在的客体（主语）称为个体词，也称客体词。

个体常元：表示具体、特定事物的个体词，用小写字母 $a, b, c, \cdots$ 表示。

个体变元：表示泛指或抽象的个体词，用小写字母 $x, y, z, \cdots$ 表示。

个体域：个体变元的取值范围称为个体域（或论域）。

1.2 谓词

定义：用来描述个体词的性质或个体词之间关系的词称为谓词，用大写字母 $F, G, H, \cdots$ 表示。

分类：

谓词常项：表示具体、特定性质或关系的谓词。

谓词变项：表示泛指或抽象性质或关系的谓词。

1.3 谓词填式

定义：谓词字母后面填上客体所得的式子叫谓词填式。

要点：谓词填式不同于谓词。

1.4 命题函数

简单命题函数：由一个谓词和一些客体变元组成的表达式称为简单命题函数。

例如：$A(x)$、$B(x,y)$

复合命题函数：由一个或多个命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。

例如：$\neg A(x)$、$A(x) \to B(x,y)$

1.5 谓词与命题的关系

• 单独一个谓词不是完整命题，完整的客体和谓词字母两部分才成为一个命题
• 一元谓词表达了客体的性质
• 多元谓词表达了客体之间的关系
• 命题是0元谓词
• 命题函数不是命题
• 当客体变元取特定值时，命题函数才构成命题
• 谓词的解释、客体变元的取值范围影响了命题的真值

1.6 常用谓词约定

1.7 量词

全称量词 $\forall$：表示"所有的"、“每一个”、“一切”、“任意的”。

存在量词 $\exists$：表示"存在"、“某一个”、“至少有一个”。

量词的作用：将命题函数转化为命题。

二、命题符号化

2.1 符号化步骤

1. 找出个体词和谓词
2. 确定量词
3. 用逻辑联结词连接

2.2 符号化示例

例1：所有的人都是要死的。

• 个体域：所有人
• $F(x)$：$x$ 是人；$G(x)$：$x$ 是要死的
• 符号化：$\forall x(F(x) \to G(x))$

例2：有些人长着黑头发。

• 个体域：所有人
• $F(x)$：$x$ 是人；$G(x)$：$x$ 长着黑头发
• 符号化：$\exists x(F(x) \wedge G(x))$

例3：所有的人都跑掉了。

• 个体域：所有人
• $F(x)$：$x$ 是人；$G(x)$：$x$ 跑掉了
• 符号化：$\forall x(F(x) \to G(x))$

例4：没有不犯错误的人。

• 个体域：所有人
• $F(x)$：$x$ 是人；$G(x)$：$x$ 犯错误
• 符号化：$\neg \exists x(F(x) \wedge \neg G(x))$
• 等价于：$\forall x(F(x) \to G(x))$

例5：尽管有人聪明，但未必所有人都聪明。

• 个体域：所有人
• $F(x)$：$x$ 是人；$G(x)$：$x$ 聪明
• 符号化：$\exists x(F(x) \wedge G(x)) \wedge \neg \forall x(F(x) \to G(x))$

2.3 重要规律

规律1：全称量词 $\forall$ 后面跟蕴含联结词 $\to$

$\forall x(F(x) \to G(x))$

规律2：存在量词 $\exists$ 后面跟合取联结词 $\wedge$

$\exists x(F(x) \wedge G(x))$

记忆口诀：“全称用蕴含，存在用合取”

2.4 特性谓词

定义：如果没有给定个体域，则要引入特性谓词来限制变元的范围。

示例：所有正实数均可开平方。

设：

• $R(x)$：$x$ 是实数
• $G(x)$：$x$ 是正数
• $B(x,y)$：$x$ 大于 $y$
• $S(x)$：$x$ 可开平方

要点：特性谓词在全称量词后用蕴含，在存在量词后用合取。

2.5 谓词公式的翻译

翻译规则：

数学表达：

• 无穷性（无穷大、无穷小）：任一个数，存在更大（小）的
• 唯一性：若存在两个，则必相等

存在量词和全称量词在翻译时的区别：

设 $M(x)$ 表示 $x$ 是人，$H(x)$ 表示 $x$ 要呼吸。

三、量词的辖域与变元

3.1 指导变元

定义：量词后面的变元称为该量词的指导变元（也称作用变元）。

例如：$\forall x A(x)$ 中，$x$ 是全称量词 $\forall$ 的指导变元。

3.2 辖域

定义：量词的辖域（作用范围）是量词所约束的范围。

确定方法：

• 若量词后有括号，则括号内的部分为辖域
• 若量词后无括号，则量词后最短的公式为辖域

3.3 约束出现与自由出现

约束出现：在量词的辖域内，与量词指导变元同名的变元的出现称为约束出现。

自由出现：不在任何量词辖域内，或虽然在量词辖域内但与量词指导变元不同名的变元的出现称为自由出现。

3.4 约束变元与自由变元

约束变元：约束出现的变元称为约束变元。

自由变元：自由出现的变元称为自由变元。

示例：$\forall x(F(x, y) \to \exists y G(x, y, z))$

• $x$ 在 $F(x, y)$ 中约束出现，在 $G(x, y, z)$ 中约束出现
• $y$ 在 $F(x, y)$ 中自由出现，在 $G(x, y, z)$ 中约束出现（被 $\exists y$ 约束）
• $z$ 自由出现

3.5 换名规则

规则：改变约束变元的名称，不改变公式的含义。

方法：

• 将量词的指导变元和辖域内所有同名的约束变元同时替换为新的变元
• 新变元不能与辖域内其他变元同名

示例：
$\forall x F(x, y) \Leftrightarrow \forall t F(t, y)$

四、谓词等价式

4.1 代入实例

定义：将命题逻辑中的公式推广到谓词逻辑中，得到的公式称为原公式的代入实例。

示例：

• 命题逻辑中的 $A \to B$ 的代入实例：$\forall x F(x) \to \exists x G(x)$
• 命题逻辑中的 $A \vee \neg A$ 的代入实例：$\forall x F(x) \vee \neg \forall x F(x)$

性质：命题逻辑中的重言式的代入实例在谓词逻辑中仍为重言式。

4.2 量词否定转移（德摩根律的推广）

定理：

$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$

$\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$

理解：

• “并非所有人都满足性质A” $\Leftrightarrow$ “存在某人不满足性质A”
• “不存在满足性质A的人” $\Leftrightarrow$ “所有人都不满足性质A”

示例：

• $\neg \forall x F(x) \Leftrightarrow \exists x \neg F(x)$
• $\neg \exists x G(x) \Leftrightarrow \forall x \neg G(x)$

4.3 辖域扩张与收缩

定理（设 $B$ 中不含自由变元 $x$）：

$\forall x(A(x) \wedge B) \Leftrightarrow \forall x A(x) \wedge B$

$\forall x(A(x) \vee B) \Leftrightarrow \forall x A(x) \vee B$

$\exists x(A(x) \wedge B) \Leftrightarrow \exists x A(x) \wedge B$

$\exists x(A(x) \vee B) \Leftrightarrow \exists x A(x) \vee B$

要点：当 $B$ 不含量词变元 $x$ 时，量词可以扩张或收缩其辖域。

4.4 量词对联结词的分配律

成立的分配律：

$\forall x(A(x) \wedge B(x)) \Leftrightarrow \forall x A(x) \wedge \forall x B(x)$

$\exists x(A(x) \vee B(x)) \Leftrightarrow \exists x A(x) \vee \exists x B(x)$

不成立的分配律：

$\forall x(A(x) \vee B(x)) \not\Leftrightarrow \forall x A(x) \vee \forall x B(x)$

$\exists x(A(x) \wedge B(x)) \not\Leftrightarrow \exists x A(x) \wedge \exists x B(x)$

记忆口诀：“全称对合取分配，存在对析取分配”

4.5 双量词的顺序

要点：全称量词和存在量词的顺序不能随意改变！

四种双量词形式：

重要结论：

• $\forall x \forall y P(x,y) \Leftrightarrow \forall y \forall x P(x,y)$（全称量词可交换）
• $\exists x \exists y P(x,y) \Leftrightarrow \exists y \exists x P(x,y)$（存在量词可交换）
• $\forall x \exists y P(x,y) \not\Leftrightarrow \exists y \forall x P(x,y)$（全称和存在不可交换）

示例：

• $\forall x \exists y P(x,y)$：对每个x，都存在y使得P(x,y)成立
• $\exists y \forall x P(x,y)$：存在y，使得对所有x都有P(x,y)成立

多个量词的使用方法与双量词类似。

五、消去量词

5.1 有限个体域的情况

当个体域 $D = \{a_1, a_2, \cdots, a_n\}$ 为有限集时：

全称量词的消去：

$\forall x A(x) \Leftrightarrow A(a_1) \wedge A(a_2) \wedge \cdots \wedge A(a_n)$

存在量词的消去：

$\exists x A(x) \Leftrightarrow A(a_1) \vee A(a_2) \vee \cdots \vee A(a_n)$

5.2 示例

设个体域 $D = \{1, 2, 3\}$，$F(x)$：$x$ 是偶数。

• $\forall x F(x) \Leftrightarrow F(1) \wedge F(2) \wedge F(3)$（假，因为1和3不是偶数）
• $\exists x F(x) \Leftrightarrow F(1) \vee F(2) \vee F(3)$（真，因为2是偶数）

六、前束范式

6.1 定义

前束范式：如果一个谓词逻辑公式具有如下形式：

$Q_1 x_1 Q_2 x_2 \cdots Q_n x_n M$

其中 $Q_i$（$i = 1, 2, \cdots, n$）是量词（$\forall$ 或 $\exists$），$M$ 是不含量词的公式，则称该公式为前束范式。

要点：

• 量词全在公式的最前面
• 后面是不含量词的部分 $M$

6.2 求前束范式的方法

利用换名规则和辖域扩张/收缩，将量词移到公式的最前面。

步骤：

1. 利用等值式消去公式中的 $\to$ 和 $\leftrightarrow$
2. 将否定符号 $\neg$ 移到各原子命题前
3. 利用换名规则，使所有约束变元不同名
4. 利用辖域扩张，将量词移到公式最前面

示例：

$\forall x F(x) \to \exists x G(x)$

$\Leftrightarrow \neg \forall x F(x) \vee \exists x G(x)$

$\Leftrightarrow \exists x \neg F(x) \vee \exists x G(x)$

$\Leftrightarrow \exists x \neg F(x) \vee \exists y G(y) \quad \text{（换名）}$

$\Leftrightarrow \exists x(\neg F(x) \vee \exists y G(y))$

$\Leftrightarrow \exists x \exists y(\neg F(x) \vee G(y))$

七、谓词逻辑的推理规则

7.1 四条基本规则

规则1：全称量词消去（UI / US）

$\frac{\forall x A(x)}{A(c)}$

其中 $c$ 是个体域中任意一个个体。

含义：如果所有 $x$ 都满足性质 $A$，则任意一个特定的个体 $c$ 也满足性质 $A$。

规则2：存在量词消去（EI / ES）

$\frac{\exists x A(x)}{A(c)}$

其中 $c$ 是个体域中某个特定的个体（常称为"新名"）。

含义：如果存在某个 $x$ 满足性质 $A$，则可以假设存在一个特定的个体 $c$ 满足性质 $A$。

注意：$c$ 必须是之前未在推理中出现过的新名称。

规则3：全称量词引入（UG）

$\frac{A(c) \text{ 对任意 } c}{\forall x A(x)}$

含义：如果对任意个体 $c$ 都有 $A(c)$ 成立，则可以得出 $\forall x A(x)$。

条件：$c$ 必须是"任意的"，不能依赖于任何特殊假设。

规则4：存在量词引入（EG）

$\frac{A(c)}{\exists x A(x)}$

含义：如果某个特定个体 $c$ 满足性质 $A$，则存在某个 $x$ 满足性质 $A$。

7.2 推理规则总结

八、推理证明示例

8.1 示例1

前提：$\forall x(F(x) \to G(x))$，$\forall x F(x)$

结论：$\forall x G(x)$

证明：

8.2 示例2

前提：$\forall x(F(x) \to G(x))$，$\exists x F(x)$

结论：$\exists x G(x)$

证明：

8.3 证明中的注意事项

消去量词的顺序：

• 先消去存在量词（EI），再消去全称量词（UI）
• 这样可以确保 EI 引入的新名不会与 UI 中的个体冲突

EI 引入的新名：

• 必须是之前推理中未出现过的名称
• 代表"某个特定但未知的个体"

UG 的使用条件：

• 对任意个体 $c$ 都能推出 $A(c)$
• $c$ 不能依赖于前提中的特殊个体

本节小结

• 个体词：客体，分个体常元和个体变元
• 谓词：描述个体性质或关系，有一元、二元、$n$ 元之分
• 谓词填式：谓词字母后面填上客体所得的式子
• 命题函数：含有谓词变项的表达式，不是命题
• 命题是0元谓词
• 量词：全称量词 $\forall$（所有）、存在量词 $\exists$（存在）
• 符号化规律：全称用蕴含 $\forall x(F(x) \to G(x))$，存在用合取 $\exists x(F(x) \wedge G(x))$
• 特性谓词：没有给定个体域时，引入特性谓词限制变元范围
• 辖域：量词约束的范围
• 约束变元与自由变元：在量词辖域内受约束的变元 vs 不受约束的变元
• 换名规则：改变约束变元名称不影响公式
• 量词否定转移：$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$，$\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$
• 分配律：$\forall$ 对 $\wedge$ 分配，$\exists$ 对 $\vee$ 分配
• 双量词顺序：全称和存在量词的顺序不能随意改变
• 消去量词：有限个体域时，$\forall$ 转合取，$\exists$ 转析取
• 前束范式：量词全在前面，后面是不含量词的公式
• 推理规则：UI（全称消去）、EI（存在消去）、UG（全称引入）、EG（存在引入）

关键术语速查

练习题

练习1：谓词符号化

题目：将下列命题符号化。

(1) 没有不犯错误的人。

(2) 尽管有人聪明，但未必所有人都聪明。

(3) 每个人都有且仅有一个最好的朋友。

解：

设 $F(x)$：$x$ 是人，$G(x)$：$x$ 犯错误，$H(x)$：$x$ 聪明，$B(x, y)$：$y$ 是 $x$ 最好的朋友。

(1) “没有不犯错误的人” = “不存在不犯错误的人”

$\neg \exists x(F(x) \wedge \neg G(x)) \Leftrightarrow \forall x(F(x) \to G(x))$

(2) “有人聪明” ∧ “并非所有人都聪明”

$\exists x(F(x) \wedge H(x)) \wedge \neg \forall x(F(x) \to H(x))$

$\Leftrightarrow \exists x(F(x) \wedge H(x)) \wedge \exists x(F(x) \wedge \neg H(x))$

(3) “每个人都有最好的朋友” ∧ “每个人最好的朋友唯一”

$\forall x(F(x) \to \exists y(B(x, y) \wedge \forall z(B(x, z) \to z = y)))$

练习2：辖域与变元判断

题目：指出下列公式中各变元的约束出现和自由出现。

$\forall x(F(x, y) \to \exists y G(x, y, z))$

解：

• $x$：在 $F(x, y)$ 中约束出现（被 $\forall x$ 约束），在 $G(x, y, z)$ 中约束出现（被 $\forall x$ 约束）
• $y$：在 $F(x, y)$ 中自由出现（不在 $\forall x$ 的辖域内对 $y$ 的约束），在 $G(x, y, z)$ 中约束出现（被 $\exists y$ 约束）
• $z$：自由出现（不在任何量词的辖域内）

练习3：前束范式

题目：将公式 $\forall x F(x) \to \exists x G(x)$ 化为前束范式。

解：

$\forall x F(x) \to \exists x G(x)$

$\Leftrightarrow \neg \forall x F(x) \vee \exists x G(x)$（消除 $\to$）

$\Leftrightarrow \exists x \neg F(x) \vee \exists x G(x)$（量词否定转移）

$\Leftrightarrow \exists x \neg F(x) \vee \exists y G(y)$（换名，使约束变元不同名）

$\Leftrightarrow \exists x(\neg F(x) \vee \exists y G(y))$（辖域扩张）

$\Leftrightarrow \exists x \exists y(\neg F(x) \vee G(y))$（辖域扩张）

前束范式为：$\exists x \exists y(\neg F(x) \vee G(y))$

练习4：前束范式（进阶）

题目：将公式 $(\forall x F(x) \vee \exists y G(y)) \to \exists z H(z)$ 化为前束范式。

解：

$(\forall x F(x) \vee \exists y G(y)) \to \exists z H(z)$

$\Leftrightarrow \neg(\forall x F(x) \vee \exists y G(y)) \vee \exists z H(z)$（消除 $\to$）

$\Leftrightarrow (\neg \forall x F(x) \wedge \neg \exists y G(y)) \vee \exists z H(z)$（德摩根律）

$\Leftrightarrow (\exists x \neg F(x) \wedge \forall y \neg G(y)) \vee \exists z H(z)$（量词否定转移）

$\Leftrightarrow \exists x(\neg F(x) \wedge \forall y \neg G(y)) \vee \exists z H(z)$（辖域扩张）

$\Leftrightarrow \exists x \forall y(\neg F(x) \wedge \neg G(y)) \vee \exists z H(z)$（辖域扩张）

$\Leftrightarrow \exists x \forall y \exists z((\neg F(x) \wedge \neg G(y)) \vee H(z))$（辖域扩张）

前束范式为：$\exists x \forall y \exists z((\neg F(x) \wedge \neg G(y)) \vee H(z))$

练习5：谓词逻辑推理

题目：前提：$\forall x(F(x) \to G(x))$，$\exists x F(x)$。结论：$\exists x G(x)$。证明结论成立。

证明：

练习6：谓词逻辑推理（CP规则）

题目：前提：$\forall x(F(x) \to G(x))$，$\forall x(G(x) \to H(x))$。结论：$\forall x(F(x) \to H(x))$。证明结论成立。

证明（使用 CP 规则）：

常见考点

1. 命题符号化：根据自然语言描述，正确使用量词和联结词
2. 辖域与变元判断：判断变元的约束出现和自由出现
3. 量词否定转移：$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$
4. 分配律：记住哪些分配成立，哪些不成立
5. 前束范式：将公式化为前束范式
6. 消去量词：有限个体域下将量词公式转化为命题公式
7. 推理证明：正确使用 UI、EI、UG、EG 四条规则进行形式证明