本章记录一阶逻辑的符号化、公式和解释。量词、个体域和谓词的作用域是最容易出错的地方。

一阶逻辑命题符号化

为达到表达出个体和总体之间的内在联系和数量关系，需要引入量词。这就是一阶逻辑所研究的内容，其也称作一阶谓词逻辑或谓词逻辑。

一阶逻辑命题符号化的三个要素：个体词、谓词和量词。

1. 个体词是指所研究对象中可以独立存在的、具体的或抽象的客体。表示具体或特定的客体的个体词称作个体常项，一般用小写字母 $a,b,c$ 表示；将表示抽象的或泛指的个体词称为个体变项，常用 $x,y,z$ 等表示。

称个体变项的取值范围为个体域或论域，其可以是有穷集合也可以是无穷集合。由宇宙间一切事物组成的个体域称为全总个体域，若没有特别指明采用的个体域，则视为使用全总个体域。

2. 谓词是用来刻画个体词性质及个体词之间相互关系的词，常用 $F,G,H$ 等表示。表示具体关系或性质的谓词称作谓词常项，表示抽象的或泛指的性质或关系的谓词称作谓词变项。无论是谓词常项还是谓词变项都用大写字母 $F,G,H$ 表示。

含 $n$ 个命题变项的谓词 $P$ 称作 $n$ 元谓词，记作 $P(x_1,x_2,\ldots,x_n)$。 其是以个体域为定义域，以 $\lbrace0,1\rbrace$ 为值域的 $n$ 元函数或关系。

将不带个体变项的谓词称作零元谓词。当 $F,G,H$ 为谓词常项时，零元谓词为命题。任何命题都可以表示为零元谓词，即命题为特殊的谓词。

3. 量词是指表示个体常项或变相之间数量关系的词，有全称量词和存在量词。$\forall xF(x)$ 表示个体域中所有个体 $x$ 都有性质 $F$，$\exists xF(x)$ 表示个体域中存在个体 $x$ 有性质 $F$。这两者可以混合使用。

当使用全总个体域时，我们引入谓词 $M(x)$ 用于限制个体域，称为特性谓词。

$\rightarrow$ 和 $\wedge$ 的使用场景要分清楚。

在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。

同一个命题，在不同个体域中的真值也可能不同。

未指明个体域时应使用全总个体域。

命题中表示性质和关系的谓词，分别符号化为一元和 $n$ 元谓词。

当多个谓词出现时，它们的顺序不能随意调换。

命题的符号化形式不唯一。

一阶逻辑公式及其解释

一阶语言，是用于一阶逻辑的形式语言，一阶逻辑是建立在一阶语言上的逻辑体系。一阶语言本身是由抽象符号构成的，可以根据需要被解释成各种具体的含义。有多种形式的一阶语言。

个体常项、个体变项、函数、谓词、量词、联结词、括号与逗号、个体常项符号、函数符号和谓词符号称作非逻辑符号，个体变相符号、量词符号、联结词符号和括号与逗号称作逻辑符号。

设 $L$ 是一个非逻辑符号集合，由 $L$ 生成的一阶语言 $\mathscr{L}$ 的字母表包括以下符号：

非逻辑符号：

• (1) $L$ 中的个体常项符号，比如 $a,b,c$。
• (2) $L$ 中的函数符号，比如 $f,g,h$。
• (3) $L$ 中的谓词符号，比如 $F,G,H$。

逻辑符号：

• (1) 个体变项符号，比如 $x,y,z$。
• (2) 量词符号
• (3) 联结词符号
• (4) 括号与逗号

$\mathscr{L}$ 的项定义如下：

• (1) 个体常项符号与个体变项符号是项
• (2) 若 $\phi(x_1,x_2,\ldots,x_n)$ 是 $n$ 元函数符号， $t_1,t_2,\ldots,t_n$ 是项，则 $\phi(t_1,t_2,\ldots,t_n)$ 是项。
• (3) 所有项都是使用有限次(1)(2)得到的

设 $R(x_1,x_2,\ldots,x_n)$ 是 $\mathscr{L}$ 的 $n$ 元谓词符号， $t_1,t_2,\ldots,t_n$ 是 $\phi$ 的 $n$ 个项，则称 $R(t_1,t_2,\ldots,t_n)$ 为 $\mathscr{L}$ 的原子公式。

零元谓词不是原子公式。

$\mathscr{L}$ 的合式公式，也称谓词公式，简称公式，定义如下：

• (1) 原子公式是合式公式
• (2) 若 $A$ 是合式公式，则 $\neg A$ 是合式公式。
• (3) 若 $A,B$ 是合式公式，则 $A \vee B,A \wedge B,A \rightarrow B,A \leftrightarrow B$ 是合式公式。
• (4) 若 $A$ 是合式公式，则 $\forall xA,\exists xA$ 是合式公式。
• (5) 有限次运用(1)(2)(3)(4)得到的符号串是合式公式

$A,B$ 是元语言符号，表示任意的合式公式。

不同的一阶语言使用不同的 $L,$ 但它们构造合式公式的规则是一样的。我们不再特殊指明 $L$。

函数是个体到个体的映射，谓词是个体到真值的映射。

$L$ 不一定要包含全部 $3$ 种非逻辑符号，可以只包含其中一种或两种。若一种也不包含，则 $L=\emptyset,$ 无意义。当 $L$ 不包含谓词符号时， $\mathscr{L}$ 退化为命题逻辑中的语言。

在公式 $\forall xA$ 和 $\exists xA$ 中，称 $x$ 为指导变元，$A$ 为量词的辖域。在 $\forall x$ 和 $\exists x$ 的辖域中，$x$ 的所有出现都称作约束出现。$A$ 中不是约束出现的其他变项都称为自由出现。

例：指出下列公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。

• (1) $\forall x(F(x,y) \rightarrow G(x,z))$
• (2) $\forall (F(x) \rightarrow G(y)) \rightarrow \exists y (H(x) \wedge L(x,y,z))$

答案：(1) $x$ 是指导变元， $\forall$ 的辖域为 $A=(F(x,y) \rightarrow G(x,z)),$ 在 $A$ 中 $x$ 约束出现， $y,z$ 自由出现。

• (2) 前件量词 $\forall$ 的指导变元为 $x,$ 辖域为 $(F(x) \rightarrow G(y)),$ 后件指导变元为 $y,$ 辖域为 $(H(x) \wedge L(x,y,z))$。

(2) 中前件的 $x$ 与后件的 $x$ 不是同一个事物，只是两个不同的事物使用了同一个符号。

我们定义 $A(x_1,x_2,\ldots,x_n)$ 为 $x_1,x_2,\ldots,x_n$ 自由出现的公式， $\Delta$ 表示量词。

设 $A$ 是任意公式，若 $A$ 中不含自由出现的个体变项，称其为闭式。

要将 $r$ 个自由出现的个体变项的公式变成闭式至少要加上 $r$ 个量词。

$\mathscr{L}$ 中出现的公式是按照形成规则生成的符号串，没有实际含义。只有将其中变项用实际常项代替后，才有特定含义。

对公式中个体域、个体常项符号、函数符号、谓词符号的指定称作解释，指定自由出现的变量的值称作赋值。

设 $\mathscr{L}$ 是由 $L$ 生成的一阶语言，其解释 $I$ 由下面四部分组成：

• (1) 非空个体域 $D_I$。
• (2) 对每一个个体常项符号 $a \in L,\exists \overline{a} \in D_I,$ 称 $\overline{a}$ 为 $a$ 在 $I$ 中的解释。
• (3) 对每一个 $n$ 元函数符号 $f \in L,\exists n$ 元函数 $\overline{f}:D_I^n \rightarrow D_I,$ 称 $\overline{f}$ 为 $f$ 在 $I$ 中的解释。
• (4) 对每一个 $n$ 元谓词符号 $F \in L,\exists n$ 元谓词常项 $\overline{F},$ 称 $\overline{F}$ 为 $F$ 在 $I$ 中的解释。

赋值 $\sigma$：对每一个个体变项符号 $x$ 指定 $D_I$ 中的一个值 $\sigma(x)$。

设公式 $A$ ，规定在解释 $I$ 和赋值 $\sigma$ 下，取个体域 $D_I,$ 将 $a,f,F$ 换成 $\overline{a},\overline{f},\overline{F},$ 把自由生成的个体变项符号 $x$ 替换为 $\sigma(x),$ 操作后得到的公式记作 $A’$。称 $A’$ 为 $A$ 在 $I$ 下的解释，或 $A$ 在 $I$ 下被解释为 $A’$。

给定 $I$ 和 $\delta,$ 任何公式都能被解释为命题。若是闭式，则无需 $\sigma$。

设 $A$ 为一公式，若 $A$ 在任何解释和该解释下的任何赋值下均为真，则称 $A$ 为永真式，也称作逻辑有效式。若 $A$ 在任何解释和该解释下的任何赋值下均为假，则称 $A$ 为矛盾式，也称作永假式。若存在至少一个解释和该解释下的一个赋值使 $A$ 为真，则称 $A$ 是可满足式。

设 $A_0$ 含命题变项 $p_1,p_2,\ldots,p_n$ 的命题公式， $A_1,A_2,\ldots,A_n$ 有 $n$ 个谓词公式，用 $A_i$ 出处代替 $A_0$ 中的 $p_i,$ 称所得公式为 $A_0$ 的代换实例。

定理：重言式的代换示例都是永真式，矛盾式的代换示例都是矛盾式。

证明永真式时，先设出个体域、解释和赋值，然后慢慢分析。

判断永真式还是矛盾式时，先考虑是否是某个重言式或者矛盾式的代换示例，然后再取出解释和赋值。

下面整理一些容易漏条件的题目。

1. 通常在 $\forall$ 里用 $\rightarrow,$ 在 $\exists$ 里用 $\wedge$。

2. 数学公式不再重新符号化。

3. 将下列命题符号化。

• (1) 说有的火车比所有汽车都快是正确的
• (2) 个体域为 $R,$ 任给 $\epsilon>0,$ 存在 $\delta>0,$ 使得当 $|x-x_0|<\delta$ 时，均有 $|f(x)-f(x_0)|<\epsilon$。
• (3) 火车都比轮船快
• (4) 有的火车比有的汽车快
• (5) 不存在比所有火车都快的汽车
• (6) 说凡是汽车就比火车慢是不对的
• (7) 若所有的 $x$ 都具有性质 $F,$ 则所有的 $y$ 都有性质 $G$。
• (8) 若存在 $x$ 具有性质 $F,$ 则所有的 $y$ 都没有性质 $G$。
• (9) 不存在最大的自然数

答案：

• (1) $\exists x(F(x)\wedge \forall y(G(y) \rightarrow H(x,y)))$
• (2)

$$ \forall \epsilon (\epsilon>0 \rightarrow (\exists \delta(\delta>0 \wedge (|x-x_0|<\delta \rightarrow |f(x)-f(x_0)|<\epsilon)))) $$

• (3) $\forall x \forall y (F(x) \wedge G(y) \rightarrow H(x,y))$
• (4) $\exists x \exists y(F(x) \wedge G(y) \wedge H(x,y))$
• (5) $\neg \exists x(G(x) \wedge \forall y(F(y) \rightarrow H(x,y)))$
• (6) $\neg \forall x (G(x) \rightarrow \forall y(F(y) \rightarrow H(x,y)))$
• (7) $\forall xF(x) \rightarrow \forall yG(y)$。
• (8) $\exists xF(x) \rightarrow \forall y \neg G(y)$。
• (9) $\neg \exists x(F(x) \wedge \forall y(F(y) \rightarrow H(x,y))$。

4. 判断下列公式的类型。

• (1) $\forall x \exists yF(x,y) \rightarrow \exists x \forall yF(x,y)$。
• (2) $\exists x \forall yF(x,y) \rightarrow \forall y \exists xF(x,y)$。
• (3) $F(x) \rightarrow xF(x)$。
• (4) $\exists xF(x) \rightarrow F(x)$。

答案：

• (1) 是可满足式，但不是永真式。
• (2) 是永真式
• (3) 是可满足式，但不是永真式。
• (4) 是可满足式，但不是永真式。