1.4. 谓词和量词
本节我们将介绍一种表达能力更强的逻辑，即谓词逻辑。我们将看到谓词逻辑如何用来表达数学和计算机科学中各种语句的意义，并允许我们推理和探索对象之间的关系。
谓语
对于语句“xxx大于3”。我们可以用P(x)P(x)P(x)表示语句“xxx大于3”，其中PPP表示谓词“大于3”，而xxx是变量。语句P(x)P(x)P(x)也可以说成是命题函数PPP在xxx的值。一旦给变量xxx赋一个值，语句P(x)P(x)P(x)就称为命题并具有真值。
形式为P(x1,x2,…,xn)P(x_1,x_2,\dots,x_n)P(x1,x2,…,xn)的语句是命题函数PPP在nnn元组(x1,x2,…,xn)(x_1,x_2,\dots,x_n)(x1,x2,…,xn)的值，PPP也称为n\bm{n}n位谓词 或n\bm{n}n元谓词
前置条件和后置条件
谓词还可以用来验证计算机程序，也就是证明当给定合法输入时计算机程序总是能产生所期望的输出。描述合法输入的语句叫做前置条件，而程序运行的输出应满足的条件称为后置条件。
量词
处理谓词和量词的逻辑领域称为谓词演算。
全称量词
许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真，这一特定域称为变量的论域或全体域，时常简称为域。对特定论域而言P(x)P(x)P(x)的全称量化是这样一个命题：它断言P(x)P(x)P(x)对xxx在其论域中的所有值均为真。论域对顶了变脸xxx所有可能取的值。当我们改变论域时，P(x)P(x)P(x)的全称量化的意义也随之改变。在使用全称量词是必须制定论域，否则语句的全称量化就是无定义的。
全称量化
P(x)P(x)P(x)的全称量化是语句：“P(x)P(x)P(x)对xxx在其论域中的所有值均为真。”
符号∀ xP(x)\forall\,xP(x)∀xP(x)表示P(x)P(x)P(x)的全称量化，其中∀\forall∀称为全称量词。命题∀ xP(x)\forall\,xP(x)∀xP(x)读做“对所有xxx，P(x)P(x)P(x)”或“对每个xxx，P(x)P(x)P(x)”。
一个使P(x)P(x)P(x)为假的个体称为∀ xP(x)\forall\,xP(x)∀xP(x)的反例。
通常，我们会做一个隐式的假设，即量词的论域均为非空的。注意如果论域为空的。注意如果论域为空，那么∀xP(x)\forall xP(x)∀xP(x)对任何命题函数P(x)P(x)P(x)都为真，因为论域中没有单个xxx使P(x)P(x)P(x)为假。
存在量化
P(x)P(x)P(x)的存在量化命题是：“论域中存在一个个体xxx满足P(x)P(x)P(x)”。
我们用符号∃xP(x)\exist xP(x)∃xP(x)表示P(x)P(x)P(x)的存在量化，其中∃\exist∃称为存在量词。
当使用∃xP(x)\exist xP(x)∃xP(x)时必须制定一个论域。
唯一量词
符号∃!\exist !∃!或∃1\exist_1∃1表示唯一量词，∃!xP(x)\exist !xP(x)∃!xP(x)或∃1xP(x)\exist_1xP(x)∃1xP(x)表示“存在一个唯一的xxx使得P(x)P(x)P(x)为真”。
约束论域的量词
在限定一个量词的论域时经常IXUS会采用简写的表示法。在这个表示法中，变量必须满足的条件直接放在量词的后面。如下：
∀ x<0(x2>0)\forall\:x < 0(x^2 > 0)∀x<0(x2>0)，这里的论域为x<0x < 0x<0
∃ z>0(z2=2)\exist\:z>0(z^2=2)∃z>0(z2=2)，这里的论域为z>0z>0z>0
量词的优先级
量词∀\forall∀和∃\exist∃比命题演算中的所有逻辑运算符都具有更高的优先级。
∀ xP(x)∨Q(x)\forall\:xP(x)\lor Q(x)∀xP(x)∨Q(x)是∀ xP(x)\forall\:xP(x)∀xP(x)和Q(x)Q(x)Q(x)的析取。
变量绑定
当量词作用于变量xxx时，我们说次变量的这次出现为约束的。如果没有量词约束或设置为某一特定值，则称为是自由的。
语句∃x(x+y=1)\exist x(x + y = 1)∃x(x+y=1)，变量xxx受存在量词∃x\exist x∃x约束，但是变量yyy是自由的。
涉及量词的逻辑等价式
定义3
涉及谓词和量词的语句是逻辑等价的当且仅当无论用什么谓词代入这些语句，也无论为这些命题函数里的变量指定什么论域，它们都有相同的真值。我们用S≡TS \equiv TS≡T表示涉及谓词和量词的两个语句SSS和TTT是逻辑等价的。
例如：∀ x(P(x)∧Q(x))≡∀ xP(x)∧∀ xQ(x)\forall\:x(P(x)\land Q(x)) \equiv \forall\:xP(x)\land\forall\:xQ(x)∀x(P(x)∧Q(x))≡∀xP(x)∧∀xQ(x)
量化表达式的否定
对于“班上每个学生都学过一门微积分课”，这个语句的全称量化命题是：∀ xP(x)\forall\:xP(x)∀xP(x)，其中P(x)P(x)P(x)为“xxx学过一门微积分课”。
只要班上有一个学生没有学过微积分，那么以上命题就不成立。这一语句的否定命题就是**“并非班上每一个学生都学过一门微积分课”**，即：∃ x¬P(x)\exist\:x\lnot P(x)∃x¬P(x)
注意“班上每个学生都学过一门微积分课”的否定命题不是：“班上每个学生都没有学过一门微积分课”
∀ xP(x)\forall\:xP(x)∀xP(x) 的否定命题是：∃ x¬P(x)\exist\:x\lnot P(x)∃x¬P(x)
这个例子说明了下面的等价关系
¬∀ xP(x)≡∃ x¬P(x)¬∃ xQ(x)≡∀ x¬Q(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}¬∀xP(x)¬∃xQ(x)≡∃x¬P(x)≡∀x¬Q(x)
量词的否定规则称为量词的德·摩根律
否定等价语句何时为真何时为假¬∃xP(x)\lnot\exist xP(x)¬∃xP(x)∀x¬P(x)\forall{x}\lnot P(x)∀x¬P(x)对于每个xxx,P(x)P(x)P(x)为假存在一个xxx,使P(x)P(x)P(x)为真¬∀xP(x)\lnot\forall xP(x)¬∀xP(x)∃x¬P(x)\exist{x}\lnot P(x)∃x¬P(x)存在一个xxx,使$P(x)为假对于每个xxx,P(x)P(x)P(x)为真
语句到逻辑表达式的翻译
例1：
语句“班上的每个学生都学过微积分”。如何翻译为逻辑表达式？
首先重写此语句，使得能很清楚的确定所要使用的合适的量词。重写后的语句为：“对班上的每一个学生，该学生学过微积分”，
然后引入变量xxx，语句变为“对班上的每一个学生xxx，xxx学过微积分”。
然后引入谓词C(x)C(x)C(x)表示语句“xxx学过微积分”。
如果xxx的论域是班上的学生，我们可以将语句翻译为 ∀xC(x)\:\forall{x}C(x)∀xC(x)
如果S(x)S(x)S(x)表示语句“xxx在这个班上”，则表达式可写为∀x(S(x)→C(x))\forall x(S(x) \to C(x))∀x(S(x)→C(x))
注意不能表示为∀x(S(x)∧C(x))\forall x(S(x) \land C(x))∀x(S(x)∧C(x))，因为这表示每个xxx都是班上的学生并且学过微积分。
我们倾向于使用双变量谓词Q(x,y)Q(x,y)Q(x,y)表示语句“学生xxx学过课程yyy”，我们可以把C(x)C(x)C(x)替换成Q(x,微积分)Q(x,\text{微积分})Q(x,微积分)。得到∀xQ(x,微积分)\forall xQ(x,\text{微积分})∀xQ(x,微积分)或∀x(S(x)→Q(x,微积分))\forall x(S(x) \to Q(x,\text{微积分}))∀x(S(x)→Q(x,微积分))。
例2：
用谓词和量词表达语句“这个班上的某个学生去过墨西哥”和“这个班上的每个学生或去过加拿大，或去过莫斯哥”。
语句“这个班上的某个学生去过墨西哥”的意思是“在这个班上有个学生，他去过墨西哥”。引入变量xxx，因此语句变成“在这个班上有个学生xxx，他去过墨西哥”。引入谓词M(x)M(x)M(x)表示语句“xxx去过墨西哥”。如果论域为这个班上的学生，则可以翻译为∃ xM(x)\exist\:xM(x)∃xM(x)。
如果xxx的论域为所有人，我们引入谓词S(x)S(x)S(x)表示“xxx是这个班上的一个学生”。答案就变成了∃ x(S(x)∧M(x))\exist\:x(S(x)\land M(x))∃x(S(x)∧M(x))，它表示“存在一个人xxx，他是班上的学生并且他去过墨西哥”。
注意语句不能表示为∃ x(S(x)→M(x))\exist\:x(S(x)\to M(x))∃x(S(x)→M(x))，它表示当有一个人不在这个班里时也是真的。（参见p→qp\to qp→q的真值表）当S(x)S(x)S(x)为FFF时，无论M(x)M(x)M(x)为何值，表达式的真值都为真。
第二个语句表示成“对于班上的每一个xxx，xxx具有这样的特性：xxx去过加拿大或xxx去过墨西哥”。令谓词C(x)C(x)C(x)表示语句“xxx去过加拿大”。如果论域为这个班的学生，则第二个语句可以表达为：∀ x(C(x)∨M(x))\forall\:x(C(x)\lor M(x))∀x(C(x)∨M(x))。
如果xxx的论域时所有人，我们的语句就可以表示成：
“对于每一个人xxx，如果xxx在这个班，则xxx去过加拿大或去过墨西哥”。此时语句表示成∀ x(S(x)→(C(x)∨M(x)))\forall\:x(S(x)\to(C(x)\lor M(x)))∀x(S(x)→(C(x)∨M(x)))，这里的S(x)S(x)S(x)是C(x)∨M(x)C(x)\lor M(x)C(x)∨M(x)的充分条件。
注意这里要理解题意，题目的意思是“只要是这个班上的学生，那么他要么去过加拿大要么去过墨西哥”，并不是“去过加拿大或去过墨西哥的人都是这个班上的同学。”
系统规范说明中量词的使用
每封大于1MB的邮件会被压缩
如果一个用户处于活动状态，那么至少有一条网络链路是有效的
令S(m,y)S(m,y)S(m,y)表示是“邮件mmm大于yyyMB”,其中变量xxx的论域是所有邮件。变量yyy是一个正实数；令C(m)C(m)C(m)表示“邮件会被压缩”，那么表达式就可以写为：∀ m(S(m,1)→C(m))\forall\:m(S(m,1) \to C(m))∀m(S(m,1)→C(m))
A(u)A(u)A(u)表示“用户u处于活动状态”，S(n,x)S(n,x)S(n,x)表示“网络链路nnn处于xxx状态”。那么 2 可以表示为 ∃ uA(u)→∃ nS(n,有效)\exist\:uA(u) \to \exist\:nS(n,\text{有效})∃uA(u)→∃nS(n,有效)
习题部分
空量化
DEFINITION 空量化（null quantification）
当受量词约束的变元没有出现在语句的某一部分时，称之为空量化。如∀xA\forall x A∀xA，其中xxx在AAA中不作为自由变元出现。
空量化规则，其中xxx在AAA中不作为自由变元出现。假设论域非空。
(∀xP(x))∨A≡∀x(P(x)∨A)(∀xP(x))∧A≡∀x(P(x)∧A)(∃xP(x))∨A≡∃x(P(x)∨A)(∃xP(x))∧A≡∃x(P(x)∧A)∀x(A→P(x))≡A→∀xP(x)∃x(A→P(x))≡A→∃xP(x)∀x(P(x)→A)≡∃xP(x)→A∃x(P(x)→A)≡∀xP(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}(∀xP(x))∨A(∀xP(x))∧A(∃xP(x))∨A(∃xP(x))∧A∀x(A→P(x))∃x(A→P(x))∀x(P(x)→A)∃x(P(x)→A)≡∀x(P(x)∨A)≡∀x(P(x)∧A)≡∃x(P(x)∨A)≡∃x(P(x)∧A)≡A→∀xP(x)≡A→∃xP(x)≡∃xP(x)→A≡∀xP(x)→A