Simplify boolean expression algorithm

Olmo picture Olmo · Mar 15, 2011 · Viewed 14.9k times · Source

Anybody knows of an algorithm to simplify boolean expressions?

I remember the boolean algebra and Karnaught maps, but this is meant for digital hardware where EVERITHING is boolean. I would like something that takes into account that some sub-expressions are not boolean.

For example:

a == 1 && a == 3

this could be translated to a pure boolean expression:

a1 && a3 

but this is expression is irreducible, while with a little bit of knowledge of arithmetics everibody can determine that the expression is just:

false

Some body knows some links?

Answer

Benjamin picture Benjamin · Mar 15, 2011

You might be interested in K-maps and the Quine–McCluskey algorithm.

I think SymPy is able to solve and simplify boolean expressions, looking at the source might be useful.