1.4. 谓词和量词

本节我们将介绍一种表达能力更强的逻辑，即谓词逻辑。我们将看到谓词逻辑如何用来表达数学和计算机科学中各种语句的意义，并允许我们推理和探索对象之间的关系。

谓语

对于语句“$x$大于3”。我们可以用$P(x)$表示语句“$x$大于3”，其中$P$表示谓词“大于3”，而$x$是变量。语句$P(x)$也可以说成是命题函数$P$在$x$的值。一旦给变量$x$赋一个值，语句$P(x)$就称为命题并具有真值。

形式为$P(x_1,x_2,\dots,x_n)$的语句是命题函数$P$在$n$元组$(x_1,x_2,\dots,x_n)$的值，$P$也称为$\bm{n}$位谓词 或$\bm{n}$元谓词

前置条件和后置条件

谓词还可以用来验证计算机程序，也就是证明当给定合法输入时计算机程序总是能产生所期望的输出。描述合法输入的语句叫做前置条件，而程序运行的输出应满足的条件称为后置条件。

量词

处理谓词和量词的逻辑领域称为谓词演算。

全称量词

许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真，这一特定域称为变量的论域或全体域，时常简称为域。对特定论域而言$P(x)$的全称量化是这样一个命题：它断言$P(x)$对$x$在其论域中的所有值均为真。论域对顶了变脸$x$所有可能取的值。当我们改变论域时，$P(x)$的全称量化的意义也随之改变。在使用全称量词是必须制定论域，否则语句的全称量化就是无定义的。

全称量化

$P(x)$的全称量化是语句：“$P(x)$对$x$在其论域中的所有值均为真。”

符号$\forall\,xP(x)$表示$P(x)$的全称量化，其中$\forall$称为全称量词。命题$\forall\,xP(x)$读做“对所有$x$，$P(x)$”或“对每个$x$，$P(x)$”。

一个使$P(x)$为假的个体称为$\forall\,xP(x)$的反例。

通常，我们会做一个隐式的假设，即量词的论域均为非空的。注意如果论域为空的。注意如果论域为空，那么$\forall xP(x)$对任何命题函数$P(x)$都为真，因为论域中没有单个$x$使$P(x)$为假。

存在量化

$P(x)$的存在量化命题是：“论域中存在一个个体$x$满足$P(x)$”。

我们用符号$\exist xP(x)$表示$P(x)$的存在量化，其中$\exist$称为存在量词。

当使用$\exist xP(x)$时必须制定一个论域。

唯一量词

符号$\exist !$或$\exist_1$表示唯一量词，$\exist !xP(x)$或$\exist_1xP(x)$表示“存在一个唯一的$x$使得$P(x)$为真”。

约束论域的量词

在限定一个量词的论域时经常IXUS会采用简写的表示法。在这个表示法中，变量必须满足的条件直接放在量词的后面。如下：

• $\forall\:x < 0(x^2 > 0)$，这里的论域为$x < 0$
• $\exist\:z>0(z^2=2)$，这里的论域为$z>0$

量词的优先级

量词$\forall$和$\exist$比命题演算中的所有逻辑运算符都具有更高的优先级。

$\forall\:xP(x)\lor Q(x)$是$\forall\:xP(x)$和$Q(x)$的析取。

变量绑定

当量词作用于变量$x$时，我们说次变量的这次出现为约束的。如果没有量词约束或设置为某一特定值，则称为是自由的。

语句$\exist x(x + y = 1)$，变量$x$受存在量词$\exist x$约束，但是变量$y$是自由的。

涉及量词的逻辑等价式

定义3

涉及谓词和量词的语句是逻辑等价的当且仅当无论用什么谓词代入这些语句，也无论为这些命题函数里的变量指定什么论域，它们都有相同的真值。我们用$S \equiv T$表示涉及谓词和量词的两个语句$S$和$T$是逻辑等价的。

例如：$\forall\:x(P(x)\land Q(x)) \equiv \forall\:xP(x)\land\forall\:xQ(x)$

量化表达式的否定

对于“班上每个学生都学过一门微积分课”，这个语句的全称量化命题是：$\forall\:xP(x)$，其中$P(x)$为“$x$学过一门微积分课”。

只要班上有一个学生没有学过微积分，那么以上命题就不成立。这一语句的否定命题就是**“并非班上每一个学生都学过一门微积分课”**，即：$\exist\:x\lnot P(x)$

注意

“班上每个学生都学过一门微积分课”的否定命题不是：“班上每个学生都没有学过一门微积分课”

$\forall\:xP(x)$ 的否定命题是：$\exist\:x\lnot P(x)$

这个例子说明了下面的等价关系

$$\begin{align} \lnot\forall\:xP(x) &\equiv \exist\:x\lnot P(x) \\ \lnot\exist\:xQ(x) &\equiv \forall\:x\lnot Q(x) \end{align}$$

量词的否定规则称为量词的德·摩根律

否定	等价语句	何时为真	何时为假
$\lnot\exist xP(x)$	$\forall{x}\lnot P(x)$	对于每个$x$,$P(x)$为假	存在一个$x$,使$P(x)$为真
$\lnot\forall xP(x)$	$\exist{x}\lnot P(x)$	存在一个$x$,使$P(x)为假	对于每个$x$,$P(x)$为真

语句到逻辑表达式的翻译

例1：

语句“班上的每个学生都学过微积分”。如何翻译为逻辑表达式？

1. 首先重写此语句，使得能很清楚的确定所要使用的合适的量词。重写后的语句为：“对班上的每一个学生，该学生学过微积分”，
2. 然后引入变量$x$，语句变为“对班上的每一个学生$x$，$x$学过微积分”。
3. 然后引入谓词$C(x)$表示语句“$x$学过微积分”。
4. 如果$x$的论域是班上的学生，我们可以将语句翻译为$\:\forall{x}C(x)$

如果$S(x)$表示语句“$x$在这个班上”，则表达式可写为$\forall x(S(x) \to C(x))$

注意

不能表示为$\forall x(S(x) \land C(x))$，因为这表示每个$x$都是班上的学生并且学过微积分。

我们倾向于使用双变量谓词$Q(x,y)$表示语句“学生$x$学过课程$y$”，我们可以把$C(x)$替换成$Q(x,\text{微积分})$。得到$\forall xQ(x,\text{微积分})$或$\forall x(S(x) \to Q(x,\text{微积分}))$。

---

例2：

用谓词和量词表达语句“这个班上的某个学生去过墨西哥”和“这个班上的每个学生或去过加拿大，或去过莫斯哥”。

语句“这个班上的某个学生去过墨西哥”的意思是“在这个班上有个学生，他去过墨西哥”。引入变量$x$，因此语句变成“在这个班上有个学生$x$，他去过墨西哥”。引入谓词$M(x)$表示语句“$x$去过墨西哥”。如果论域为这个班上的学生，则可以翻译为$\exist\:xM(x)$。

如果$x$的论域为所有人，我们引入谓词$S(x)$表示“$x$是这个班上的一个学生”。答案就变成了$\exist\:x(S(x)\land M(x))$，它表示“存在一个人$x$，他是班上的学生并且他去过墨西哥”。

注意

语句不能表示为$\exist\:x(S(x)\to M(x))$，它表示当有一个人不在这个班里时也是真的。（参见$p\to q$的真值表）当$S(x)$为$F$时，无论$M(x)$为何值，表达式的真值都为真。

第二个语句表示成“对于班上的每一个$x$，$x$具有这样的特性：$x$去过加拿大或$x$去过墨西哥”。令谓词$C(x)$表示语句“$x$去过加拿大”。如果论域为这个班的学生，则第二个语句可以表达为：$\forall\:x(C(x)\lor M(x))$。

如果$x$的论域时所有人，我们的语句就可以表示成：
“对于每一个人$x$，如果$x$在这个班，则$x$去过加拿大或去过墨西哥”。此时语句表示成$\forall\:x(S(x)\to(C(x)\lor M(x)))$，这里的$S(x)$是$C(x)\lor M(x)$的充分条件。

注意

这里要理解题意，题目的意思是“只要是这个班上的学生，那么他要么去过加拿大要么去过墨西哥”，并不是“去过加拿大或去过墨西哥的人都是这个班上的同学。”

系统规范说明中量词的使用

1. 每封大于1MB的邮件会被压缩
2. 如果一个用户处于活动状态，那么至少有一条网络链路是有效的

令$S(m,y)$表示是“邮件$m$大于$y$MB”,其中变量$x$的论域是所有邮件。变量$y$是一个正实数；令$C(m)$表示“邮件会被压缩”，那么表达式就可以写为：$\forall\:m(S(m,1) \to C(m))$

$A(u)$表示“用户u处于活动状态”，$S(n,x)$表示“网络链路$n$处于$x$状态”。那么 2 可以表示为 $\exist\:uA(u) \to \exist\:nS(n,\text{有效})$

习题部分

空量化

DEFINITION 空量化（null quantification）

当受量词约束的变元没有出现在语句的某一部分时，称之为空量化。如$\forall x A$，其中$x$在$A$中不作为自由变元出现。

空量化规则，其中$x$在$A$中不作为自由变元出现。假设论域非空。

$$\begin{array}{ll} (\forall x P(x))\lor A & \equiv \forall x (P(x) \lor A) \\ (\forall x P(x))\land A & \equiv \forall x (P(x) \land A) \\ (\exist x P(x))\lor A & \equiv \exist x (P(x) \lor A) \\ (\exist x P(x))\land A & \equiv \exist x (P(x) \land A) \\ \forall x (A \to P(x)) & \equiv A \to \forall x P(x) \\ \exist x (A \to P(x)) & \equiv A \to \exist x P(x) \\ \forall x (P(x) \to A) & \equiv \exist x P(x) \to A \\ \exist x (P(x) \to A) & \equiv \forall x P(x) \to A \end{array}$$