谓词逻辑与量词

上一章里，条件命题 $P\to Q$ 已经让我们能讨论“如果……那么……”。可一进入真正的数学证明，只靠命题字母很快就不够用了。我们想说的通常不是一条孤零零的命题，而是：每个偶数都有某种性质，至少有一个对象满足某个条件，或者对每个输入都能找到一个与它配合的输出。

这里最容易出错的地方，不是忘记量词符号怎么写，而是没有看见句子里隐藏的选择顺序。比如“每个学生都选了一门课”和“有一门课被每个学生选择”，词几乎一样，数学要求却完全不同。前一句允许每个人选自己的课，后一句要求找到一门大家共同选择的课。

谓词逻辑要做的，就是把对象、性质、范围和选择顺序拆开。我们会一步步看清：一个带变量的句子何时才有真值，量词管理哪一段公式，否定为什么会让量词互换，以及“存在唯一”究竟比“存在”多证明了什么。

命题留下的空位：谓词

先看两句话：

• “4 是偶数”已经有确定真值，它是命题。
• “$x$ 是偶数”还缺一个对象，暂时不能判断真假。

第二句话就是谓词。我们可以给它起名：

把 $x=4$ 代进去，$E(4)$ 是真命题；把 $x=5$ 代进去，$E(5)$ 是假命题。谓词像一个带插槽的句子，变量填进插槽，句子才变成命题。

一元谓词说性质，多元谓词说关系

只带一个变量的谓词常用来描述对象的性质。例如：

带两个变量的谓词常用来描述两个对象之间的关系。例如：

这里 $a\mid b$ 表示“$a$ 整除 $b$”。于是 $D(3,12)$ 为真，$D(5,12)$ 为假。

三个变量也没有本质区别。例如：

$B(2,3,5)$ 为真，而 $B(2,3,6)$ 为假。变量个数告诉我们这个性质或关系需要几个对象才能检查。

谓词不是普通数值函数

谓词记号 $P(x)$ 很像函数记号 $f(x)$，但输出类型不同。若 $f(x)=x^2+1$，那么 $f(3)=10$，输出是一个数；若 表示“ 是质数”，那么 的输出是真， 的输出是假。

可以把谓词理解成一种只输出“真”或“假”的判断规则。后面讨论集合时，我们还会看到另一种等价视角：谓词会从论域中筛出所有让它为真的对象。

先说范围：论域决定一句话在谈什么

“每个 $x$ 都满足 $x^2\ge 0$”听起来很熟，但它其实省略了一件事：$x$ 从哪里取值？如果 $x$ 是实数，这句话为真；如果允许 $x$ 是复数，符号 $\ge$ 在通常意义下就没有定义。

变量允许取值的集合叫作论域，也叫讨论域。论域可以是整数集 $\mathbb Z$、实数集 $\mathbb R$、某个班级的学生、某张图的顶点，或者一张数据表里的记录。

同一个谓词换了论域，全称命题可能改变真假。令

在 $D_1=\{-2,-1,0,1,2\}$ 中，每个对象都满足 $P$；在 $D_2=\{1,2,3,4,5\}$ 中，、、 都不满足 。

两种说明论域的方法

第一种方法是在文字中先约定：“以下变量都在整数范围内取值。”之后写 $\forall x\,P(x)$ 时，读者就知道 $x$ 的范围是 $\mathbb Z$。

第二种方法是把范围写在量词旁边：

这种写法很直观，但它其实是一种受限量词的缩写。若大论域是 $U$，而 $A\subseteq U$，那么：

注意这两个展开式的连接词不同。全称句的意思是“只要 $x$ 属于 $A$，它就满足 $P$”，所以用蕴含；存在句要找到同一个 $x$，让“$x$ 属于 $A$”和“$P(x)$”同时成立，所以用合取。

空范围再次遇见空真

数学里通常约定总论域非空。但受限量词里的集合 $A$ 仍然可能是空集。

如果 $A=\varnothing$，那么 $\forall x\in A\,P(x)$ 为真，因为不存在一个 $A$ 中的对象能充当反例。它展开后是 $\forall x(x\in A\to P(x))$：没有对象满足前件 ，每个条件命题都空真。

相反，$\exists x\in A\,P(x)$ 为假，因为空集里根本拿不出见证。这正好把上一章的条件命题接到了量词语言上。

自由变量、绑定变量与作用域

量词不只是放在公式前面的符号，它会管理变量。被量词管理的变量叫绑定变量；尚未被量词管理的变量叫自由变量。

在

中，$x$ 和 $y$ 都是自由变量。它表示一个二元谓词。

在

中，$x$ 被 $\forall x$ 绑定，$y$ 仍然自由。整个式子还不是一句封闭命题，它仍然依赖 $y$。更准确地说，它现在是关于 $y$ 的一元谓词：“每个 $x$ 都与这个 $y$ 满足关系 $$。”

再加上一个量词：

两个变量都被绑定，公式不再留下空位，这时它才是一句能够判断真假的封闭公式。

量词只管理自己的作用域

看这个式子：

括号内 $P(x,y)$ 里的 $x$ 被绑定，$y$ 自由；括号外 $Q(x)$ 里的 $x$ 也是自由的。相同字母出现在同一个公式里，不代表它们一定受同一个量词管理。

这也是为什么复杂公式要认真加括号。括号不是排版装饰，它在告诉读者量词的管辖范围到哪里结束。

绑定变量可以改名，但不能捕获自由变量

绑定变量像程序里的局部变量。只要新名字没有和别的变量冲突，改名不会改变含义：

但不能把它随便改成 $y$：

这个新公式把原本自由的 $y$ 也一起绑定了，意思已经改变。这种错误叫变量捕获。实际写证明时，如果同一个字母在不同作用域里反复出现，最稳妥的做法是先换成彼此不同的名字，再继续推导。

全称与存在：一个怕反例，一个要见证

全称量词 $\forall$ 读作“对所有”“任意”或“每一个”。

它要求论域 $D$ 中每个对象都让 $P(x)$ 为真。

存在量词 $\exists$ 读作“存在”“有一个”或“至少有一个”。

它只要求论域中至少有一个对象让 $P(x)$ 为真，并没有说满足者只有一个。

证明和推翻的动作刚好相反

要证明 $\exists x\,P(x)$，拿出一个具体对象 $a$ 并验证 $P(a)$ 即可。这个 $a$ 叫作见证。

要推翻 $\forall x\,P(x)$，拿出一个具体对象 $b$ 并验证 $\neg P(b)$ 即可。这个 $b$ 叫作反例。

但另两个方向不能偷懒：证明全称命题时，检查几个例子不够；推翻存在命题时，排除几个候选也不够。面对无限论域，更不可能靠枚举完成。

比如要证明“每个偶整数的平方都能被 4 整除”，思考过程应当是：先任取一个偶整数 $n$。因为它是偶数，可以写成 $n=2k$，其中 $k\in\mathbb Z$。于是

因此 $4\mid n^2$。这里的“任取”很关键：我们没有挑一个特别好算的偶数，而是让 $n$ 代表任何可能的偶整数。

一个谓词也可以用量词定义

“$n$ 是偶数”本身可以写成：

这里 $k$ 被存在量词绑定，而 $n$ 保持自由，所以整个公式仍是关于 $n$ 的谓词。代入 $n=10$ 时，$k=5$ 是见证；代入 $n=11$ 时，不存在整数 让 。

整除关系也可以这样定义：

量词并不只出现在定理陈述里，它经常藏在最基本的数学定义中。

限定对象时，蕴含还是合取

中文句子翻成公式时，最常见的错误之一，是量词选对了，连接词却选错了。

“所有 A 都是 B”用蕴含

令 $A(x)$ 表示“$x$ 是偶数”，$B(x)$ 表示“$x$ 的平方能被 4 整除”，总论域是整数。

“所有偶数的平方都能被 4 整除”应写成：

它说的是：任取整数 $x$，如果它是偶数，那么它满足后面的性质。奇数不属于这句话真正要检查的对象，因此遇到奇数时前件为假，条件命题自动为真。

若误写成

就变成“每个整数既是偶数，平方又能被 4 整除”。它额外要求所有整数都是偶数，明显比原句强得多。

“存在 A 是 B”用合取

“存在一个偶质数”应写成：

我们要找到同一个 $x$，它既是偶数又是质数，数字 2 就是见证。

若误写成

事情就会变得荒唐：随便找一个奇数，前件 $A(x)$ 为假，整个蕴含便为真。这个公式几乎没有表达出“偶质数”的要求。

“只有 A 才是 B”要盯住箭头方向

“只有注册用户才能下载”可以改写成：“如果某人能下载，那么他是注册用户。”若 $D(x)$ 表示“$x$ 能下载”，$R(x)$ 表示“$x$ 是注册用户”，公式是：

“只有 A 才 B”给的是 $B\to A$，不是 $A\to B$。注册可能只是下载的必要条件，并不保证每个注册用户都一定下载过文件。

多重量词：顺序记录了依赖关系

两个量词放在一起时，不要一口气把公式念完。按从左到右的顺序做选择，意思会清楚得多。

读法是：先任意给定一个 $x$，然后可以根据这个 $x$ 选择一个合适的 $y$。不同的 $x$ 可以配不同的 $y$。

读法是：先选定一个固定的 $y$，然后它必须对每个 $x$ 都适用。这个 $y$ 不能看到 $x$ 后再改变。

用整数例子看见“依赖”

令变量都在整数中取值，$R(x,y)$ 表示 $y>x$。

这是真的。先给我任意整数 $x$，我都可以选 $y=x+1$。注意 $y$ 的选法依赖 $x$。

交换量词：

这要求先找一个固定整数 $y$，让它大于所有整数。无论候选 $y$ 是多少，取 $x=y$ 就得到 $y>y$，所以它是假的。

这个例子还说明一个方向关系：

如果真有一个共同的 $y$ 服务所有 $x$，当然也可以在每次需要时都选它。但反方向通常不成立：每个 $x$ 各有一个合适的 $y$，并不保证这些见证能合并成同一个对象。

同类量词可以交换，异类量词通常不能

下面两式等价：

它们都要求所有有序对都满足 $R$。两个存在量词也可以交换：

但 $\forall x\exists y$ 与 $\exists y\forall x$ 一般不能交换。看到不同类量词相邻时，就问自己：“里面那个见证能不能随着外面的对象改变？”

三个量词仍按同一个办法读

假设 $S(s,c,t)$ 表示“学生 $s$ 在时间 $t$ 学习课程 $c$”。

意思是每名学生都能找到一门课程和一个时间进行学习；课程和时间都可以随学生变化。

而

要求存在同一门课程、同一个时间，让所有学生都在那时学习它。量词越多，越不能只看符号数量，必须追踪每个选择依赖谁。

否定量词：把失败条件说准确

“不是所有学生都交了作业”不等于“所有学生都没交作业”。前一句只说至少有一名学生没交；后一句说一个交作业的人都没有。

这两个中文句子之间的距离，正是量词否定要处理的东西。

否定穿过一个量词时，$\forall$ 与 $\exists$ 互换，同时否定继续向谓词内部移动。

为什么量词会互换

$\forall x\,P(x)$ 要求每个对象都通过。要让它失败，只需找到一个没通过的对象，所以否定后变成 $\exists x\,\neg P(x)$。

$\exists x\,P(x)$ 只要一个见证就成功。要让它失败，就必须让每个对象都不满足 $P$，所以否定后变成 $\forall x\,\neg P(x)$。

这不是需要死记的符号戏法，而是在精确描述原命题“失败时会发生什么”。

多重量词逐层翻转

否定

时，不要跳步。先给整个公式加否定：

否定穿过 $\forall x$：

再穿过 $\exists y$：

读回中文就是：存在一个 $x$，它和任何 $y$ 都不满足关系 $R$。原句说“每个 $x$ 都能找到伙伴”，否定句则说“至少有一个 $x$，谁也配不上”。

受限全称句的否定还会改变连接词

“每个偶整数的平方都能被 4 整除”写成：

其中 $M(n)$ 表示 $4\mid n^2$。否定它：

上一章知道 $\neg(P\to Q)\equiv P\land\neg Q$，于是得到：

也就是“存在一个偶整数，它的平方不能被 4 整除”。这正是原全称命题所害怕的反例形状。

唯一存在：先找到，再排除第二个

$\exists x\,P(x)$ 只保证“至少一个”。若要说“恰好一个”，常写：

感叹号不是强调语气，它表示唯一存在。这个记号可以展开成普通的全称和存在量词：

外层先找一个满足 $P$ 的 $x$；内层再说，只要 $y$ 也满足 $P$，它就必须与 $x$ 是同一个对象。

唯一性也可写成“任意两个都相等”

另一种常见展开是：

前半句证明至少有一个，后半句证明至多有一个。两部分合起来才是恰好一个。

这个拆法直接给出了证明模板：

例题：线性方程有唯一解

题目：在实数范围内，证明存在唯一的 $x$ 使 $2x+3=11$。

“我只找到一个”还不叫唯一性

方程 $x^2=1$ 中，先找到 $x=1$ 只能证明存在。$x=-1$ 也是解，所以唯一存在为假。

唯一存在失败有两种完全不同的原因：一个满足者都没有，或者有至少两个不同满足者。它的否定可以写成：

第一部分说“零个”，第二部分说“至少两个”。

把多元谓词看成关系表

若 $T(s,c)$ 表示“学生 $s$ 选择课程 $c$”，可以把它画成一张表：行是学生，列是课程，蓝点表示该学生选择了该课程。

现在读两个公式：

外层先固定学生 $s$，因此要逐行检查；内层只要求存在一门课，所以每行至少一个蓝点即可。

外层先选课程 $c$，因此要找一列；内层要求每名学生都选它，所以这一整列必须全是蓝点。

这种关系表不只是帮助画图。数据库里的“找出至少选过一门课的学生”带有存在量词；“找出修完所有必修课的学生”带有全称量词。程序写法可能是查询、循环或集合运算，底层判断仍然是同一套逻辑。

从中文翻译到公式：先拆句，再写符号

一看到“所有”就立刻写 $\forall$，很容易把论域、条件或量词顺序漏掉。更稳的做法是先把句子拆成几个问题。

四种句型的对照

令 $A(x)$ 表示“$x$ 是 A 类对象”，$B(x)$ 表示“$x$ 有性质 B”。在同一总论域中：

第三句还等价于 $\forall x(A(x)\to\neg B(x))$。把两个版本互相转换，是检查连接词是否用对的好办法。

例题：每名学生都有自己提交的作业

令 $S$ 为学生集合，$H$ 为作业集合，$T(s,h)$ 表示“学生 $s$ 提交了作业 $h$”。句子“每名学生至少提交了一份作业”写成：

思考顺序是：先给一名任意学生，再为这名学生找一份作业。不同学生可以提交不同作业。

句子“有一份作业被每名学生提交”则写成：

这里必须先固定同一份作业。若中文原句是“所有学生都提交了某份作业”，它本身可能含糊，正式写作时应主动说明究竟是哪一种意思，而不是让符号替我们猜。

有效推理与反模型

谓词公式的真假依赖论域和谓词解释。比如 $\forall x\exists y\,(y>x)$ 在整数中为真，但如果论域只有一个对象，且 $>$ 被解释成“严格大于”，它就为假。

有些推理不管论域里的对象是什么、谓词具体表示什么都成立。例如：

为什么？假设前件为真，就有一个固定对象 $y_0$，对每个 $x$ 都满足 $R(x,y_0)$。那么任意给出一个 $x$，我们都可以把同一个 当作它的见证，所以后件为真。

反方向

并不总成立。要推翻“它永远成立”，不需要检查所有可能解释，只要给出一个反模型：取论域为整数，让 $R(x,y)$ 表示 $y>x$。前件为真，因为可取 $y=x+1$；后件为假，因为不存在大于所有整数的固定整数。

这个方法以后会反复出现：要推翻全称声称，找一个反例；要推翻“公式在所有解释下都成立”，找一个论域和谓词解释组成的反模型。

常见误区：问题究竟错在哪一步

把“并非所有”写成“所有都不”

错误写法：

左边只需要一个反例，右边要求每个对象都是反例。正确式子是 $\exists x\neg P(x)$。

把“至少一个”当成“只有一个”

$\exists xP(x)$ 允许一个、两个甚至很多个见证。只有原句明确说“恰好一个”“唯一”时，才使用 $\exists!$。

在存在句中使用蕴含

$\exists x(A(x)\to B(x))$ 可以被任何不满足 $A$ 的对象轻易见证，通常不能表达“存在一个 A 是 B”。后者应使用 $\exists x(A(x)\land B(x))$。

看见两个量词却不记录选择顺序

$\forall x\exists y$ 允许 $y$ 依赖 $x$；$\exists y\forall x$ 要求 $y$ 先固定。把量词交换不是排版调整，而是改变了谁能看到谁之后再作选择。

同一个字母跨越多个作用域

在复杂公式里反复写 $x$，可能让自由变量被误绑定，也可能让两个互不相关的局部变量看起来像同一个对象。先把绑定变量改成互不冲突的新名字，通常比盯着原式硬想更安全。

用几个例子“证明”全称命题

检查 $2,4,6$ 都满足某性质，只能提供支持直觉，不能证明所有偶数都满足。真正的全称证明必须从任意对象出发，用定义或已知事实覆盖整个论域。

从谓词走向集合

固定论域 $D$ 后，每个一元谓词 $P(x)$ 都会挑出一批使它为真的对象：

这个 $A$ 就是谓词 $P$ 的真值集合。反过来，给定一个集合 $A\subseteq D$，也可以定义谓词：

于是量词可以直接用集合大小来理解：

量词和集合其实在描述同一件事：谓词告诉我们谁符合条件，集合把所有符合条件的对象收在一起。下一步进入集合语言时，元素、子集、交集和补集就会把这套判断变成可操作的对象。

练习：先说思路，再看答案

练习一：自由变量与绑定变量

在公式

中，哪些变量自由，哪些变量绑定？整个公式是不是命题？

练习二：翻译限定对象

总论域为整数。令 $E(n)$ 表示“$n$ 是偶数”，$P(n)$ 表示“$n$ 是正数”。翻译“每个正偶数都大于 1”。

练习三：否定多重量词

否定下面的公式，并把结果读成中文：

练习四：判断量词顺序

论域为实数。判断下面两个公式的真假：

练习五：唯一存在

在实数范围内，把“方程 $x^2-2x+1=0$ 有唯一解”写成不使用 $\exists!$ 的公式，并说明证明分哪两步。

练习六：给出反模型

说明下面的推理为什么不总成立：

存在性：取 $x=1$，代入得到 $1-2+1=0$。

唯一性：若 $P(y)$ 成立，则 $(y-1)^2=0$，所以 $y=1$。因此任何解都等于已找到的解。

后件为假：它要求存在一个固定整数 $y$，同时等于每个整数 $x$ 加 1。取两个不同的 $x$ 就会要求同一个 $y$ 等于两个不同的数。因此这个解释构成反模型。