嵌套量词

所谓嵌套，指的是一个量词处于另一个量词的作用范围内。如果我们只关注两个量词的情况，共有四种嵌套方式。假设一个任意的论域 $D$，包含 $n$ 个元素，以及一个含有两个变量的谓词 $P$。

我们已知：

$$\forall x \forall y P(x,y) \equiv \forall y \forall x P(x,y)$$

这类命题表示：对于从论域 $D$ 中任取的一对 $(x,y)$，$P(x,y)$ 都为真。

我们也知道：

$$\exists x \exists y P(x,y) \equiv \exists y \exists x P(x,y)$$

这类命题表示：我们可以从 $D$ 中至少选出一对 $(x,y)$，使得 $P(x,y)$ 为真。

现在，我们来讨论剩下的两种情况，逐一分析。

对所有 $x$，存在 $y$

我们来讨论存在量词位于全称量词作用范围内的场景，即：

$$\forall x \exists y P(x,y)$$

在这种情况下，该命题断言：对于论域中的每一个元素 $x$，都存在至少一个论域中的元素 $y$，使得 $P(x,y)$ 为真。下面我们通过几个例子来说明这种表达的实际含义。

例子

---

将论域设为所有现存的人，定义如下谓词：

• $L(x,y)$：$x$ 爱 $y$。

---

对该谓词进行量化：

• $\forall x \exists y L(x,y)$：每个人都至少爱一个人。

可以简写为：

• $\forall x \exists y L(x,y)$：人人都爱某人。

---

再次以所有现存的人作为论域，考虑以下谓词：

• $M(y,x)$：$y$ 是 $x$ 的母亲。

---

量化后得到：

• $\forall x \exists y M(y,x)$：每个人都有一个母亲。

---

考虑整数集作为论域，定义如下谓词：

• $I(x,y)$：$x + y = 0$。

现在对其进行量化：

• $\forall x \exists y I(x,y)$：每个整数都有一个加法逆元。

---

再考虑整数集作为论域，定义如下谓词：

• $S(x,y)$：$y = x^2$。

---

对其进行量化：

• $\forall x \exists y S(x,y)$：每个整数都有一个平方。

存在一个 $x$，使得对所有 $y$

接下来讨论全称量词位于存在量词作用范围内的场景，即：

$$\exists x \forall y P(x,y)$$

在这种情况下，该命题断言：论域中至少存在一个元素 $x$，使得对于论域中的每一个元素 $y$，$P(x,y)$ 都为真。下面我们通过一些例子来理解这种结构。

例子

考虑整数集作为论域，定义如下谓词：

• $M(x,y)$：$x \times y = y$。

对该谓词进行量化：

• $\exists x \forall y M(x,y)$：存在一个整数 $x$，当它与任意整数 $y$ 相乘时，结果仍为 $y$。

可以简写为：

• $\exists x \forall y M(x,y)$：整数具有乘法单位元。

我们熟知，乘法单位元是 1。

---

将论域设为所有现存的人，定义如下谓词：

• $L(x,y)$：$x$ 爱 $y$。

---

对其进行量化：

• $\exists x \forall y L(x,y)$：存在至少一个人，他爱所有人。

可以简洁地表述为：

• $\exists x \forall y L(x,y)$：有人爱所有人。

---

再次以所有现存的人作为论域，定义如下谓词：

• $F(x,y)$：$x$ 比 $y$ 更富有。

---

对其进行量化：

• $\exists x \forall y F(x,y)$：有人比所有人都富有。

测验

测试你对嵌套量词的理解。

多个论域

到目前为止，我们只讨论了多个变量来自同一论域的情形。但在许多实际情境中，谓词中的不同变量可能属于不同的论域。下面我们通过几个例子进一步说明这一点。

例子

以下是几个示例。

---

考虑“人”集合和“旅游景点”集合。

定义一个谓词如下：

• $P(x,y)$：$x$ 正计划今年夏天去参观 $y$。

---

注意：$x$ 属于“人”的集合，而 $y$ 属于“旅游景点”的集合。

对该谓词进行量化：

• $\forall x \exists y P(x,y)$：每个人都计划今年夏天去参观某个旅游景点。

现在换一种方式量化同一个谓词：

• $\exists y \forall x P(x,y)$：存在某个旅游景点，所有人都计划去参观。

• $\forall x \forall y P(x,y)$：每个人都计划去参观每一个旅游景点。

• $\exists x \exists y P(x,y)$：有人计划去参观某个旅游景点。

量词作为循环

假设有一个谓词 $P$ 和一个论域 $D$。我们可以将全称量词理解为遍历 $D$ 中的所有元素，并验证 $P$ 对每个元素都成立；类似地，存在量词可理解为遍历 $D$ 中的元素，确认至少有一个元素使 $P$ 成立。

我们定义两个集合如下：

• $A = \{$ Ahmad, John, Smith, Beth, Sara $\}$

• $B = \{$ Apple, Mango, Grapes, Melon, Banana $\}$

假设 $x \in A$，$y \in B$。定义一个谓词：

• $P(x,y)$：$x$ 喜欢吃 $y$。

运行以下代码，观察 $\forall x\forall y P(x,y)$、$\exists x\exists y P(x,y)$、$\forall x \exists y P(x,y)$ 以及 $\exists x \forall y P(x,y)$ 在什么条件下为真。你可以通过增减集合 $A$ 和 $B$ 中的元素来尝试修改代码。

1A = ["Ahmad", "John", "Smith", "Beth", "Sara"]
2B = ["Apple", "Mango", "Grapes", "Mellon", "Banana"]
3s=""
4print("\u2200x\u2200yP(x,y) is true if:")
5for x in A:
6    for y in B:
7        s+="P("+x+","+y+")\u2227"
8    s+="\n"
9print(s[:-2]+" is TRUE.")
10s="" 
11print("\n\u2203x\u2203yP(x,y) is true if:")
12for x in A:
13    for y in B:
14        s+="P("+x+","+y+")\u2228"
15    s+="\n"
16print(s[:-2]+" is TRUE.")
17s="" 
18print("\n\u2200x\u2203yP(x,y) is true if:")
19for x in A:
20    s+="("
21    for y in B:
22        s+="P("+x+","+y+")\u2228"
23    s=s[:-1]+")\u2227\n"
24print(s[:-2]+" is TRUE.")
25s="" 
26print("\n\u2203x\u2200yP(x,y) is true if:")
27for x in A:
28    s+="("
29    for y in B:
30        s+="P("+x+","+y+")\u2227"
31    s=s[:-1]+")\u2228\n"
32print(s[:-2]+" is TRUE.")

解释

• 第1–2行： 我们指定了变量 x 和 y 的论域。

• 第3–9行： 我们遍历 $A$ 和 $B$，生成证明 $\forall x\forall y P(x,y)$ 为真的命题。

• 第10–16行： 我们遍历 $A$ 和 $B$，生成证明 $\exists x\exists y P(x,y)$ 为真的命题。

• 第17–24行： 我们遍历 $A$ 和 $B$，生成证明 $\forall x \exists y P(x,y)$ 为真的命题。

• 第25–32行： 我们遍历 $A$ 和 $B$，生成证明 $\exists x \forall y P(x,y)$ 为真的命题。