可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):

问题:

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.

回答1:

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:

The length of the common factor
The number of terms having this common factor

回答2:

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.

回答3:

Use the Quine-McCluskey algorithm for minimizing boolean expressions. It's functionally equivalent to the Karnaugh Map approach, but much more amenable to implementation on a computer.

回答4:

You may also like to look at Espresso heuristic logic minimizer.

回答5:

Unfortunately, most of the given suggestions may not actually give @turtlesoup what he/she is looking for. @turtlesoup asked for a way to minimize the number of characters for a given boolean expression. Most simplification methods don't target the number of characters as a focus for simplification. When it comes to minimization in electronics, users typically want the fewest number of gates (or parts). This doesn't always result in a shorter expression in terms of the "length" of the expression -- most times it does, but not always. In fact, sometimes the expression can become larger, in terms of length, though it may be simpler from an electronics standpoint (requires fewer gates to build).

boolengine.com is the best simplification tool that I know of when it comes to boolean simplification for digital circuits. It doesn't allow hundreds of inputs, but it allows 14, which is a lot more than most simplification tools.

When working with electronics, simplification programs usually break down the expression into sum-of-product form. So the expression '(ab)+'cd becomes 'c+'b+'a+d. The "simplified" result requires more characters to print as an expression, but is easier to build from an electronics standpoint. It only requires a single 4-input OR gate and 3 inverters (4 parts). Whereas the original expression would require 2 AND gates, 2 inverters, and an OR gate (5 parts).

After giving @turtlesoup's example to BoolEngine, it shows that BC(A+D)+DE becomes E+D+ABC. This is a shorter expression, and will usually be. But certainly not always.