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

CHAP. 15] BOOLEAN ALGEBRA 373

Definition 15.1:A Boolean expressionEis called asum-of-productsexpression ifEis a fundamental product
or the sum of two or more fundamental products none of which is contained in another.

Definition 15.2: LetEbe any Boolean expression. Asum-of-products formofEis an equivalent Boolean
sum-of-products expression.

EXAMPLE 15.4 Consider the expressions

E 1 =xz′+y′z+xyz′ and E 2 =xz′+x′yz′+xy′z

Although the first expressionE 1 is a sum of products, it is not a sum-of-products expression. Specifically,
the productxz′is contained in the productxyz′. However, by the absorption law,E 1 can be expressed as

E 1 =xz′+y′z+xyz′=xz′+xyz′+y′z=xz′+y′z

This yields a sum-of-products form forE 1. The second expressionE 2 is already a sum-of-products expression.

Algorithm for Finding Sum-of-Products Forms

Figure 15-4 gives a four-step algorithm which uses the Boolean algebra laws to transform any Boolean
expression into an equivalent sum-of-products expression.

Fig. 15-4

EXAMPLE 15.5 Suppose Algorithm 15.1 is applied to the following Boolean expression:

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

Step 1. Using DeMorgan’s laws and involution, we obtain

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

Enow consists only of sums and products of literals.

Step 2. Using the distributive laws, we obtain

E=xyxz′+xyyz+xz′z′+yzz′

Enow is a sum of products.

Step 3. Using the commutative, idempotent, and complement laws, we obtain

E=xyz′+xyz+xz′+ 0

Each term inEis a fundamental product or 0.