0x00 解答
玩图灵完备的时候发现有一个成就时仅使用四个与非门构建异或门,化简来化简去一直都是至少5个,对这个成就感觉非常疑惑。
一番搜索后得到了一个非常精妙的表达式
F=F=\overline{\overline{\overline{AB}\cdot B}\cdot\overline{\overline{AB}\cdot A}}
这个表达式虽然略微复杂了一点,但是仔细观察可以发现,里边有一个共同项:\overline{AB},所以实际使用与非门4个。实际电路图:
0x01 推理
根据异或的真值表有,
F=\overline{A}B+A\overline{B}
应用德摩根定律可以得到全部使用与非的表达式,
F=\overline{\overline{\overline{A}B}\cdot\overline{A\overline{B}}}
这里表达式和答案已经非常接近了,那么应该如何得到这一个公共项\overline{AB}呢?
我们不妨倒推一下。(因为当时顺推推不下去了)
根据德摩根定律有
\overline{AB}=\overline{A}+\overline{B}
所以有
\begin{aligned}
\overline{AB}\cdot A\;&=(\overline{A}+\overline{B})\cdot A \\
&=\overline{A}A+\overline{B}A \\
&=0+\overline{B}A \\
&=\overline{B}A
\end{aligned}
同理有,
\overline{AB}\cdot B=\overline{A}B
这里很机智地添加了一个零项,手动构造了一个相同项,用这种办法降低了电路的复杂度。只能说很佩服这些做芯片的和研究数学的。