algorithm - 最小化布尔表达式

Question

我正在尝试编写一段代码,可以将布尔表达式的LENGTH降低到最小,因此代码应该尽可能少地减少表达式中元素的数量.现在我被卡住了,我需要一些帮助= [

这是规则:布尔表达式中可以有任意数量的元素,但它只包含AND和OR运算符,以及括号.

例如,如果我传入一个布尔表达式:ABC + BCD + DE,最佳输出将是BC(A + D)+ DE,与原始值相比,这节省了2个单位空间,因为两个BC组合成一个.

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

有人可以提示如何有效地做到这一点吗？即使是我可以在Google上搜索的一些关键字也可以.

Answer 1

您正在寻找的是一种最小化布尔函数的方法.这是芯片设计界特别感兴趣的事情.用于您的目的的技术是Quine-McCluskey算法,或者您可以在评论中使用Li-aung Yip建议的卡诺图.

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. 具有该公因数的项数