2.6. Boolean Algebra Theorems
Purpose of Theorems
The Theorems & Huntington’s Postulates are key in our ability to reduce the number of literal
(variables) used in a function and therefore reduce the number of gates required to implement a given
function. Sometimes they are used to simply rearrange the expression so it is easier to implement.
Example: (X+Y)(X+ Y)=X
It is clear that right-hand-side requires fewer gates to implement compared to the left hand side. Two methods available for proving theorems
Prove through Boolean Algebra
Use the Huntington’s postulates or theorems already proved to show that both sides of theorem
are the same.
Prove through Truth Tables
Show that for all possible values on the left hand-side is equal to the right-hand side of the
equation. This method works well for a small number of variables. Theorems and proofs
Theorem 1 “ Double Complementation or Double Negation Theorem”
a) X=X
Theorem 2 “Idempotency Theorem”
a) X+X = X
b) X X = X Theorem 3 “Identity Element Theorem”
a) X + 1 = 1
b) X 0 = 0 Theorem 4 “Absorption Theorem”
a) X + X Y=X
b) X (X+Y) = X Theorem 5 “Associative Theorem”
a) X + (Y+Z) = (X + Y) + Z
b) X (Y Z) = (X Y)Z Theorem 6 “Adjacency Theorem”
a) X Y + X Y = X
b) (X + Y)(X + Y) = X Theorem 7 “Consensus Theorem”
a) X Y + XZ + Y Z = X Y + XZ
b) (X + Y)( X + Z)(Y + Z) = (X + Y)( X + Z) Theorem 8 “Simplification Theorem”
a) X + XY = X + Y
b) X ( X + Y) = X Y