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

372 BOOLEAN ALGEBRA [CHAP. 15

Fig. 15-3

rectangle (universal set) into eight numbered sets which can be represented as follows:

( 1 )A∩B∩C( 3 )A∩Bc∩C( 5 )A∩Bc∩Cc ( 7 )Ac∩Bc∩C

( 2 )A∩B∩Cc ( 4 )Ac∩B∩C( 6 )Ac∩B∩Cc ( 8 )Ac∩Bc∩Cc

Each of these eight sets is of the formA∗∩B∗∩C∗where:

A∗=AorAc,B∗=BorBc,C∗=CorCc

Consider any nonempty set expressionEinvolving the sets A,B, andC, say,

E=[(A∩Bc)c∪(Ac∩Cc)]∩[(Bc∪C)c∩(A∪Cc)]

ThenEwill represent some area in Fig. 15-3 and hence will uniquely equal the union of one or more of the
eight sets.
Suppose we now interpret a union as a sum and an intersection as a product. Then the above eight sets are
products, and the unique representation ofEwill be a sum (union) of products. This unique representation ofE
is the same as the complete sum-of-products expansion in Boolean algebras which we discuss below.

15.8Sum-of-Products Form for Boolean Algebras

Consider a set of variables (or letters or symbols), sayx 1 ,x 2 ,...,xn.ABoolean expression Ein these
variables, sometimes writtenE(x 1 ,...,xn), is any variable or any expression built up from the variables using
the Boolean operations+,∗, and′. (Naturally, the expressionEmust bewell-formed, that is, where+and∗are
used as binary operations, and′is used as a unary operation.) For example,

E 1 =(x+y′z)′+(xyz′+x′y)′ and E 2 =((xy′z′+y)′+x′z)′

are Boolean expressions inx,y, andz.
Aliteralis a variable or complemented variable, such asx,x′,y,y′, and so on. Afundamental productis a
literal or a product of two or more literals in which no two literals involve the same variable. Thus

xz′,xy′z, x, y′,x′yz

are fundamental products, butxyx′zandxyzyare not. Note that any product of literals can be reduced to either
0 or a fundamental product, e.g.,xyx′z=0 sincexx′=0 (complement law), andxyzy=xyzsinceyy=y
(idempotent law).
A fundamental productP 1 is said to becontained in(orincluded in) another fundamental productP 2 if the
literals ofP 1 are also literals ofP 2. For example,x′zis contained inx′yz, butx′zis not contained inxy′zsince
x′is not a literal ofxy′z. Observe that ifP 1 is contained inP 2 , sayP 2 =P 1 ∗Q, then, by the absorption law,

P 1 +P 2 =P 1 +P 1 ∗Q=P 1

Thus, for instance,x′z+x′yz=x′z.