有趣的算法问题

Question

我这里有一个有趣的算法问题.问题在于与电子设计的模拟有关.

比方说,我有一个包含一些门的结构.说一个3输入AND门.有8种可能的输入,即

这些中8个输入,如果我只喂在两个输入(000)和(111),我同时获得可能的输出,即0和1.

因此,在输出上产生状态'0'和'1'的最小输入向量集是{000,111}.

给出了一个设计,一些门的排列,给出了一个算法来找到最小输入向量集,该最小输入向量集在最终输出上产生两种状态(即0和1).

Answer 1

您的问题等同于解决布尔可满足性问题.因此它是NP完全的.

要获得其中一个输入,您可以选择任意输入并查看是否给出0或1.要查找提供其他输出的输入,您需要SAT求解器.

维基百科提出了一些可以使用的算法:

如果您不想实现它,那么有些工具可以随时使用SAT求解器:

Answer 2

这是通过Quine McCluskey算法解决的.还有一些JavaScripts和工具可以解决您的问题.