谓词

1.4.2 谓词

涉及变量的语句，例如：

“$x>3$”，“$x=y+3$”，“$x+y=z$”

以及

\quad “Computer $x$ is under attack by an intruder”
\quad “Computer $x$ is functioning properly”

经常出现在数学表达式、计算机程序和系统规范中。当变量的值没有被指定时，这些语句既不为真也不为假。在本节中，我们将讨论如何从这些语句中构造命题。

语句“$x$ is greater than 3”包含两部分。第一部分是变量 $x$，它是该语句的主体。第二部分是谓词“is greater than 3”，它指的是该语句可能具有的性质。我们可以用 $P(x)$ 表示语句“$x$ is greater than 3”，其中 $P$ 表示谓词“is greater than 3”，$x$ 是变量。语句 $P(x)$ 也被称为命题函数 $P$ 在 $x$ 处的值。一旦给变量 $x$ 赋值，语句 $P(x)$ 就成为一个命题，并具有真值。

例1 令 $P(x)$ 表示语句“$x>3$”。$P(4)$ 和 $P(2)$ 的真值是什么？

解 通过在语句“$x>3$”中设 $x=4$，我们得到语句 $P(4)$，即“$4>3$”，是真命题。因此，$P(4)$ 为真。而 $P(2)$ 对应的语句是“$2>3$”，这是假命题，因此 $P(2)$ 为假。

例2 令 $A(x)$ 表示语句“Computer $x$ is under attack by an intruder”。假设在校园中的计算机中，只有 CS2 和 MATH1 当前正在被攻击。$A(CS1)$、$A(CS2)$ 和 $A(MATH1)$ 的真值是什么？

解 通过将 $x=CS1$ 代入语句“Computer $x$ is under attack by an intruder”，我们得到语句 $A(CS1)$。由于 CS1 不在当前被攻击的计算机列表中，因此 $A(CS1)$ 为假。同理，由于 CS2 和 MATH1 是当前被攻击的计算机，因此我们知道 $A(CS2)$ 和 $A(MATH1)$ 为真。

我们也可以有涉及多个变量的语句。例如，考虑语句“$x=y+3$”。我们可以用 $Q(x,y)$ 表示这个语句，其中 $x$ 和 $y$ 是变量，$Q$ 是谓词。当为变量 $x$ 和 $y$ 赋值时，语句 $Q(x,y)$ 就具有真值。

例3 令 $Q(x,y)$ 表示语句“$x=y+3$”。命题 $Q(1,2)$ 和 $Q(3,0)$ 的真值是什么？

解 通过在语句 $Q(x,y)$ 中设 $x=1$ 和 $y=2$，我们得到语句 $Q(1,2)$，即“$1=2+3$”，这是假的。因此，$Q(1,2)$ 为假。而 $Q(3,0)$ 对应的语句是“$3=0+3$”，这是真命题，因此 $Q(3,0)$ 为真。

例4 令 $A(c,n)$ 表示语句“Computer $c$ is connected to network $n$”，其中 $c$ 是表示计算机的变量，$n$ 是表示网络的变量。假设计算机 MATH1 连接到网络 CAMPUS2，但没有连接到网络 CAMPUS1。$A(MATH1,CAMPUS1)$ 和 $A(MATH1,CAMPUS2)$ 的值是什么？

解 由于 MATH1 没有连接到 CAMPUS1 网络，我们可以得出 $A(MATH1,CAMPUS1)$ 为假。然而，由于 MATH1 连接到 CAMPUS2 网络，我们可以得出 $A(MATH1,CAMPUS2)$ 为真。

类似地，我们可以让 $R(x,y,z)$ 表示语句“$x+y=z$”。当给变量 $x$，$y$ 和 $z$ 赋值时，这个语句具有真值。

例5 命题 $R(1,2,3)$ 和 $R(0,0,1)$ 的真值是什么？

解 命题 $R(1,2,3)$ 是通过在语句 $R(x,y,z)$ 中设置 $x=1$，$y=2$ 和 $z=3$ 得到的。我们看到 $R(1,2,3)$ 是语句“$1+2=3$”，这是正确的。还要注意 $R(0,0,1)$，这是语句“$0+0=1$”，是错误的。

一般来说，涉及 $n$ 个变量 $x_1,x_2,\dots ,x_n$ 的语句可以表示为 $P(x_1,x_2,\dots ,x_n)$。

形如 $P(x_1,x_2,\dots ,x_n)$ 的语句是命题函数 $P$ 在 $n$ 元组 $(x_1,x_2,\dots ,x_n)$ 处的值，$P$ 也被称为一个 $n$ 位谓词或 $n$ 元谓词。在计算机程序中出现的命题函数，如例 6 所示。

例6 考虑语句

“if $x>0$ then $x:=x+1$.”

当在程序中遇到此语句时，程序执行时变量 $x$ 的值被插入到 $P(x)$ 中，即“$x>0$”。如果对该值 $x$ 来说 $P(x)$ 为真，则执行赋值语句 $x:=x+1$，因此 $x$ 的值增加 1。如果对该值 $x$ 来说 $P(x)$ 为假，则不执行赋值语句，因此 $x$ 的值不变。

前置条件和后置条件 谓词也用于证明计算机程序的正确性，即证明在给定有效输入时，计算机程序总是产生所需的输出。（请注意，除非证明了计算机程序的正确性，否则任何数量的测试都无法证明它对所有输入值产生所需的输出，除非每个输入值都被测试过。）描述有效输入的语句称为前置条件，而描述程序运行后输出应满足的条件称为后置条件。正如例 7 所示，我们使用谓词来描述前置条件和后置条件。我们将在 5.5 节更详细地研究这一过程。

例7 考虑以下程序，用来交换两个变量 $x$ 和 $y$ 的值。

temp := x
x := y
y := temp

找到我们可以用作前置条件和后置条件的谓词，以验证该程序的正确性。然后解释如何使用它们来验证对于所有有效输入，该程序按预期工作。

解 对于前置条件，我们需要表达在运行程序之前 $x$ 和 $y$ 具有特定的值。因此，对于这个前置条件，我们可以使用谓词 $P(x,y)$，其中 $P(x,y)$ 是语句“$x=a$ 且 $y=b$”，其中 $a$ 和 $b$ 是在运行程序之前 $x$ 和 $y$ 的值。因为我们想要验证程序交换 $x$ 和 $y$ 的值对于所有输入值都成立，对于后置条件我们可以使用 $Q(x,y)$，其中 $Q(x,y)$ 是语句“$x=b$ 且 $y=a$”。

为了验证程序始终按预期工作，假设前置条件 $P(x,y)$ 成立。也就是说，我们假设语句“$x=a$ 且 $y=b$”为真。这意味着 $x=a$ 且 $y=b$。程序的第一步，$temp:=x$，将 $x$ 的值赋给变量 $temp$，所以在这一步之后我们知道 $x=a$，$temp=a$，并且 $y=b$。在程序的第二步，$x:=y$，我们知道 $x=b$，$temp=a$，并且 $y=b$。最后，在第三步，我们知道 $x=b$，$temp=a$，并且 $y=a$。因此，在程序运行之后，后置条件 $Q(x,y)$ 成立，即语句“$x=b$ 且 $y=a$”为真。

量词

全称量词

当命题函数中的变量被赋值时，得到的语句成为具有某个真值的命题。然而，还有另一种重要的方式，称为量化，用于从命题函数创建命题。量化表达谓词在元素范围内为真的程度。在英文中，词语“all”、“some”、“many”、“none”、“few” 用于量化。我们将在此集中讨论两种类型的量化：全称量化，它告诉我们谓词对所考虑的每个元素都为真；以及存在量化，它告诉我们存在一个或多个所考虑的元素使得谓词为真。处理谓词和量词的逻辑领域称为谓词演算。

定义 1 $P(x)$ 的全称量化是语句
\quad “$P(x)$ 对域中的所有 $x$ 值为真。”
符号 $\forall xP(x)$ 表示 $P(x)$ 的全称量化。这里 $\forall$ 称为全称量词。我们将 $\forall xP(x)$ 读作“对所有 $xP(x)$”或“对于每个 $xP(x)$”。使 $P(x)$ 为假的元素称为 $\forall xP(x)$ 的反例。

例8 设 $P(x)$ 为语句“$x+1>x$。”当论域包含所有实数时，量化 $\forall xP(x)$ 的真值是多少？

解 因为对于所有实数 $x$，$P(x)$ 为真，因此量化 $\forall xP(x)$ 为真。

一个语句 $\forall xP(x)$ 为假，当且仅当 $P(x)$ 是一个命题函数且 $P(x)$ 在 $x$ 属于论域时并不总是真。证明 $P(x)$ 在 $x$ 属于论域时并不总是真的一种方法是找到 $\forall xP(x)$ 的一个反例。请注意，单个反例就足以证明 $\forall xP(x)$ 为假。例 9 说明了如何使用反例。

例9 设 $Q(x)$ 为语句“$x<2$。”当论域包含所有实数时，量化 $\forall xQ(x)$ 的真值是多少？

解 $Q(x)$ 对于每个实数 $x$ 都不成立，例如，$Q(3)$ 为假。也就是说，$x=3$ 是 $\forall xQ(x)$ 的一个反例。因此，$\forall xQ(x)$ 为假。

例11 如果 $N(x)$ 是“Computer $x$ is connected to the network”，并且论域包含校园内的所有计算机，那么语句 $\forall xN(x)$ 是什么意思？

解 语句 $\forall xN(x)$ 意味着对于校园内的每台计算机 $x$，该计算机 $x$ 连接到了网络。这个语句可以用英文表达为 “Every computer on campus is connected to the network”。

存在量词

定义 2 $P(x)$ 的存在量化是命题
\quad “There exists an element $x$ in the domain such that $P(x)$。”
我们使用符号 $\exists xP(x)$ 表示 $P(x)$ 的存在量化。这里 $\exists$ 被称为存在量词。

例13 设 $P(x)$ 表示语句 “$x>3$。”当论域包含所有实数时，量化 $\exists xP(x)$ 的真值是多少？

解 因为 “$x>3$” 有时为真——例如，当 $x=4$ 时——$P(x)$ 的存在量化，即 $\exists xP(x)$，为真。

例14 设 $Q(x)$ 表示语句 “$x=x+1$。”当论域包含所有实数时，量化 $\exists xQ(x)$ 的真值是多少？

解 因为对于每个实数 $x$，$Q(x)$ 都为假，$Q(x)$ 的存在量化，即 $\exists xQ(x)$，为假。

有限域上的量词

当量词的论域是有限的，也就是说，当它的所有元素都可以列出时，可以使用命题逻辑来表达量化语句。特别地，当论域的元素是 $x_1,x_2,\dots ,x_n$，其中 $n$ 是一个正整数时，全称量化 $\forall xP(x)$ 等价于合取

$$P(x_1)\wedge P(x_2)\wedge \cdots \wedge P(x_n),$$

因为当且仅当 $P(x_1),P(x_2),\dots ,P(x_n)$ 全部为真时，这个合取为真。

例15 $\forall xP(x)$ 的真值是多少，其中 $P(x)$ 表示语句 “$x^2<10$”，并且论域由不超过 4 的正整数组成？

解 语句 $\forall xP(x)$ 与合取

$$P(1)\wedge P(2)\wedge P(3)\wedge P(4),$$

相同，因为论域由整数 1、2、3 和 4 组成。由于 $P(4)$，即语句“$4^2<10$”为假，得出 $\forall xP(x)$ 为假。

类似地，当论域的元素是 $x_1,x_2,\dots ,x_n$ 时，其中 $n$ 是正整数，$P(x)$ 的存在量化 $\exists xP(x)$ 与析取

$$P(x_1)\vee P(x_2)\vee \cdots \vee P(x_n),$$

相同，因为当且仅当 $P(x_1),P(x_2),\dots ,P(x_n)$ 中至少有一个为真时，这个析取为真。

例16 $\exists xP(x)$ 的真值是多少，其中 $P(x)$ 表示语句 “$x^2>10$”，并且论域由不超过 4 的正整数组成？

解 因为论域是 $1,2,3,4$，命题 $\exists xP(x)$ 等价于析取

$$P(1)\vee P(2)\vee P(3)\vee P(4).$$

由于 $P(4)$，即语句 “$4^2>10$”，为真，得出 $\exists xP(x)$ 为真。

量化和循环之间的联系 有时在确定量化的真值时，使用循环和搜索的思路是有帮助的。假设变量 $x$ 的论域中有 $n$ 个对象。为了确定 $\forall xP(x)$ 是否为真，我们可以循环遍历 $x$ 的全部 $n$ 个值，看看 $P(x)$ 是否始终为真。如果我们遇到一个 $P(x)$ 为假的值 $x$，那么我们已经证明 $\forall xP(x)$ 为假。否则，$\forall xP(x)$ 为真。为了判断 $\exists xP(x)$ 是否为真，我们循环遍历 $x$ 的 $n$ 个值，搜索一个使 $P(x)$ 为真的值。如果我们找到一个这样的 $x$，那么 $\exists xP(x)$ 为真。如果我们从未找到这样的 $x$，那么我们已经确定 $\exists xP(x)$ 为假。（请注意，这种搜索程序不适用于论域中有无限多个值的情况。然而，这仍然是思考量化真值的一种有用方式。）

限制论域的量词

一种简化的符号通常用于限制量词的论域。在这种符号中，变量必须满足的条件被包含在量词之后。如例 17 所示，我们还将在 2.1 节描述涉及集合成员关系的其他形式的这种符号。

例17 语句 $\forall x<0(x^2>0)$，$\forall y\ne 0(y^3\ne 0)$ 和 $\exists z>0(z^2=2)$ 分别是什么意思，其中论域在每种情况下都由实数组成？

解：语句 $\forall x<0(x^2>0)$ 表示对于每个实数 $x$，其中 $x<0$，有 $x^2>0$。也就是说，它表示 “The square of a negative real number is positive”。这个语句等价于 $\forall x(x<0\to x^2>0)$。

语句 $\forall y\ne 0(y^3\ne 0)$ 表示对于每个实数 $y$，其中 $y\ne 0$，有 $y^3\ne 0$。也就是说，它表示 “The cube of every nonzero real number is nonzero”。这个语句等价于 $\forall y(y\ne 0\to y^3\ne 0)$。

最后，语句 $\exists z>0(z^2=2)$ 表示存在一个实数 $z$，其中 $z>0$ 并且 $z^2=2$。也就是说，它表示 “There is a positive square root of 2”。这个语句等价于 $\exists z(z>0\wedge z^2=2)$。

请注意，全称量化的限制与条件语句的全称量化相同。例如，$\forall x<0(x^2>0)$ 是表达 $\forall x(x<0\to x^2>0)$ 的另一种方式。另一方面，存在量化的限制与合取的存在量化相同。例如，$\exists z>0(z^2=2)$ 是表达 $\exists z(z>0\wedge z^2=2)$ 的另一种方式。

量词的优先级

量词 $\forall$ 和 $\exists$ 的优先级高于命题演算中的所有逻辑运算符。例如，$\forall xP(x)\vee Q(x)$ 是 $\forall xP(x)$ 和 $Q(x)$ 的析取。换句话说，它表示 $(\forall xP(x))\vee Q(x)$，而不是 $\forall x(P(x)\vee Q(x))$。

绑定变量

当一个量词作用于变量 $x$ 时，我们说该变量的这个出现是绑定的。如果变量的某个出现没有被量词绑定或没有被赋值为特定值，那么这个变量被称为自由的。所有在命题函数中出现的变量必须被绑定或被赋值为特定值，才能将它变为命题。这可以通过使用全称量词、存在量词和赋值的组合来完成。

一个逻辑表达式中应用量词的部分称为该量词的范围。因此，如果一个变量位于该公式中所有量词的作用范围之外，它就是自由的。

例18 在语句 $\exists x(x+y=1)$ 中，变量 $x$ 被存在量词 $\exists x$ 绑定，但变量 $y$ 是自由的，因为它没有被量词绑定，也没有被赋值给这个变量。这说明了在语句 $\exists x(x+y=1)$ 中，$x$ 是绑定的，但 $y$ 是自由的。

在语句 $\exists x(P(x)\wedge Q(x))\vee \forall xR(x)$ 中，所有变量都是绑定的。第一个量词 $\exists x$ 的作用范围是表达式 $P(x)\wedge Q(x)$，因为 $\exists x$ 仅作用于 $P(x)\wedge Q(x)$，而不作用于语句的其余部分。同样地，第二个量词 $\forall x$ 的作用范围是表达式 $R(x)$。也就是说，存在量词 $\exists$ 绑定了 $P(x)\wedge Q(x)$ 中的变量 $x$，而全称量词 $\forall x$ 绑定了 $R(x)$ 中的变量 $x$。请注意，我们可以将语句写成两个不同的变量 $x$ 和 $y$，如 $\exists x(P(x)\wedge Q(x))\vee \forall yR(y)$，因为两个量词的作用范围不重叠。读者应该意识到，在常用表达中，同一个字母通常用于表示由不同量词绑定且作用范围不重叠的变量。

涉及量词的逻辑等价

在 1.3 节中，我们介绍了复合命题的逻辑等价的概念。我们可以将这一概念扩展到涉及谓词和量词的表达式。

定义 3 涉及谓词和量词的语句在无论用何谓词替换这些语句并且对这些命题函数中的变量使用何论域的情况下，都具有相同的真值，当且仅当如此时，它们是逻辑等价的。我们使用符号 $S\equiv T$ 来表示两个涉及谓词和量词的语句 $S$ 和 $T$ 是逻辑等价的。

例 19 说明了如何证明两个涉及谓词和量词的语句是逻辑等价的。

例19 证明 $\forall x(P(x)\wedge Q(x))$ 和 $\forall xP(x)\wedge \forall xQ(x)$ 是逻辑等价的（其中始终使用相同的论域）。这种逻辑等价表明我们可以将全称量词分配到合取中。此外，我们还可以将存在量词分配到析取中。然而，我们不能将全称量词分配到析取中，也不能将存在量词分配到合取中。（见练习 52 和 53。）

解 为了证明这些语句是逻辑等价的，我们必须证明它们在任何情况下都具有相同的真值，无论谓词 $P$ 和 $Q$ 是什么，也无论使用何种论域。假设我们有特定的谓词 $P$ 和 $Q$，它们有一个共同的论域。我们可以通过两种方式证明 $\forall x(P(x)\wedge Q(x))$ 和 $\forall xP(x)\wedge \forall xQ(x)$ 是逻辑等价的。首先，我们证明如果 $\forall x(P(x)\wedge Q(x))$ 为真，那么 $\forall xP(x)\wedge \forall xQ(x)$ 也为真。其次，我们证明如果 $\forall xP(x)\wedge \forall xQ(x)$ 为真，那么 $\forall x(P(x)\wedge Q(x))$ 也为真。

首先，假设 $\forall x(P(x)\wedge Q(x))$ 为真。这意味着如果 $a$ 在论域中，那么 $P(a)\wedge Q(a)$ 为真。因此，$P(a)$ 为真并且 $Q(a)$ 也为真。因为 $P(a)$ 和 $Q(a)$ 对论域中的每个元素 $a$ 都为真，所以我们可以得出 $\forall xP(x)$ 和 $\forall xQ(x)$ 都为真。这意味着 $\forall xP(x)\wedge \forall xQ(x)$ 为真。

接下来，假设 $\forall xP(x)\wedge \forall xQ(x)$ 为真。因此，如果 $a$ 在论域中，那么 $P(a)$ 为真并且 $Q(a)$ 也为真（因为对于论域中的所有元素 $P(x)$ 和 $Q(x)$ 都为真，在这里使用相同的 $a$ 值没有冲突）。因此，所有 $a$ 都满足 $P(a)\wedge Q(a)$ 为真。由此可得 $\forall x(P(x)\wedge Q(x))$ 为真。我们现在可以得出结论：

$$\forall x(P(x)\wedge Q(x))\equiv \forall xP(x)\wedge \forall xQ(x)$$。

否定量化表达式

例20 语句“There is an honest politician”和“All Americans eat cheeseburgers”的否定是什么？

解 设 $H(x)$ 表示“$x$ 是诚实的。”那么语句“There is an honest politician”表示为 $\exists xH(x)$，其中论域由所有政客组成。这个语句的否定是 $\neg \exists xH(x)$，这等价于 $\forall x\neg H(x)$。这个否定可以表达为 “Every politician is dishonest”。（注意：在英文中，语句 “All politicians are not honest” 是模棱两可的。在日常用法中，这个语句通常意味着 “Not all politicians are honest”。因此，我们不会用这个语句来表达这个否定。）

设 $C(x)$ 表示“$x$ 吃芝士汉堡。”那么语句“All Americans eat cheeseburgers”表示为 $\forall xC(x)$，其中论域由所有美国人组成。这个语句的否定是 $\neg \forall xC(x)$，这等价于 $\exists x\neg C(x)$。这个否定可以通过几种不同的方式表达，包括 “Some American does not eat cheeseburgers” 和 “There is an American who does not eat cheeseburgers”。

例21 语句 $\forall x(x^2>x)$ 和 $\exists x(x^2=2)$ 的否定是什么？

解 $\forall x(x^2>x)$ 的否定是语句 $\neg \forall x(x^2>x)$，这等价于 $\exists x\neg (x^2>x)$。这可以改写为 $\exists x(x^2\le x)$。$\exists x(x^2=2)$ 的否定是语句 $\neg \exists x(x^2=2)$，这等价于 $\forall x\neg (x^2=2)$。这可以改写为 $\forall x(x^2\ne 2)$。这些语句的真值取决于论域。

我们在例 22 中使用了量词的德摩根律。

例22 证明 $\neg \forall x(P(x)\to Q(x))$ 和 $\exists x(P(x)\wedge \neg Q(x))$ 是逻辑等价的。

解 根据全称量词的德摩根律，我们知道 $\neg \forall x(P(x)\to Q(x))$ 和 $\exists x(\neg (P(x)\to Q(x)))$ 是逻辑等价的。根据 1.3 节的第五逻辑等价表，我们知道 $\neg (P(x)\to Q(x))$ 与 $P(x)\wedge \neg Q(x)$ 对每个 $x$ 来说是逻辑等价的。因为我们可以在逻辑等价的公式中替换一个逻辑等价的表达式，因此得出 $\neg \forall x(P(x)\to Q(x))$ 和 $\exists x(P(x)\wedge \neg Q(x))$ 是逻辑等价的。

将英文翻译为逻辑表达式

例23 用谓词和量词表达 “Every student in this class has studied calculus” 这个语句。

解 首先，我们重写这个语句，以便能够清楚地识别适当的量词。这样做，我们得到：

“For every student in this class, that student has studied calculus.”

接下来，我们引入一个变量 $x$，使我们的语句变为：

“For every student $x$ in this class, $x$ has studied calculus.”

继续，我们引入 $C(x)$，表示语句“$x$ 已经学习了微积分。”因此，如果 $x$ 的论域由班上的学生组成，我们可以将这个语句翻译为 $\forall xC(x)$。

然而，还有其他正确的方法；不同的论域和其他谓词可以使用。我们选择的方法取决于我们想要进行的后续推理。例如，我们可能对比这个班级以外的更广泛的人群感兴趣。如果我们将论域更改为由所有人组成，我们需要将我们的语句表达为：

“For every person $x$, if person $x$ is a student in this class, then $x$ has studied calculus.”

如果 $S(x)$ 表示语句“人 $x$ 是这个班级的学生”，我们看到可以将我们的语句表示为 $\forall x(S(x)\to C(x))$。【注意！我们的语句不能表示为 $\forall x(S(x)\wedge C(x))$，因为这个语句表示所有人都是这个班的学生并且都学习了微积分！】

最后，当我们对除微积分以外的学科中的人群背景感兴趣时，我们可能更喜欢使用双变量量词 $Q(x,y)$ 来表示语句“学生 $x$ 学习了科目 $y$”。然后，我们将 $C(x)$ 替换为 $Q(x,\text{calculus})$，以两种方法中的任何一种来获得 $\forall xQ(x,\text{calculus})$ 或 $\forall x(S(x)\to Q(x,\text{calculus}))$。

例24 用谓词和量词表达语句 “Some student in this class has visited Mexico” 和 “Every student in this class has visited either Canada or Mexico”。

解 语句 “Some student in this class has visited Mexico” 的意思是：

“There is a student in this class with the property that the student has visited Mexico.”

我们可以引入一个变量 $x$，使我们的语句变为：

“There is a student $x$ in this class having the property that $x$ has visited Mexico.”

我们引入 $M(x)$，表示语句“$x$ 已经去过墨西哥。”如果 $x$ 的论域由班上的学生组成，我们可以将这个第一个语句翻译为 $\exists xM(x)$。

然而，如果我们对班级以外的人感兴趣，我们以不同的方式看待这个语句。我们的语句可以表示为：

“There is a person $x$ having the properties that $x$ is a student in this class and $x$ has visited Mexico.”

在这种情况下，变量 $x$ 的论域由所有人组成。我们引入 $S(x)$ 表示“$x$ 是这个班级的学生。”我们的解法变为 $\exists x(S(x)\wedge M(x))$，因为语句是说存在一个人 $x$ 是这个班级的学生并且已经去过墨西哥。【注意！我们的语句不能表示为 $\exists x(S(x)\to M(x))$，因为当 $x$ 不在班级中时，$S(x)\to M(x)$ 成为 $F\to T$ 或 $F\to F$，两者都为真。】

同样地，第二个语句可以表示为：

“For every $x$ in this class, $x$ has the property that $x$ has visited Mexico or $x$ has visited Canada.”

（注意：我们假设是包含性的“或”，而不是排他性的“或”。）我们让 $C(x)$ 表示“$x$ 已经去过加拿大。”根据我们之前的推理，我们看到如果 $x$ 的论域由班级中的学生组成，第二个语句可以表示为 $\forall x(C(x)\vee M(x))$。然而，如果 $x$ 的论域由所有人组成，我们的语句可以表示为：

“For every person $x$, if $x$ is a student in this class, then $x$ has visited Mexico or $x$ has visited Canada.”

在这种情况下，语句可以表示为 $\forall x(S(x)\to (C(x)\vee M(x)))$。

我们可以使用两个变量的谓词 $V(x,y)$ 来表示“$x$ 已经去过国家 $y$”，代替使用 $M(x)$ 和 $C(x)$ 来表示 $x$ 已经去过墨西哥和 $x$ 已经去过加拿大。这样，$V(x,\text{Mexico})$ 和 $V(x,\text{Canada})$ 将具有与 $M(x)$ 和 $C(x)$ 相同的含义，并且可以在我们的答案中替换它们。如果我们在处理涉及不同国家的人时工作，我们可能更喜欢使用这种双变量的方法。然而，为了简洁起见，我们将继续使用单变量谓词 $M(x)$ 和 $C(x)$。

在系统规格说明中使用量词

在 1.2 节中，我们使用命题来表示系统规格说明。然而，许多系统规格说明涉及谓词和量词。例 25 说明了这一点。

使用谓词和量词来表达系统规格说明 “Every mail message larger than one megabyte will be compressed” 和 “If a user is active, at least one network link will be available”。

解 设 $S(m,y)$ 为 “Mail message $m$ is larger than $y$ megabytes”，其中变量 $x$ 的论域为所有邮件，并且变量 $y$ 是一个正实数，设 $C(m)$ 表示 “Mail message $m$ will be compressed”。那么规格说明 “Every mail message larger than one megabyte will be compressed” 可以表示为 $\forall m(S(m,1)\to C(m))$。

设 $A(u)$ 表示 “User $u$ is active”，其中变量 $u$ 的论域为所有用户，设 $S(n,x)$ 表示 “Network link $n$ is in state $x$”，其中 $n$ 的论域为所有网络链接，并且 $x$ 的论域为网络链接的所有可能状态。那么规格说明 “If a user is active, at least one network link will be available” 可以表示为 $\exists uA(u)\to \exists nS(n,\text{available})$。

来自路易斯·卡罗尔的例子

路易斯·卡罗尔（实际上是以笔名写作的 C. L. Dodgson），爱丽丝梦游仙境 的作者，也是几部关于符号逻辑的作品的作者。他的书包含许多使用量词的推理例子。例 26 和 例 27 来自他的书 符号逻辑；该书中的其他例子可以在本节末尾的练习中找到。这些例子展示了如何使用量词来表达各种类型的语句。

例26 考虑这些语句。前两个被称为前提，第三个被称为结论。整个集合被称为一个论证。

•	“All lions are fierce.”
•	“Some lions do not drink coffee.”
•	“Some fierce creatures do not drink coffee.”

（在 1.6 节中，我们将讨论结论是否是前提的有效结果。在这个例子中，它是。）设 $P(x),Q(x),R(x)$ 分别为语句 “$x$ is a lion”， “$x$ is fierce”，以及 “$x$ drinks coffee。”假设论域由所有生物组成，用量词以及 $P(x),Q(x),R(x)$ 表达这些语句。

解 我们可以将这些语句表达为：

$$\forall x(P(x)\to Q(x)).$$

$$\exists x(P(x)\wedge \neg R(x)).$$

$$\exists x(Q(x)\wedge \neg R(x)).$$

注意，第二个语句不能表示为 $\exists x(P(x)\to \neg R(x))$。原因是 $P(x)\to \neg R(x)$ 当 $x$ 不是狮子时总为真，因此 $\exists x(P(x)\to \neg R(x))$ 只要存在一个生物不是狮子就为真，即使每只狮子都喝咖啡。同样，第三个语句也不能表示为 $\exists x(Q(x)\to \neg R(x))$。

例27 考虑这些语句，前三个是前提，第四个是一个有效的结论。

•	“All hummingbirds are richly colored.”
•	“No large birds live on honey.”
•	“Birds that do not live on honey are dull in color.”
•	“Hummingbirds are small.”

设 $P(x),Q(x),R(x),S(x)$ 分别为语句 “x is a hummingbird,” “x is large,” “x lives on honey,” 和 “x is richly colored.” 假设论域由所有鸟类组成，用量词以及 $P(x),Q(x),R(x),S(x)$ 来表达论证中的这些语句。

解：我们可以将论证中的语句表达为：

$$\forall x(P(x)\to S(x)).$$

$$\neg \exists x(Q(x)\wedge R(x)).$$

$$\forall x(\neg R(x)\to \neg S(x)).$$

$$\forall x(P(x)\to \neg Q(x)).$$

（注意，我们假设 “small” 与 “not large” 相同，并且 “dull in color” 与 “not richly colored” 相同。）要证明第四个语句是前三个语句的有效结论，我们需要使用 1.6 节中讨论的推理规则。

逻辑编程

一种重要类型的编程语言是为使用谓词逻辑规则进行推理而设计的。Prolog（源自Programming in Logic），由从事人工智能领域的计算机科学家于20世纪70年代开发，是此类语言的一个例子。Prolog 程序包括由两种语句组成的一组声明，Prolog facts 和 Prolog rules。Prolog facts 通过指定满足这些谓词的元素来定义谓词。Prolog rules 用于使用 Prolog facts 已经定义的谓词来定义新的谓词。例 28 说明了这些概念。

例28 考虑一个 Prolog 程序，该程序包含一些事实，告诉它每门课的老师和学生注册了哪些课程。该程序使用这些事实来回答有关教授哪些学生的查询。这样的程序可以使用谓词 instructor(p, c) 和 enrolled(s, c) 来表示教授 $p$ 是课程 $c$ 的授课教师，并且学生 $s$ 注册了课程 $c$。例如，Prolog 程序中的事实可能包括：

instructor(chan, math273)
instructor(patel, ee222)
instructor(grossman, cs301)
enrolled(kevin, math273)
enrolled(juana, ee222)
enrolled(juana, cs301)
enrolled(kiko, math273)
enrolled(kiko, cs301)

（使用小写字母表示条目，因为 Prolog 将以大写字母开头的名称视为变量。）

一个新的谓词 teaches(p, s)，表示教授 $p$ 教授学生 $s$，可以通过 Prolog 规则定义为：

teaches(P, S) :- instructor(P, C), enrolled(S, C)

这意味着 teaches(p, s) 为真，当且仅当存在课程 $c$ 使得教授 $p$ 是课程 $c$ 的授课教师，且学生 $s$ 注册了课程 $c$。（注意，逗号用于表示 Prolog 中谓词的连接；分号用于表示谓词的析取。）

Prolog 使用给定的事实和规则来回答查询。例如，使用列出的事实和规则，查询

?enrolled(kevin, math273)

会产生响应

yes

因为 enrolled(kevin, math273) 作为输入提供的事实。

查询

?enrolled(X, math273)

会产生响应

kevin
kiko

为了生成这个响应，Prolog 确定了所有可能的 $X$ 值，使得 enrolled(X, math273) 作为 Prolog 事实被包括在内。同样，为了找到教授 Juana 所注册课程的所有教授，我们使用查询：

?teaches(X, juana)

这个查询返回

patel
grossman