数字逻辑中的最小完全集

这里只研究单输入单输出、二输入单输出的逻辑门。 单输入的逻辑门是非门（恒等的情况不考虑），真值表为

逻辑门的类型，参见下表

任一种 c1,c2,c3,c4 的组合都构成一种逻辑门，所以理论上共有16个逻辑门（逻辑函数）。但是经常提到的只有与门（AND）、或门(OR)、与非门(NAND)、或非门(NOR)、同或门(XNOR)、异或门(XOR)等。它们的真值表分别是

通常只提到它们的原因是，这些逻辑门满足交换律，即AB=BA，或者说AB不可区分，表现在真值表上就是中间两行的输出值相等。

这样满足交换律的门还有两个，即输出全为0和输出全为1的，是无意义或者说是平凡的。所以说，以上六个逻辑门是所有的非平凡的对称逻辑门。除此之外，还有8个不满足对称性的逻辑门。

能够实现任何逻辑函数的逻辑门类型的集合，被称为逻辑门的完全集。 1

完全集的一个常见的例子是与门、或门、非门。但是这样的概念并不精炼，数学上我们还要求完全集具有最少的元素，即满足 1. 任一个逻辑函数，都可以集合中的逻辑门实现，即完备性； 2. 集合中的一个元素不能被集合中其他元素实现，即独立性。 我们称这样的集合为最小完全集。 事实上我们马上会知道，{与门，或门，非门}并不是一个最小完全集。

那么哪些逻辑门可以构成最小完全集呢？

我们提出以下命题：

与非门证明：

已知{与门，或门，非门}是完全集，所以与单独一种与非门可以实现所有逻辑函数，构成一个单元素的完全集（当然也就是最小完全集）。

图示： blabla

或者考虑代数的表示

X NAND Y=(X⋅Y)′=X′+Y′ ⇒ 1. X NAND 1=X′+0=X′ 2. (X NAND Y) NAND 1=((X⋅Y)′)′=X⋅Y 3. (X NAND 1) NAND (Y NAND 1)=X′ NAND Y′=X+Y

或非门证明：

如果异或门可以构成完全集，那么可以实现与逻辑。按照与逻辑的真值表

得

因此同或门和异或门都不可以单独构成完全集。

补充： 证明同或门不可行也可以用代数方法直接证明，而不必通过两步转换。

X⨀Y = X+Y+1(mod2) 仅用同或逻辑可以实现的所有逻辑函数可以表示成若干个 X,Y,1,0 的同或运算的和，即

如果同或门可以构成完全集，那么可以实现与逻辑。按照与逻辑的真值表，得到

证法二 3群论方法

同或满足交换律和结合律。 X⨀Y=Y⨀A (X⨀Y)⨀Z=X⨀(Y⨀Z) 任一个逻辑函数可以表示成若干个X,Y,1,0的异或运算的和，根据交换律和结合律，可以得到 F=（A⨀⋯⨀A）⨀（B⨀⋯⨀B）⨀（1⨀⋯⨀1）⨀（0⨀⋯⨀0） 同或的性质是 2k+1 个 A 得到A， 2k 个 A 得到1，所以 （1⨀⋯⨀1）⨀（0⨀⋯⨀0） 的结果只能是0或1，与输入无关。至于输入 A,B ，根据奇偶性有四种情况，组合起来一共有8种情况

上面这8行，每行代表一个逻辑函数，所以单独的同或门只能实现着8种逻辑函数，不能构成完全集。

证法三 4穷举法

穷举的判据仍然是：如果只用这一种（同或）逻辑可以实现所有的逻辑函数，那么它就是完全集。

用真值表来表述：如果只用这一种（同或）逻辑可以得到所有16种真值表，那么它就是完全集。仅用同或门可以实现的所有逻辑函数可以用若干个A,B,0,1进行异或运算得到。

给A,B,0,1分别编码为 (0,0,1,1),(0,1,0,1),(0,0,0,0),(1,1,1,1) ，它们中的每两个运算，就是相应的两个编码按位进行运算，运算的结果也是一个四位编码，对应一个逻辑函数。对这个码字的运算的组合、顺序和次数进行穷举，如果可以得到16个不同的码字，那么就证明了同或门可以构成完全集，反之不可以。

穷举的过程用计算机来实现，因为运算次数虽然有限，还是挺繁琐的。贴一段python代码实现5：

输出结果：

这就是在同或逻辑下实现的8个逻辑函数，因为完全集要求有16个输出结果，所以同或门不能构成完全集。

因此{与门，非门}和{或门，非门}构成最小完全集。

下面考虑用编程的方法，对完全集做进一步的探索。

有一个说法是，能够单独构成完全集的二输入逻辑门只有与非门和或非门。其实这个说法的前提是对称的逻辑门，也就是以上六种门，当然可以这么说了。事实上，不满足交换律的逻辑门还有四个也可以单独构成完全集。

输出结果

这多出来的四个逻辑门的真值表是 1.

2.

3.

4.

实际上，这四个门可以归结成一个，即不满足交换律，且当输入同为0或同为1时输出相同。

本文内容来自PKU2013级电子系数字逻辑电路课程小班讨论整理，感谢参与讨论的各位同学、老师和助教。