Ned*_*ham 5 algorithm boolean-logic inverse
我正在尝试实现一个非常非常快的布尔表达式引擎。我使用它来表示非常大的状态空间中的状态，因此我需要它每秒处理尽可能多的操作。该引擎的根本是产品的总和。我遇到了一个优化NOT运算符的问题。例如，如果我有一个带有N个小项的乘积之和，每个小项都有大约M个变量，则尝试求反，将创建M ^ N个小项，然后使用espresso算法对其进行简化。如果在逆操作期间间歇运行espresso算法，则可以加快速度并节省一些内存，但这还不够。我怀疑自己是第一个遇到此问题的人，并且我尝试进行研究，但似乎找不到有效的方法来解决此问题。
有人能指出我正确的方向吗？
距离我提出这个问题已经过去五年了。最近重新发现它后，我意识到我犯了大罪。从那时到现在的某个时刻，我找到了一个相当快的算法来完成这个任务，但再也没有回来回答这个问题。问题是我丢失了所有相关文档。韦尔普……就在这里。如果我重新发现来源，我会更新这个答案。
编辑：找到来源
PLA 合成的多值逻辑最小化作者：Richard L. Rudell，第 58 页
https://apps.dtic.mil/dtic/tr/fulltext/u2/a606736.pdf
这使用广义香农展开，递归地补充展开的两侧，并通过简化启发式合并补充。