布尔表达式简化

Question

[我正在尝试使用正好39个输入和大约5亿至8亿个术语（如许多和/或/非/或陈述）简化布尔表达式。

不需要完美的简化，但是好的简化会很好。

我知道K-maps，Quine–McCluskey和Espresso算法。但是我也知道，根据我所读的内容，这些机制将花费太长时间来简化这种规模的电路

我需要在24小时内尽可能简化此表达式。

经过Google搜索后，我发现很难找到任何资源来简化这种规模的机器！那里的任何资源或那里的图书馆都可以尝试在24小时内至少在某种程度上简化此过程？

Answer 1

在一些过时的书中描述了贪婪的启发式方法[[Simplify

Robert K. Brayton，Gary D. Hachtel，C。McMullen，Alberto Sangiovanni-VincentelliVLSI综合的逻辑最小化算法

您可以找到章节online。

Simplify

基于unate范式。在分治法中，它递归地应用Shannon's expansion theorem将功能拆分为较小的子功能。启发式规则是先按最大二进位变量进行拆分，即分开最多项的变量。]​​>

---

第二种方法可能是使用诸如METIS之类的图分区工具将术语划分为独立的（或至少是松散相关的）子集。但是我不知道对于逻辑综合任务已经成功地尝试了这一点。我最喜欢的搜索引擎对此表示怀疑，不会返回任何匹配。

---

基于Binary Decision Diagrams的较新算法是[]中的[C0

Olivier Coudert：快速执行两级逻辑最小化

[本文列出了与您手头的任务相似的具有大量术语的示例。

某种程度上相关的简化技术

BDD扫描

，如published中所述。

Answer 2

这是一个重复的问题。有关逻辑优化或布尔表达式的简化的资源，请参见A Study of Sweeping Algorithms in the Context of Model Checking。