功能完全性 · Topos Uranos

摘要

每个公式都确定一张真值表；本课证明其逆命题：每张表，即对各行的每一种真值指派，都是某个公式的表。本课定义真值函数，计数 $n$ 元真值函数（ $2^{2^{n}}$ ），并明确一个公式何时表示其中之一。接着借助表公式证明功能完全性定理；表公式是逐行构造的文字合取式的析取式，关于范式的一课将把它用作析取范式存在性的第一个证明。由于本课程的每个公式都是由圆圈和圆盘组成的符号串，无须更多工作即可推出或非单独就足够了，并说明如何用它写出任意函数。最后，本课研究哪些联结词集足以表示所有函数：证明一个一般判据，将其应用于 $\{\neg, \wedge\}$ 、 $\{\neg, \vee\}$ 、 $\{\neg, \rightarrow\}$ 、 $\{\downarrow\}$ 和与非，并证明 $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ 不够，因为它的所有公式都保持值 $1$ 。

学习目标

计数 $n$ 元真值函数，并借助公式所表示的函数判定两个公式何时等价。
由一个真值函数的表构造表示它的公式，并在合适时寻找更简短的等价公式。
解释为什么在本课程的语言中或非单独就足够了，并只用或非写出表示给定函数的公式。
证明一个联结词集是完全的，方法是用它的公式表达或非。
证明一个联结词集不是完全的，方法是借助它的所有公式都保持的某种性质。

真值函数

关于命题逻辑的语义学的一课在每个赋值下为每个公式指派了一个真值，并说明这个值只依赖于在公式中出现的变元的值；由此，每个含 $n$ 个变元的公式都有一张 $2^{n}$ 行的真值表。本课的问题是反过来的。给定任意一张表，即在 $2^{n}$ 行旁边任意写下的一列一和零，是否有某个公式以它为真值表？如果对每张表都是如此，语言就没有表达上的缺口：关于 $n$ 个陈述句的真值、作为它们的值的函数所能说的一切，都能用一个公式说出。又由于在本课程中每个复合公式都是一个或非，答案也将说明单独一个联结词是否足以说出一切。

从前面各课中用到的内容

一个赋值是一个函数 $v$ ，从变元集 $\{v_1, v_2, \ldots\}$ 到 $\{0, 1\}$ ，其中 $1$ 表示真， $0$ 表示假；它到所有公式的扩张也记作 $v$ ，由递归定义： $v((\varphi \downarrow \psi)) = 1$ 当且仅当 $v(\varphi) = 0$ 且 $v(\psi) = 0$ 。同一课在派生联结词的值的定理中，从正式缩写出发算出了每个联结词的值；用和与积写出来，它们如下，对每个赋值 $v$ 以及所有公式 $\varphi$ 和 $\psi$ ：

v(\neg\varphi) = 1 - v(\varphi), \qquad v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), \qquad v((\varphi \vee \psi)) = v(\varphi) + v(\psi) - v(\varphi)\,v(\psi)

v((\varphi \rightarrow \psi)) = 1 - v(\varphi) + v(\varphi)\,v(\psi), \qquad v((\varphi \downarrow \psi)) = (1 - v(\varphi))\,(1 - v(\psi))

此外， $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$ ，它等于 $1$ 当且仅当 $v(\varphi) = v(\psi)$ ； $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$ ，它等于 $1$ 当且仅当 $v(\varphi) \neq v(\psi)$ 。由于值都是 $0$ 或 $1$ ，一个值的平方就是这个值本身，即 $v(\varphi)\,v(\varphi) = v(\varphi)$ ，而若干值之积等于 $1$ 当且仅当每个因子都等于 $1$ ；这两点以后使用时不再重复。还要用到一致引理：如果两个赋值在 $\varphi$ 的变元上一致，即在作为 $\varphi$ 的子公式的那些变元上一致，它们就给 $\varphi$ 相同的值。从关于语义后承与语义等价的一课取来语义等价： $\varphi \eqsem \psi$ 是指 $v(\varphi) = v(\psi)$ 对每个赋值 $v$ 都成立。最后，关于形式化的一课中的字母约定仍然有效： $p$ 、 $q$ 和 $r$ 表示变元 $v_1$ 、 $v_2$ 和 $v_3$ 。

真值函数及其个数

设 $n$ 是一个自然数。由 $n$ 个值组成的一个行是一个序列 $a = (a_1, \ldots, a_n)$ ，其中每个 $a_i$ 是 $0$ 或 $1$ ；所有这些行的集合记作 $\{0, 1\}^{n}$ 。一个 $n$ 元真值函数是一个函数

f\colon \{0, 1\}^{n} \to \{0, 1\}

它给每一行指派一个真值。它以表的形式给出：各行按表的顺序写出，从所有值都是 $1$ 的那一行开始（两个自变量时为 $1\,1$ 、 $1\,0$ 、 $0\,1$ 、 $0\,0$ ），每行旁边写出其值。因此，真值函数就是没有公式的真值表：右边那一列，表头什么也不写。

命题共有

2^{2^{n}}

个

n

元真值函数

对每个自然数 $n$ ，恰有 $2^{n}$ 个由 $n$ 个值组成的行，以及 $2^{2^{n}}$ 个 $n$ 元真值函数。

证明

$\dato{filas}{1\,0\,1 \;\; \longmapsto \;\; \sigI\sigO\sigI}$
一行是由 $n$ 个符号组成的序列，每个符号是 $1$ 或 $0$ 。如果用圆盘代替 $1$ 、用圆圈代替 $0$ 来写，各行就与双符号字母表上长度为 $n$ 的符号串一一对应，而这样的符号串有 $2^{n}$ 个，这是关于归纳法的一课的第一道例题，那里用对 $n$ 的归纳证明了它。
$f \;\; \longmapsto \;\; f(1, \ldots, 1) \;\; \ldots \;\; f(0, \ldots, 0)$
一个真值函数由它在各行上的值确定，而这些值的任何选取都给出一个函数。如果按表的顺序写出这些值，函数就与由 $2^{n}$ 个符号组成、每个符号为 $1$ 或 $0$ 的序列一一对应。
$2^{\resaltar{2^{n}}}$
由同样的计数，现在应用于长度为 $2^{n}$ 的序列，函数共有 $2$ 的 $2^{n}$ 次方个。
$2^{2} = 4, \quad 2^{4} = 16, \quad 2^{8} = 256, \quad 2^{16} = 65\,536$
最初几个值显示这个数增长得多快：有五个自变量时，函数已经超过四十亿个。

例题一元函数与二元函数

四个一元函数是常值 $1$ 、恒等函数、改变值的函数和常值 $0$ ；公式 $\top$ 、 $p$ 、 $\neg p$ 和 $\bot$ （其中 $\top := (p \rightarrow p)$ 和 $\bot := \neg\top$ 是在关于语义学的一课中固定的公式）分别具有这些表。十六个二元函数中有本课程六个联结词的函数：或非、析取、合取、蕴涵、双条件和不相容析取。还剩另外十个，其中有两个常值函数、只关注其中一个自变量的函数，以及与非（谢弗竖线），它取值 $0$ 的情形只有一种：两个自变量都取值 $1$ ；例题 1 对它们全部进行分类。

表示函数的公式

公式与真值函数之间的联系如下。如果 $\varphi$ 是一个公式，其变元都在 $v_1, \ldots, v_n$ 之中，就说 $\varphi$ 表示真值函数 $f$ （ $n$ 元），如果对每个赋值 $v$ ，

v(\varphi) = f(v(v_1), \ldots, v(v_n))

也就是说， $\varphi$ 的表（用变元 $v_1, \ldots, v_n$ 写出）就是 $f$ 的表。对变元的条件不是细节：公式 $(p \wedge q)$ 不表示任何一元函数，因为它的值不只依赖于 $p$ 的值。

命题公式的函数

设 $\varphi$ 是一个公式，其变元都在 $v_1, \ldots, v_n$ 之中。那么 $\varphi$ 恰好表示一个 $n$ 元真值函数，记作 $f_\varphi$ 。如果 $\psi$ 是另一个公式，其变元都在 $v_1, \ldots, v_n$ 之中，那么 $\varphi \eqsem \psi$ 当且仅当 $f_\varphi = f_\psi$ 。

证明

$\dato{va}{v_a(v_i) = a_i \quad (i \leq n), \qquad v_a(v_k) = 0 \quad (k > n)}$
对每一行 $a$ ，都有一个赋值给每个 $v_i$ 指派值 $a_i$ ：只需给其余变元指派值 $0$ 。
$v(v_i) = v'(v_i) = a_i \quad (i \leq n) \;\; \Rightarrow \;\; v(\varphi) = v'(\varphi) = \resaltar{f_\varphi(a)}$
如果两个赋值给 $v_1, \ldots, v_n$ 指派行 $a$ 的值，它们就在 $\varphi$ 的变元上一致，于是由一致引理，它们给 $\varphi$ 相同的值。把这个共同的值取作 $f_\varphi(a)$ ；按构造， $\varphi$ 表示 $f_\varphi$ 。
$g(a) = v_a(\varphi) = f_\varphi(a)$
如果 $\varphi$ 还表示一个函数 $g$ ，那么在每一行 $a$ 上都有 $g(a) = v_a(\varphi) = f_\varphi(a)$ ：所表示的函数是唯一的。
$v(\varphi) = f_\varphi(v(v_1), \ldots, v(v_n)) = f_\psi(v(v_1), \ldots, v(v_n)) = v(\psi)$
如果 $f_\varphi = f_\psi$ ，那么对每个赋值 $v$ ， $\varphi$ 与 $\psi$ 的值都是同一个函数在同一行上的值；由此 $\varphi \eqsem \psi$ 。
$f_\varphi(a) = v_a(\varphi) = v_a(\psi) = f_\psi(a)$
反之，如果 $\varphi \eqsem \psi$ ，那么在每一行 $a$ 上，赋值 $v_a$ 给两个公式相同的值，因此 $f_\varphi(a) = f_\psi(a)$ 。

变元在 $v_1, \ldots, v_n$ 之中的公式有无穷多个，而函数只有 $2^{2^{n}}$ 个；因此许多公式表示同一个函数，而上述命题说，它们恰好是彼此等价的公式。尚待知道的是：每个函数是否都由某个公式表示，还是有些表没有以它为表的公式。