算法-最小化布尔表达式

Question

我试图写出一段代码，可以将布尔表达式的长度减到最小，因此代码应该尽可能减少表达式中元素的数量。现在我陷入困境，需要帮助

规则如下：布尔表达式中可以有任意数量的元素，但它只包含AND和OR运算符，加上括号。

例如，如果我传入一个布尔表达式：a BC+BC D+DE，则最佳输出将是BC（a+D）+DE，这与原始值相比节省了2个单位空间，因为这两个BC合并为一个。

我的逻辑是试图找出表达式中出现频率最高的元素，并将其分解。然后我递归地调用该函数，对分解表达式执行相同的操作，直到它完全分解。 但是，如何在原始表达式中找到最常见的元素？也就是说，在上面的例子中，BC？似乎我必须尝试所有不同的元素组合，并找出每个组合在整个表达式中出现的次数。但这听起来真的很幼稚。 第二

有人能提示一下如何有效地做到这一点吗？甚至一些我可以在谷歌上搜索的关键字也可以。

Answer 1

使用Quine-McCluskey算法最小化布尔表达式。它在功能上等同于卡诺图方法，但更易于在计算机上实现。

Answer 2

很抱歉，我还没有读到所有这些很酷的算法，但是你问我如何找到共同的因素，所以我想到了以下几点：

import itertools
def commons(exprs):
    groups = []
    for n in range(2, len(exprs)+1):
        for comb in itertools.combinations(exprs, n):
            common = set.intersection(*map(set, comb))
            if common:
                groups.append(
                            (len(common), n, comb, ''.join(common)))
    return sorted(groups, reverse=True)

>>> exprs
['ABC', 'BCD', 'DE', 'ABCE']

>>> commons(exprs)
[(3, 2, ('ABC', 'ABCE'), 'ACB'),
 (2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'),
 (2, 2, ('BCD', 'ABCE'), 'CB'),
 (2, 2, ('ABC', 'BCD'), 'CB'),
 (1, 2, ('DE', 'ABCE'), 'E'),
 (1, 2, ('BCD', 'DE'), 'D')]

该函数返回按以下顺序排序的列表：

1. 公因子的长度
2. 具有此公共因子的项数

Answer 3

你要找的是一种最小化布尔函数的方法。这是芯片设计界特别感兴趣的事情。一种用于你的目的的技术是Quine-McCluskey algorithm，或者你可以使用Karnaugh Maps，正如李昂业在评论中建议的那样。