5.1.2 谓词演算公式

为了发展数学的逻辑基础, 我们需要一种逻辑, 它具有比命题演算更强的表达力. 为刻画多数数学对象的性质和这些对象间的关系, 谓词演算是必须的.

1. 谓词

被研究的对象包含在一个集合中,即包含在个体区域 (或全域) $X$ 中,例如,这个区域可以是自然数集 $\mathbb{N}$ . 个体的性质,例如,“ $n$ 是素数”,以及个体间的关系,例如, “ $m$ 小于 $n$ ”,被认为是谓词.个体区域 $X$ 上的 $n$ 位谓词乃是一个指派 $P:X^n\to$ $\{\mathrm{F},\mathrm{T}\}$ ,它对每个 $n$ 个体组派定一个真值. 于是上面引进的自然数集上的谓词是 1 位 (或一元) 谓词和 2 位 (或二元) 谓词.

2. 量词

谓词逻辑的一个特色是使用量词,即全域量词或 “对于每个” 量词 $\mathrm{\forall }$ ,以及存在量词或 “对于某个” 量词 $\mathrm{\exists }$ . 如果 $P$ 是一元谓词,那么语句 “ $P\left(x\right)$ 对于 $X$ 中的每个 $x$ 真” 表示为 $\mathrm{\forall }xP\left(x\right)$ ,并且语句 “在 $X$ 中存在 $P\left(x\right)$ 真的 $x$ ” 表示为 $\mathrm{\exists }xP\left(x\right)$ . 对于一元谓词 $P$ 应用量词就给出一个语句. 如果 (例如) $\mathbb{N}$ 是自然数个体区域,而 $P$ 表示 (一元) 谓词 “ $n$ 是素数”,那么 $\mathrm{\forall }nP\left(n\right)$ 是假语句,而 $\mathrm{\exists }nP\left(n\right)$ 是真语句.

3. 谓词演算公式

谓词演算公式是用归纳方式定义的:

(1) 如果 $x_1,\cdots ,x_n$ 是个体变量 (变量在个体变量域上运行),而 $P$ 是一个 $n$ 位谓词符号, 那么

$$\begin{array}{}\text{(5.21)}& P\left(x_1,\cdots ,x_n\right)\text{是一个公式 (基本公式).}\end{array}$$

(2)如果 $A$ 和 $B$ 是公式,那么

$$\begin{array}{}\text{(5.22)}& \left(\mathrm{\neg }A\right),\left(A\wedge B\right),\left(A\vee B\right),\left(A\Rightarrow B\right),\left(A\iff B\right),\left(\mathrm{\forall }xA\right)\text{以及}\left(\mathrm{\exists }xA\right)\end{array}$$

也是公式.

将命题变量看作零位谓词, 那么命题演算可以看作谓词演算的一个部分. 如果个体变量 $x$ 是 $\mathrm{\forall }x$ 或 $\mathrm{\exists }x$ 中的一个变量,或 $x$ 是在这些类型量词的范围中出现,那么 $x$ 在公式中的出现是约束的; 不然 $x$ 在这个公式中的出现是自由的. 如果一个谓词逻辑公式不含有任何自由出现的个体变量, 那么称它为闭公式.

4. 谓词演算公式的解释

谓词演算公式的一个解释是一个由

• 一个集合 (个体区域),

• 一个指派 (对每个 $n$ 项谓词符号派定一个 $n$ 位谓词)

组成的对. 对于自由变量每个预先指定的值, 公式真值计算的概念与命题情形类似. 闭公式的真值是 $\mathrm{T}$ 或 $\mathrm{F}$ . 在公式含自由变量的情形,可以将它与使公式真值计算为真的个体的值相结合; 这些值在全域 (个体区域) 上形成某个关系 (参见第 444 页 5.2.3,1.).

• 设 $P$ 表示个体区域 $\mathbb{N}$ 上的 2 位关系 $\le$ ,这里 $\mathbb{N}$ 是自然数集,那么

• $P\left(x,y\right)$ 刻画所有满足 $x\le y$ ( $\mathbb{N}$ 上的 2 位或二元关系) 的自然数对(x, y)的集合; 这里 $x,y$ 是自由变量.

• $\mathrm{\forall }yP\left(x,y\right)$ 刻画 $\mathbb{N}$ 的仅由 0 组成的子集 (一元关系); 这里 $x,y$ 是约束变量.

• $\mathrm{\exists }x\mathrm{\forall }yP\left(x,y\right)$ 对应于语句 “存在最小的自然数”; 真值是真; 这里 $x,y$ 是约束变量.

5. 逻辑有效公式

若一个公式对于每个解释恒真, 则称为逻辑有效的(或是一个重言式). 公式的否定由下列的恒等式刻画:

$$\begin{array}{}\text{(5.23)}& \mathrm{\neg }\mathrm{\forall }xP\left(x\right)=\mathrm{\exists }x\mathrm{\neg }P\left(x\right)\text{ 或 }\mathrm{\neg }\mathrm{\exists }xP\left(x\right)=\mathrm{\forall }x\mathrm{\neg }P\left(x\right).\end{array}$$

应用 (5.23) 量词 $\mathrm{\forall }$ 和 $\mathrm{\exists }$ 可以互相由对方表示:

$$\begin{array}{}\text{(5.24)}& \mathrm{\forall }xP\left(x\right)=\mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }P\left(x\right)\text{ 或 }\mathrm{\exists }xP\left(x\right)=\mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }P\left(x\right).\end{array}$$

其他的量词演算恒等式是

$$\begin{array}{}\text{(5.25)}& \mathrm{\forall }x\mathrm{\forall }yP\left(x,y\right)=\mathrm{\forall }y\mathrm{\forall }xP\left(x,y\right),\end{array}$$$$\begin{array}{}\text{(5.26)}& \mathrm{\exists }x\mathrm{\exists }yP\left(x,y\right)=\mathrm{\exists }y\mathrm{\exists }xP\left(x,y\right),\end{array}$$$$\begin{array}{}\text{(5.27)}& \mathrm{\forall }xP\left(x\right)\wedge \mathrm{\forall }xQ\left(x\right)=\mathrm{\forall }x\left(P\left(x\right)\wedge Q\left(x\right)\right),\end{array}$$$$\begin{array}{}\text{(5.28)}& \mathrm{\exists }xP\left(x\right)\vee \mathrm{\exists }xQ\left(x\right)=\mathrm{\exists }x\left(P\left(x\right)\vee Q\left(x\right)\right).\end{array}$$

下列蕴涵也是有效的:

$$\begin{array}{}\text{(5.29)}& \mathrm{\forall }xP\left(x\right)\vee \mathrm{\forall }xQ\left(x\right)\Rightarrow \mathrm{\forall }x\left(P\left(x\right)\vee Q\left(x\right)\right),\end{array}$$$$\begin{array}{}\text{(5.30)}& \mathrm{\exists }x\left(P\left(x\right)\wedge Q\left(x\right)\right)\Rightarrow \mathrm{\exists }xP\left(x\right)\wedge \mathrm{\exists }xQ\left(x\right),\end{array}$$$$\begin{array}{}\text{(5.31)}& \mathrm{\forall }x\left(P\left(x\right)\Rightarrow Q\left(x\right)\right)\Rightarrow \left(\mathrm{\forall }xP\left(x\right)\Rightarrow \mathrm{\forall }xQ\left(x\right)\right),\end{array}$$$$\begin{array}{}\text{(5.32)}& \mathrm{\forall }x\left(P\left(x\right)\iff Q\left(x\right)\right)\Rightarrow \left(\mathrm{\forall }xP\left(x\right)\iff \mathrm{\forall }xQ\left(x\right)\right),\end{array}$$$$\begin{array}{}\text{(5.33)}& \mathrm{\exists }x\mathrm{\forall }yP\left(x,y\right)\Rightarrow \mathrm{\forall }y\mathrm{\exists }xP\left(x,y\right).\end{array}$$

这些蕴涵的逆并不成立,特别,我们要注意量词 $\mathrm{\forall }$ 和 $\mathrm{\exists }$ 不交换的事实 (最后给出的蕴涵其逆是假).

6. 约束谓词

将谓词限制于给定集合的子集常常是有用的. 例如, 将

$$\begin{array}{}\text{(5.34)}& \mathrm{\forall }x\in XP\left(x\right)\text{看作}\mathrm{\forall }\left(x\in X\Rightarrow P\left(x\right)\right)\text{的简短记号,}\end{array}$$

以及将

$$\begin{array}{}\text{(5.35)}& \mathrm{\exists }x\in XP\left(x\right)\text{看作}\mathrm{\exists }\left(x\in X\Rightarrow P\left(x\right)\right)\text{的简短记号.}\end{array}$$