1.3 量词与否定

量词的作用，是把开放句变成命题。在本课里，它们让我们可以说“对所有允许的对象”，或者“至少存在一个允许的对象”，而不需要把每一个情况都逐条写出来。

谓词与定义域

定义

谓词

谓词是含有一个或多个自由变量的陈述。只有当每个自由变量都已经被赋值，或者被量词绑定之后，它才会变成命题。

定义

定义域

定义域是变量允许取值的集合。

每次见到 ∀ 或 ∃，都要先问：变量可以在什么集合里取值？同一个形式，在不同定义域下可以有不同意思。

例如 $x^2 = 1$ 在自然数、整数、有理数和实数里，答案会不一样。如果没有说明定义域，陈述其实还不完整。

常见错误

不要漏掉定义域

∀x P(x) 如果不清楚 x 可以取哪些值，就不算完整。实际中，定义域通常会明示，或者由上下文默认。

全称量词与存在量词

定义

量词

∀x P(x) 表示对每一个允许的 x，P(x) 都真。

∃x P(x) 表示至少有一个允许的 x 使得 P(x) 真。

如果想用口语来读：

∀ 是“对所有”或“对每个”。
∃ 是“存在”。

句子要到量词加上去之后才算完成。所以 P(x) 本身不是命题，但 ∀x P(x) 和 ∃x P(x) 都是。

例题

把带量词的句子读成自然语言

设 P(x) 表示“x 可以被 2 整除”，定义域是整数。

那么 ∀x P(x) 就是：

“每个整数都可以被 2 整除。”

这句话是假的。相反，∃x P(x) 是：

“存在一个整数可以被 2 整除。”

这句话是真的，例如 $x = 2$ 。

解答

量词在做什么

否定量词

定理

量词否定

最基本的否定规则是：

¬∀x\,P(x) \equiv ∃x\,¬P(x)

¬∃x\,P(x) \equiv ∀x\,¬P(x)

读这两条规则时，要记住两件事：

外层量词要翻转。
内部谓词要否定。

就是这么简单。

例题

否定质数的定义

工作纸用以下方式定义 n 是质数：对每个自然数 d，如果 d 整除 n，那么 $d = 1$ 或 $d = n$ 。

符号写法是：

∀d ∈ N,\; d \mid n \to (d = 1 \lor d = n).

它的否定是：

∃d ∈ N \text{ 使得 } d \mid n \text{，而且 } d \neq 1 \text{ 并且 } d \neq n。

这正是“n 不是质数”的意思：存在一个非平凡除数。

解答

为什么这个否定正确

例题

否定一个学生陈述

设 Student(x) 表示“x 是学生”，Submitted(x) 表示“x 已提交表格”。

则

∃x\,(Student(x) \land Submitted(x))

表示至少有一个学生已提交表格。

它的否定是

∀x\,(\neg Student(x) \lor \neg Submitted(x)).

也就是说：每个允许的对象都至少缺少其中一个性质。

解答

读法

为什么量词次序很重要

量词次序是意思的一部分。

∀x ∃y P(x, y) 表示对每个 x，都可以找到一个可能不同的 y。

∃y ∀x P(x, y) 表示有同一个 y 对所有 x 都有效。

两者差别很大。第一句允许 y 依赖 x，第二句不允许。

例题

每本书有借阅者，不等于同一个人借完所有书

设 Book(b) 表示 b 是书，Borrows(x, b) 表示 x 借了 b。

∀b\,(Book(b) \to ∃x\,Borrows(x, b))

意思是每本书至少有一个借阅者。

∃x\,∀b\,(Book(b) \to Borrows(x, b))

意思是有一个人借完所有书。

第一句可以真，而第二句可以假。

解答

这个例子要记住什么

常见的错误形式化

常见错误

蕴含不等于合取

如果意思是“对每个学生，如果他有注册，那么他满足先修要求”，正确形式应该是

∀x\,((Student(x) \land Enrolls(x)) \to Prereq(x)).

如果写成纯粹 $Student(x) \land Enrolls(x)$ ，就会变成更强、而且完全不同的说法。

例题

把课程要求写成量词公式

设 Taken(x, m) 表示“学生 x 修过数学课 m”。 “每个学生至少修过一门数学课”可以写成

∀x\,(Student(x) \to ∃m\,(MathCourse(m) \land Taken(x, m))).

这个写法比压成一句模糊陈述更清楚。

解答

为什么内层必须有存在量词

快速检查

写出 `∀x P(x)` 的否定，并化简。

把外层量词翻转，再否定内部谓词。

解答

答案

快速检查

`∃x (x 是学生且 x 已提交表格)` 的否定是什么？

用德摩根律处理内部合取。

解答

答案

快速检查

`∀x∃y P(x,y)` 和 `∃y∀x P(x,y)`，哪个更强？

想想是否只需要一个 y 就能对所有 x 成立。

解答

答案

快速检查

把 $∀b(Book(b) → ∃x Borrows(x,b))$ 读成中文。

由外到内读量词。

解答

答案

嵌入式检查

用 stepper 练习在带量词的陈述和其否定之间来回转换。

边读边试

仔细否定一个带量词的陈述

互动步骤器会逐步显示量词否定的每一步。

例子

对每个实数 x，都有 x^2 >= 0。

1. 先从外层量词开始：“对每个 x”。

先读这一页

如果想先重温命题逻辑，请读 1.1 命题逻辑。

MATH1090：集合论

逻辑

集合与关系

由构造得到的数系

序与完备性

谓词与定义域

谓词

定义域

不要漏掉定义域

全称量词与存在量词

量词

把带量词的句子读成自然语言

量词在做什么

否定量词

量词否定

否定质数的定义

为什么这个否定正确

否定一个学生陈述

读法

为什么量词次序很重要

每本书有借阅者，不等于同一个人借完所有书

这个例子要记住什么

常见的错误形式化

蕴含不等于合取

把课程要求写成量词公式

为什么内层必须有存在量词

快速检查

写出 ∀x P(x) 的否定，并化简。

答案

∃x (x 是学生 且 x 已提交表格) 的否定是什么？

答案

∀x∃y P(x,y) 和 ∃y∀x P(x,y)，哪个更强？

答案

把 ∀b(Book(b)→∃xBorrows(x,b))∀b(Book(b) → ∃x Borrows(x,b))∀b(Book(b)→∃xBorrows(x,b)) 读成中文。

答案

嵌入式检查

仔细否定一个带量词的陈述

先读这一页

Section mastery checkpoint

先备知识

本单元重点词汇

本系列更多笔记

写出 `∀x P(x)` 的否定，并化简。

`∃x (x 是学生且 x 已提交表格)` 的否定是什么？

`∀x∃y P(x,y)` 和 `∃y∀x P(x,y)`，哪个更强？

把 $∀b(Book(b) → ∃x Borrows(x,b))$ 读成中文。