Boolean Algebra
Boolean Algebra is the set of elements B with two binary operations AND {?} and OR {+} and a unary operation {’} such that the following axioms hold:
1. The set B contains at least two elements a, b such that a ? b.
2. Closure: For every a, b in B,
a. a OR b is in B
b. a AND b is in B
3. Commutative laws: For every a, b in B,
a. a OR b = b OR a
b. a AND b = b AND a
4. Associative laws: For every a, b, C in B,
a. (a OR b) OR c = a OR (b OR c)
b. (a AND b) AND c = a AND (b AND c)
5. Identities:
a. There exists an identity element with respect to OR, designated by 0, such that a OR 0 = a for every a in B.
b. There exists an identity element with respect to AND, designated by 1, such that a AND 1 = a for every a in B.
6. Distributive laws: For every a, b, c in B,
a. a OR (b AND c) = (a OR b) AND (a OR c)
b. a AND (b OR c) = (a AND b) OR (a AND c)
7. Complement: For each a in B, there exists an element a' in B (the complement of a) such that
a. a OR a’ = 1
b. a AND a’ = 0
Note: We can also use ā instead of a’.
It is easy to verify that the set B = {0, 1} and the logical operations AND, OR, and NOT satisfy all the axioms of a Boolean Algebra.
The reason Boolean Algebra is so important in digital or computer design is that this is at the very heart of the latter’s foundation. Boolean Algebra maps to digital electronics and vice versa.
In the proceeding sections, the symbol {+} will be used for OR, {?} for AND, and {’} for NOT.
Laws and Theorems of Boolean Algebra
|
THEOREM |
DUAL THEOREM |
|
Operations with 0 and 1 |
|
|
1. X + 0 = X |
X ? 1 = X |
|
2. X + 1 = 1 |
X ? 0 = 0 |
|
Idempotent Theorem |
|
|
3. X + X = X |
X ? X = X |
|
Involution Theorem |
|
|
4. (X’)’ = X |
|
|
Theorem of Complementarity |
|
|
5. X + X’ = 1 |
X ? X’ = 0 |
|
Commutative Law |
|
|
6. X + Y = Y + X |
X ? Y = Y ? X |
|
Associative Law |
|
|
7. (X + Y) + Z = X + (Y + Z) |
(X ? Y) ? Z = X ? (Y ? Z) |
|
Distributive Law |
|
|
8. X ? (Y + Z) = X ? Y + X ? Z |
X + (Y ? Z) = (X + Y) ? (X + Z) |
|
Simplification Theorems |
|
|
9. X ? Y + X ? Y’ = X |
(X + Y) ? (X + Y’) = X |
|
10. X + X ? Y = X |
X ? (X + Y) = X |
|
11. (X + Y’) ? Y = X ? Y |
(X ? Y’) + Y = X + Y |
|
DeMorgan’s Theorem |
|
|
12. (X + Y + Z + ...)’ = X’ ? Y’ ? Z’ ? ... |
(X ? Y ? Z ? ...)’ = X’ + Y’ + Z’ + ... |
|
13. {f(X1, X2, ..., Xn, 0, 1, +, ?)}’ = {f(X1’, X2’, ..., Xn’, 1, 0, ?, 1)} |
|
|
Duality |
|
|
14. (X + Y + Z + ...)D = X ? Y ? Z ? ... |
(X ? Y ? Z ? ...)D = X + Y + Z + ... |
|
15. {f(X1, X2, ..., Xn, 0, 1, +, ?)}D = {f(X1, X2, ..., Xn, 1, 0, ?, 1)} |
|
|
Theorem for Multiplying and Factoring |
|
|
16. (X + Y) ? (X’ + Z) = X ? Z + X’ ? Y |
X ? Y + X’ ? Z = (X + Z) ? (X’ + Y) |
|
Consensus Theorem |
|
|
17. X ? Y + Y ? Z + X’ ? Z = X ? Y + X’ ? Z |
(X + Y) ? (Y + Z) ? (X’ + Z) = (X + Y) ? (X’ + Z) |
The Idea of Duality
The idea of duality is a very important concept in Boolean algebra. Every Boolean expression has a dual and it is derived from the original by replacing AND with OR operations and vice versa, while leaving the literals unchanged. It is also a fundamental theorem that any statement that is true for a Boolean expression is also true for its dual.