You may have been intimidated by the mathematical word problems on the SAT or ACT. On first reading they seem almost impossible to solve.
"Larry and Fred share a bookcase. Larry has twice as many books as Fred. There are 75 books on the bookcase. How many books does Fred have?"
Then you realize how the problem can be redefined as an algebra problem. As an algebra problem the solution is much easier.
2*F + F = 75
F = 25
Fred has 25 books.
For many of the same reasons digital systems are based on an algebra--not the regular algebra you and I are familiar with but rather Boolean algebra. Boolean algebra is the theoretical foundation for digital systems.
Boolean algebra formalizes the rules of logic. On the surface computers are great number crunchers, but inside computations are performed by binary digital circuits following the rules of logic.
We use Boolean algebra in this class to simplify Boolean expressions which represent circuits. In this lecture we will study algebraic techniques for simplifying expressions. In the next lecture we will look at mechanical ways--algorithms you can use with pencil and paper to simplify moderately complex Boolean functions and algorithms that machines can follow to simplify arbitrarily complex Boolean functions.
In 1854 George Boole Introduced the following formalism that eventually became Boolean Algebra.
Premise: There is a set B and two operators: + and * that satisfy the following axioms:
Axiom #1: Closure
If a and b are elements of B, (a + b) and (a * b) are in B.
Axiom #2: Cardinality
There are at least two elements a and b in B such that a != b.
Axiom #3: Commutative
If a and b are elements of B
(a + b) = (b + a), and
(a * b) = (b * a)
Axiom #4: Associative
If a and b are elements of B
(a + b) + c = a + (b + c), and
(a * b) * c = a * (b * c)
Axiom #5: Identity Element
B has identity elements with respect to + and *
0 is the identity element for +, and
1 is the identity element for *
a + 0 = a
a * 1 = a
Axiom #6: Distributive
* is distributive over + and + is distributive over *
a * (b + c) = (a * b) + (a * c), and
a + (b * c) = (a + b) * (a + c)
Axiom #7: Complement Element
For every a in B there is an element a' in B such that
a + a' = 1, and
a * a' = 0
From the axioms above we can derive the following theorems.
| Theorem #1: Idempotent | Proof |
| x + x = x x * x = x (dual) |
x + x (x + x) * 1 (Identity) (x + x) * (x + x') (Complement) x + xx' (Distributive) x + 0 (Complement) x (Identity) |
It's not necessary to provide a separate proof for the dual because of the principle of duality.
|
Duality Any algebraic equality derived from the axioms of Boolean algebra remains true when the operators OR and AND are interchanged and the identity elements 0 and 1 are interchanged. This property is called the duality principle. For example, x + 1 = 1 Because of the duality principle, for any given theorem we get it's dual for free. |
| Theorem #2: Operations with 0 and 1 | Proof |
| x + 1 = 1 x * 0 = 0 (dual) |
x + 1 x + x + x' (Complement) x + x' (Idempotent Theorem) 1 (Complement) |
| Theorem #3: Absorption | Proof |
| y * x + x = x (y + x) * x = x (dual) |
y * x + x y * x + x * 1 (Identity) y * x + 1 * x (Commutative) (y + 1) * x (Distributive) 1 * x (Operations with 0 and 1) x (Identity) |
| Theorem #4: DeMorgan's Law | Proof | ||||||||||||||||||||||||||||||
| (x + y)' = x' * y' (x * y)' = x' + y' (dual) |
The proof for DeMorgan's law
using the axioms of Boolean algebra is long. Another method (that also
works for the other theorems we just discussed) is to show equality with a
truth table:
|
In this class we will use the axioms and theorems of Boolean algebra to simplify Boolean expressions. Using Boolean algebra to simplify Boolean expressions is an art. There is no algorithm you can follow that is guaranteed to result in the simplest form of the expression. Like learning to play chess, with practice you will learn heuristics and begin to recognize patterns that will guide you to the solution.
On the subject of simplification there is another more fundamental question that has to be answered, "What is simplification?" An expression with the fewest literals? An expression with the fewest operations? An expression with the fewest levels? The answer is it depends on what you are trying to optimize for. Speed? Number of interconnections between gates? Number of components? Before you can fully understand the relationship between these tradeoffs you need an understanding of how Boolean expressions are implemented with gates. This is the topic of the next section.
Q. What is the difference between a variable, a literal and a term?
A. A variable is a symbol that may take on the value 0 or 1. A literal is the use of a variable or its complement in an expression. A term is the expression formed by literals and operations at one level. For example, the following function:
F1=xy+xy'z+x'yz
Has 3 variables (x,y,z), 8 literals (x,y,x,y',z,x',y,z), and 4 terms (xy, xy'z, x'yz, and the OR term that combines the first level AND terms).