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

CHAP. 15] BOOLEAN ALGEBRA 375

15.9Minimal Boolean Expressions, Prime Implicants

There are many ways of representing the same Boolean expressionE. Here we define and investigate a
minimal sum-of-products form forE. We must also define and investigate prime implicants ofEsince the
minimal sum-of-products involves such prime implicants. Other minimal forms exist, but their investigation lies
beyond the scope of this text.

Minimal Sum-of-Products

Consider a Boolean sum-of-products expressionE. LetELdenote the number of literals inE(counted
according to multiplicity), and letESdenote the number of summands inE. For instance, suppose

E=xyz′+x′y′t+xy′z′t+x′yzt

ThenEL= 3 + 3 + 4 + 4 =14 andES=4.
SupposeEandFare equivalent Boolean sum-of-products expressions. We sayEissimplerthanFif:

(i)EL<FLandES≤FL, or (ii)EL ≤FLandES<FL

We sayEisminimalif there is no equivalent sum-of-products expression which is simpler thanE. We note that
there can be more than one equivalent minimal sum-of-products expressions.

Prime Implicants

A fundamental productPis called aprime implicantof a Boolean expressionEif

P+E=E

but no other fundamental product contained inPhas this property. For instance, suppose

E=xy′+xyz′+x′yz′

One can show (Problem 15.15) that:

xz′+E=E but x+E=E and z′+E=E

Thusxz′is a prime implicant ofE.

The following theorem applies.

Theorem 15.9:A minimal sum-of-products form for a Boolean expressionEis a sum of prime implicants ofE.

The following subsections give a method for finding the prime implicants ofEbased on the notion of the
consensus of fundamental products. This method can then be used to find a minimal sum-of-products form forE.
Section 15.12 gives a geometric method for finding such prime implicants.

Consensus of Fundamental Products

LetP 1 andP 2 be fundamental products such that exactly one variable, sayxk, appears uncomplemented
in one ofP 1 andP 2 and complemented in the other. Then theconsensusofP 1 andP 2 is the product (without
repetitions) of the literals ofP 1 and the literals ofP 2 afterxkandx′kare deleted. (We do not define the consensus
ofP 1 =xandP 2 =x′.)
The following lemma (proved in Problem 15.19) applies.

Lemma 15.10: SupposeQis the consensus ofP 1 andP 2. ThenP 1 +P 2 +Q=P 1 +P 2.

EXAMPLE 15.7 Find the consensusQofP 1 andP 2 where:

(a) P 1 =xyz′sandP 2 =xy′t.

Deleteyandy′and then multiply the literals ofP 1 andP 2 (without repetition) to obtainQ=xz′st.