最少与非门问题
2024-01-24 10:23:10

源于今天玩NandGame时产生的一个小问题:怎么使用最少的与非门来构造一个异或门?

单纯采用德摩根定律可以把异或门的逻辑式化简成 Y=AB·AB ,此时需要5个与非门。

然而对上式稍作改动,变成 Y=AAB·BAB ,此时只需要4个与非门(AB由一个门引出)。

这需要一些巧妙的技巧性构造,那么是否有什么通用的方法求逻辑表达式的最少与非门形式呢?

网上相关的资料寥寥无几,只找到了一篇野生的文章,《原变量下用最少与非门实现逻辑函数》,但没有仔细阅读(格式有些糟糕),在各大学术平台也搜索不到相关内容,google的某个相关问题中更有人称这是一个NP难问题,真伪难辨。。。不过参考上面异或门的例子,一味追求“使用最少的与非门”可能在某种程度上破坏了抽象思想,即用与非门构造出其它基本门,再用这些基本门(与、或等)组合出有意义的逻辑电路,再层层抽象。。。这样构造出的电路大概率不是“最少与非门”的,但这显然降低了电路设计的复杂程度。

不过如果存在一种通用的方法,也许可以应用到集成电路设计软件中自动生成最简的底层电路。

这个问题暂时留个尾巴,之后有机会再深入研究一下。