数字逻辑中的最小完全集

大家好，欢迎来到IT知识分享网。

逻辑门

A	B
0	1
1	0

逻辑门的类型，参见下表

A	B	C
0	0	$c_1$
0	1	$c_2$
1	0	$c_3$
1	1	$c_4$

任一种 $c_1,c_2,c_3,c_4$ 的组合都构成一种逻辑门，所以理论上共有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

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

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

我们提出以下命题：

与非门（或非门）一种可以构成完全集

与非门证明：

与非门一个输入端接高电平，得到非门；

与非门串联一个非门，得到与门；

两个非门输入到一个与非门上，得到或门。

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

或者考虑代数的表示

$X$ NAND $Y = (X \cdot Y)'=X'+Y'$
$\Rightarrow$
1. $X$ NAND $1 = X'+0= X'$
2. $(X$ NAND $Y)$ NAND $1 = ((X \cdot Y)')'=X\cdot Y$
3. $(X$ NAND $1)$ NAND $(Y$ NAND $1)=X'$ NAND $Y'=X+Y$

或非门证明：

或非门一个输入端接低电平，得到非门；

或非门串联一个非门，得到或门；

两个非门输入到一个或非门上，得到与门。

同或门（异或门）一种不能构成完全集

证法一 2数论方法

异或门不能构成完全集。
$X\bigoplus Y$ = $X+Y(mod \,2)$
仅用异或逻辑可以实现的所有逻辑函数可以表示成若干个 $X,Y,1,0$ 的异或运算的累加，即 $F = = m 1 X + m 2 Y + m 3 \cdot 1 + m 4 \cdot 0 m 1 X + m 2 Y + m 3$
$\begin{align*}F=&m_1X+m_2Y+m_3\cdot 1+m_4 \cdot 0\\=&m_1X+m_2Y+m_3\end{align*}$

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

X Y F

0 0 0

0 1 0

1 0 0

1 1 1

得
$⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ m 3 \equiv 0 m 2 \equiv 0 (m o d 2) m 1 \equiv 0 m 1 + m 2 + m 3 \equiv 1$
$\begin{cases}m_3\equiv0\\m_2\equiv0\quad \quad\quad\quad(mod \,2)\\ m_1\equiv 0 \\ m_1+m_2+m_3\equiv 1\end{cases}$

矛盾。所以异或门不能单独构成完全集。
2. 同或门和异或门的等价性。
异或门串联一个非门即得同或门，而非门可以用异或门实现，方法是异或门的一端接高电平。

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

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

$X\bigodot Y$ = $X+Y+1(mod \,2)$
仅用同或逻辑可以实现的所有逻辑函数可以表示成若干个 $X,Y,1,0$ 的同或运算的和，即
$F = = m 1 X + m 2 Y + m 3 \cdot 1 + m 4 \cdot 0 + (m 1 + m 2 + m 3 + m 4 - 1) m 1 X + m 2 Y + m 1 + m 2 + 2 m 3 + m 4$
$\begin{align*}F=&m_1X+m_2Y+m_3\cdot 1+m_4 \cdot 0+(m_1+m_2+m_3+m_4-1)\\=&m_1X+m_2Y+m_1+m_2+2m_3+m_4\end{align*}$
$⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ m 1 + m 2 + 2 m 3 + m 4 \equiv 0 m 2 \equiv 0 m 1 \equiv 0 (m o d 2) m 1 + m 2 \equiv 1$
$\begin{cases}m_1+m_2+2m_3+m_4\equiv0\\m_2\equiv0\\ m_1\equiv 0 \quad \quad\quad\quad(mod \,2)\\ m_1+m_2\equiv 1\end{cases}$

矛盾。
所以同或门不能单独构成完全集。

证法二 3群论方法

01组合 A B F

1 2m 2n 1

1 2m 2n+1 B`1

1 2m+1 2n A

1 2m+1 2n+1 A $\bigodot$ B

0 2m 2n 0

0 2m 2n+1 B’

0 2m+1 2n A’

0 2m+1 2n+1 (A $\bigodot$ B)’

上面这8行，每行代表一个逻辑函数，所以单独的同或门只能实现着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	A $\bigodot$ B
0	2m	2n	0
0	2m	2n+1	B’
0	2m+1	2n	A’
0	2m+1	2n+1	(A $\bigodot$ B)’

证法三 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：

def Xnor(x,y): 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 1001 0101 0000 1010 0011 0000 1100 0011 1010 0110 8 ['0101', '0011', '0000', '1111', '1001', '1010', '1100', '0110'] >>>

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

与门和非门（或门和非门）构成最小完全集

与非门（或非门）可以单独构成完全集
与门+非（或）门可以实现与（或）非门
单独的与门、或门、非门都不能构成完全集

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

最小完全集代码全解6

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

单独构成完全集的二输入逻辑门

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

def find_new_element(door,x,y): 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=True #print(len(stas),stas) if (len(stas)==16): print door

输出结果

2 4 8 11 13 14

A	B	C
0	0	0
0	1	0
1	0	1
1	1	0

A	B	C
0	0	0
0	1	1
1	0	0
1	1	0

A	B	C
0	0	1
0	1	1
1	0	0
1	1	1

A	B	C
0	0	1
0	1	0
1	0	1
1	1	1

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

由对称二输入逻辑门以及非门中的两个构成的完全集。

（待续）

完全集的应用

注：

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

数字设计——原理与实践（第四版）John F. Wakerly 机械工业出版社 p162 ↩
by 朱雅轩 ↩
by 张瑞松 ↩
by 徐佳浩 ↩
by 徐佳浩 ↩
by 徐佳浩 ↩

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/125527.html