Simplify boolean expression algorithm

algorithm boolean-logic boolean boolean-expression
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.

Related questions

How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
What does O(log n) mean exactly?

I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, …

Read More