Boolean Algebra Simplified

Once one has defined a notation for an algebra, the rules to manipulate expressions follow. The most simple are the rules that concern the unary operator NOT:

(A')' = A

A • A' = 0

A + A' = 1

 

General rules like the distributive, commutative, and associative rules hold for the AND and OR binary operators (except one weird one) so that:

Distributive:

A•(B+C) = A•B + A•C

A+(B•C) = (A+B)•(A+C) (the weird one!)

 

Commutative:

A•B = B•A

A+B = B+A

Associative: (A•B)•C = A•(B•C)

(A+B)+C = A+(B+C)

 

In addition, there are simplification rules for Boolean equations. There are three important groups of simplification rules.

The first one uses just one variable:

A•A = A

A+A = A

 

The second group uses Boolean constants 0 and 1:

A • 0 = 0

A • 1 = A

A + 0 = A

A + 1 = 1

 

The third group involves two or more variables and contains a large number of possible simplification rules (or theorems) such as:

 

A + A•( B ) = A

( proof: A + A•B = A•(1+B) = A•1 = A )

 

Note that in this expression either A or B may stand for any complex Boolean expression.

There are two important rules which constitute de Morgan's theorem:

(A+B)' = A' • B'

(A•B)' = A' + B'

 

This theorem is widely used in Boolean logic design. Stated in words it is: To "invert" (negate) a Boolean expression, you replace the AND operator with the OR operator (or vice versa) and invert the individual terms. The theorem holds for any number of terms, so:

 

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

and similarly:

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

 

You may have noticed by now that rules are often given in pairs. It makes sense that in a binary system there is some kind of symmetry between the two operators. For Boolean algebra this symmetry is called Duality. Every equation has its dual which one can generate by replacing the AND operators with ORs (and vice versa) and the constants 0 with 1s (and vice versa).

 

For example, the dual equation of the important simplifying rule:

A + A•B = A

is:

A•(A+B) = A (proof: A•A + A•B = A + A•B = A )

 

Do not mix up or get confused between a dual expression which is generated by the above rules and the complement (or inverted) expression which is generated by applying the NOT operator. The rules are similar, but they mean very different things.

 

Finally, let us consider the proposition (I am not taking an umbrella), or:

 

(U)' = ( C'•(W+R) )'

Apply de Morgan's theorem

U' = (C')' + (W+R)'

Apply de Morgan's theorem again

U' = (C')' + W'•R'

And simplify

U' = C + W'•R'