最少与非门问题
2024-01-24 10:23:10
源于今天玩NandGame时产生的一个小问题:怎么使用最少的与非门来构造一个异或门?
单纯采用德摩根定律可以把异或门的逻辑式化简成
然而对上式稍作改动,变成
这需要一些巧妙的技巧性构造,那么是否有什么通用的方法求逻辑表达式的最少与非门形式呢?
网上相关的资料寥寥无几,只找到了一篇野生的文章,《原变量下用最少与非门实现逻辑函数》,但没有仔细阅读(格式有些糟糕),在各大学术平台也搜索不到相关内容,google的某个相关问题中更有人称这是一个NP难问题,真伪难辨。。。不过参考上面异或门的例子,一味追求“使用最少的与非门”可能在某种程度上破坏了抽象思想,即用与非门构造出其它基本门,再用这些基本门(与、或等)组合出有意义的逻辑电路,再层层抽象。。。这样构造出的电路大概率不是“最少与非门”的,但这显然降低了电路设计的复杂程度。
不过如果存在一种通用的方法,也许可以应用到集成电路设计软件中自动生成最简的底层电路。
这个问题暂时留个尾巴,之后有机会再深入研究一下。