Introduction to Digital Electronics-Logic Minimization using Boolean Algebra

Boolean Algebra

                Boolean algebra is perhaps the oldest method used to minimize logic equations. It is also one of the ways of minimizing logic equations. It provides a formal algebraic system that can be used to manipulate logic equations in an attempt to find more minimal equations. Boolean algebra is a way of manipulating boolean variables. A boolean variable has exactly two states(1 or 0,On or Off,True of False). A boolean function is a function that takes boolean parameters (inputs) and returns a boolean output. Primitive functions take one or two inputs. A two-input truth table has four lines: one line for each combination of 1s and 0s that can be assigned to the two inputs. There are four because for each 1 or 0 for the first input, the second input can be either 1 or 0. Therefore, there are 2*2 = 4 combinations. For an N-input truth table, the first input can be either 1 or 0; the second input can be either 1 or 0 for each 1 or 0 in the first input; the third input can be either 1 or 0 for any of the 2*2 different combinations of the first two inputs, doubling the number of combinations to 2*2*2; the fourth input can be either 1 or 0 for each of the different combinations of the first three inputs, doubling the number of combinations to 2*2*2*2, and so on. By the time we get to the Nth input, there are 2N combinations. Thus, an N-input truth table has 2N lines.

 Boolean Postulates

(1)	A + 0 = A	A · 1 = A	identity
(2)	A + NOT[A] = 1	A · NOT[A] = 0	complement
(3)	A + B = B + A	A · B = B · A	commutative law
(4)	A + (B + C) = (A + B) + C	A · (B · C) = (A · B) · C	associative law
(5)	A + (B · C) = (A + B) · (A + C)	A · (B + C) = (A · B) + (A · C)	distributive law

Boolean Theorem

(6)	A + A = A	A · A = A
(7)	A + 1 = 1	A · 0 = 0
(8)	A + (A · B) = A	A · ( A + B) = A
(9)	A + (NOT[A] · B) = A + B	A · (NOT[A] + B) = A · B
(10)	(A · B) + (NOT[A] · C) + (B · C) = (A · B) + (NOT[A] · C)	A · (B + C) = (A · B) + (A · C)
(11)	NOT[A + B] = NOT[A] · NOT[B]	NOT[A · B] = NOT[A] + NOT[B]	de Morgan's theorem