Boolean Algebra and Simplification Techniques
199
or by the sum of the remaining variables in the case of a product-of-sums expression will be redundant.
The following example further illustrates the point:
AABBC + AACCD + BBCCD + BBCCD + AACCD = AABBC + AACCD + BBCCD
If we consider the first two terms of the Boolean expression, BBCCD becomes redundant. If we consider
the first and third terms of the given Boolean expression, AACCD becomes redundant.
Example 6.4
Prove that AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCDDE + AABBCCDDE + AABBCCDDE can
be simplified to AABB
Solution
AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCDDE + AABBCCDDE + AABBCCDDE
= AABBCCD + AABBCCD + AABBCCD + AABBCCD
= AABBBCCD + CCD + CCD + CCDD = AAB
• AABBCCD appears in AABBCCDDE, AABBCCD appears in AABBCCDDE and AABBCCD appears in
AABBCCDDE.
• As a result, all three five-variable terms are redundant.
• Also, variables C and D appear in all possible combinations and are therefore redundant.
6.3.13 Theorem 13 (DeMorgan’s Theorem)
(a) X 1 + X 2 + X 3 + + X n = X 1 X 2 X 3 n
(6.22)
(b) X 1 X 2 X 3 n = X 1 + X 2 + X 3 + + X n
(6.23)
According to the first theorem the complement of a sum equals the product of complements, while
according to the second theorem the complement of a product equals the sum of complements. Figures
6.3(a) and (b) show logic diagram representations of De Morgan’s theorems. While the first theorem
can be interpreted to say that a multi-input NOR gate can be implemented as a multi-input bubbled
AND gate, the second theorem, which is the dual of the first, can be interpreted to say that a multi-input
NAND gate can be implemented as a multi-input bubbled OR gate.
DeMorgan’s theorem can be proved as follows. Let us assume that all variables are in a logic ‘0’
state. In that case
LHS = X 1 + X 2 + X 3 + · · · + X n = 0 + 0 + 0 + · · · + 0 = 0 = 1
RHS = X 1 X 2 X 3 n = 000 0 = 111 = 1
Therefore, LHS = RHS.
Now, let us assume that any one of the n variables, say X 1 , is in a logic HIGH state:
199
or by the sum of the remaining variables in the case of a product-of-sums expression will be redundant.
The following example further illustrates the point:
AABBC + AACCD + BBCCD + BBCCD + AACCD = AABBC + AACCD + BBCCD
If we consider the first two terms of the Boolean expression, BBCCD becomes redundant. If we consider
the first and third terms of the given Boolean expression, AACCD becomes redundant.
Example 6.4
Prove that AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCDDE + AABBCCDDE + AABBCCDDE can
be simplified to AABB
Solution
AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCDDE + AABBCCDDE + AABBCCDDE
= AABBCCD + AABBCCD + AABBCCD + AABBCCD
= AABBBCCD + CCD + CCD + CCDD = AAB
• AABBCCD appears in AABBCCDDE, AABBCCD appears in AABBCCDDE and AABBCCD appears in
AABBCCDDE.
• As a result, all three five-variable terms are redundant.
• Also, variables C and D appear in all possible combinations and are therefore redundant.
6.3.13 Theorem 13 (DeMorgan’s Theorem)
(a) X 1 + X 2 + X 3 + + X n = X 1 X 2 X 3 n
(6.22)
(b) X 1 X 2 X 3 n = X 1 + X 2 + X 3 + + X n
(6.23)
According to the first theorem the complement of a sum equals the product of complements, while
according to the second theorem the complement of a product equals the sum of complements. Figures
6.3(a) and (b) show logic diagram representations of De Morgan’s theorems. While the first theorem
can be interpreted to say that a multi-input NOR gate can be implemented as a multi-input bubbled
AND gate, the second theorem, which is the dual of the first, can be interpreted to say that a multi-input
NAND gate can be implemented as a multi-input bubbled OR gate.
DeMorgan’s theorem can be proved as follows. Let us assume that all variables are in a logic ‘0’
state. In that case
LHS = X 1 + X 2 + X 3 + · · · + X n = 0 + 0 + 0 + · · · + 0 = 0 = 1
RHS = X 1 X 2 X 3 n = 000 0 = 111 = 1
Therefore, LHS = RHS.
Now, let us assume that any one of the n variables, say X 1 , is in a logic HIGH state: