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

376 BOOLEAN ALGEBRA [CHAP. 15

(b)P 1 =xy′andP 2 =y.

Deletingyandy′yieldsQ=x.

(c) P 1 =x′yzandP 2 =x′yt.

No variable appears uncomplemented in one of the products and complemented in the other. HenceP 1 and

P 2 have no consensus.

(d)P 1 =x′yzandP 2 =xyz′.

Each ofxandzappear complemented in one of the products and uncomplemented in the other. HenceP 1

andP 2 have no consensus.

Consensus Method for Finding Prime Implicants

Figure 15-6 contains an algorithm, called theconsensus method, which is used to find the prime implicants
of a Boolean expressionE. The following theorem gives the basic property of this algorithm.

Theorem 15.11: The consensus method will eventually stop, and thenEwill be the sum of its prime implicants.

Fig. 15-6

EXAMPLE 15.8 LetE=xyz+x′z′+xyz′+x′y′z+x′yz′. Then:

E=xyz+x′z′+xyz′+x′y′z(x′yz′includesx′z′)

=xyz+x′y′+xyz′+x′y′z+xy (consensus ofxyzandxyz′)

=x′z′+x′y′z+xy (xyzandxyz′includexy)

=x′z′+x′y′z+xy+x′y′ (consensus ofx′z′andx′y′z)

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

=x′z′+xy+x′y′+yz′ (consensus ofx′z′andxy)

Now neither step in the consensus method will changeE. ThusEis the sum of its prime implicants, which appear
in the last line, that is,x′z′,xy, x′y′, andyz′.

Finding a Minimal Sum-of-Products Form

The consensus method (Algorithm 15.3) is used to express a Boolean expressionEas a sum of all its
prime implicants. Figure 15-7 contains an algorithm which uses such a sum to find a minimal sum-of-products
form forE.