离散数学 1 第 3 章：谓词概念——量词翻译与变元约束

命题逻辑把原子命题当成不可再分的黑盒，于是"所有人都会死"和"苏格拉底是人"推不出"苏格拉底会死"——因为盒子里面装着什么，它根本看不见。谓词逻辑就是把盒子打开：把一句话拆成个体词 + 谓词 + 量词，让"所有""存在"这类结构变成可运算的符号。这一章的难点集中在两处：特性谓词该配 → 还是配 ∧，以及辖域到哪里结束。这两处一错，后面第 4 章的前束范式就没有干净的前提。

一、个体词与谓词

个体词是研究对象。表示具体对象的叫个体常项，记 a、b、c；表示抽象对象的叫个体变项，记 x、y、z。个体变项的取值range叫个体域（论域）D，通常约定 D 非空。

谓词刻画个体的性质或个体之间的关系，记 P(x)、Q(x,y)。谓词里个体词的个数叫元数：P(x) 是一元谓词，表示"x 是素数"；L(x,y) 是二元谓词，表示"x 小于 y"。

三条必须分清的性质：

• n 元谓词本身不是命题，它是"命题函数"。P(x) 的真值随 x 变，谈不上真假。
• 只有当所有个体词都换成常项（P(3)），或全部变元都被量词约束（∀xP(x)），才成为命题。
• 0 元谓词就是命题，这是命题逻辑被谓词逻辑包含的接口。

二、全称量词与存在量词

• 全称量词 ∀x："对所有 x"。∀xP(x) 为真，当且仅当论域中每一个个体代入 P 都为真。
• 存在量词 ∃x："存在 x"。∃xP(x) 为真，当且仅当论域中至少有一个个体使 P 为真。

量词的真值依赖论域，这一点常被忽略。∀x(x>0) 在正整数集上为真，在整数集上为假（0 不大于 0），在实数集上也为假。题目若不给论域，默认全总个体域，此时凡涉及"人""数"这类范围，必须用特性谓词把范围写进公式里。

三、翻译：全称配 →，存在配 ∧

这是全章最容易丢分的一条规则。设 M(x) 表示"x 是人"，D(x) 表示"x 会死"，C(x) 表示"x 聪明"：

自然语言	正确符号化	若写错会怎样
所有人都会死	∀x(M(x)→D(x))	∀x(M(x)∧D(x)) 断言"论域里每个个体都是人且会死"，论域含狗时即为假
有的人会死	∃x(M(x)∧D(x))	∃x(M(x)→D(x)) 只要有一个非人个体就为真，等于废话
没有人不犯错误	¬∃x(M(x)∧¬F(x))，即 ∀x(M(x)→F(x))	漏掉内层 ¬ 就变成"没有人犯错误"
所有偶数都能被 2 整除	∀x(E(x)→D(x))	同第一行
存在既是奇数又是素数的数	∃x(O(x)∧P(x))	用 → 则会因为"不是奇数"的个体而意外为真

原因很实在：∀ 要求"对每一个个体都成立"，如果论域里混进了不是人的东西，就得先用 M(x)→… 把它"豁免"掉；∃ 要求"找一个真的"，那就必须 M(x)∧… 同时成立才算数。一句话记住：全称管范围用蕴含，存在管范围用合取。

四、约束变元与自由变元

量词的辖域是它后面紧跟的那个公式；若后面带括号，辖域就是括号内的部分。在辖域内、与量词的指导变元同名的变元出现，叫约束出现；不在任何量词辖域内的变元出现，叫自由出现。

两个必看的例子：

• ∀x(P(x)→Q(y))：x 的所有出现都在 ∀x 的辖域内，是约束变元；y 不在，是自由变元。
• ∀xP(x)∧Q(x)：第一个 x 约束，第二个 x 自由。因为 ∀x 的辖域只到 P(x)，∧ 之后的 Q(x) 不在其中。这是最经典的陷阱，看到量词后面没括号就要立刻警惕。

不含自由变元的公式叫闭式。只有闭式在给定解释下才有确定的真值；含自由变元的公式只是命题函数。

两条改名/替换规则要分清：

• 换名规则（约束变元改名）：把某个量词的指导变元及其辖域内所有同名变元一起换成新名。要求新名在该辖域内不被其他量词约束，也不与任何自由变元同名。
• 代入规则（自由变元代入）：把自由变元 x 的每处自由出现都换成项 t。要求 t 对 x 可代入——即 t 中出现的变元不会被 x 所在位置的量词"捕获"。

五、解释：真值只在解释下才有

一个解释 I 由四样东西组成：非空论域 D；每个个体常项指派 D 中一个元素；每个 n 元函数符号指派 D 上的一个 n 元函数；每个 n 元谓词符号指派 D 上的一个 n 元关系。

例：公式 ∀x∃y L(x,y)，取 D = {2,3}，L 解释为"小于"。检查：x=2 时 y 可取 3，成立；x=3 时找不到比 3 大的元素，失败。所以该公式在此解释下为假。若取 D 为正整数集，同一公式为真。

同一符号串在不同解释下真值不同，这正是谓词逻辑必须谈"解释"的原因。在所有解释下都真的公式叫逻辑有效式（永真式），如 ∀xP(x)→∃xP(x)——它的有效性依赖 D 非空这一约定；若允许空论域，∀xP(x) 空真而 ∃xP(x) 为假，蕴含就垮了。

顺带说清量词的顺序，这是翻译题的第二个失分点：∀x∃y 与 ∃y∀x 不等值。∀x∃yL(x,y) 表示"每个数都存在比它大的数"，在整数集上为真；∃y∀xL(x,y) 表示"存在一个数比所有数都大"，为假。存在量词在外、全称在内是最强的断言——∀∃ 只要求逐个找到配对的对象，∃∀ 要求同一个对象通吃全场。所以"每个人都有母亲"要写 ∀x∃yM(y,x)，写成 ∃y∀xM(y,x) 就变成了"有一个人是所有人的母亲"。

易错点

1. ∀xP(x)∧Q(x) 里的第二个 x 是自由的，"所有 x 都 P，并且 x 是 Q"和"对所有 x，P 且 Q"完全不是一回事。
2. 全称配 →、存在配 ∧，写成 ∀x(M(x)∧D(x)) 是最常见的错误，语义上等于"世上只有人"。
3. 换名只能换约束变元，代入只能代自由变元，两者不能混用；换名后的新名不能已被占用。
4. 谓词公式不指明论域和解释就没有真值，答题时不要直接说"这个公式是真的"。

这一章在整门课里的位置

本章把第 1 章的原子命题拆开，但联结词一个没改，所以第 2 章的等值定律在这里仍然全部可用。第 4 章会在本章的约束/自由概念上做量词否定与辖域变换，进而求前束范式；第 5 章讲关系的定义时，"R 是 A 上的二元关系"本身就是二元谓词的一次具体化。

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