1.3 量词与否定

动机

命题逻辑把完整句子当作一个不可分割的命题，但“所有人都会死”和“有一个人不喜欢奶酪”还需要说明对象及其性质。谓词逻辑加入变量、谓词和量词，使质数定义、先修要求、函数和关系中的对象及条件得以明确表达。可靠的方法是从外向内读：先确定定义域，再确定每个量词的作用域、连接词和见证的依赖关系。否定时也要由外向内，保留变量所受的每个条件。

“所有人都会死；某人是人；所以某人会死”可以写成 $\forall x\,(H(x)\to M(x))$ 、 $H(s)$ ，从而得到 $M(s)$ 。先把全称前提代入指定的 $s$ ，再使用蕴含。

定义

谓词与命题

谓词是其真值可能依赖一个或多个变量的公式。没有被量词控制的变量出现称为自由出现。给自由变量赋值，可以在该赋值下评价公式的真值，但不会消除自由变量。用量词绑定所有自由出现，才得到语法上封闭的句子。

定义

定义域与赋值

定义域是量词变量可以选取的集合。赋值为自由变量指定值。若定义域为整数， $P(x,y)$ 表示 $x=y$ ，赋值 $x=1$ 、 $y=2$ 使 $P(x,y)$ 为假。在 $\forall x\,P(x,y)$ 中， $x$ 被绑定而 $y$ 仍自由，所以公式在语法上仍然开放；赋值可以评价 $y$ ，但自由状态本身不预设真值一定改变。量词只在自己的作用域内控制变量；内层量词重用字母时，指的是内层绑定。

定义域是陈述的一部分。 $x^2=1$ 在自然数中有一个解，在整数、有理数和实数中有两个解。因此 $\forall x\,P(x)$ 在说明定义域前并不完整。有界写法把集合直接写出： $\forall x\in S\,P(x)$ 和 $\exists x\in S\,P(x)$ 。

定义

全称量词与存在量词

$\forall x\,P(x)$ 表示定义域内每个 $x$ 都使 $P(x)$ 为真。 $\exists x\,P(x)$ 表示至少有一个允许的 $x$ 使 $P(x)$ 为真；这样的值叫见证。证明全称句要从任意元素开始，证明存在句要给出并检验一个见证。否定全称句只需一个反例，否定存在句则必须说明所有候选都失败。

例题

赋值后再观察量词

令有界定义域 $D=\{1,2\}$ ，赋值的环境域为 $\mathbb Z$ ， $P(x,y)$ 表示 $x=y$ 。赋值 $x=1$ 、 $y=2$ 时开放公式为假。在 $\forall x\in D\,P(x,y)$ 中， $x$ 已绑定而 $y$ 自由，所以它在语法上仍是开放公式；自由变量并不保证真值一定随赋值改变。例如 $\forall x\in\mathbb Z\,(x=y)$ 仍因 $y$ 自由而开放，却对每个整数赋值都为假，因为 $x=y+1$ 是反例。回到有界公式， $y=1$ 时因 $x=2$ 失败而为假， $y=3$ 虽不属于有界见证域，却可作为环境中的外部赋值。公式 $\forall x\in D\,\exists y\in D\,P(x,y)$ 则是命题：对每个 $x$ 取 $y=x$ 即可。量词绑定变量，但没有改变谓词本身。

量词的语法与作用域

量词的作用域是紧接其后的公式，括号可以把作用域扩大。例如

\forall x\,(P(x)\to\exists y\,(Q(x,y)\land R(y)))

外层 $\forall$ 控制括号中的 $x$ ，内层 $\exists$ 只控制自己的括号中的 $y$ 。 $y$ 可以依赖已经选定的 $x$ ，但不能在内层作用域外使用。绑定变量只是局部占位符；若 $z$ 在公式体内没有出现，可把 $\forall x\,P(x)$ 改写为 $\forall z\,P(z)$ 。若替换字母已被内层量词使用，就可能发生变量捕获，真值随之改变。

量词也决定证明的开头。证明 $\forall x\in D\,P(x)$ 时写“令 $x\in D$ 任意”，不能只检验一个方便的数。证明 $\exists x\in D\,P(x)$ 时要先说出候选，再验证它属于 $D$ 并满足 $P$ 。在 $\forall x\,\exists y\,P(x,y)$ 中先给定任意 $x$ ， $y$ 可以依赖 $x$ ；在 $\exists y\,\forall x\,P(x,y)$ 中必须先选一个固定 $y$ 。

若有界定义域为空，则由展开式可见： $\forall x\in\varnothing,P(x)$ 为真，因为每个蕴含 $x\in\varnothing\to P(x)$ 的前件都为假；而 $\exists x\in\varnothing,P(x)$ 为假，因为不存在能使合取 $x\in\varnothing\land P(x)$ 为真的对象。

否定如何翻转量词

定理

量词否定律

在固定定义域上，

\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).

否定会翻转外层量词并否定其完整作用域，定义域不变。

定理

有界量词与德摩根律

有界写法是缩写：

\forall x\in S\,P(x)\equiv\forall x\,(x\in S\to P(x)), \qquad \exists x\in S\,P(x)\equiv\exists x\,(x\in S\land P(x)).

所以

\neg\forall x\in S\,P(x)\equiv\exists x\in S\,\neg P(x), \qquad \neg\exists x\in S\,P(x)\equiv\forall x\in S\,\neg P(x).

内部还要使用 $\neg(A\land B)\equiv(\neg A\lor\neg B)$ 、 $\neg(A\lor B)\equiv(\neg A\land\neg B)$ 以及 $\neg(A\to B)\equiv A\land\neg B$ 。

证明思路

“并非每个对象都满足 $P$ ”的意思，正是“存在一个对象使 $P$ 失败”；“没有对象满足 $P$ ”的意思，则是“每个对象都使 $P$ 失败”。遇到嵌套量词时一次只翻转一个，从外向内进行：

\begin{aligned} \neg\forall x\,\exists y\,P(x,y) &\equiv\exists x\,\neg\exists y\,P(x,y)\\ &\equiv\exists x\,\forall y\,\neg P(x,y). \end{aligned}

最终见证的 $x$ 是使原全称句失败的对象；对这个 $x$ ，所有 $y$ 都使 $P$ 失败。若只翻转第一层，就会漏掉内层作用域。

保留定义域并追踪见证

例题

否定质数的定义

全程固定自然数 $n\ge 2$ ；这个假设不能删除，因为 1 不是质数。质数定义为

\forall d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr).

逐层否定：

\begin{aligned} \neg\forall d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr) &\equiv\exists d\in\mathbb N\,\neg\bigl(d\mid n\to(d=1\lor d=n)\bigr)\\ &\equiv\exists d\in\mathbb N\,\bigl(d\mid n\land\neg(d=1\lor d=n)\bigr)\\ &\equiv\exists d\in\mathbb N\,\bigl(d\mid n\land d\ne1\land d\ne n\bigr). \end{aligned}

中文读法是：存在自然数 $d$ ，它整除 $n$ ，且既不是 1 也不是 $n$ 。这正是非平凡除数。否定保留了 $n\ge2$ 这个例子的假设。

例题

有界条件必须随见证保留

否定

\forall n\in\mathbb Z\,(n\gt 0\to n^2\gt n)

得到

\exists n\in\mathbb Z\,(n\gt 0\land n^2\le n).

$n=1$ 同时满足 $n\gt0$ 和 $n^2\le n$ ，所以是见证。0 虽满足 $0^2\le0$ ，却不满足 $n\gt0$ ，不能作为见证。

一个固定见证，还是随输入选择

例题

量词次序与依赖见证

在 $\mathbb N$ 上，

\forall x\in\mathbb N\,\exists y\in\mathbb N\,(x\lt y)

为真，给定任意 $x$ 后取 $y=x+1$ 。但

\exists y\in\mathbb N\,\forall x\in\mathbb N\,(x\lt y)

为假，因为固定的 $y$ 会被允许的 $x=y$ 反驳。有限集合也有相同现象：在 $X=\{1,2\}$ 、 $P(x,y)$ 表示 $x=y$ 时， $\forall x\in X\,\exists y\in X\,P(x,y)$ 由 $y=x$ 成立； $\exists y\in X\,\forall x\in X\,P(x,y)$ 为假，因为 $y=1$ 在 $x=2$ 失败， $y=2$ 在 $x=1$ 失败。

例题

量词的分配与同类交换

在固定定义域上，有以下两个恒等式

\forall x\,(P(x)\land Q(x))\equiv(\forall x\,P(x))\land(\forall x\,Q(x)), \qquad \exists x\,(P(x)\lor Q(x))\equiv(\exists x\,P(x))\lor(\exists x\,Q(x))

第一个从任意元素出发：同一个元素的合取为真，当且仅当两个性质都成立。第二个按见证属于哪个析取分支分类，反向则直接使用该见证。同类量词也可交换，但含义要说准确： $\forall x\forall y,P(x,y)$ 检查每个有序对， $\exists x\exists y,P(x,y)$ 只需一个有序对。不同类量词通常不可交换。

在 $\{1,2\}$ 上令 $P(x)$ 为 $x=1$ 、 $Q(x)$ 为 $x=2$ ，则 $\forall x(P(x)\lor Q(x))$ 为真，而 $(\forall xP(x))\lor(\forall xQ(x))$ 为假；同样， $\exists x(P(x)\land Q(x))$ 为假，而 $(\exists xP(x))\land(\exists xQ(x))$ 为真。这是两个交叉失败的具体反例。

定理

见证传递

若 $\forall x\,(P(x)\to Q(x))$ 且 $\exists x\,P(x)$ ，则 $\exists x\,Q(x)$ 。取满足 $P(a)$ 的见证 $a$ ；把全称前提代入 $a$ 得 $P(a)\to Q(a)$ ，所以 $Q(a)$ ，同一个 $a$ 就是结论的见证。

例题

否定存在合取

由外向内使用量词否定律和德摩根律：

\neg\exists x\,(P(x)\land Q(x)) \equiv\forall x\,\neg(P(x)\land Q(x)) \equiv\forall x\,(\neg P(x)\lor\neg Q(x))

最后一句表示每个对象至少有一个性质失败，并不表示每个对象两个性质都失败。

例题

在指定定义域中读回有序量词

公式

\exists y\,\forall x\,(x\le y)

表示存在一个固定的 $y$ ，使定义域中的每个 $x$ 都满足 $x\le y$ 。它是否为真取决于定义域；未说明定义域时，不能把它误读成关于所有数的断言。

例题

不同图书与不同借阅者

设 $People$ 和 $Books$ 分别为人和书的集合。两句陈述是

\forall b\in Books\,\exists x\in People\,Borrows(x,b)

和

\exists x\in People\,\forall b\in Books\,Borrows(x,b).

第一句说每本书至少有一个借阅者；第二句说同一个人借阅所有书。两本书由不同的人分别借走时，第一句为真而第二句为假，所以量词顺序确实改变了意思。

“每个人至少读两本书”要求对每位读者给出两本不同的书：

\forall x\in People\,\exists b_1,b_2\in Books\,(b_1\ne b_2\land Reads(x,b_1)\land Reads(x,b_2))

例题

课程先修要求的否定

设 $Student(x)$ 、 $Enrolls(x)$ 和 $Prereq(x)$ 分别表示学生、选课和满足先修要求。考虑以下陈述

\forall x\,\bigl((Student(x)\land Enrolls(x))\to Prereq(x)\bigr).

否定是

\exists x\,\bigl(Student(x)\land Enrolls(x)\land\neg Prereq(x)\bigr).

见证必须是已选课而又不满足先修要求的学生。没有选课的人不反驳原蕴含，因为原句没有对他作出要求。

例题

在学生定义域中翻译

定义域为某大学的所有学生。若 $S(x)$ 表示“ $x$ 学习数学”， $P(x)$ 表示“ $x$ 通过考试”，则“所有学习数学的学生都通过考试”“至少一名学生通过考试”“至少一名学习数学的学生没有通过考试”分别写成

\forall x\,(S(x)\to P(x)),\qquad \exists x\,P(x),\qquad \exists x\,(S(x)\land\neg P(x))

定义域已经包含“学生”；谓词只表达题目要求的性质。

先表达依赖关系，再写符号

例题

从英文建立量词公式

“每个学生至少修过一门数学课”是

\forall x\,\bigl(Student(x)\to\exists m\,(MathCourse(m)\land Taken(x,m))\bigr).

“有一位教授教授系内的每一门课”是

\exists p\,\bigl(Professor(p)\land\forall c\,(DepartmentCourse(c)\to Teaches(p,c))\bigr)

“每场考试都有一道每个学生都觉得困难的题目”是

\forall e\,\bigl(Exam(e)\to\exists q\,(Question(q,e)\land\forall s\,(Student(s)\to Difficult(s,q)))\bigr).

题目可以随考试改变，但对该考试选定的题目必须对每个学生都困难。把存在量词移到最外层，就错误地声称有一道题适用于所有考试。

用见证诊断错误的陈述

例题

识别错误形式化与安全改名

公式

\exists d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr)

太弱。保留 $n\ge2$ 的假设时，取 $d=n+1$ ；它不整除 $n$ ，所以蕴含以前件为假而真，存在式无需检查所有除数。（当 $n=0$ 时不要用这个特定见证，因为 $1$ 整除 $0$ 。）质数定义需要 $\forall d$ 。事实上，取 $d=1$ 就能对任何 $n$ 成为见证，因为 $1\mid n$ 且 $d=1$ ； $d=n+1$ 则突出了 $n\ge2$ 时的真空成立。同样， $\forall a\,\exists d\,SubmittedBefore(a,d)$ 允许每份作业有自己的期限；单一期限应写成 $\exists d\,\forall a\,(Assignment(a)\to SubmittedBefore(a,d))$ 。

$\forall x\,\exists y\,Attends(x,y)$ 也不是“每场讲座至少有一名学生参加”的正确写法；它没有说明 $x$ 和 $y$ 的类型。正确形式是

\forall \ell\,(Lecture(\ell)\to\exists s\,(Student(s)\land Attends(s,\ell))).

替换字母在公式体内处处不出现是充分的安全保障，并非必要条件；必要条件是改名不能改变相关出现位置的绑定状态，不能造成变量捕获。 $X=\{1,2\}$ 上的

\forall x\in X\,\exists y\in X\,(x\ne y)

为真。若把外层 $x$ 草率改成已有的 $y$ ，便得到 $\forall y\in X\,\exists y\in X\,(y\ne y)$ ，内层量词捕获了两个出现位置，公式为假。改用全新的 $z$ 才得到等价的 $\forall z\in X\,\exists y\in X\,(z\ne y)$ 。

例题

唯一性包含两个证明要求

“存在唯一的 $x\in D$ 使 $P(x)$ ”表示存在性和至多一个：

\exists x\in D\,\bigl(P(x)\land\forall y\in D\,(P(y)\to y=x)\bigr).

先给一个见证并验证 $P$ ，再令 $y$ 为任意满足 $P$ 的元素并证明 $y=x$ 。在整数中 $x^2=1$ 有 $1$ 和 $-1$ 两个见证，存在但不唯一。对 $x^2=0$ ， $0$ 是见证；若整数 $y$ 满足 $y^2=0$ ，平方非负且只有 $y=0$ 时平方为零，所以 $y=0$ ，这就完成了至多一个的证明。“我的同学恰有一个朋友”也用同一模式：在人为定义域、 $o$ 指定该同学时， $\exists!x\,Friend(o,x)$ 同时要求朋友存在且至多一人。

例题

函数与关系的量词定义

把“ $f:X\to Y$ 是单射”写成

\forall x_1,x_2\in X\,(f(x_1)=f(x_2)\to x_1=x_2).

证明时先取任意 $x_1,x_2\in X$ ，假设像相等，再推出输入相等；反例则给出两个不同输入而像相等。偏序的完整条件是

\forall x\in X\,(xRx),\quad \forall x,y\in X\,(xRy\land yRx\to x=y),\quad \forall x,y,z\in X\,(xRy\land yRz\to xRz)

等价关系把中间一项换成 $\forall x,y\in X\,(xRy\to yRx)$ 。每一项都要单独履行证明要求，不能用一个样本代替全称证明。

从符号读回句子

若人的定义域满足

\forall x\,\exists y\,(x\ne y\land Friend(x,y)),

它表示每个人都有一个与自己不同的朋友。若定义域包含人和学生，

\exists x\,\forall y\,(Student(y)\to Older(x,y))

表示存在一个人比每一名学生年长，并不表示每个人都比每名学生年长，也不自动要求这个人是学生。读回英文或中文时，要明确第一个见证是谁，以及后面的见证是否可依赖它。

常见错误

在 $\exists x\,(Student(x)\to P(x))$ 中，非学生就能让蕴含真而成为见证，即使他不满足 $P$ ；若见证必须是学生，应写成 $\exists x\,(Student(x)\land P(x))$ 。“只有学生可以提交”是 $\forall x\,(Submitted(x)\to Student(x))$ ，而“所有学生都提交”是 $\forall x\,(Student(x)\to Submitted(x))$ ；“只有”决定蕴含方向。

常见错误

蕴含不等于合取

否定 $A\to B$ 得 $A\land\neg B$ 。不要写成 $\neg A\to\neg B$ ，也不要丢掉原蕴含的前件。普遍量化的反例必须属于限制的类别并且使结论失败。

常见错误

不要交换混合量词

同类量词有时可以交换，但 $\forall x\exists y$ 与 $\exists y\forall x$ 通常不同。有限集合 $X=\{1,2\}$ 的等式例子给出了具体反例。

常见错误

真值表不能枚举无限定义域

谓词逻辑扩展命题逻辑。真值表可以处理连接词的真值，却不能代替在 $\mathbb N$ 上对所有元素作证明。全称句要用任意元素证明或一个反例否定，存在句要给见证或说明所有候选失败。

逐步跟踪否定

使用 stepper 逐层在陈述和否定之间转换：翻转一个量词，否定完整作用域，再化简连接词。它只是辅助检查，不替代书面证明。

边读边试

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

这个示范逐步显示量词否定的每一步。

例子

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

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

总结

量词在固定定义域内绑定变量；自由变量仍需要赋值。有界全称使用蕴含，有界存在使用合取，否定时定义域不变。由外向内翻转量词并使用德摩根律，尤其要记住 $\neg(A\to B)\equiv A\land\neg B$ 。量词次序决定见证能否依赖输入；全称证明从任意元素开始，存在证明给出已检验的见证，唯一性则要分别证明存在与至多一个。

练习：作用域、见证与证明

练习 1

在固定定义域上，完全化简 $\neg\forall x\,\exists y\,P(x,y)$ 。

解答 · 提示

逐层翻转量词，并否定最后的谓词。

解答 · 参考解答

$\exists x\,\forall y\,\neg P(x,y)$ 。第一个见证使原全称句失败，并且对它所有 $y$ 都失败。

练习 2

形式化：有一名学生，在每场考试中都觉得至少一道题目困难。使用 Student、Exam、Question 和 Difficult。

解答 · 提示

先固定学生，再考虑考试；题目可以随考试改变。

解答 · 参考解答

\exists s\,\bigl(Student(s)\land\forall e\,(Exam(e)\to\exists q\,(Question(q,e)\land Difficult(s,q)))\bigr).

学生的见证位于考试的量词之外。给定任意考试后，再为同一名学生选择一道题目。

练习 3

假设 $n\ge2$ 。为什么 $\exists d\in\mathbb N\,(d\mid n\to(d=1\lor d=n))$ 太弱，不能定义质数？

解答 · 提示

给出使蕴含因前件为假而成立的自然数见证。

解答 · 参考解答

在 $n\ge2$ 下取 $d=n+1$ 。它不整除 $n$ ，所以蕴含以前件为假而真；存在式没有检查所有除数，质数定义必须使用 $\forall d$ 。

练习 4

当定义域为 $\mathbb N$ 时，有限真值表能单独判定 $\forall x\,P(x)$ 吗？请说明正确的证明方法。

解答 · 提示

区分连接词的真值赋值与对无限定义域元素的量化。

解答 · 参考解答

不能。真值表只处理有限个原子命题的真值，不能枚举所有自然数。应对任意自然数作全称证明，或给出一个自然数反例。

先读这一页

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

1.3 量词与否定

动机

定义

谓词与命题

定义域与赋值

全称量词与存在量词

赋值后再观察量词

量词的语法与作用域

否定如何翻转量词

量词否定律

有界量词与德摩根律

证明思路

保留定义域并追踪见证

否定质数的定义

有界条件必须随见证保留

一个固定见证，还是随输入选择

量词次序与依赖见证

量词的分配与同类交换

见证传递

否定存在合取

在指定定义域中读回有序量词

不同图书与不同借阅者

课程先修要求的否定

在学生定义域中翻译

先表达依赖关系，再写符号

从英文建立量词公式

用见证诊断错误的陈述

识别错误形式化与安全改名

唯一性包含两个证明要求

函数与关系的量词定义

从符号读回句子

常见错误

蕴含不等于合取

不要交换混合量词

真值表不能枚举无限定义域

逐步跟踪否定

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

总结

练习：作用域、见证与证明

练习 1

练习 2

练习 3

练习 4

先读这一页

练习

先备知识

本单元重点词汇

本系列更多笔记