1.5. 嵌套量词

嵌套量词: 一个量词出现在另一个量词的作用域内。嵌套量词经常出现在数学和计算机科学中。

理解涉及嵌套量词的语句

例题1

假定$x$和$y$的论域时所有实数的集合。

$\forall x \forall y(x + y = y + x)$，表示对于所有实数$x$和$y$，$x + y = y + x$。这是加法的交换律。

$\forall x \exist y (x + y = 0)$，对于所有实数$x$，存在一个实数$y$使得$x + y = 0$。也就是每个实数都有一个加法的逆。

$\forall x \forall y \forall z(x + (y + z) = (x + y) + z)$，加法的结合律。

例题2

$\forall x \forall y ((x > 0) \land (y < 0) \to (xy < 0))$。其中$x$和$y$的论域时所有实数的集合。
表示一个正实数和一个负实数的积是负数。

---

将量化当做循环 在处理多个变量的量化式时，有时候借助嵌套循环来思考是有益的。例如要判定$\forall x \forall y P(x, y)$是否为真，我们先对$x$的所有值做循环，而对$x$的每个值再对$y$的所有值循环。

量词的顺序

例题3

令$P(x,y)$为语句$x+y=y+x$，量化式$\forall\: x \: \forall\: y P(x, y)$和$\forall\: y \: \forall\: x P(x, y)$的真值是什么。

这两个量化式表示的意义是相同的，都是加法交换律。真值都为真。

这说明了一个原理，即在没有其他量词的语句中，在不改变量化式意义的前提下嵌套[全称量词]的顺序是可以改变的

例题4

令$P(x,y)$为语句$x+y=0$，量化式$\exist\: y \: \forall\: x P(x, y)$和$\forall\: x \: \exist\: y P(x, y)$的真值是什么。这里的论域为全体实数。

量化式$\exist\: y \: \forall\: x P(x, y)$ 表示“存在一个实数$y$，对每个实数$x$，使得$P(x,y)$成立”。因为不存在这样一个实数，所以语句的真值为假。

量化式$\forall\: x \: \exist\: x P(x, y)$表示“对每个实数$x$，存在一个实数$y$，使得$P(x,y)$成立”。这个实数就是$y = -x$，所以语句的真值为真。

例4说明了量词的出现顺序会产生不同的影响。

两个变量的量化式

语句	何时为真	何时为假
$\forall\: x \: \forall\: y P(x, y) \\ \forall\: y \: \forall\: x P(x, y)$	对每一对$x,y$，$P(x,y)$都为真	存在一对$x,y$，使得$P(x,y)$为假
$\forall\: x \: \exist\: y P(x, y)$	对每个$x$,都存在一个$y$使得$P(x,y)$为真	存在一个$x$,使得$P(x,y)$对每个$y$总为假
$\exist\: x \: \forall\: y P(x, y)$	存在一个$x$,使得$P(x,y)$对每个$y$总为真	对每个$x$,都存在一个$y$使得$P(x,y)$为假
$\exist\: x \: \exist\: y P(x, y) \\ \exist\: y \: \exist\: x P(x, y)$	存在一对$x,y$，使得$P(x,y)$为真	对每一对$x,y$，$P(x,y)$均为假

数学语句到嵌套量词语句的翻译

两个正整数的和总是正数

$$\forall x \forall y ((x > 0) \land (y > 0) \to (x+y > 0))$$

这里的论域为全体整数。如果论域为全体正整数就可以写为：

$$\forall x \forall y (x + y > 0)$$

---

除了0以外的每个实数都有一个乘法逆元（一个实数$x$的乘法逆元是使$xy=1$的实数y）

$$\forall x ((x \neq 0) -> \exist y (xy = 1))$$

---

极限的定义$\:lim_{x\to a}f(x) = L$

对每个实数 $\epsilon > 0$，存在一个实数 $\delta > 0$，使得对任意的x，只要$0 < | x- a | < \delta$，就有$|f(x) -L| < \epsilon$。极限的这一定义可以用量词表示为：

$$\forall\:\epsilon\:\exist\:\delta\:\forall\:x(0<|x -a|<\delta \to |f(x) - L| < \epsilon)$$

其中$\epsilon$和$\delta$的论域是正实数集合。

$$\forall\:\epsilon>0\:\exist\:\delta>0\:\forall\:x(0<|x -a|<\delta \to |f(x) - L| < \epsilon)$$

其中$\epsilon$和$\delta$的论域是实数集合。

可以理解为只要$x$无限靠近$c$，那么函数值就无限靠近$L$

嵌套量词到自然语言的翻译

汉语语句到逻辑表达式的翻译

嵌套量词的否定