Boolean Algebra and Simplification Techniques
201
Table 6.4 Proof of theorem 13(a).
X
Y
Z
XY
XZ
X+Z
X + Y
XY+ XZ
(X+Z)X + YY
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
6.3.15 Theorem 15
(a) XXffXX XX YY ZZ Z Z Z Z = XXff1 0 YY ZZ Z Z Z Z
(6.25)
(b) X + ffXX XX YY ZZ Z Z Z Z = X + ff0 1 YY ZZ Z Z Z Z
(6.26)
According to theorem 15(a), if a variable X is multiplied by an expression containing X and X in
addition to other variables, then all Xs and Xs can be replaced with 1s and 0s respectively. This would
be valid as XXX = X and XX1 = X. Also, XXX = 0 and XX0 = 0. According to theorem 15(b), if a
variable X is added to an expression containing terms having X and X in addition to other variables,
then all Xs can be replaced with 0s and all Xs can be replaced with ls. This is again permissible as
X + X as well as X + 0 equals X. Also, X + X and X + 1 both equal 1.
This pair of theorems is very useful in eliminating redundancy in a given expression. An important
corollary of this pair of theorems is that, if the multiplying variable is X in theorem 15(a), then all
Xs will be replaced by 0s and all Xs will be replaced by ls. Similarly, if the variable being added in
theorem 15(b) is X, then Xs and Xs in the expression are replaced by 1s and 0s respectively. In that
case the two theorems can be written as follows:
(a) XXffXX XX YY ZZ Z Z Z Z = XXff0 1 YY ZZ Z Z Z Z
(6.27)
(b) X + ffXX X YY ZZ Z Z Z Z = X + ff1 0 YY ZZ Z Z Z Z
(6.28)
The theorems are further illustrated with the help of the following examples:
1. AAAAAB + AAC + A + DDDDA + EEE = AAA0B + 1C + 0 + DDDD1 + EEE = AAAC + DD.
2. A + AAB + AAC + A + BBBBA + EEE = A + 0B + 1C + 0 + BBBB1 + EEE = A + C + B.
6.3.16 Theorem 16
(a) ffXX XX YY Y Y Y Y ZZ = XXff1 0 YY Y Y Y Y ZZ + XXff0 1 YY Y Y Y Y ZZ
(6.29)
(b) ffXX XX YY Y Y Y Y ZZ = X + ff0 1 YY Y Y Y Y ZZZZX + ff1 0 YY Y Y Y Y ZZZ
(6.30)