Boolean Algebra
Introduction
The most obvious way to simplify boolean expressions is to manipulate them in the same way as normal algebraic expressions are manipulated. With regards to logic relations in digital forms, a set of rules for symbolic manipulation is needed in order to solve for the unknowns.
A set of rules formulated by the English mathematician George Boole describe certain propositions whose outcome would be either true or false. With regard to digital logic, these rules are used to describe circuits whose state can be either, 1 (true) or 0 (false). In order to fully understand this, the relation between the AND
gate, OR
gate and NOT
gate operations should be appreciated. A number of rules can be derived from these relations as Table 1 demonstrates.
Table 1: Boolean postulates | |
---|---|
P1 | X = 0, X = 1 |
P2 | 0 · 0 = 0 |
P3 | 1 + 1 = 1 |
P4 | 0 + 0 = 0 |
P5 | 1 · 1 = 1 |
P6 | 1 · 0 = 0 · 1 = 0 |
P7 | 1 + 0 = 0 + 1 = 1 |
Laws of Boolean Algebra
Table 2 shows the basic Boolean laws. Note that every law has two expressions, a and b. This is known as duality. These are obtained by changing every AND
(·) to OR
(+), every OR
to AND
and all 1's to 0's and vice-versa.
Table 2: Boolean laws | |||
---|---|---|---|
L1 | Commutative law | a | A + B = B + A |
b | A · B = B · A | ||
L2 | Associative Law | a | (A + B) + C = A + (B + C) |
b | (A · B) · C = A · (B · C) | ||
L3 | Distributive Law | a | A · (B + C) = (A · B) + (A · C) |
b | A + (B · C) = (A + B) · (A + C) | ||
L4 | Identity Law | a | A + A = A |
b | A · A = A | ||
L5 | … | a | (A · B) + (A · B) = A |
b | (A + B) · (A + B) = A | ||
L6 | Redundancy Law | a | A + (A · B) = A |
b | A · (A + B) = A | ||
L7 | … | a | 0 + A = A |
b | 0 · A = 0 | ||
L8 | … | a | 1 + A = 1 |
b | 1 · A = A | ||
L9 | … | a | !A + A = 1 |
b | !A · A = 0 | ||
L10 | … | a | A + (!A · B) = A + B |
b | A · (!A + B) = A · B | ||
L11 | De Morgan's Theorem | a | !(A + B) = !A ·! B |
b | !(A · B) = !A + !B |
Original text composed by David Belton - April 98
(Original page was at www.ee.surrey.ac.uk/Projects/Labview/boolalgrebra — now on web archive)
Edited by Federico Scala, January 2005
Wikified by Federico Scala, October 2017