Simplifying a group of AND and OR clauses

So if I have a group of AND and OR clauses as foll开发者_Python百科ows:

Y = ( A + B ) . ( A + C' ) . ( B + D' )

Can I simplify it like this:

Y = A . ( B + C' ) . ( B + D' ) ; Because A is common to ( A + B ) and ( A + C' )
Y = A . B . ( C' + D' )         ; Because B is common to ( B + C' ) and ( B + D' )

Thanks for your time.

No, if you use the following values:

A = 1
B = 0
C = 0
D = 0

Then the original statement is true where your simplified version is false. You can find another way to represent it by expanding the boolean expression and then attempting to reduce it algebraicly, like this:

(A + B)(A + C')(B + D')
(AA + AC' + AB + BC')(B + D')                          // expand first 2 groups
AAB + ABC' + ABB + BBC' + AAD' + AC'D' + ABD' + BC'D'  // expand all groups
AB + ABC' + AB + BC' + AD' + AC'D' + ABD' + BC'D'      // apply identity to reduce
AB + BC' + AD'                                         // eliminate redundant expressions

That final result would look like this in your notation

(A . B) + (B . C') + (A . D')

One step further could bring it to

B . (A + C') + (A . D')

or

A . (B + D') + (B . C')

The only equivalence I can think of as useful here is

(A+B).(A+C') === A+(B.C')

So it becomes

(A+(B.C')) . (B+D')

if B: --> A . D'
else: --> (A+C')

Don't know whether that helps you get anything more efficient/useful

A   B   C'  D'  f()
TRUE    TRUE    TRUE    TRUE    TRUE
TRUE    TRUE    TRUE    FALSE   TRUE
TRUE    TRUE    FALSE   TRUE    TRUE
TRUE    TRUE    FALSE   FALSE   TRUE
TRUE    FALSE   TRUE    TRUE    TRUE
TRUE    FALSE   TRUE    FALSE   TRUE
TRUE    FALSE   FALSE   TRUE    FALSE
TRUE    FALSE   FALSE   FALSE   FALSE
FALSE   TRUE    TRUE    TRUE    TRUE
FALSE   TRUE    TRUE    FALSE   FALSE
FALSE   TRUE    FALSE   TRUE    TRUE
FALSE   TRUE    FALSE   FALSE   FALSE
FALSE   FALSE   TRUE    TRUE    FALSE
FALSE   FALSE   TRUE    FALSE   FALSE
FALSE   FALSE   FALSE   TRUE    FALSE
FALSE   FALSE   FALSE   FALSE   FALSE

Watch it live in a spreadsheet: google docs

eZanmoto, at first glance it looks like it would work, but I quick went through and did truth tables for each one and here are the cases where it fails:

@A = B = C = D = True
Original = True
First = True
Second = False

@A = C = True, B = D = True
Original = True
First = False
Second = False

@A = True, B = C = D = False
Original = True
First = True
Second = False

@A = C = False, B = D = True
Original = True
First = False
Second = False

@A = C = D = False, B = True
Original = True
First = False
Second = False

Late answer. I recently learned more about Quine-McClusky algorithm and Karnaugh maps, which are systematic approaches to mimizing boolean epxressions.

I stumbled across this python implementation that seemed nice and thought I'd verify my earlier answer using it:

import logic
A,B,C,D = logic.bools('ABCD')

print logic.boolsimp((A & B) | (A & ~C) | (B & ~D))

Sure enough it prints

(B & ~D) | (~C & A) | (B & A)

^{Pythonists: nevermind the strange choice of operators for logical operations; this is mainly due to the fact that and, or and not cannot be overloaded in Python}

Sanity check

As a sanity check I did check that the equivalence that I thought would lead to a potential simplification was 'seen' by the algorithm implementation:

print logic.boolsimp((A & B) | (A & ~C))
print logic.boolsimp(A & (B | ~C))

prints twice the same output ((~C & A) | (B & A))