2.3 谓词与量词

第 2.1 节介绍过开放语句 $x>4$。因为 $x$ 的值缺失，它还不是命题。现在，我们需要一种简洁方法来表示“不同对象可能具有或不具有某种性质”，并进一步对这些对象作出完整陈述。

谓词负责记录性质，量词负责说明选定论域中有多少对象必须满足该性质。

学完本节后，你将能够：

• 识别谓词及其论域；

• 使用反例与见证判断全称命题和存在命题；

• 正确否定带量词的命题；

• 解释为什么交换两个量词的顺序可能改变含义和真值。

谓词在代入对象后才变成真假确定的命题

谓词（predicate）是含有一个或多个变量的语句。把具体值代入全部变量后，它会变成命题。

令

记号 $P(x)$ 为谓词命名，同时表明它的真值依赖 $x$。代入之后得到命题：

计算谓词之前，必须先规定变量允许取值的集合，这个集合叫作论域（domain，也叫讨论域）。

若论域是

就只能在这六个值上检查 $P(x)$。改变论域可能改变带量词命题的真值。例如，“每个数都是正数”在 $\{1,2,3\}$ 上为真，在 $\{-1,1,2,3\}$ 上为假。

谓词不必讨论数字。若 $D$ 是设备集合，可以定义

表达式 $Online(d_2)$ 就是关于某台具体设备 $d_2$ 的命题。

全称量词检查每一个对象

全称量词（universal quantifier）记作 $\forall$，读作“对每个”或“对所有”。语句

表示“论域 $D$ 中每个 $x$ 都使 $P(x)$ 为真”。

令 $D=\{1,2,3,4\}$，并定义

逐个检查：

每一行都通过，因此 $\forall x\in D,\;P(x)$ 为真。

要说明全称命题为假，不需要永远检查下去，只要找到一个失败对象就够了。这个对象叫作反例（counterexample）。若论域改成 $D=\{1,2,3,4,7\}$，那么 $x=7$ 就是反例，因为 $P(7)$ 为假。

由此产生两种不同任务：

• 证明有限论域上的全称命题，需要检查每个对象；

• 推翻全称命题，只需给出一个反例。

存在量词只寻找一个见证

存在量词（existential quantifier）记作 $\exists$，读作“存在”或“至少有一个”。语句

表示“论域 $D$ 中至少有一个 $x$ 使 $P(x)$ 为真”。

让谓词为真的对象叫作见证（witness）。若 $D=\{1,2,3,4,7\}$，$P(x)$ 表示 $x>4$，那么 $7$ 就是见证。其他元素不必全部通过。

证明存在命题时，给出一个见证即可。推翻有限论域上的存在命题时，则必须说明每个候选对象都失败。

不要只背口号，可以把差异记成需要执行的动作：

边界情况：空论域

若 $D=\emptyset$，没有任何对象能够违反全称命题，所以 $\forall x\in D,\;P(x)$ 被视为真。同时，也没有对象能够充当存在命题的见证，所以 $\exists x\in D,\;P(x)$ 为假。

这与第 1 章解释 $\emptyset\subseteq A$ 时使用的是同一模式：不存在能够违反要求的元素。

观测站允许你同时改变谓词与论域。不要只看最后的真假标签，还要定位被高亮的对象：在 $\exists$ 命题中，它是让命题成立的见证；在为假的 $\forall$ 命题中，它是打破命题的反例。

按固定顺序翻译带量词的自然语言

自然语言经常把论域和谓词隐藏在句子中。可以分三步翻译：

1. 找出论域；

2. 用直白语言定义谓词；

3. 根据“每个”“有些”或“没有”选择量词。

假设 $S$ 是学生集合，并定义

那么

表示“每名学生都已提交”，而

表示“至少有一名学生已提交”。

“没有学生提交”表示不存在见证：

它也可以写成

两种写法含义相同。

否定量词会改变搜索方向

否定全称命题时，需要找到一个反例：

它表示：“并非每个对象都有性质 $P$”等价于“存在一个对象没有性质 $P$”。

否定存在命题时，必须让所有候选对象都失败：

这两条规则是德摩根律的量词版本。否定穿过量词时，要把 $\forall$ 改成 $\exists$，或把 $\exists$ 改成 $\forall$，然后再否定谓词。

常见错误是只否定谓词，却保留原量词。例如，“每个传感器都已启动”的否定并不是“每个传感器都未启动”，正确否定是“至少有一个传感器未启动”。当设备群中同时存在已启动和未启动传感器时，两句话的差异会非常明显。

含两个变量的谓词描述对象之间的配对关系

谓词可以依赖多个变量。令

同时给出 $k$、$r$ 后，$Unlocks(k,r)$ 就具有确定真值。有序对 $(k,r)$ 把这里的知识与第 1.3 节的笛卡尔积连接起来：所有可能的密钥—机器人配对构成笛卡尔积，其中为真的配对构成一个关系。

现在比较两条带量词的命题：

与

量词要从左向右读取。

第一条表示：

> 对每台机器人 $r$，都能找到某把密钥 $k$ 解锁它。

不同机器人可以使用不同密钥。

第二条表示：

> 存在同一把密钥 $k$，它能够解锁每台机器人 $r$。

现在必须由同一把密钥服务所有机器人，因此要求更强。

假设有三台机器人和三把密钥：$K_1$ 打开 $R_1$，$K_2$ 打开 $R_2$，$K_3$ 打开 $R_3$。每台机器人都有某把可用密钥，所以第一条命题为真；但没有一把密钥能打开全部三台机器人，所以第二条命题为假。量词顺序不能随意交换。

请直接绘制密钥—机器人关系，而不只是阅读表格。先制造“每台机器人都有钥匙，但不存在万能钥匙”的分布式方案，再填满某一整列，观察究竟哪条量词命题发生变化。

从逻辑命题走向数字决策

现在，我们已经能够写出精确命题、对命题取否定，并判断需要什么证据来证明或推翻它。第 2.4 节会回到本章最初的真与假，并把它们写成 $0$ 与 $1$。布尔代数将把逻辑联结词和真值表变成数字电路能够执行的计算规则。