离散数学（二）—

离散数学（二）——一阶逻辑

离散数学的前半部分，大抵都是对“命题”的数学结构化描述。一阶逻辑在命题逻辑公式的基础上，通过引入一些其他的符号，完善了对具体-抽象类型命题的描述与判断。

一、基本概念

1.个体与谓词

首先，我们要细分原子命题的结构。原子命题本身是对一个事物性质的直接描述、或是对几个事物间关系的判断，这里的“事物”就被称为个体。个体通常可以替换为其他的实例，这种不确定性使之具有“变量”的意味，我们以小写字母 $𝑥, 𝑦, 𝑧 \dots$ 来表示个体，称为个体变量。

定义 1.（谓词）

对个体进行性质或关系的判断，称为谓词。谓词是从个体变量到真值的映射，因而具有“函数”的意味。我们通常用大写字母

𝑃, 𝑄, 𝑅 \dots

表示谓词，并在其后的括号中填入个体变量。例如

𝑃 (𝑥)

表示“

𝑥

具有性质

𝑃

”。

谓词必须作用于个体变量上，但个体变量的数量不限。这样，如果要表示“ $𝑥, 𝑦$ 具有关系 $𝑄$ ”，就可以形式化地表示为 $𝑄 (𝑥, 𝑦)$ 。一个谓词能作用的个体数目称为元数，元数为 $𝑛$ 的谓词称为 $𝑛$ 元谓词。

注 1.（一阶与高阶）

谓词也可以作用在谓词、函数、公式之类之上，但这不属于一阶逻辑的范畴。一阶谓词只作用在个体上；可以作用在谓词等对象上的谓词称为高阶谓词。

个体变量自然可以拥有具体的赋值，称为个体常量，常以 $𝑎, 𝑏, 𝑐 \dots$ 表示。比如 $𝑃 (𝑥)$ 可以具体例化为 $𝑃 (𝑎)$ 。

2.量词

具体应用时，常常要说明是否是全体个体都符合谓词，这就引入了量词。其一是全称量词，以 $\forall$ 表示。例如，要表示“全体的 $𝑥$ 都有性质 $𝑃$ ”，就符号化为 $\forall 𝑥 𝑃 (𝑥)$ 。这种命题称为全称命题。

其二是存在量词，以 $\exists$ 表示。例如，要表示“部分的 $𝑥$ 都有性质 $𝑃$ ”，就符号化为 $\exists 𝑥 𝑃 (𝑥)$ 。这种命题称为存在命题。全称命题和存在命题统称为量化命题。

注 2.（量词的作用范围）

一阶逻辑中，量词也只允许作用于个体变量上，不允许作用于谓词上。

3.论域与特征谓词

就像上述所说，个体变量的“变量”意味、谓词的“函数”意味，是我们必须限定个体变量的“范围”，这类似于限定函数的定义域。对个体变量所限定的范围，就称为这个个体变量的论域。

注 3.

例如，命题“所有自然数都大于等于

0

”，可以符号化为

\forall 𝑥 𝑃 (𝑥)

。其中

𝑥

表示自然数，

𝑃 (𝑥)

表示“

𝑥

大于等于

0

”，那么

𝑥

的论域就是自然数集。

就像是函数的定义域，论域自然可以是其他论域的子集，但扩大论域显然极有可能使原来的命题失效。为此，必须要多引入一个谓词，以限定论域的范围，这个谓词称为特征谓词。

注 4.

还是以上面为例，命题“所有自然数都大于等于

0

”，如果

𝑥

的论域是实数集，

𝑃 (𝑥)

表示“

𝑥

大于等于

0

”，那么必须引入额外的谓词

𝑄 (𝑥)

表示“

𝑥

是自然数

0

”以限定

𝑥

的范围，这个谓词就是特征谓词。此时公式符号化为

\forall 𝑥 (𝑄 (𝑥) \to 𝑃 (𝑥))

。

二、一阶逻辑公式的基本概念

1.逻辑符号与非逻辑符号

与命题逻辑公式类似，为了定义一阶逻辑公式——通常简称为一阶公式或公式——首先必须要区分公式中的所有符号。在公式中，符号分为逻辑符号与非逻辑符号。

逻辑符号集中包括：

(1)逻辑运算符 $\neg, \land, \lor, \to, \leftrightarrow$ ，量词符号 $\forall, \exists$ ，和辅助表明运算顺序的左右圆括号 $(,)$ ，以及多元谓词中分隔各变量的逗号 $,$ ；
(2)个体变量集，例如 $𝑥, 𝑦, 𝑧 \dots$ ，这个集合单独记为 $𝑉$ 。

非逻辑符号集，记为 $ℒ︀$ ，包括：

(1)个体常量集，例如 $𝑎, 𝑏, 𝑐 \dots$ ；
(2)谓词符号，例如 $𝑃, 𝑄, 𝑅 \dots$ ；
(3)函数符号，例如 $𝑓, 𝑔, ℎ \dots$ ，出现时常以算术运算符 $+, -, \times, 𝛁 \cdot \dots$ 出现。

2.项与公式

与多项式中的项相似，公式中的项是变量与常量通过函数耦合构造的较复杂的个体。

定义 2.（项的额归纳定义）

在给定非逻辑符号集 $ℒ︀$ 和个体变量集 $𝑉$ 的情况下，公式的项是：

归纳基： $ℒ︀$ 中的个体常量和 $𝑉$ 中的个体变量都是项；
归纳步：对 $ℒ︀$ 中的任意 $𝑛$ 元函数 $𝑓$ ，若 $𝑡_{1}, 𝑡_{2}, \dots, 𝑡_{𝑛}$ 是项，那么 $𝑓 (𝑡_{1}, 𝑡_{2}, \dots, 𝑡_{𝑛})$ 也是项。

公式则是子公式通过逻辑运算符号和量词符号耦合构造的较复杂公式，而原子公式是仅由谓词生成的不可再分的简单公式。

定义 3.（公式的归纳定义）

在给定非逻辑符号集 $ℒ︀$ 和个体变量集 $𝑉$ 的情况下，公式是：

归纳基：对 $ℒ︀$ 中的任意 $𝑛$ 元谓词 $𝐹$ ，若 $𝑡_{1}, 𝑡_{2}, \dots, 𝑡_{𝑛}$ 是项，那么 $𝐹 (𝑡_{1}, 𝑡_{2}, \dots, 𝑡_{𝑛})$ 是公式，并且是原子公式；
归纳步：若 $𝑥$ 是个体变量， $𝐴, 𝐵$ 是公式，那么： $(\neg 𝐴), (𝐴 \land 𝐵), (𝐴 \lor 𝐵), (𝐴 \to 𝐵), (𝐴 \leftrightarrow 𝐵), \forall 𝑥 𝐴, \exists 𝑥 𝐴$ 都是公式。

上述归纳步中的七个公式形式，分别称为否定式、合取式、析取式、蕴涵式、双蕴含式、全称量词公式、存在量词公式，其中后二者合称为量词公式。

3.辖域，自由变量和约束变量

假设有公式 $𝐴 = \forall 𝑥 𝐵$ ，那么个体变量 $𝑥$ 称为量词 $\forall 𝑥$ 的指示变量，称子公式 $𝐵$ 为这个量词的辖域或作用域。

如果个体变量 $𝑥$ 在 $𝐴$ 中的一处出现，是在以自己为指示变量的量词公式的辖域(即 $𝐵$ )中，那么称之为约束出现。否则称为自由出现。

如果个体变量 $𝑥$ 在 $𝐴$ 中的所有出现都是约束出现，那么称 $𝑥$ 是 $𝐴$ 的约束变量。否则称为自由变量。即 $𝑥$ 只要有一个或以上自由出现，就是自由变量。

如果一个公式没有自由变量，那么将公式称为闭公式或句子。

在上述的例子中，将全称量词 $\forall$ 替换为存在量词 $\exists$ ，也是一样的。

有时为了避免一个变量既约束出现又自由出现，我们会对公式做约束变量改名，或者自由变量替换，这两种方法的结果殊途同归，但约束变量改名更加保险。依然以 $𝐴 = \forall 𝑥 𝐵$ 为例，约束变量改名是指：将指示变量 $𝑥$ 、与 $𝐵$ 中自由出现的 $𝑥$ ，都替换为一个不在 $𝐴$ 中自由出现的个体变量 $𝑦$ 。

注 5.

需要注意的是，对于同一个位置的

𝑥

，在

𝐴

中约束出现的

𝑥

在

𝐵

中不一定是约束出现！例如，

𝐴 = \forall 𝑥 𝐵 = \forall 𝑥 (𝐹 (𝑥) \to \forall 𝑧 𝐺 (𝑧))

，其中

𝐵 = 𝐹 (𝑥) \to \forall 𝑧 𝐺 (𝑧)

，

𝑥

在

𝐴

中约束出现，在

𝐵

中却是自由出现。

在上述的例子中，将 $\forall$ 替换为 $\exists$ ，也是一样的。

三、一阶逻辑公式的等值式

1.基本等值式

与命题逻辑公式相同，基本逻辑等值式也能完全用在一阶公式上。在这里复习一下基本逻辑等值式：

表 1 基本逻辑等值式模式

序号	名称	等值式
1	同一律	$\begin{matrix} 𝐴 \land 1 \equiv 𝐴 \\ 𝐴 \lor 0 \equiv 𝐴 \end{matrix}$
2	零律	$\begin{matrix} 𝐴 \land 0 \equiv 0 \\ 𝐴 \lor 1 \equiv 1 \end{matrix}$
3	矛盾律	$𝐴 \land (\neg 𝐴) \equiv 0$
4	排中律	$𝐴 \lor (\neg 𝐴) \equiv 1$
5	双重否定律	$\neg (\neg 𝐴) \equiv 𝐴$
6	幂等律	$\begin{matrix} 𝐴 \land 𝐴 \equiv 𝐴 \\ 𝐴 \lor 𝐴 \equiv 𝐴 \end{matrix}$
7	交换律	$\begin{matrix} 𝐴 \land 𝐵 \equiv 𝐵 \land 𝐴 \\ 𝐴 \lor 𝐵 \equiv 𝐵 \lor 𝐴 \end{matrix}$
8	结合律	$\begin{matrix} 𝐴 \land (𝐵 \land 𝐶) \equiv (𝐴 \land 𝐵) \land 𝐶 \\ 𝐴 \lor (𝐵 \lor 𝐶) \equiv (𝐴 \lor 𝐵) \lor 𝐶 \end{matrix}$
9	分配律	$\begin{matrix} 𝐴 \land (𝐵 \lor 𝐶) \equiv (𝐴 \land 𝐵) \lor (𝐴 \land 𝐶) \\ 𝐴 \lor (𝐵 \land 𝐶) \equiv (𝐴 \lor 𝐵) \land (𝐴 \lor 𝐶) \end{matrix}$
10	吸收律	$\begin{matrix} 𝐴 \land (𝐴 \lor 𝐵) \equiv 𝐴 \\ 𝐴 \lor (𝐴 \land 𝐵) \equiv 𝐴 \end{matrix}$
11	德摩根律	$\begin{matrix} \neg (𝐴 \land 𝐵) \equiv (\neg 𝐴) \lor (\neg 𝐵) \\ \neg (𝐴 \lor 𝐵) \equiv (\neg 𝐴) \land (\neg 𝐵) \end{matrix}$
12	蕴涵等值式	$𝐴 \to 𝐵 \equiv \neg 𝐴 \lor 𝐵$
13	蕴涵等值式	$𝐴 \leftrightarrow 𝐵 \equiv (𝐴 \to 𝐵) \land (𝐵 \to 𝐴)$

除此之外，量词的引入使得一阶公式还有其他的逻辑等值式。如下列：

表 2 一阶公式逻辑等值式模式

序号	名称	等值式
14	量词交换等值式	$\begin{matrix} \forall 𝑥 \forall 𝑦 𝐹 (𝑥, 𝑦) \equiv \forall 𝑦 \forall 𝑥 𝐹 (𝑥, 𝑦) \\ \exists 𝑥 \exists 𝑦 𝐹 (𝑥, 𝑦) \equiv \exists 𝑦 \exists 𝑥 𝐹 (𝑥, 𝑦) \end{matrix}$
15	量词分配等值式	$\begin{matrix} \forall 𝑥 (𝐴 (𝑥) \land 𝐵 (𝑥)) \equiv \forall 𝑥 𝐴 (𝑥) \land \forall 𝑥 𝐵 (𝑥) \\ \exists 𝑥 (𝐴 (𝑥) \lor 𝐵 (𝑥)) \equiv \exists 𝑥 𝐴 (𝑥) \lor \exists 𝑥 𝐵 (𝑥) \end{matrix}$
16	消除量词等值式	$\begin{matrix} \forall 𝑥 𝐴 (𝑥) \equiv 𝐴 (𝑎_{1}) \land 𝐴 (𝑎_{2}) \land \dots \land 𝐴 (𝑎_{𝑛}) \\ \exists 𝑥 𝐴 (𝑥) \equiv 𝐴 (𝑎_{1}) \lor 𝐴 (𝑎_{2}) \lor \dots \lor 𝐴 (𝑎_{𝑛}) \end{matrix}$
17	量词否定等值式	$\begin{matrix} \neg \forall 𝑥 𝐴 (𝑥) \equiv \exists 𝑥 \neg 𝐴 (𝑥) \\ \neg \exists 𝑥 𝐴 (𝑥) \equiv \forall 𝑥 \neg 𝐴 (𝑥) \end{matrix}$
18	量词辖域扩张收缩	$\begin{aligned} \forall 𝑥 (𝐴 (𝑥) \land 𝐵) & \equiv \forall 𝑥 𝐴 (𝑥) \land 𝐵 \\ \forall 𝑥 (𝐴 (𝑥) \lor 𝐵) & \equiv \forall 𝑥 𝐴 (𝑥) \lor 𝐵 \\ \forall 𝑥 (𝐴 (𝑥) \to 𝐵) & \equiv \exists 𝑥 𝐴 (𝑥) \to 𝐵 \\ \forall 𝑥 (𝐵 \to 𝐴 (𝑥)) & \equiv 𝐵 \to \forall 𝑥 𝐴 (𝑥) \\ \exists 𝑥 (𝐴 (𝑥) \land 𝐵) & \equiv \exists 𝑥 𝐴 (𝑥) \land 𝐵 \\ \exists 𝑥 (𝐴 (𝑥) \lor 𝐵) & \equiv \exists 𝑥 𝐴 (𝑥) \lor 𝐵 \\ \exists 𝑥 (𝐴 (𝑥) \to 𝐵) & \equiv \forall 𝑥 𝐴 (𝑥) \to 𝐵 \\ \exists 𝑥 (𝐵 \to 𝐴 (𝑥)) & \equiv 𝐵 \to \exists 𝑥 𝐴 (𝑥) \end{aligned}$

2.前束范式

前束范式是一种结构规整的公式。假设以 $𝑄$ 表示量词符号即 $\forall$ 或 $\exists$ ， $𝐴$ 表示一个不含量词的公式，那么前束范式的形式为：

𝑄_{1} 𝑥_{1} 𝑄_{2} 𝑥_{2} \dots 𝑄_{𝑘} 𝑥_{𝑘} 𝐴

也就是，所有的量词都被束缚在公式的前面。前束范式对于之后的推理中的例化泛化非常重要。为了从任意公式化为前束范式的形式，可以遵从以下步骤：

(1)使用约束变量改名，使所有个体变量要么约束出现、要么自由出现。并且，应使每个量词的指示变量均不相同；
(2)使用量词否定等值式，将否定逻辑符放到量词之后；
(3)使用量词辖域扩张等值式，将量词放到所有逻辑运算符之前。

可以对变换之后的公式做检查。一种简单的检查方式是，除指示变量外，对于相同位置的个体变量，原先是约束出现的变换后还是约束出现，原先是自由出现的变换后还是自由出现。如非如此，必有错误。

四、一阶逻辑公式的真值

这一部分的理论内容是较为晦涩的，这里尽量以通俗的语言来描述，避免书本上的公理化描述。

1.个体变量指派函数

公式本身是一种抽象语言，在只给定“公式”这一字符串的时候，它只有数学上的意义。但是，我们显然可以将一些具体情况应用在给定的公式上，而且可以有多种不同的具体情况，这就是通俗意义上的公式的解释，并以 $ℳ︀$ 表示。也就是说，一个抽象的公式可以有多个具体的解释。

注 6.

正确的说法是，解释是对一阶公式的非逻辑符号集的解释，而不是对公式的解释。

解释亦称为模型。非逻辑符号集的解释首先需要包含一个非空的论域，以及至少一个谓词。其次还可以包含个体常量和函数，但并非必须。

上述的四个非逻辑符号也都有自己的解释，用 $⟦ \dots ⟧$ 表示。比如，如果非逻辑符号集中有谓词 $𝐹$ ，那么此谓词在这个论域上的解释就记为 $⟦ 𝐹 ⟧$ 。

正如之前所说，论域可以简单类比理解为公式的定义域。那么，解释中的个体常量，就相当于选取论域(定义域)中的一个具体的对象，将其赋值到公式中的某个个体变量中。这称为个体变量指派函数，记为 $𝜎$ 。例如，如果将公式中的 $𝑥$ 指派为解释的论域中的一个元素 $𝑎$ ，就记为 $𝜎 (𝑥) = 𝑎$ 。

指派函数的变换的定义略显奇怪：

定义 4.（指派函数的变换）

设 $𝑥$ 是个体变量集中的一个变量， $𝑑$ 是解释的论域中的一个元素，那么对任意个体变量集中的一个变量 $𝑦$ ，其指派函数记为 $𝜎 [𝑥 \mapsto 𝑑]$ ，定义为：

𝜎 [𝑥 \mapsto 𝑑] (𝑦) = {\begin{cases} 𝑑 \\ 𝑦 = 𝑥 \\ 𝜎 (𝑦) \\ 𝑦 \neq 𝑥 \end{cases}

乍一看不知所云，但笔者的通俗理解是：这个变换函数是在将 $𝑥$ 指派为 $𝑑$ 的情况下(即中括号中的内容)，对 $𝑦$ 的指派。

注 7.

例如，假设

𝜎 (𝑥) = 𝑎, 𝜎 (𝑦) = 𝑏

，那么

𝜎 [𝑥 \mapsto 𝑑] (𝑦) = 𝜎 (𝑦) = 𝑏

。这个函数似乎有些啰嗦！目前还不太清楚这个函数的意义，但请看之后的内容。

2.公式的真值

在上述定义中，个体变量指派函数是将一个个体变量指派为论域中的一个个体常量。 $𝜎$ 函数中也可以对一个公式起作用，此时它就类似于命题逻辑中的真值赋值函数。即， $𝜎 (𝐴)$ 只能等于 $𝟎$ 或 $𝟏$ 。

要判断公式的真值，就应当从其原子公式下手。一个原子公式的真值，取决于谓词的解释中是否含有被指派的变量(仅是一种浅显的说法！不一定完全正确！)。

注 8.

比如，假设 $ℳ︀$ 的论域 $𝐷 = {𝑎, 𝑏, 𝑐}$ ，而一个一元谓词的解释 $⟦ 𝐹 ⟧ = {𝑎, 𝑏}$ ，一个二元谓词的解释 $⟦ 𝐺 ⟧ = {⟨ 𝑎, 𝑏 ⟩, ⟨ 𝑎, 𝑐 ⟩}$ 。那么：

\begin{matrix} 𝜎 [𝑥 \mapsto 𝑎] (𝐹 (𝑥)) = 𝟏 \\ 𝜎 [𝑥 \mapsto 𝑏] (𝐹 (𝑥)) = 𝟏 \\ 𝜎 [𝑥 \mapsto 𝑐] (𝐹 (𝑥)) = 𝟎 \\ 𝜎 [𝑥 \mapsto 𝑎] [𝑦 \mapsto 𝑎] (𝐺 (𝑥, 𝑦)) = 𝟎 \\ 𝜎 [𝑥 \mapsto 𝑎] [𝑦 \mapsto 𝑏] (𝐺 (𝑥, 𝑦)) = 𝟏 \\ 𝜎 [𝑥 \mapsto 𝑎] [𝑦 \mapsto 𝑐] (𝐺 (𝑥, 𝑦)) = 𝟏 \end{matrix}

这里可以结合上面“指派函数的变换”理解。

当与量词结合后，就应当应用消除量词等值式进行展开。

注 9.

还是以上例为例。 $𝜎 [𝑥 \mapsto 𝑎] (𝐹 (𝑥)) = 𝟏$ 这个形式略显麻烦，不妨记为 $𝐹 (𝑎) \equiv 𝟏$ ¹¹ 严格来说这样写是不符合等值式的形式的，但是不至于混淆的情况下如此简写也是可以的。那么，假设公式 $𝐴 = \forall 𝑥 𝐹 (𝑥)$ ，那么 $𝐴$ 就应当展开为：

𝐹 (𝑎) \land 𝐹 (𝑏) \land 𝐹 (𝑐) \equiv 𝟏 \land 𝟏 \land 𝟎 \equiv 𝟎

即

𝜎 (𝐴) = 𝟎

。

3.公式的分类

假设有一个公式 $𝐴$ ，其非逻辑符号集为 $ℒ︀$ ，那么：

(1)如果 $𝐴$ 在 $ℒ︀$ 中的任意解释、在任意个体变量指派函数下，其真值都为真，那么称为永真式，也称为普遍有效式；
(2)如果 $𝐴$ 在 $ℒ︀$ 中的任意解释、在任意个体变量指派函数下，其真值都为假，那么称为矛盾式；
(3)如果 $𝐴$ 不是矛盾式，那么称 $𝐴$ 是可满足的。

有时候利用命题逻辑中的永真式或矛盾式可以快速判断公式是一个永真式或矛盾式。比如， $𝑝 \to (𝑞 \to 𝑝)$ 是一个命题逻辑永真式，那么 $\forall 𝑥 𝐹 (𝑥) \to (\exists 𝑥 𝐺 (𝑥) \to \forall 𝑥 𝐹 (𝑥))$ 也必是永真式。但这不是充分必要的，命题逻辑形式不是永真式的，一阶逻辑形式的也可能是永真的。

五、一阶逻辑的推理论证

一阶逻辑的推理、论证的定义与命题逻辑是相似的，不再赘述。命题逻辑的推理规则也完全适用于一阶逻辑。我们复习一下九个基本推理规则：

(1)假言推理： $𝐴 \to 𝐵, 𝐴 ⟹ 𝐵$
(2)假言易位： $𝐴 \to 𝐵, \neg 𝐵 ⟹ \neg 𝐴$
(3)合取规则： $𝐴, 𝐵 ⟹ 𝐴 \land 𝐵$
(4)化简规则： $𝐴 \land 𝐵 ⟹ 𝐴$
(5)附加规则： $𝐴 ⟹ 𝐴 \lor 𝐵$
(6)析取三段论规则： $\neg 𝐴, 𝐴 \lor 𝐵 ⟹ 𝐵$
(7)假言三段论规则： $𝐴 \to 𝐵 ， 𝐵 \to 𝐶 ⟹ 𝐴 \to 𝐶$
(8)双蕴涵推理规则： $𝐴 \leftrightarrow 𝐵 ⟹ 𝐴 \to 𝐵, 𝐴 \leftrightarrow 𝐵 ⟹ 𝐵 \to 𝐴$
(9)等值置换规则：对所有一阶逻辑等值式模式 $𝐴 \equiv 𝐵$ ，都存在 $𝐴 ⟹ 𝐵$ 和 $𝐵 ⟹ 𝐴$ 。

由于量词的引入，一阶逻辑的推理还有四个额外的推理规则：

(10)全称例化规则，又称为全称量词消除规则。这条规则包含两种形式。其一，若 $𝑥$ 不在 $𝐴 (𝑥)$ 中的任意量词 $\forall 𝑦$ 或 $\exists 𝑦$ 的辖域中自由出现，那么：

\forall 𝑥 𝐴 (𝑥) ⟹ 𝐴 (𝑦)

其二，这个形式没有特殊的要求， $𝑐$ 可以是任意个体常量：

\forall 𝑥 𝐴 (𝑥) ⟹ 𝐴 (𝑐)

(11)全称泛化规则，又称为全称量词引入规则。若 $𝑥$ 不在 $𝐴 (𝑦)$ 中约束出现、并且不是 $𝐴 (𝑦)$ 中除 $𝑦$ 之外的其他自由变量，以及 $𝑦$ 不是前提公式、或消除附加前提前的附加前提公式中的自由变量，那么：

𝐴 (𝑦) ⟹ \forall 𝑥 𝐴 (𝑥)

(12)存在例化规则，又称为存在量词消除规则。若 $𝐴 (𝑥)$ 只含有自由变量 $𝑥$ 、没有其他自由变量，并且将要替换 $𝑥$ 的个体常量 $𝑐$ 在前提、 $𝐴 (𝑥)$ 以及所有之前的论证公式序列中都不出现，那么：

\exists 𝑥 𝐴 (𝑥) ⟹ 𝐴 (𝑐)

(13)存在泛化规则，又称为存在量词引入规则。这个规则的要求不高，只要将要替换 $𝑐$ 的 $𝑥$ 不在 $𝐴 (𝑐)$ 中出现即可：

𝐴 (𝑐) ⟹ \exists 𝑥 𝐴 (𝑥)

应当注意全称、存在例化中前提公式的形式。 $\forall 𝑥 𝐴 (𝑥)$ ， $\exists 𝑥 𝐴 (𝑥)$ 都是前束范式，在使用这两个规则之前必须首先将公式化为前束范式。

与命题逻辑相似，当推理的结论是蕴涵式时，应当使用附加前提法；当推理的结论是否定式时，应当使用反证法。在使用附加前提法时，务必注意全称泛化的使用条件。