Boolean Algebra

Sum of Products Form

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.

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.

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

All of 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:

Logic Boolean Algebra

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

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

a b' + a' b

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:

a b a X b

1 1 0

1 0 1

0 1 1

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

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:

a b a' b' a b' a' b a b' + a' b

1 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

(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:

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)

Let us illustrate this one more time with the following product:

a * (a + b)

a b a + b a * (a + b)

1 1 1 1

1 0 1 1

0 1 1 0

0 0 0 0

We see that there are two rows with 1's in the final column:

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'

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.

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

Go to: Title Page Table of Contents Index

Please send comments or suggestions to the author.

	Logic	Boolean Algebra
Identities	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'