谓词逻辑与量词

命题逻辑能处理“今天下雨”“如果一个数能被 4 整除，那么它能被 2 整除”这类已经有真假的语句。进入证明以后，我们经常要说更细的事：某个对象有某种性质，所有对象都有某种性质，至少有一个对象有某种性质，或者恰好有一个对象有某种性质。

谓词逻辑就是为这类话准备的语言。它把“对象”“性质”“关系”和“范围”分开，让一句话可以被检查、被否定、被翻译，也可以被放进证明。

这一章的目标很朴素：看见“所有”“存在”“唯一存在”时，不靠语感猜，而是能写出清楚的量词表达式；看见量词表达式时，也能知道它到底要求检查什么。

从命题到谓词

命题是已经能判断真假的陈述。例如“4 是偶数”是真命题，“5 是偶数”是假命题。

谓词先保留一个空位。比如“$x$ 是偶数”还不能直接判断真假，因为 $x$ 还没有被指定。把 $x$ 换成 4，它变成真命题；把 $x$ 换成 5，它变成假命题。

我们常把谓词写成 $P(x)$、$Q(n)$、$R(x,y)$。这里的字母不是神秘缩写，只是给“某个性质”或“某个关系”起一个名字。

性质谓词与关系谓词

一个变量的谓词通常表达性质。例如：

两个或多个变量的谓词通常表达关系。例如：

如果指定 $x=3$、$y=12$，那么 $R(3,12)$ 是真命题；如果指定 $x=5$、$y=12$，那么 是假命题。

自由变量与绑定变量

在 $P(x)$ 中，$x$ 是自由变量。它还没有被量词管理，也没有被具体赋值。

在 $\forall x\,P(x)$ 中，$x$ 被全称量词绑定；在 $\exists x\,P(x)$ 中，$x$ 被存在量词绑定。绑定以后，整个式子不再依赖某个未说明的 $x$，而是在指定范围内说一句完整的话。

例如：

这句话只有在我们知道 $x$ 从哪里取值时才完整。如果 $x$ 在实数范围内取值，它是真的；如果 $x$ 在复数范围内取值，符号 $\ge$ 本身就需要重新解释。

论域先于判断

论域是变量允许取值的范围。它可以是整数、实数、某个班级的学生、某个网站的用户，也可以是一张数据表里的记录。

同一个谓词，换了论域，整句话可能改变真假。比如 $P(x): x < 3$。

如果论域是所有自然数，并且自然数从 1 开始，那么“每个 $x$ 都满足 $x < 3$”是假的，因为 3、4、5 都不满足。

如果论域是 $D=\{1,2\}$，同一句全称判断就是真的。

显式写出论域

有两种常见写法。

第一种是在句子前先说明论域。例如：“在整数范围内，令 $P(x)$ 表示 $x$ 是偶数。”后面再写 $\forall x\,P(x)$ 或 $\exists x\,P(x)$。

第二种是把论域条件写进公式。例如“每个偶整数的平方都能被 4 整除”可以写成：

其中 $E(x)$ 表示“$x$ 是偶数”，$M_4(x^2)$ 表示“$x^2$ 能被 4 整除”，论域是整数。

也可以写成：

这两种写法的核心一样：先把变量从哪里取值说清楚。

全称量词与存在量词

全称量词 $\forall$ 读作“对所有”或“任意”。存在量词 $\exists$ 读作“存在”或“至少有一个”。

表示论域中的每一个对象都满足 $P$。

表示论域中至少有一个对象满足 $P$。

见证与反例

要证明 $\exists x\,P(x)$ 为真，只要拿出一个对象 $a$，并说明 $P(a)$ 为真。这个 $a$ 叫作见证。

要证明 $\forall x\,P(x)$ 为假，只要拿出一个对象 $a$，并说明 $P(a)$ 为假。这个 $a$ 叫作反例。

这两个词很有用。它们把“存在”和“全称”的检查方式压缩成两句话：存在命题找见证，全称命题怕反例。

例题：翻译一个关于整数的句子

题目：把“每个偶整数的平方都能被 4 整除”写成谓词逻辑公式，并说明每个部分的含义。

存在句的连接词

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

这里用合取 $\land$，因为我们要找同一个 $x$，它既是偶数，又是质数。

如果误写成：

意思会变弱。只要找到一个不是偶数的 $x$，蕴含 $E(x)\to P(x)$ 就会为真，这不能表达“存在一个偶质数”。

量词否定

否定含量词的句子时，最稳的办法是先用中文理解它，再写公式。

“并非所有学生都交了作业”是什么意思？不是“所有学生都没交”，而是“至少有一个学生没交”。

“不存在学生交了作业”是什么意思？它才是“每个学生都没交”。

两条规则如下：

这就是量词版本的德摩根律。否定推进到里面时，$\forall$ 和 $\exists$ 要互换。

例题：否定一个双变量句子

题目：论域中有学生和课程。令 $F(s,c)$ 表示“学生 $s$ 完成了课程 $c$ 的项目”。否定下面的句子，并写成自然中文：

多重量词顺序

当一个句子里有两个变量，量词顺序常常决定意思。

看下面两句话：

第一句说：每个 $x$ 都可以找到一个适合它的 $y$。不同的 $x$ 可以对应不同的 $y$。

第二句说：存在一个同一个 $y$，它适合所有 $x$。这通常强得多。

一个整数例子

令论域为整数，令 $G(x,y)$ 表示 $y>x$。

公式

是真的。因为给定任意整数 $x$，都可以取 $y=x+1$。

公式

是假的。它要求存在一个整数 $y$，比所有整数 $x$ 都大。但整数没有最大数。只要取 $x=y$，就会得到 $y>y$，不可能为真。

日常语言里的歧义

“每个学生都选了一门课程”通常表达：

意思是每个学生至少有一门课。不同学生可以选不同课程。

“有一门课程被每个学生选择”表达：

它要求同一门课覆盖所有学生。两句话看起来只换了几个字，逻辑要求差很多。

唯一存在

存在量词 $\exists$ 表示“至少有一个”。如果想表达“恰好有一个”，要用唯一存在。

常见记号是：

它读作“存在唯一的 $x$ 使得 $P(x)$ 成立”。

严格写法可以拆成两部分：

等价于：

这句话先说存在一个满足 $P$ 的 $x$，再说任何满足 $P$ 的 $y$ 都必须等于这个 $x$。换成证明语言，就是先证明“有一个”，再证明“没有第二个”。

例题：证明一个线性方程有唯一解

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

用关系表读懂量词

多变量谓词可以看成一张关系表。行对应第一个变量，列对应第二个变量，某个格子为真，表示这两个对象之间有关系。

例如 $T(s,c)$ 表示“学生 $s$ 选择课程 $c$”。一张选课表就能直接读出很多量词句子。

关系表也能解释数据库查询里的量词直觉。“找出至少选过一门课的学生”就是存在查询；“找出选过所有必修课的学生”则要检查一组课程是否都被覆盖。真正写成程序时，形式可能是子查询、集合差或关系除法，但背后的逻辑仍然是 $\exists$ 和 $\forall$。

例题：从表格条件到量词

题目：令 $T(s,c)$ 表示“学生 $s$ 选择课程 $c$”。翻译下面两句话。

句子 A：每名学生至少选择一门课程。

句子 B：有一门课程被所有学生选择。

翻译含量词语句

翻译量词句子时，不要急着写符号。先把四件事说清楚：论域是什么，谓词怎么定义，量词顺序是什么，连接词用蕴含还是合取。

一个可复用的翻译流程

常见误区

小结与练习

本章的主线可以压成五句话。谓词是带变量的性质或关系；论域决定变量从哪里取值；全称量词检查每一个对象，存在量词寻找至少一个见证；量词否定时全称和存在互换；多重量词的顺序会改变对象之间的依赖关系。

下面的练习不追求计算量，重点是把中文、公式和检查方式对齐。

练习

1. 论域为整数。令 $E(x)$ 表示“$x$ 是偶数”，令 $P(x)$ 表示“$x$ 是质数”。把“存在一个偶质数”写成公式。

2. 否定下面的公式，并写成自然中文：

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

4. 在实数范围内，写出“方程 $x^2=0$ 有唯一解”的唯一存在表达式。

5. 令 $L(s,b)$ 表示“学生 $s$ 借阅过书 $b$”。分别翻译“每名学生都借阅过至少一本书”和“有一本书被每名学生借阅过”。

它的证明分两步：$x=0$ 是一个解；如果 $y^2=0$，那么 $y=0$，所以没有第二个不同的解。