algorithm - minimizing boolean expressions

Question

I'm trying to write out a piece of code that can reduce the LENGTH of a boolean expression to the minimum, so the code should reduce the number of elements in the expression to as little as possible. Right now I'm stuck and I need some help =[

Here's the rule: there can be arbitrary number of elements in a boolean expression, but it only contains AND and OR operators, plus brackets.

For example, if I pass in a boolean expression: ABC+BCD+DE, the optimum output would be BC(A+D)+DE, which saves 2 unit spaces compared to the original one because the two BCs are combined into one.

My logic is that I will attempt to find the most frequently appeared element in the expression, and factor it out. Then I call the function recursively to do the same thing to the factored expression until it's completely factored. However, how can I find the most common element in the original expression? That is, in the above example, BC? It seems like I would have to try out all different combinations of elements, and find number of times each combination appears in the whole expression. But this sounds really naive. Second

Can someone give a hint on how to do this efficiently? Even some keywords I can search up on Google will do.

Answer 1

What you are looking for is a way to minimise a boolean function. This is something that is of interest in particular to the chip design community. An technique that is used for your purposes is the Quine-McCluskey algorithm, or you can use Karnaugh Maps as suggested by Li-aung Yip in the comments.

Answer 2

Sorry I haven't read about all those cool algorithms yet, but you asked about finding the common factor, so I thought of the following:

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')]

The function returns a list sorted by:

1. The length of the common factor
2. The number of terms having this common factor