范式 · Topos Uranos

摘要

同一个真值函数有无穷多个表示它的公式，而随手取其中一个，都看不出它说的是什么。本课固定两种模子，在等价的意义下每个公式都能放进其中之一：析取范式，即文字的合取式的析取式；以及合取范式，即文字的析取式的合取式。本课定义文字、子句和简单合取式；证明当每个文字换成其相反文字时，否定把一种范式变为另一种，这就是两者之间的对偶性；从真值表构造主范式，并证明它们是唯一的。存在定理得到两个证明：一个借助真值表，作为功能完全性的推论；另一个对复杂度归纳，只有或非这一种情形，并且使用该证明所要求的双重归纳假设。最后可以看到它们为何值得花这番功夫：合取范式的有效性和析取范式的可满足性一眼就能判定。

学习目标

识别文字、子句、简单合取式以及处于析取范式或合取范式的公式，区分形式与等价：形式是符号串的性质，等价是意义的性质。
从真值表构造公式的主析取范式和主合取范式，并证明主范式是唯一的，且它决定公式的等价类。
利用对偶性、广义德摩根律与分配律以及语义替换，对复杂度归纳证明每个公式都等价于某个析取范式和某个合取范式。
一眼判定合取范式的有效性和析取范式的可满足性，并把范式应用于语义后承以及范式最小规模的估计。

本单元前面的几课赋予了公式意义：关于命题逻辑的语义学的一课把每个赋值扩张到全体公式；关于语义后承与语义等价的一课定义了等价 $\varphi \eqsem \psi$ 并证明了语义替换；关于广义德摩根律与分配律的一课把这些定律推广到 $n$ 个公式的合取与析取；关于功能完全性的一课表明每个真值函数都由某个公式表示。然而，一个真值函数由无穷多个公式表示，它们彼此可能相差很大： $(v_1 \rightarrow v_2)$ 、 $\neg(v_1 \wedge \neg v_2)$ 和 $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ 是同一事物的三个名字。既然如此，就宜于在每个等价类中选出一个形式固定的代表，它读起来毫不费力，而且某些问题看一眼就能回答。这就是范式。

文字、子句与范式

回顾关于广义定律的一课中 $n$ 个公式的合取与析取的记号，它由递归定义，并且从左结合；单个公式的合取与析取就是该公式本身。

\bigwedge_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigwedge_{i=1}^{n + 1} \varphi_i = \left( \bigwedge_{i=1}^{n} \varphi_i \wedge \varphi_{n + 1} \right)

\bigvee_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigvee_{i=1}^{n + 1} \varphi_i = \left( \bigvee_{i=1}^{n} \varphi_i \vee \varphi_{n + 1} \right)

同一课中证明了，在等价的意义下，项的顺序和结合方式不改变公式（广义结合律以及与顺序和重复无关性）；因此我们也写 $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ 而不加括号，理解为从左结合。

文字是一个变元 $v_n$ ，称为正文字，或者是一个变元的否定 $\neg v_n$ ，称为负文字。文字 $\ell$ 的相反文字记作 $\ell^{*}$ ，它是同一变元的、符号相反的文字：

\ell = v_n \;\Rightarrow\; \ell^{*} = \neg v_n, \qquad \ell = \neg v_n \;\Rightarrow\; \ell^{*} = v_n

由定义得 $(\ell^{*})^{*} = \ell$ 。两个文字若其中一个是另一个的相反文字，就构成一个互补对，例如 $v_3$ 和 $\neg v_3$ 。

子句是文字的析取式 $\bigvee_{j=1}^{k} \ell_j$ ，简单合取式是文字的合取式 $\bigwedge_{j=1}^{k} \ell_j$ ，两种情形下都有 $k \geq 1$ ；因此单独一个文字既是子句又是简单合取式。若一个文字是子句或简单合取式的 $\ell_j$ 之一，就说它出现在其中。

一个公式若是简单合取式的析取式，就处于析取范式；若是子句的合取式，就处于合取范式；也就是说，它分别具有下面两种形式之一，其中 $m$ 和 $k_1, \ldots, k_m$ 是自然数，每个 $\ell_{i,j}$ 是一个文字：

\bigvee_{i=1}^{m} \bigwedge_{j=1}^{k_i} \ell_{i,j}, \qquad \bigwedge_{i=1}^{m} \bigvee_{j=1}^{k_i} \ell_{i,j}

我们说 $\Phi$ 是 $\varphi$ 的一个析取范式，如果它处于析取范式并且 $\varphi \eqsem \Phi$ ；合取范式同理。长度 $k_i$ 可以随合取式（或子句）而不同：要求所有合取式含有相同个数的文字，就不得不用重复来填充，却什么也没有增加。

例题什么处于范式，什么不处于范式

公式 $(v_1 \wedge \neg v_2) \vee \neg v_3$ 处于析取范式，其中 $m = 2$ 、 $k_1 = 2$ 和 $k_2 = 1$ ；它不处于合取范式，因为它不是合取式（它的两个成分不同，而合取式是一个双重否定），也不是子句：读作析取式时，它有一项 $(v_1 \wedge \neg v_2)$ 既不是文字，也不是文字的析取式。公式 $v_1 \wedge \neg v_2 \wedge v_3$ 同时处于两种范式：作为单个简单合取式（ $m = 1$ ）的析取式，以及作为每个只含一个文字的三个子句的合取式。同样， $(\neg v_1 \vee v_2)$ 既是子句，即 $m = 1$ 的合取范式，又是两个各含一个文字的合取式组成的析取范式。

(v_1 \wedge \neg v_2) \vee \neg v_3, \qquad v_1 \wedge \neg v_2 \wedge v_3, \qquad \neg v_1 \vee v_2

与此相反， $(v_1 \downarrow v_2)$ 和 $\neg(v_1 \rightarrow v_2)$ 不处于任何一种范式，尽管前者等价于 $(\neg v_1 \wedge \neg v_2)$ ，后者等价于 $(v_1 \wedge \neg v_2)$ ，而这两者是处于范式的。

(v_1 \downarrow v_2) \eqsem \neg v_1 \wedge \neg v_2, \qquad \neg(v_1 \rightarrow v_2) \eqsem v_1 \wedge \neg v_2

值得停下来想一想“处于范式”是什么意思。它是圆圈和圆盘组成的符号串的性质，而不是其意义的性质：关于自然数上与公式上的归纳法的一课证明了唯一可读性，因此一个公式是不是析取式、是什么的析取式，只有一个答案。然而，正式缩写使得一些公式处于范式却看不出来。蕴涵 $(v_1 \rightarrow v_2)$ 被定义为 $(\neg v_1 \vee v_2)$ ：不是说它等价于这个子句，而是说它就是这同一个符号串，因此它本来就处于范式。更令人意外的是双重否定。根据 $\neg$ 和 $\vee$ 的定义，符号串 $(\varphi \vee \varphi)$ 就是 $\neg(\varphi \downarrow \varphi)$ ，即 $\neg\neg\varphi$ ；由此 $\neg\neg v_1$ 不是文字，但逐字逐符地说，它就是子句 $(v_1 \vee v_1)$ 。

(\varphi \vee \varphi) = \neg(\varphi \downarrow \varphi) = \neg\neg\varphi

合取与析取的值

从关于语义学的一课中取来派生联结词的值： $v(\neg\varphi) = 1 - v(\varphi)$ ； $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$ ，它取值 $1$ 当且仅当两者都取值 $1$ ；以及 $v(\varphi \vee \psi) = 0$ 当且仅当两者都取值 $0$ 。关于广义德摩根律与分配律的一课对项数归纳，把它们推广到 $n$ 个公式，即值引理：对每个赋值 $v$ ，合取 $\bigwedge_{i=1}^{n} \varphi_i$ 取值 $1$ 于 $v$ 当且仅当每个 $\varphi_i$ 取值 $1$ 于 $v$ ；析取 $\bigvee_{i=1}^{n} \varphi_i$ 取值 $1$ 于 $v$ 当且仅当某个 $\varphi_i$ 取值 $1$ 于 $v$ 。这里引用该引理而不重复其证明，它是计算任何范式的值的工具。

引理文字的否定

对每个文字 $\ell$ ， $\ell$ 的否定等价于其相反文字 $\neg\ell \eqsem \ell^{*}$ ；特别地， $v(\ell^{*}) = 1 - v(\ell)$ ，对每个赋值 $v$ 都成立。

证明

$\ell = v_n \;\Rightarrow\; \neg\ell = \neg v_n = \ell^{*}$
若 $\ell$ 是变元 $v_n$ ，其相反文字是 $\neg v_n$ ，它恰好就是符号串 $\neg\ell$ ：没有什么需要证明。
$\ell = \neg v_n \;\Rightarrow\; \neg\ell = \resaltar{\neg\neg v_n} \eqsem v_n = \ell^{*}$
若 $\ell$ 是 $\neg v_n$ ，其否定是 $\neg\neg v_n$ ，它不是文字；由双重否定律（关于语义后承与语义等价的一课），它等价于 $v_n$ ，而这正是 $\ell$ 的相反文字。
$v(\ell^{*}) = v(\neg\ell) = 1 - v(\ell)$
在两种情形下， $\ell^{*}$ 和 $\neg\ell$ 在每个赋值下取相同的值，而 $\neg\ell$ 的值由否定的值给出。

第二种情形很容易被忽略：对范式取否定时，人们倾向于在文字的位置上写 $\neg\ell_{i,j}$ ，而 $\neg\neg v_n$ 不是文字。正是双重否定把结果送回模子里。

引理简单合取式与子句

简单合取式是可满足的，当且仅当它不含任何互补对。子句是有效的，当且仅当它含有某个互补对。

证明

$v(\ell)\,v(\ell^{*}) = v(\ell)\,(1 - v(\ell)) = 0$
若一个简单合取式含有 $\ell$ 和 $\ell^{*}$ ，由上一引理，在每个赋值下两者之一取值 $0$ ；由值引理，该合取式在每个赋值下取值 $0$ 。
$\dato{val}{v_n = \ell_j \;\Rightarrow\; v(v_n) = 1, \qquad \neg v_n = \ell_j \;\Rightarrow\; v(v_n) = 0}$
若它不含任何互补对，就定义一个赋值：给每个以正文字身份出现在其中的变元以 $1$ ，给每个以负文字身份出现在其中的变元以 $0$ （其余变元给 $0$ ）。这个定义不矛盾，因为没有变元以两种方式出现。
$v\left( \bigwedge_{j=1}^{k} \ell_j \right) = 1$
在这个赋值下它的所有文字都取值 $1$ ，由值引理该合取式取值 $1$ ：它是可满足的。
$v(\ell) + v(\ell^{*}) = 1$
若一个子句含有 $\ell$ 和 $\ell^{*}$ ，则在每个赋值下两者之一取值 $1$ ，该子句取值 $1$ ：它是有效的。
$v\left( \bigvee_{j=1}^{k} \ell_j \right) = 0$
若它不含任何互补对，那么给它的正变元以 $0$ 、给它的被否定变元以 $1$ 的赋值使它的所有文字都取值 $0$ ；由值引理，该子句在此赋值下取值 $0$ ，因而不是有效的。