Page 143 - Engineering Digital Design

114 CHAPTER 3 / BACKGROUND FOR DIGITAL DESIGN

To illustrate, consider a function F consisting of a string of four multivariable terms W, X, Y,
and Z interconnected initially by XOR operators:

= W QX 07 @Z = W QXQY 0 Z = • • •
(3.24)

An examination of Eqs. (3.24) reveals that there are 64 possible expressions representing
F and 64 for F, all generated by repeated applications of Eqs. (3.23). The number 64 is
derived from combinations of seven different objects taken an even or odd number at a time
for F and F, respectively.
Application of Eqs. (3.24) is illustrated by

A O (A O D + C) Q B = A O [(A 0 D)C] Q B
= A 0 [(A 0 D)C] 0 B,

where the original function has been converted from one having only EQV operators and
two complemented variables to one having only XOR operators with no complemented
variables. The two alternative forms (right side) differ from each other by only two comple-
mentations. Notice also that the first alternative form involved applications of DeMorgan's
laws given by Eqs. (3.15) and (3.22).

3.11.1 Two Useful Corollaries

Interesting and useful relationships result between XOR algebra and conventional Boolean
algebra by recognition of the following two dual corollaries, which follow directly from the
definitions of the XOR and EQV operations:

COROLLARY I If two functions, a and ft, never take the logic 1 value at the
same time, then
a- ft =0 and a+ft=a®ft (3.25)
and the logic operators (+) and (0) are interchangeable.
COROLLARY II If two functions, a and ft, never take the logic 0 value at the
same time, then
a + ft = l and a-f t = (xOft (3.26)
and the logic operators (•) and (Q) are interchangeable.

Corollary I requires that a and ft each be terms consisting of ANDed variables called
product terms (p-terms) and that they be disjoint, meaning that the two terms never take logic
1 simultaneously. By duality, Corollary II requires that a and ft each be terms consisting of
ORed variables called sum terms (s-terms) and that they be disjoint, meaning that the two
terms never take logic 0 simultaneously. The subject of these corollaries will be revisited
in Section 5.5 where their generalizations will be discussed.