Page 142 - Engineering Digital Design

3.11 LAWS OF XOR ALGEBRA 113

given by Eq. (3.4) and by using the AND and OR laws of Eqs. (3.9):

[(XY) 0 (XZ)] = [(XY)](XZ) + (XY)[(XZ)] Eq. (3.4) and Eq. (3.15)
= [(X + Y)(XZ)] + [(XY)(X + Z)] Factoring law [Eqs. (3.12)]
= [XXZ + XYZ] + [XXY + XYZ] AND and OR laws [Eqs. (3.9)]
= [XYZ + XYZ] Factoring law [Eqs. (3.12)]
= X[YZ + YZ] Eq. (3.4)
= X(Y © Z).

In these equations, the square brackets [ ] are used to draw attention to those portions where
the laws or equations indicated on the right are to be applied in going to the next step.
Equation (3.4) refers to the defining relation for XOR given by X ®7 = XY + XY.
The absorptive laws are also easily proven by using Boolean algebra. Beginning with
the first of Eqs. (3.20), there follows

X • [(X 0 Y)] = X • (XY + XY) Eq. (3.4)
= [X • (XY + XY)] Factoring law [Eqs. (3.12)]
= [X • XY + X • XY] AND and OR laws [Eqs. (3.9)]
= XY,

where the square brackets [ ] are again used to draw attention to those portions where the
laws or equations indicated on the right are to be applied. The second of Eqs. (3.20) is
proven by the following sequence of steps:
X + [(X O Y)] = X + (XY) + (XY) Eq. (3.5)
= [X + (XY)] + XY Factoring law [Eqs. (3.12)]
= [X(l + Y) + XY] OR and AND laws
= [X + XY] Absorptive law [Eqs. (3.13)]
-y i -y

Notice that in the foregoing proofs, use is tacitly made of the important dual relations

9 _ ~ 0 ~ ° (3.23)
XQY = XQY=XQY = X@Y.

These relations are easily verified by replacing the variable (X or Y) by its complement
(X or Y) in the appropriate defining relation, (3.4) or (3.5).
An inspection of Eqs. (3.23) reveals what should already be understood — that comple-
menting one of the connecting variables complements the function, and that the complement
of an XOR function is the EQV function and vice versa. A generalization of this can be
stated as follows:

In any string of terms interconnected only with XOR and/or EQV operators, an odd
number of complementations (variable or operator complementations) complements
the function, whereas an even number of complementations preserves the function.