命题连接词

命题连接词的完备性和冗余性

我们已经见过了一些命题连接词，例如 $\mathrm{\neg }$、$\wedge$、$\vee$、$\to$ 和 $\leftrightarrow$。有时我们会进一步追问，为什么是这些命题连接词？这些命题连接词是否可以去掉或者新增？因此，我们是时候来将目光放在命题连接词上了。

首先，我们考虑 $k$ 元的布尔函数，来看看多元的布尔函数是否可以扩充我们的命题连接词家族。（这一想法的出发点是：基础的命题连接词可以看作二元的布尔函数）显然，我们可以看出，从合式公式 $\alpha$ 可以产生布尔函数。例如，对于合式公式 $A_1\wedge A_2$，我们可以定义布尔函数 $B(\overrightarrow{X})=B(X_1,X_2)$，其中 $B(X_1,X_2)$ 是 $\alpha$ 的真值，当 $\alpha$ 的真值 $A_1$ 和 $A_2$ 的真值分别是 $X_1$ 和 $X_2$ 时。我们可以看出，对于 $k$ 元的布尔函数，我们应该可以找到一个 $k$ 元的合式公式，使得这个合式公式的真值表和这个布尔函数的真值表一致。下面的定理保证了这一点

布尔函数和合式公式的等价性

设 $G$ 是一个 $n$ 元的布尔函数，其中 $n\ge 1$，那么我们可以找到一个合式公式 $\alpha$ 使得 $G=B_{\alpha }^n$。其中 $B_{\alpha }^n(X_1,X_2,\cdots ,X_n)$ 是 $\alpha$ 的真值，当 $\alpha$ 的真值 $X_1,X_2,\cdots ,X_n$ 分别是 $X_1,X_2,\cdots ,X_n$ 时。

这个定理告诉我们，我们可以通过合式公式来表示任意的布尔函数。因此，我们可以看出，我们的命题连接词是足够强大的，并不需要进行扩充了。下面我们来看看，我们的命题连接词是否可以去掉一些。

显然，$\to$ 和 $\leftrightarrow$ 是可以去掉的，因为它们可以用其他的命题连接词来表示。仔细想想，$\wedge$ 和 $\vee$ 也是可以去掉其中一个的，因为我们有德摩根律。换句话说，$\{\wedge ,\mathrm{\neg }\}$ 和 $\{\vee ,\mathrm{\neg }\}$。但是，我们可以证明，$\{\wedge ,\to \}$ 是不完备的。试想一个所有命题符号都赋值为真的合式公式，那么这个合式公式的真值只能是真而不可能是假，这就说明了不完备性。

$n$ 元联结词

我们还可以考虑 $n$ 元联结词。我们将 $n$ 元联结词定义为一个 $n$ 元的布尔函数，它的真值表是一个 $2^n$ 行的真值表。我们可以证明，$n$ 元联结词的个数是 $2^{2^n}$。

对于一元连接词，显然有四个，但是只有否定连接词是有意义的。其余三个连接词是恒等函数和常值函数。

我们有十六个二元联结词，其中，只有十个是真正二元的。在这里，我们介绍几个常用的附加二元连接词：

• 异或：$A\oplus B$，当 $A$ 和 $B$ 的真值不同的时候，真值为真，否则为假。
• 或非：$A\downarrow B$，当 $A$ 和 $B$ 的真值都为假的时候，真值为真，否则为假。
• 与非：$A|B$，当 $A$ 和 $B$ 的真值都为真的时候，真值为假，否则为真。即 $\mathrm{\neg }(A\wedge B)$，$A$ 和 $B$ 不能同时成立。
• 排序：$A<B$ 和 $A>B$，可将 $T$ 和 $F$ 视为 $1$ 和 $0$，则 $A<B$ 表示 $A$ 的真值小于 $B$ 的真值，$A>B$ 表示 $A$ 的真值大于 $B$ 的真值。

我们可以进一步发现，或非和与非是完备的。