Take the 2-minute tour ×

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.

share|improve this question
Use the Karnaugh Map, Luke? –  Li-aung Yip Jul 4 '12 at 8:04
@Li-aungYip Ya I've thought of that, but that's only if you're using pencils and paper right? How can I make a computer code that does it? –  turtlesoup Jul 4 '12 at 8:08
With the parentheses, BC(A+D)+DE and ABC+BCD+DE are the same length. I'm working on the same problem right now. This link talks about it a little under the Algebraic Minimization section. I think it is just doing passes that apply boolean identities to the formula. –  douggard Sep 11 '13 at 1:47

6 Answers 6

up vote 3 down vote accepted

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:
                            (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
share|improve this answer
Thanks for the algorithm for finding the common factor, I'll try to build a boolean converter on top of that. Current existing algorithms are hard to be implemented in my case =] –  turtlesoup Jul 20 '12 at 19:59

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.

share|improve this answer
Whoops, beat me by 12 minutes. :) –  Li-aung Yip Jul 4 '12 at 8:17
I've read a little about Quine-McCluskey algorithm, and it says the memory and time grows exponentially as the input gets larger. I am looking for something that can deal with hundreds of inputs(literials in the expression)... so is there another way of doing it? Or did I misunderstand how to use Quine's algorithm? thanks! –  turtlesoup Jul 4 '12 at 12:13
@Jimster: I strongly suggest that you read the linked Wikipedia article, which discusses this issue. The wiki article mentions that large boolean expressions can be handled heuristically by the Espresso minimiser, which scales much better than Quine-McCluskey. –  Li-aung Yip Jul 5 '12 at 3:09
As @Li-aungYip says, there are heuristics for handling large expressions, and Espresso is a good package for exploring these. But in general the thing you would like to do is very hard computationally. The EDA (Electronics Design Automation - responsible for all the chip design tools) Industry has been working in this and similar areas for a long time, but there is no quick fix and exact algorithms are exponential in the number of variables. –  Alex Wilson Jul 5 '12 at 6:51

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.

share|improve this answer

Here's an applet implementing Karnaugh maps: http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer


