数理逻辑 (2) 谓词逻辑

Posted on Edited on In , ,

Abstract. 从语义的角度来看谓词逻辑，对应书上的第四、第五章。因为听说 thu 没学 6789 章，猜测可能是难度比较大，故在这里断章。

基本概念 命题的形式化

相关定义

以下面两个命题为例。

  • 我是傻逼。
  • 接受礼物不等于我同意。

在命题逻辑当中这两句话属于原子命题，但是显然这些命题还可以继续分解。其中“我”，“接受礼物”和“我同意”在句子当中属于主体，“是傻逼”描述主体的性质，“不等于”描述多个主体之间的关系。从这个角度来剖析一个命题，得到谓词逻辑。

Definition 1. 命题中表示思维对象的词，称为个体词或个体常项。

如果其指代对象是不定的，称为个体变项或者个题变元。

Definition 2. 个体变项变化的范围称为论域，记作 $D$。一般默认论域是包含一切事物的最广的类[1]。

Definition 3. 从论域到真假的映射 $P : D \rightarrow \{T, F\}$ 称为谓词。当然也存在多元谓词，用映射的形式来表达就是 $P^n : D^n \rightarrow \{T, F\}$。

可以定义论域之间的函数，和习见的定义相同，$F : D \rightarrow D’$。注意和谓词不同的是，这里 $D’$ 不一定要是 $\{T, F\}$。

Definition 4. 对个体词所加的约束限制称为量词。

有两个最通用的量词，是全称量词 $\forall$ 和存在量词 $\exists$。从语义上来说，$(\forall x) P(x)$ 为真当且仅当对于论域中所有的 $x$ 都有 $P(x)$ 为真，$(\exists x) P(x)$ 为真当且仅当论域中至少有一个 $x$ 使得 $P(x)$ 为真。

Example. 我们形式化两句话。

  • 一切物质都是运动的。这句话结构类似于 $(\forall x) P(x)$。根据 $\forall$ 的优先级也可以写成 $\forall x (P(x))$，出于简便也可以写成 $(x) (P(x))$。
  • 存在一事物称为动物。这句话结构类似于 $(\exists x) Q(x)$。或者也可以写 $\exists x (Q(x))$。

这里的符号优先级很奇怪但是比较琐碎，这里不做讨论，我们一般会加括号到没有歧义为止，等到后续讨论语法的时候再细说。

受量词约束的变元称为约束变元，否则称为自由变元。量词约束的范围称为量词的辖域。以下面这个命题为例

$$
(\forall \varepsilon)((\exists \delta) P(\varepsilon, \delta))
$$

这里 $P(\varepsilon, \delta)$ 是 $(\exists \delta)$ 的辖域，$((\exists \delta) P(\varepsilon, \delta))$ 是 $(\forall \varepsilon)$ 的辖域。

合式公式

合式公式的构成方式不是唯一的，只需其语义有意义，含义唯一，下面给出一种方式。

Definition. 只有如下的式子才是合式公式（下文中出现的 $A, B$ 默认是合式公式，可以随时忽略最外层匹配的括号）：

  • 命题常项，命题变项和不含联结词的谓词是合式公式。
  • $\neg A$ 是合式公式。
  • 如果所有的变元 $x$ 在 $A, B$ 中同约束、同自由，那么 $A \odot B$ 是合式公式，其中 $\odot$ 是逻辑联结词。
  • $x$ 是 $A$ 中的自由变元，那么 $(\forall x) (A)$ 和 $(\exists x) (A)$ 是合式公式。

合式公式中的约束变量是 dummy variable。即

$$
(\forall x) P(x) = (\forall y) P(y)
$$

此外你可以看出全称量词 $\forall$ 是合取词 $\wedge$ 的推广，$\exists$ 是析取词 $\vee$ 的推广。换言之如果论域是有限域，那么 $(\forall x) P(x)$ 可以展开成 $P(x_1) \wedge \cdots \wedge P(x_n)$ 类似物。在考虑一个谓词公式的时候，我们常考虑其在所谓的 $\{1, 2\}$ 域上的展开形式来初步判断其正确性。

一些代表性句子的形式化方法

Example 1. 所有满足 $P$ 的 $x$ 都满足 $Q$。（比如所有有理数都是实数）

Answer.

$$
(\forall x) (P(x) \rightarrow Q(x))
$$

Example 2. 有的满足 $P$ 的 $x$ 也满足 $Q$。（比如有的实数是有理数）

Answer.

$$
(\exists x) (P(x) \wedge Q(x))
$$

Example 3. 对于 Peano 自然数，形式化如下语句：

  • 每个数有且仅有一个后继。
  • 不存在一个数的后继是 $0$。
  • 除 $0$ 外，每个数有且仅有一个前驱。

这里需要构造有且仅有，之前所谓的 $\exists !$ 在这里是不允许使用的。

Answer.

每个数有且仅有一个后继：

$$
(\forall x) ((\exists y) (y = \mathrm{suc}(x) \wedge (\forall z) (z = \mathrm{suc}(x) \rightarrow y = z)))
$$

不存在一个数的后继是 $0$：

$$
\neg (\exists x)(\mathrm{suc}(x) = 0)
$$

除 $0$ 外，每个数有且仅有一个前驱：

$$
(\forall x)(x \ne 0 \rightarrow (\exists y)(y = \mathrm{pre}(x) \wedge (\forall z)(z = \mathrm{pre}(x) \rightarrow y = z)))
$$

实际上这三句话可以拿来作为自然数的三条公理。

Example 4. $f(x)$ 在 $x_0$ 处连续。（用 $\varepsilon-\delta$ 语言表示）

Answer.

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

公式的解释和普遍有效性

在谓词逻辑下解释一个公式需要给定所有命题变项、自由个体变项、谓词和函数的真值。

Definition. 如果一个谓词公式在任意解释下都为真，那么称之为普遍有效的。如果其在某一解释下可为真，则称其为可满足的。否则称为不可满足的。

Example. 下面的几个谓词公式都是普遍有效的。

  1. $(\forall x) (P(x) \vee \neg P(x))$
  2. $(\forall x) P(x) \rightarrow P(y)$
  3. $(\forall x) P(x) \vee (\forall x) Q(x) \rightarrow (\forall x) (P(x) \vee Q(x))$

任给一个逻辑公式，判定它是否是一个普遍有效的逻辑公式是 NPC 的，参见 the Church-Turing thesis

等值和推理演算

等值公式

将谓词公式代入命题逻辑中的等值式，显然还是成立。因此这部分的公式我们不谈。

Theorem 1. 否定型等值式：

$$
\begin{aligned}
\neg (\forall x) P(x) = (\exists x) \neg P(x) \\
\neg (\exists x) P(x) = (\forall x) \neg P(x)
\end{aligned}
$$

证明只需要看 $\forall, \exists$ 的定义，故略去。

在有限论域上把量词展开，可以发现这实质上就是 De Morgan 律。

预告一下下方有混乱邪恶记号出现。

接下来是一些量词对联结词的分配律。

Theorem 2.1. 假设 $\Lambda$ 是全称量词或者存在量词，$\odot$ 是合取词或者析取词，那么

$$
(\Lambda x) (P(x) \odot q) = (\Lambda x) P(x) \odot q
$$

证明只需要考虑对解释中 $q$ 的真值分类讨论，然后考虑别的东西，故略去。

根据 $\rightarrow$ 的定义可以得到

$$
\begin{aligned}
(\forall x) (P(x) \rightarrow q) = (\exists x) P(x) \rightarrow q \\
(\forall x) (q \rightarrow P(x)) = q \rightarrow (\forall x) P(x)
\end{aligned}
$$

之类的东西，对于量词是 $\exists$ 的时候也是同理。

Theorem 2.2. $\forall$ 对 $\wedge$ 分配，$\exists$ 对 $\vee$ 分配。

$$
\begin{aligned}
(\forall x) (P(x) \wedge Q(x)) = (\forall x) P(x) \wedge (\forall x) Q(x) \\
(\exists x) (P(x) \vee Q(x)) = (\exists x) P(x) \vee (\exists x) Q(x)
\end{aligned}
$$

注意 $\forall$ 对 $\vee$ 是不分配的，$\exists$ 一侧同理。

Theorem 2.3. 通过变量易名也可实现量词的分配

$$
\begin{aligned}
(\forall x) (\forall y) (P(x) \wedge Q(y)) = (\forall x) P(x) \wedge (\forall x) Q(x) \\
(\exists x) (\exists y) (P(x) \vee Q(y)) = (\exists x) P(x) \vee (\exists x) Q(x)
\end{aligned}
$$

Hint. 这里的证明可以从右边推到左边，利用式 $(2)$ 做变量易名后用 Theorem 2.1 进行分配。

范式，Skolem 标准型

Definition. 假设 $\Lambda_1, …, \Lambda_n$ 是量词，$x_1, …, x_n$ 是个体变元，$M(x_1, …, x_n)$ 是不含量词的合适公式。称形如

$$
(\Lambda_1 x_1) \cdots (\Lambda_n x_n) M(x_1, …, x_n)
$$

的合式公式为前束范式，其中 $M$ 称为母式。

Theorem. 所有谓词公式都可以化为与之等值的前束范式。

存在一个显然的不断使用分配律的构造性证明，这里不写。

注意前束范式并不唯一。

在证明的过程中，我们可能并不需要「等值」的变换，只需要一个「同普遍有效」的变换，或从归结法的角度出发，只需要一个「同不可满足」的变换。（到了后面从语法角度研究的阶段，我们可能会把这种要求称为“可证等价”[2]），因此导出下面两种范式。有一个名词是 Skolem 标准型，不同的资料中既有指代第一种的又有指代第二种的，让人感到非常傻逼，所以我们暂时采用下面的区分方法。

$\exists-$前束范式

如果一个前束范式满足 $\exists$ 均在 $\forall$ 前面，至少有一个 $\exists$，且母式中没有自由变量，那么称其为 $\exists-$前束的。

我们从一个关键定理及一个构造来讲这件事情。

Theorem. 任意一个前束范式 $A$ 都可以化为一个 $\exists-$前束范式 $B$，满足 $A$ 普遍有效当且仅当 $B$ 普遍有效。

Construction.

首先所有的自由变量用 $\forall$ 来约束。接下来通过下面的构造来得到 $B$。

  1. 如果一个式子自身就是 $\exists-$前束的，那么不需要再做任何变换。

  2. 如果一个前束范式 $A(x_1, …, x_n)$ 的第一个量词不是 $\exists$，那么引入个体变项 $x_0$ 和谓词变项 $G(x)$，下式和它同普遍有效：

    $$
    (\exists x_0) ((G(x_0) \vee \neg G(x_0)) \wedge A(x_1, …, x_n))
    $$

  3. 如果一个前束范式形如

    $$
    (\exists x_1) \cdots (\exists x_i) (\forall y) P(x_1, …, x_i, y, x_{i+1}, x_n)
    $$

    其中 $P$ 是一个前束范式，$x_1, …, x_i, y$ 前面均没有量词，那么引入个体变项 $z$ 和 $i + 1$ 元谓词变项 $S$ 下式和它同普遍有效

    $$
    (\exists x_1) \cdots (\exists x_i) ((\exists y) (P(x_1, …, x_i, y, x_{i+1}, x_n) \wedge \neg S(x_1, …, x_i, y)) \vee (\forall z) S(x_1, …, x_i, z))
    $$

    接下来可以将 $(\exists y)$，$P$ 中的量词和 $(\forall z)$ 依次前置，得到一个前束范式，其中最后一个量词是 $(\forall z)$，这相当于把 $(\forall y)$ 搬到了最后面。

上面三条构造方法中只有 2 的证明比较复杂。主播已经想通了是为什么了，但是不想写了。

重复使用 1, 2 可以将所有的 $\forall$ 搬到最后。

Skolem 标准型

一个只含有 $\forall$ 的前束范式称为 Skolem 标准型。

Theorem. 任意谓词公式 $A$ 可以化成一个 Skolem 标准型 $B$，$A$ 和 $B$ 同不可满足。

Construction.

首先化为前束范式，接下来：

  1. 已经是 Skolem 标准型的式子无需变化。

  2. 如果第一个量词是 $\exists x$，那么直接扔掉 $\exists$ 即可。

  3. 如果前束范式形如

    $$
    (\forall x_1) \cdots (\forall x_i) (\exists y) P(x_1, …, x_i, y)
    $$

    将 $y$ 替换为一个未在 $P$ 中出现过的函数 $f: D^i \rightarrow D$，即

    $$
    (\forall x_1) \cdots (\forall x_i) P(x_1, …, x_i, f(x_1, …, x_i))
    $$

    这个公式和原来的公式同不可满足。

    这里你可以理解为对于任意的 $x_1, …, x_i$ 存在 $y$，那么 $y$ 依赖于前面 $x$ 的选取，因此我们用一个函数来表达这种依赖关系。

基本推理公式

基本的推理公式

$$
\begin{aligned}
(1) & (\forall x) P(x) \vee (\forall x) Q(x) \Rightarrow (\forall x)(P(x) \vee Q(x)) \\
(2) & (\exists x) (P(x) \wedge Q(x)) \Rightarrow (\exists x) P(x) \wedge (\exists x) Q(x) \\
(3) & (\forall x) (P(x) \rightarrow Q(x)) \Rightarrow (\forall x) P(x) \rightarrow (\forall x) Q(x) \\
(4) & (\exists x) (P(x) \rightarrow Q(x)) \Rightarrow (\exists x) P(x) \rightarrow (\forall x) Q(x) \\
(5) & (\forall x) (P(x) \rightarrow Q(x)) \wedge (\forall x) (Q(x) \rightarrow R(x)) \Rightarrow (\forall x) (P(x) \rightarrow R(x)) \\
(6) & (\forall x) (P(x) \rightarrow Q(x)) \wedge P(a) \Rightarrow Q(a) \\
(7) & (\forall x) (\forall y) P(x, y) \Rightarrow (\exists x) (\forall y) P(x, y) \\
(8) & (\exists x) (\forall y) P(x, y) \Rightarrow (\forall y) (\exists x) P(x, y)
\end{aligned}
$$

这些式子均不难从语义上说明。

注意这些推理一般都是不可逆的。

推理规则

  1. 全称量词消去. $(\forall x) P(x) \Rightarrow P(y)$
  2. 全称量词引入. $y$ 是自由变项，则 $P(y) \Rightarrow (\forall x) P(x)$
  3. 存在量词消去. $(\exists x) P(x) \Rightarrow P(c)$，$c$ 是个体常项。
  4. 存在量词引入. $P(c) \Rightarrow (\exists x) P(x)$

命题逻辑中的推理规则仍然适用。

此外归结法仍然是可以操作的。还是将右边的取反引入到左边然后证明前提不可满足。可以将所有的前提都化为 Skolem 标准型然后取母式做归结，因为我们说过这两个式子是同不可满足的。

  1. 1.书上这里写的是集合，但是笔者觉得这里写集合存在一些问题，所以写作类。实际上我也并不打算深入追究这个基本的问题，只想看一看上层建筑。 ↩
  2. 2.Ref: https://www.math.pku.edu.cn/teachers/linzq/teaching/ml/slides/ml-4_2.pdf ↩
  3. 3.Ref: https://en.wikipedia.org/wiki/Church–Turing_thesis ↩