200
Digital Electronics
X 1
X 2
X n
X 1
X 2
X n
(a)
X 1
X 2
X 3
X 1
X 2
X n
(b)
Figure 6.3 DeMorgan’s theorem.
LHS = X 1 + X 2 + X 3 + · · · X n = 1 + 0 + 0 + · · · + 0 = 1 = 0
RHS = X 1 X 2 X 3 X n = 100 = 011 = 0
Therefore, again LHS = RHS.
The same holds good when more than one or all variables are in the logic ‘1’ state. Therefore,
theorem 13(a) stands proved. Since theorem 13(b) is the dual of theorem 13(a), the same also stands
proved. Theorem 13(b), though, can be proved on similar lines.
6.3.14 Theorem 14 (Transposition Theorem)
(a) XXY + XXZ = X + ZZZZX + YY
and
(b) X + YYYYX + ZZ = XXZ + XXY
(6.24)
This theorem can be applied to any sum-of-products or product-of-sums expression having two terms,
provided that a given variable in one term has its complement in the other. Table 6.4 gives the proof
of theorem 14(a) using the method of perfect induction. Theorem 14(b) is the dual of theorem 14(a)
and hence stands proved.
As an example,
AAB + AAB = A + BBBBA + BB and AAB + AAB = A + BBBBA + BB
Incidentally, the first expression is the representation of a two-input EX-OR gate, while the second
expression gives two forms of representation of a two-input EX-NOR gate.