联结词的扩充与归约
前面介绍了一个 $n$ 元逻辑联结词其实就是一 $n$ 元映射，是一个从 $\set{\mathrm{T},\mathrm{F}}^n$ 到 $\set{\mathrm{T},\mathrm{F}}$ 的映射，相应的真值函数表就有 $2^{2^n}$ 种，因此可以给出更多的元逻辑联结词。那么这些未给出的逻辑联结词和前面介绍的 $5$ 个逻辑联结词之间有什么关系，这就是本节内容所要介绍的。下面先以 $n=1,2$ 为例给出更多的 $n$ 元逻辑联结词，然后给出一般情况的结论。
联结词的扩充
下面分别以 $n=1$ 和 $n=2$ 为例来给出联结词的扩充。
$n=1$ 时的联结词扩充
当 $n=1$ 时，有 $4$ 个不同的从 $\set{\mathrm{T},\mathrm{F}}$ 到 $\set{\mathrm{T},\mathrm{F}}$ 的映射，即有四个不同的一元联结词 $f_1,f_2,f_3,f_4$ ，从而对应的真值函数表就有 $4$ 个，如表1所示。
| $p$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ |
|---|---|---|---|---|
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{T}$ |
表1 $n=1$ 的 $4$ 个联结词
可见，$f_1(p)=\mathrm{T}$ ，$f_2(p)=\neg p$ ，$f_3(p)=p$ ，$f_4(p)=\mathrm{F}$ 。
$n=2$ 时的联结词扩充
当 $n=2$ 时，就有 $16$ 个不同的从 $\set{\mathrm{T},\mathrm{F}}^2$ 到 $\set{\mathrm{T},\mathrm{F}}$ 的映射，即有 $16$ 个不同的二元联结词，相应的真值函数表就有 $16$ 个，如表2所示。
| $p$ | $q$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ |
|---|---|---|---|---|---|---|---|---|---|
| $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ |
| $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ |
| $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ |
| $\mathrm T$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ |
| $p$ | $q$ | $f_9$ | $f_{10}$ | $f_{11}$ | $f_{12}$ | $f_{13}$ | $f_{14}$ | $f_{15}$ | $f_{16}$ |
|---|---|---|---|---|---|---|---|---|---|
| $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ |
| $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ | $\mathrm T$ |
| $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ | $\mathrm F$ | $\mathrm F$ | $\mathrm T$ | $\mathrm T$ |
| $\mathrm T$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ | $\mathrm F$ | $\mathrm T$ |
表2 $n=2$ 的 $16$ 个联结词
由表2可以看出 $f_2$ 即为 $\and$ ，$f_8$ 即为 $\and$ ，$f_8$ 即为 $\or$ ，$f_{14}$ 即为 $\imp$ ，$f_{10}$ 即为 $\iff$ 。另外，$f_1,f_{16}$ 为常逻辑联结词，即 $f_1(p,q)=\mathrm{T},f_{16}(p,q)=\mathrm{F}$ ；$f_4,f_6$ 的映射结果分别与变元 $p,q$ 取值相同，故通常称为投影联结词，即 $f_4(p,q)=p,f_6(p,q)=q$ ；$f_{11},f_{13}$ 的映射结果分别与变元 $q,p$ 的取值相反，即 $f_{11}(p,q)=\neg q,f_{13}(p,q)=\neg p$ ，它们通常称为二元否定词。对于 $f_{12}$ ，本质仍为 $\imp$ ，因为 $f_{12}(p,q)=q \imp p$ 。对于 $f_3,f_5$ 可视为“蕴涵否定词”，一般记为 $\not\imp$ ，即 $f_3(p,q)=p \not\imp q = \neg (p \imp q),f_5(p,q)=q \not\imp p = \neg (q \imp p)$ 。剩下几个联结词是计算机科学中用的比较多的：
$f_9$ 即为或非词 $\nor$ ，$f_9(p \nor q)=p \nor q \vDashv \neg (p \or q)$ 。
$f_{15}$ 即为与非词 $\nand$ ，$f_{15}(p,q)=p \and q \vDashv \neg (p \and q)$ 。
$f_7$ 即为异或词 $\xor$ ，$f_7(p,q)=p \xor q \vDashv \neg (p \iff q)$ 。
从上面的讨论可以看出，可以将逻辑联结词扩充得更多，同时也可以发现新扩充的联结词均可由前面给出的 $5$ 个基本联结词表示出来。下面引入联结词的可表示性概念。
联结词的归约
联结词的可表示性
联结词的完备集
(1)当 $n=1,2$ 时，由假设可知一元和二元联结词均可被 $C$ 表示。
(2)假设 $n=k$ 时，$k$ 元联结词可被 $C$ 表示。当 $n=k+1$ 时，有 $$\begin{aligned} f(p_1,p_2,\cdots,p_{k+1}) & \vDashv \begin{cases} f(\mathrm{F},p_2,\cdots,p_k,p_{k+1}) & p_1 = \mathrm{F}\\[5pt] f(\mathrm{T},p_2,\cdots,p_k,p_{k+1}) & p_1 = \mathrm{T} \end{cases}\\ & \vDashv (\neg p_1 \imp f(\mathrm{F},p_2,\cdots,p_k,p_{k+1})) \and (p_1 \imp f(\mathrm{T},p_2,\cdots,p_k,p_{k+1})) \tag{1}\end{aligned}$$
$f(\mathrm{F},p_2,\cdots,p_k,p_{k+1})$ 和 $f(\mathrm{T},p_2,\cdots,p_k,p_{k+1})$ 可以利用真值表将 $\mathrm{F}$ 和 $\mathrm{T}$ 消去，因此是一个 $k$ 元联结词，由归纳假设可知可以由 $C$ 表示，所以 $f(p_1,p_2,\cdots,p_{k+1})$ 可以由 $C$ 表示。
由数学归纳法原理可知任一命题公式均可由 $C$ 表示，即 $C$ 是一个联结词完备集。〔定理1证毕〕
联结词完备集 $\set{\neg,\or,\and,\imp,\iff}$
联结词完备集 $\set{\neg,\imp}$
因此，$\set{\neg,\imp}$ 可以表示 $\set{\or,\and,\iff}$ ，所以 $\set{\neg,\imp}$ 是一个联结词完备集。〔定理3证毕〕
联结词完备集 $\set{\neg,\or,\and}$
因此，$\set{\neg,\or,\and}$ 可以表示 $\set{\imp,\iff}$ ，所以 $\set{\neg,\or,\and}$ 是一个联结词完备集。〔定理4证毕〕
联结词完备集 $\set{\neg,\or}$
因此 $\set{\neg,\or}$ 是一个联结词完备集。〔定理5证毕〕
联结词完备集 $\set{\neg,\and}$
因此 $\set{\neg,\and}$ 是一个联结词完备集。〔定理6证毕〕
联结词完备集 $\set{\nor}$
因此 $\set{\nor}$ 是一个联结词完备集。〔定理7证毕〕
联结词完备集 $\set{\nand}$
因此 $\set{\nand}$ 是一个联结词完备集。〔定理8证毕〕
我们读诗、写诗并不是因为它们好玩，而是因为我们是人类的一份子，而人类是充满激情的。没错，医学、法律、商业、工程，这些都是崇高的追求，足以支撑人的一生。但诗歌、美丽、浪漫、爱情，这些才是我们活着的意义。― John Keating, 《死亡诗社》