Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

374 BOOLEAN ALGEBRA [CHAP. 15

Step 4. The productxz′is contained inxyz′; hence, by the absorption law,

xz′+(xz′y)=xz′

Thus we may deletexyz′from the sum. Also, by the identity law for 0, we may delete 0 from the sum.

Accordingly,

E=xyz+xz′

Eis now represented by a sum-of-products expression.

Complete Sum-of-Products Forms

A Boolean expressionE=E(x 1 ,x 2 ,...,xn)is said to be acomplete sum-of-productsexpression ifEis a
sum-of-products expression where each productPinvolves all thenvariables. Such a fundamental productP
which involves all the variables is called aminterm, and there is a maximum of 2nsuch products fornvariables.
The following theorem applies.

Theorem 15.8: Every nonzero Boolean expressionE = E(x 1 ,x 2 ,...,xn)is equivalent to a complete
sum-of-products expression and such a representation is unique.
The above unique representation ofEis called thecomplete sum-of-products formofE. Algorithm 15-1
in Fig. 15-4 tells us how to transform E into a sum-of-products form. Figure 15-5 contains an algorithm which
transforms a sum-of-products form into a complete sum-of-products form.

Fig. 15-5

EXAMPLE 15.6 ExpressE(x, y, z)=x(y′z)′into its complete sum-of-products form.

(a) Apply Algorithm 15.1 toEsoEis represented by a sum-of-products expression:

E=x(y′z)′=x(y+z′)=xy+xz′

(b) Now apply Algorithm 15.2 to obtain:

E=xy(z+z′)+xz′(y+y′)=xyz+xyz′+xyz′+xy′z′

=xyz+xyz′+xy′z′

NowEis reprsented by its complete sum-of-products form.

Warning:The terminology in this section has not been standardized. The sum-of-products form for a Boolean
expressionEis also called thedisjunctive normal formor DNF ofE. The complete sum-of-products form for
Eis also called thefull disjunctive normal form,orthedisjunctive canonical form,ortheminterm canonical
formofE.