Boolean Algebra

Boolean Algebra is both a formalization of the algebraic aspects of logic, and the customary language of logic used by the designers of computers. A Boolean Algebra is defined as:

These axioms are the same as the properties with those names which we discussed earlier; here we call them axioms because they are assumptions: from them, all of the remaining properties can be formally derived.
The boundedness identities are still valid, but they are not taken as axioms.

Logic is a Boolean Algebra:

All of the properties of the logical operators which we have previously discussed can be represented using the symbols of Boolean Algebra. For example, the first DeMorgan's Law is written as
(a + b)' = a' * b'
instead of
~(p | q) = ~p & ~q
and the (non-boundedness) Identities are written as
a + 0 = a and a * 1 = a
instead of
p | F = p and p & T = p
For the record, the complete list of axioms and properties in both logical and Boolean symbols is:
LogicBoolean Algebra
Identitiesp | F = pa + 0 = a
p & T = pa * 1 = a
Boundednessp | T = Ta + 1 = 1
p & F = Fa * 0 = 0
Commutativep & q = q & pa * b = b * a
p | q = q | pa + b = b + a
Associative(p | q) | r = p | (q | r)(a + b) + c = a + (b + c)
(p & q) & r = p & (q & r)(a * b) * c = a * (b * c)
Distributivep | (q & r) = (p | q) & (p | r)a + (b * c) = (a + b) * (a + c)
p & (q | r) = (p & q) | (p & r)a * (b + c) = (a * b) + (a * c)
Complement Lawsp | ~p = Ta + a' = 1
p & ~p = Fa * a' = 0
Uniqueness of Complementp | q = T, p & q = F → q = ~p a + x = 1, a * x = 0 → x = a'
Involution~(~p) = p(a')' = a
~F = T0' = 1
~T = F1' = 0
Idempotentp | p = pa + a = a
p & p = pa * a = a
Absorptionp | (p & q) = pa + (a * b) = a
p & (p | q) = pa * (a + b) = a
DeMorgan's~(p | q) = ~p & ~q(a + b)' = a' * b'
~(p & q) = ~p | ~q(a * b)' = a' + b'
An important aspect of the axioms and properties of Boolean Algebra (and therefore of logic as well) is the notion of "duality". While duality can play a very esoteric role in mathematics and physics, for us it is primarily a formal characteristic of the properties which will help us to remember them more easily. Consider the distributive properties:
a + (b * c) = (a + b) * (a + c)
and
a * (b + c) = (a * b) + (a * c)
Notice that if we interchange the sum and product operators in the first distributive property, we obtain the second one. In general, given any axiom or property in Boolean Algebra, if we interchange the sum and product operators and at the same time interchange the elements 0 and 1, the new expression will also be a valid property of the algebra. For instance, the Complement property
a + a' = 1
is the dual of
a * a' = 0


Sum of Products Form

One of the most useful ideas in Boolean Algebra is the "sum of products form" of any given Boolean expression. The best way to illustrate sum of products is with an example: consider the
XOR operator in terms of Boolean Algebra. We can translate the truth table for XOR into Boolean symbols as follows:
aba X b
110
101
011
000
Notice that the first two columns represent all possible values of the Boolean variables a and b, each of which can have the Boolean constant values 0 or 1. Now let us pay special attention to the two rows of the table in which there is a 1 in the final column. They are the rows in which
a is 1 and b is 0
and
a is 0 and b is 1
This is obviously true because XOR requires its operands to be different if it is to produce a value of 1. We will encode this information in the following sum:
a * b' + a' * b
which is often abbreviated as
a b' + a' b
Now let us examine the truth table of this expression:
ab a'b'a b'a' ba b' + a' b
1100000
1001101
0110011
0011000
(The fifth and six columns represent products or ANDs, and the last column is a sum or OR.)

We see that the truth table of this expression is identical to the truth table of XOR: hence they are equivalent. In general, one constructs the sum of products form for any Boolean expression as follows:

  1. there will be one term in the sum for each row in the truth table having a 1 in the final column
    (a b' and a' b)
  2. each of the terms in the sum will be a product in which each factor is either a Boolean variable or its complement
    (a b' and a' b both have either a or a' and either b or b')
  3. in each term, all of the variables (or their complements) are present as factors
    (neither a nor b is missing in either term)
  4. if the variable has a value of 1 in the row for this term, the variable itself is a factor
    (a for the second row and b for the third row)
  5. if the variable has a value of 0 in the row for this term, the complement of the variable is a factor
    (b' for the second row and a' for the third row)
Let us illustrate this one more time with the following product:
a * (a + b)

aba + ba * (a + b)
1111
1011
0110
0000

We see that there are two rows with 1's in the final column: The sum of products is then
a b + a b'
Of course, using the second Distributive Property with b' substituted for c, we can write this as
a (b + b')
and using the first Complement Property this is
a * 1
which is just
a.
As a consequence, we have proved the second Absorption Property.

Using this technique, we can easily state the boolean expressions corresponding to our remaining two logical operators:

In general, we can find the sum of products form for any Boolean expression by repeating the following sequence as needed:

  1. apply DeMorgan's Laws if necessary;
  2. distribute product over sum wherever possible;
  3. use the second Idempotent property to eliminate duplicate factors
  4. use the second Complement Law to eliminate any terms containing the product of a variable and its complement;
  5. for any terms missing one or more variables, multiply by 1 using the first Complement Law (for instance, if the term has no "a" factors, multiply by a + a'); and
  6. use the first Idempotent property to delete any duplicate terms.
This is list is not exhaustive, but includes only the properties that may not "come naturally." That is, the Identities and the second Boundedness, Commutative, Associative and Involution properties should be automatic to anyone with experience using ordinary algebra.
In our last example, this method takes the form:
a * (a + b) → a * a + a * b (step 2)
→ a + a * b (step 3)

→ a * (b + b') * (c + c') + a * b * (c + c') (step 5)

→ a b c + a b' c + a b c' + a b' c' + a b c + a b c' (step 2)

→ a b c + a b' c + a b c' + a b' c' (step 6)

We will next see how to use Boolean Algebra in the context of logic gates and circuits.


Go to:Title PageTable of ContentsIndex

©2013, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.