离散数学 1 第 4 章：谓词等价——量词分配与前束范式

第 3 章解决了"怎么把话写进符号"，这一章解决"写进去以后怎么变形"。核心只有两个动作：把否定推到量词里面（量词翻转）和把量词提到公式外面（辖域扩张）。所有前束范式题都是这两个动作的反复组合。这一章最大的坑是量词分配律——四条里只有两条是双向等值，另外两条只能单向推，反例必须能随手举出来，否则考试写成 ⇔ 就是硬伤。

一、谓词公式的等值

定义与命题逻辑一致：若 A↔B 在任何解释下都为真（逻辑有效），称 A 与 B 等值，记 A⇔B。注意"任何解释"是比"任何赋值"强得多的要求——论域、常项、函数、谓词全部都要遍历。

有一条省力的合法性依据：代换实例。命题逻辑里的每一条等值式，把其中的命题变元统一替换成谓词公式，结果仍然等值。例如 A→B ⇔ ¬A∨B 里的 A、B 换成 ∀xP(x)、∃yQ(y) 依然成立。这意味着第 2 章那张定律表可以整张搬过来用，不必重新证明。

二、量词的否定：翻转 + 内移

两条基本式，是所有变形的地基：

¬∀xP(x) ⇔ ∃x¬P(x)，¬∃xP(x) ⇔ ∀x¬P(x)

口诀：否定穿过量词，量词翻转，¬ 落到谓词上。可以连用：¬∀x∃yR(x,y) ⇔ ∃x¬∃yR(x,y) ⇔ ∃x∀y¬R(x,y)，∀→∃、∃→∀ 全部翻转，顺序保持不变。

自然语言对照能帮助校验："不是所有人都及格"就是"有人不及格"，即 ¬∀xP(x) ⇔ ∃x¬P(x)；"没有人及格"是 ¬∃xP(x) ⇔ ∀x¬P(x)，即"所有人都不及格"。这两句中文的差别，正是 ∀ 与 ∃ 的差别。多层量词则一层一层往下剥，顺序保持不变：¬∀x∃y∀zR(x,y,z) ⇔ ∃x∀y∃z¬R(x,y,z)。这里容易错的是顺手把 ∃y∀z 调换了次序——否定只翻转量词，不重排量词。

三、辖域扩张与收缩

设 B 中不含 x 的自由出现（这条前提必须检查，否则一切免谈），则有：

等值式	说明
∀x(A(x)∨B) ⇔ ∀xA(x)∨B	量词可提出/收回
∀x(A(x)∧B) ⇔ ∀xA(x)∧B	同上
∃x(A(x)∨B) ⇔ ∃xA(x)∨B	同上
∃x(A(x)∧B) ⇔ ∃xA(x)∧B	同上
∀x(A(x)→B) ⇔ ∃xA(x)→B	前件上的量词要翻转
∃x(A(x)→B) ⇔ ∀xA(x)→B	同上
∀x(B→A(x)) ⇔ B→∀xA(x)	后件不翻转
∃x(B→A(x)) ⇔ B→∃xA(x)	后件不翻转

最后四行容易记错，原因是 A→B ⇔ ¬A∨B，位于前件的公式先被否定，¬∃x 变成 ∀x¬，量词自然翻转；位于后件的不经过否定，量词保持原样。

四、量词分配律：哪两条成立

这是本章必须背准的一张表：

公式	方向	判定
∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x)	双向	成立
∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨∃xB(x)	双向	成立
∀x(A(x)∨B(x)) ⇐ ∀xA(x)∨∀xB(x)	单向	反向不成立
∃x(A(x)∧B(x)) ⇒ ∃xA(x)∧∃xB(x)	单向	反向不成立

两个反例，论域都取整数集：

• 令 A(x)：x 是偶数，B(x)：x 是奇数。∀x(A(x)∨B(x)) 为真（每个整数非偶即奇），但 ∀xA(x) 与 ∀xB(x) 都假，故 ∀xA∨∀xB 为假。∀ 不能分配到 ∨。
• 同样取偶数/奇数。∃xA(x) 真、∃xB(x) 真，合取为真；但不存在既是偶数又是奇数的整数，∃x(A(x)∧B(x)) 为假。∃ 不能分配到 ∧。

记忆的支点是"全称管合取，存在管析取"——∀ 像一个大的 ∧，∃ 像一个大的 ∨，同种运算之间才能自由合并。这也解释了为什么第 3 章翻译时"全称配 →、存在配 ∧"：→ 拆开就是 ∨，正好和 ∧ 错位，所以必须换一种配法。

另外还有一个常用的单向式：∀x(A(x)→B(x)) ⇒ ∀xA(x)→∀xB(x)。

五、前束范式

前束范式指所有量词都位于公式最前面、每个量词的辖域都延伸到公式末尾、母式（量词串之后的部分）不含量词的公式，形如 Q₁x₁Q₂x₂…Qₙxₙ M。

求法四步，顺序不能乱：

1. 消去 → 和 ↔：用 A→B ⇔ ¬A∨B、A↔B ⇔ (A→B)∧(B→A)。
2. 否定内移：用德摩根律和量词否定式，把 ¬ 压到原子公式上。
3. 约束变元换名：让每个量词用不同的变元名，且不与自由变元重名。这一步是为了第 4 步的合法性——两个量词同名时，提取会改变约束关系。
4. 量词左移：反复用辖域扩张律把量词逐个提到最前。

例：求 ∀xP(x)→∃xQ(x) 的前束范式。

∀xP(x)→∃xQ(x)
⇔ ¬∀xP(x)∨∃xQ(x)          消去 →
⇔ ∃x¬P(x)∨∃xQ(x)          否定内移
⇔ ∃x¬P(x)∨∃yQ(y)          换名，避免同名冲突
⇔ ∃x(¬P(x)∨∃yQ(y))        ∃ 对 ∨ 的辖域扩张
⇔ ∃x∃y(¬P(x)∨Q(y))        再次提取

结果 ∃x∃y(¬P(x)∨Q(y)) 就是前束范式。注意第 3 步换名不可跳过：若直接把两个 ∃x 都提出，得到 ∃x(¬P(x)∨Q(x))，语义已经变了。

关于唯一性要说清：前束范式不唯一。同一公式的不同前束范式之间，母式可能差别很大，前束词（量词序列，如 ∃∀、∀∃∃）也可能不同。考试一般只要求给出一个正确结果，不要求最简。想检验自己写得对不对，与其反复变形，不如按第 3 章的办法给一个具体解释算真值，两边的结果必须一致——这是最省时间的自查手段。

六、谓词逻辑推理简介

命题逻辑的推理规则全部沿用，另外增加四条量词规则：

• US（全称实例化）：∀xA(x) ⇒ A(c)，c 为任意个体常项。
• UG（全称泛化）：若对任意 c 都能证 A(c)，则得 ∀xA(x)。
• ES（存在实例化）：∃xA(x) ⇒ A(c)，c 必须是此前从未出现过的新常项。
• EG（存在泛化）：A(c) ⇒ ∃xA(c)。

使用顺序有一条铁律：先做 ES，后做 US。因为 ES 要占用一个新常项，若先用 US 把某个 c 用掉了，ES 就无新名可用。

例：前提 ∀x(P(x)→Q(x))、∃xP(x)，证 ∃xQ(x)。

1. ∃xP(x)          P
2. P(c)            ES, 1        c 为新常项
3. ∀x(P(x)→Q(x))   P
4. P(c)→Q(c)       US, 3
5. Q(c)            T, 2,4
6. ∃xQ(x)          EG, 5

谓词推理的难点不在规则本身，而在"什么时候该实例化"。经验是：看到存在前提先做 ES，把它换成新常项；全称前提留到需要具体个体时再 US。 若两条都要用，顺序永远是 ES 在前、US 在后，否则新常项被占，链条立断。

易错点

1. ∀x(A∨B) 与 ∀xA∨∀xB 只是单向，写成 ⇔ 直接判错；反例用"偶数或奇数"最快。
2. ∃x(A∧B) 与 ∃xA∧∃xB 同理只是单向，反例同样是偶/奇。
3. 求前束范式跳过换名，两个同名量词提出后会改变约束关系，这是最隐蔽的错误。
4. 辖域扩张的前提"B 中不含 x 的自由出现"必须逐条核对，尤其 B 是复合公式时。
5. ES 用的常项必须是全新的，且要在 US 之前执行。

这一章在整门课里的位置

本章是第 2 章等值演算在谓词层的重演，也是第 3 章约束/自由概念的唯一用途所在——不掌握辖域，第 4 步就无法判断能不能提取。往后看，第 6 章证明关系性质时会大量使用"对任意 x 成立"这类量词语句，本章的否定式直接决定反证怎么写。

本文是《离散数学 1：数理逻辑与集合论》第 4 章的知识点摘要。完整板书与例题见 课程页；上一章 谓词概念，下一章 集合与关系。