数字逻辑中的最小完全集
本文关键词：数字逻辑，由笔耕文化传播整理发布。
数字逻辑中的最小完全集
发表于2015/3/20 2:05:13 867人阅读
分类： 数字逻辑电路topics
逻辑门
这里只研究单输入单输出、二输入单输出的逻辑门。
单输入的逻辑门是非门（恒等的情况不考虑），真值表为
A B
0 1
1 0
逻辑门的类型，参见下表
A B C
0 0
0 1
1 0
1 1
任一种的组合都构成一种逻辑门，所以理论上共有16个逻辑门（逻辑函数）。但是经常提到的只有与门（AND）、或门(OR)、与非门(NAND)、或非门(NOR)、同或门(XNOR)、异或门(XOR)等。它们的真值表分别是
与门A B C
0 0 0
0 1 0
1 0 0
1 1 1
或门A B C
0 0 0
0 1 1
1 0 1
1 1 1
与非门A B C
0 0 1
0 1 1
1 0 1
1 1 0
或非门A B C
0 0 1
0 1 0
1 0 0
1 1 0
同或门A B C
0 0 1
0 1 0
1 0 0
1 1 1
异或门A B C
0 0 0
0 1 1
1 0 1
1 1 0
通常只提到它们的原因是，这些逻辑门满足交换律，即AB=BA，或者说AB不可区分，表现在真值表上就是中间两行的输出值相等。
这样满足交换律的门还有两个，即输出全为0和输出全为1的，是无意义或者说是平凡的。所以说，以上六个逻辑门是所有的非平凡的对称逻辑门。除此之外，还有8个不满足对称性的逻辑门。
完全集能够实现任何逻辑函数的逻辑门类型的集合，被称为逻辑门的完全集。
完全集的一个常见的例子是与门、或门、非门。但是这样的概念并不精炼，数学上我们还要求完全集具有最少的元素，，即满足
1. 任一个逻辑函数，都可以集合中的逻辑门实现，即完备性；
2. 集合中的一个元素不能被集合中其他元素实现，即独立性。
我们称这样的集合为最小完全集。
事实上我们马上会知道，{与门，或门，非门}并不是一个最小完全集。
那么哪些逻辑门可以构成最小完全集呢？
我们提出以下命题：
与非门（或非门）一种可以构成完全集与非门证明：
已知{与门，或门，非门}是完全集，所以与单独一种与非门可以实现所有逻辑函数，构成一个单元素的完全集（当然也就是最小完全集）。
图示：
blabla
或者考虑代数的表示
1.
2. NAND
3.
或非门证明：
同或门（异或门）一种不能构成完全集 证法一 数论方法仅用异或逻辑可以实现的所有逻辑函数可以表示成若干个
如果异或门可以构成完全集，那么可以实现与逻辑。按照与逻辑的真值表
X Y F
0 0 0
0 1 0
1 0 0
1 1 1
得
矛盾。所以异或门不能单独构成完全集。
2. 同或门和异或门的等价性。
异或门串联一个非门即得同或门，而非门可以用异或门实现，方法是异或门的一端接高电平。
因此同或门和异或门都不可以单独构成完全集。
补充：
证明同或门不可行也可以用代数方法直接证明，而不必通过两步转换。
仅用同或逻辑可以实现的所有逻辑函数可以表示成若干个
如果同或门可以构成完全集，那么可以实现与逻辑。按照与逻辑的真值表，得到
矛盾。
所以同或门不能单独构成完全集。
证法二 群论方法
同或满足交换律和结合律。
任一个逻辑函数可以表示成若干个X,Y,1,0的异或运算的和，根据交换律和结合律，可以得到
同或的性质是，根据奇偶性有四种情况，组合起来一共有8种情况
01组合 A B F
1 2m 2n 1
1 2m 2n+1 B`1
1 2m+1 2n A
1 2m+1 2n+1 AB
0 2m 2n 0
0 2m 2n+1 B’
0 2m+1 2n A’
0 2m+1 2n+1 (AB)’
上面这8行，每行代表一个逻辑函数，所以单独的同或门只能实现着8种逻辑函数，不能构成完全集。
证法三 穷举法
穷举的判据仍然是：如果只用这一种（同或）逻辑可以实现所有的逻辑函数，那么它就是完全集。
用真值表来表述：如果只用这一种（同或）逻辑可以得到所有16种真值表，那么它就是完全集。仅用同或门可以实现的所有逻辑函数可以用若干个A,B,0,1进行异或运算得到。
给A,B,0,1分别编码为，它们中的每两个运算，就是相应的两个编码按位进行运算，运算的结果也是一个四位编码，对应一个逻辑函数。对这个码字的运算的组合、顺序和次数进行穷举，如果可以得到16个不同的码字，那么就证明了同或门可以构成完全集，反之不可以。
穷举的过程用计算机来实现，因为运算次数虽然有限，还是挺繁琐的。贴一段python代码实现：
: r="" for i in range(len(x)): if x[i]==y[i]: r+='1' else: r+='0' return r stas=['0101','0011','0000','1111'] con=True while con: con=False for sta in stas: for stb in stas: newSt=Xnor(sta,stb) if not newSt in stas: stas.append(newSt) print(sta+' '+stb+' '+newSt) con=True print(len(stas),stas)输出结果：
['0101', '0011', '0000', '1111', '1001', '1010', '1100', '0110'] >>>这就是在同或逻辑下实现的8个逻辑函数，因为完全集要求有16个输出结果，所以同或门不能构成完全集。
与门和非门（或门和非门）构成最小完全集因此{与门，非门}和{或门，非门}构成最小完全集。
最小完全集代码全解下面考虑用编程的方法，对完全集做进一步的探索。
单独构成完全集的二输入逻辑门有一个说法是，能够单独构成完全集的二输入逻辑门只有与非门和或非门。其实这个说法的前提是对称的逻辑门，也就是以上六种门，当然可以这么说了。事实上，不满足交换律的逻辑门还有四个也可以单独构成完全集。
: r="" add1 = door/8 add2 = (door/4)%2 add3 = (door/2)%2 add4 = door%2 for i in range(len(x)): if (x[i]=='0')and(y[i]=='0'): r += str(add1) if (x[i]=='0')and(y[i]=='1'): r += str(add2) if (x[i]=='1')and(y[i]=='0'): r += str(add3) if (x[i]=='1')and(y[i]=='1'): r += str(add4) return r door = 1 for door in range(16): stas=['0101','0011','0000','1111'] #print "*********************" #print 'This door is ',door con=True while con: con=False for sta in stas: for stb in stas: newSt=find_new_element(door,sta,stb) if not newSt in stas: stas.append(newSt) con=(len(stas)==16): print door输出结果
这多出来的四个逻辑门的真值表是
1.
A B C
0 0 0
0 1 0
1 0 1
1 1 0
2.
A B C
0 0 0
0 1 1
1 0 0
1 1 0
3.
A B C
0 0 1
0 1 1
1 0 0
1 1 1
4.
A B C
0 0 1
0 1 0
1 0 1
1 1 1
实际上，这四个门可以归结成一个，即不满足交换律，且当输入同为0或同为1时输出相同。
由对称二输入逻辑门以及非门中的两个构成的完全集。 （待续） 完全集的应用 注：本文内容来自PKU2013级电子系数字逻辑电路课程小班讨论整理，感谢参与讨论的各位同学、老师和助教。
本文关键词：数字逻辑，由笔耕文化传播整理发布。
本文编号：287201
本文链接：https://www.wllwen.com/wenshubaike/dxkc/287201.html
