为什么只有NAND和NOR操作可以是自足算子？

作业

---

自足算子：

自足算子或自足连结词是在一特定类的算子中只靠自身就能生成所有这些算子的算子。在逻辑中，它是足够生成所有布尔值函数的一个逻辑算子，$f : X \to \mathbb{B}$，这里的 $X$ 是一个任意集合而 $\mathbb{B}$ 是一个通用的 2-元素集合，典型为 $\mathbb{B} = { 0, 1 } = { \mathrm{false}, \mathrm{true} }$，特别是生成所有的有限布尔函数，$f : \mathbb{B}^k \to \mathbb{B}$。

---

Table of binary truth functions [1]：

$p$	$q$	$\bot$	$\downarrow$	$\not\rightarrow$	$\neg q$	$\not\leftarrow$	$\neg p$	$\not\leftrightarrow$	$\uparrow$	$\land$	$\leftrightarrow$	$p$	$\leftarrow$	$q$	$\to$	$\lor$	$\top$
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

---

定义$~\bullet~$为一个二元操作，我们来分析一下如果$~\bullet~$是自足算子，$~\bullet~$需要满足的条件：

若$p=1,q=1$,如果$~\bullet~$是函数完全的，那么经过有限次$~\bullet~$的操作，必然既可以得到$1$也可以得到$0$。
若$p\bullet q=1$，因为$p=1,q=1,p\bullet q=1$ 而且无法从其它途径得到$0$，因此，无论经过多少次$~\bullet~$操作也得不到$0$。故$~\bullet~$不可能满足自足算子的性质，因此必然有$p\bullet q=0$.
同理可以得出若$p=0,q=0$，则必然有$p\bullet q=1$.

然后分析若$p=1,q=0$，$p\bullet q$应该是什么？

• 若$p\bullet q=1$，则$(p\bullet q) \bullet (p\bullet q)=0$成立。
• 若$p\bullet q=0$，则$(p\bullet q) \bullet (p\bullet q)=1$成立。

因此若$p=1,q=0$，$p\bullet q$既可以为$0$，也可以为$1$.
同理可知$p=0,q=1$，$p\bullet q$也是既可以为$0$，也可以为$1$.

又因为，若要考虑到$~\bullet~$要满足结合律，即

$$(0\bullet 1)\bullet 0 = 0\bullet(1\bullet 0)$$
故要满足$p=1,q=0$和$p=0,q=1$结果相同，因此综上$~\bullet~$可能代表的二元运算只有$\downarrow$和$\uparrow$。