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:

- a set, with two special elements (0 and 1), and
- three operations: sum ("+"), product ("*") and complement (" ' " or "prime") which obey the
Commutative,
Distributive,
Identity (not including the boundedness identities) and
Complement
**axioms**.

The boundedness identities are still valid, but they are not taken as axioms.

Logic is a Boolean Algebra:

- the set is the set of all propositions
- the special elements are T (1) and F (0)
- the three operations are AND (product), OR (sum) and NOT (complement).

(a + b)' = a' * b'instead of

~(p | q) = ~p & ~qand the (non-boundedness) Identities are written as

a + 0 = a and a * 1 = ainstead of

p | F = p and p & T = pFor the record, the complete list of axioms and properties in both logical and Boolean symbols is:

An important aspect of the axioms and properties of Boolean Algebra (and therefore of logic as well) is the notion of "

LogicBoolean AlgebraIdentities p | F = p a + 0 = a p & T = p a * 1 = a Boundedness p | T = T a + 1 = 1 p & F = F a * 0 = 0 Commutative p & q = q & p a * b = b * a p | q = q | p a + 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) Distributive p | (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 Laws p | ~p = T a + a' = 1 p & ~p = F a * a' = 0 Uniqueness of Complement p | q = T, p & q = F → q = ~p a + x = 1, a * x = 0 → x = a' Involution ~(~p) = p (a')' = a ~F = T 0' = 1 ~T = F 1' = 0 Idempotent p | p = p a + a = a p & p = p a * a = a Absorption p | (p & q) = p a + (a * b) = a p & (p | q) = p a * (a + b) = a DeMorgan's ~(p | q) = ~p & ~q (a + b)' = a' * b' ~(p & q) = ~p | ~q (a * b)' = a' + b'

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

a + a' = 1is the

a * a' = 0

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

aba X b1 1 0 1 0 1 0 1 1 0 0 0

a is 1 and b is 0and

a is 0 and b is 1This 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' * bwhich is often abbreviated as

a b' + a' bNow let us examine the truth table of this expression:

(The fifth and six columns represent products or ANDs, and the last column is a sum or OR.)

aba'b'a b'a' ba b' + a' b1 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0

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:

- 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)

- 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')

- in each term, all of the variables (or their complements) are present as factors
(neither a nor b is missing in either term)

- 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)

- 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)

a * (a + b)We see that there are two rows with 1's in the final column:

aba + ba * (a + b)1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0

- in the first, a = 1 and b = 1 so the corresponding term is
a b

- in the second, a = 1 and b = 0, so the corresponding term is
a b'

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 * 1which 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:

- p → q becomes a b + a' b + a' b'
- p ↔ q becomes a b + a' b'

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

In our last example, this method takes the form: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.

- apply DeMorgan's Laws if necessary;

- distribute product over sum wherever possible;

- use the second Idempotent property to eliminate duplicate factors

- use the second Complement Law to eliminate any terms containing the product of a variable and its complement;

- 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

- use the first Idempotent property to delete any duplicate terms.

a * (a + b) → a * a + a * b (step 2)We will next see how to use Boolean Algebra in the context of logic gates and circuits.→ 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)

Go to: Title Page Table of Contents Index

©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.