Page 137 - Engineering Digital Design

108 CHAPTER 3 / BACKGROUND FOR DIGITAL DESIGN

where the double arrow (•< — >) again represents the duality relationship of the set. For each
dual set it can be seen that an operator in the left side equation has been replaced by its
dual in the right side while the logic 0 and 1 (in the first dual set) are interchanged. Note
that the two equations in a given set are not algebraically equal — they are duals of each
other. However, a dual set of equations are complementary if an equation is equal to logic
1 or logic 0 as in the first example. Such is not the case for the second set. The concept of
duality pervades the entire field of mathematical logic, as will become apparent with the
development of Boolean algebra.

3.10.3 Associative, Commutative, Distributive, Absorptive, and Consensus Laws
The associative, commutative, distributive, absorptive, and consensus laws are presented
straightforwardly in terms of the multivariable functions X, Y, and Z to emphasize their
generality, but the more formal axiomatic approach is avoided for the sake of simplicity.
These laws are given in a dual form that the reader may find useful as a mnemonic tool:

Associative Laws { > (3.10)
(X + 7) + Z = X + (Y + Z) = X + Y + Z

Commutative Laws { > (3.11)

(X-Y ) + (X-Z ) = X-(Y + Z) Factoring Law 1
Distributive Laws \ \ (3.12)
(X + Y)-( X + Z) = X + (Y • Z) Distributive Law

Absorptive Laws { [ (3.13)
H

Consensus Laws < _ } . (3.14)
\(X + Y) • (X + Z) • (7 + Z) = (X + Y) • (X + Z)J

Notice that for each of the five sets of laws, duality exists whereby the AND and OR
operators are simultaneously interchanged. The dual set of distributive laws in Eqs. (3.12)
occur so often that they are sometimes given the names factoring law and distributive law
for the first and second, respectively. The factoring law draws its name from its similarity
to the factoring law of Cartesian algebra.
Although rigorous proof of these laws will not be attempted, they are easily verified
by using truth tables. Shown in Figs. 3.33 and 3.34 are the truth table verifications for the
AND form of the associative law and the factoring law. Their dual forms can be verified in
a similar manner.
Proof of the commutative laws is obtained simply by assigning logic 0 and logic 1 to the
X's and F's in the two variable forms of these laws and then comparing the results with the
AND and OR truth tables given by Eqs. (3.7) and (3.8), respectively.
The distributive law can also be verified by using truth tables. However, having verified
the factoring law, it is simpler to prove this law with Boolean algebra by using the factoring