0x00 解答

玩图灵完备的时候发现有一个成就时仅使用四个与非门构建异或门,化简来化简去一直都是至少5个,对这个成就感觉非常疑惑。
Snipaste_2025-06-19_22-17-47-ijguahwtjoipeyxn.jpg一番搜索后得到了一个非常精妙的表达式

F=F=\overline{\overline{\overline{AB}\cdot B}\cdot\overline{\overline{AB}\cdot A}}

这个表达式虽然略微复杂了一点,但是仔细观察可以发现,里边有一个共同项:\overline{AB},所以实际使用与非门4个。实际电路图:
Snipaste_2025-06-19_22-20-50-rvdcccusaxenhypu.jpg

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

这里很机智地添加了一个零项,手动构造了一个相同项,用这种办法降低了电路的复杂度。只能说很佩服这些做芯片的和研究数学的。