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:
The boundedness identities are still valid, but they are not taken as axioms.
Logic is a Boolean Algebra:
(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 "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:
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'
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' = 1is the dual of
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
a b a X b 1 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.)
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
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:
(a b' and a' b)
(a b' and a' b both have either a or a' and either b or b')
(neither a nor b is missing in either term)
(a for the second row and b for the third row)
(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:
a b a + b a * (a + b) 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0
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:
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)
©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.