Search code examples
logicboolean-expression

How to simplify an arbitrary boolean expression?

How could I go about simplifying an arbitrarily complex boolean expression?

For example:

!(!a && !b || !a && b || a && !b) && !(!a && !b || !a && b || a && !b) ||
!(!a && !b || !a && b || a && !b) && (!a && !b || !a && b || a && !b) ||
(!a && !b || !a && b || a && !b) && !(!a && !b || !a && b || a && !b)

Is an extremely verbose way of saying:

a && b

I could just about do this manually by using boolean laws intuitively. Is there a programmatic approach?

How does Wolfram Alpha do it?

Solution

  • thats simple boolean algebra

    see : http://en.wikipedia.org/wiki/Binary_decision_diagram

    http://en.wikipedia.org/wiki/Circuit_minimization

    http://en.wikipedia.org/wiki/Karnaugh_map