Algorithm - Minimizing Boolean Expressions

Question

I am trying to write a piece of code that can reduce the LENGTH value from a Boolean expression to a minimum, so the code should reduce the number of elements in the expression as little as possible. I'm stuck right now and I need help = [

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

For example, if I go into the logical expression: ABC + BCD + DE, the best output would be BC (A + D) + DE, which saves 2 units of space compared to the original, since the two BCs are combined into one.

My logic is that I will try to find the most frequently occurring element in the expression and refute it. Then I call the function recursively to do the same with the factorized expression until it is fully accounted for. However, how to find the most common element in the original expression? That is, in the example above, BC? It seems like I would have to try all the different combinations of elements and find the number of times each combination appears in the whole expression. But that sounds really naive. Second

Can someone tell me how to do this effectively? Even some of the keywords that I can find on Google will do.

Answer 1

Sorry, I have not read about all these cool algorithms yet, but you asked about finding a common factor, so I thought about 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:

• Total Ratio Length
• Number of members having this total ratio

Answer 2

What you are looking for is a way to minimize a Boolean function. This is of interest, in particular, to the chip development community. The technique used for your purposes is the Quine-McCluskey algorithm , or you can use the Carnot Maps suggested by Li-aun Ip in the comments.

Answer 3

Use the Quine-McCluskey algorithm to minimize boolean expressions. It is functionally equivalent to the Carnot map approach, but much more amenable to computer implementation.

Answer 4

You may also like the heuristic heuristic logic algorithm .

Answer 5

Unfortunately, most of the suggestions given cannot 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 do not focus on the number of characters as the focus for simplification. When it comes to minimization in electronics, users usually require the smallest number of gates (or parts). This does not always lead to a shorter expression in terms of the “length” of the expression - in most cases, but not always. In fact, sometimes the expression can increase in length, although it can be easier from an electronic point of view (fewer gates are required for assembly).

boolengine.com is the best simplification tool that I know of when it comes to logical simplification for digital circuits. It does not allow hundreds of entries, but it allows 14, which is much more than most simplification tools.

When working with electronics, simplification programs usually break down the expression by the amount of the product. Thus, the expression '(ab) +' cd becomes' c + 'b +' a + d. A “simplified” result requires more characters to print as an expression, but it is easier to build from an electronic point of view. This requires only one valve with 4 inputs and 3 inverters (4 parts). While the original expression will require 2 I-gates, 2 inverters and an OR logic element (5 parts).

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

Answer 6

Here the applet implements Carnot maps: http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

You can enter your expression or fill out the truth table.