Page 139 - Engineering Digital Design

110 CHAPTER 3 / BACKGROUND FOR DIGITAL DESIGN

The first of the consensus laws in Eqs. (3.14) is proven by applying the OR and factoring
laws:
XY + XZ + YZ = XY + XZ + [(X + X)YZ] OR law and factoring law
= XY + XZ + [XYZ + XYZ] Factoring law
= [XY(l + Z)] + [XZ(1 + Y)] Factoring law (applied twice); OR law
= XY + XZ.
Proof of the second of the consensus laws follows by duality.

3.10.4 DeMorgan's Laws

In the latter half of the nineteenth century, the English logician and mathematician Augustus
DeMorgan proposed two theorems of mathematical logic that have since become known
as DeMorgan's theorems. The Boolean algebraic representations of these theorems are
commonly known as DeMorgan's laws. In terms of the two multivariable functions X and
7, these laws are given in dual form by

DeMorgan's Laws { _ _ _ > (3.15)
6
More generally, for any number of functions, the DeMorgan laws take the following
form:
X-Y -Z N = X + Y + Z-{ [-N

and (3.15a)
X + Y + Z + -- - + N = X - Y - Z N.

DeMorgan's laws are easily verified by using truth tables. Shown in Fig. 3.35 is the truth
table for the first of Eqs. (3.15).
Application of DeMorgan's laws can be demonstrated by proving the absorptive law
X + XY = X + Y:

X + XY = X • (XY) = X-( X + Y) = X- X + X-Y = X-Y = X + Y.
Notice that the double bar over the term X + XY is a NOT law and does not alter the
term. Here, DeMorgan's laws are first applied by action of the "inner" bar followed by
simplification under the "outer" bar. Final application of DeMorgan's law by application

X Y X-Y X-Y X Y X + Y
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

FIGURE 3.35
Truth table for DeMorgan's LawX • Y = X + Y.