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

CHAP. 15] BOOLEAN ALGEBRA 383

Boolean Functions

LetEbe a Boolean expression withnvariablesx 1 ,x 2 ,...,xn. The entire discussion above can also be
applied toEwhere now the special sequences are assigned to the variablesx 1 ,x 2 ,...,xninstead of the input
devicesA 1 ,A 2 ,...,An. The truth tableT =T(E)ofEis defined in the same way as the truth tableT=T (L)
for a logic circuitL. For example, the Boolean expression

E=xyz+xy′z+x′y

which is analogous to the logic circuitLin Example 15.12, yields the truth table

T( 00001111 , 00110011 , 01010101 )= 00110101

or simplyT(E)=00110101, where we assume the input consists of the special sequences.

Remark: The truth table for a Boolean expressionE=E(x 1 ,x 2 ,...,xn) withnvariables may also be viewed
as a “Boolean” function fromBnintoB. (The Boolean algebrasBnandB={ 0 , 1 }are defined in Example 15.1.)
That is, each element inBnis a list ofnbits which when assigned to the list of variables inEproduces an element
inB. The truth tableT(E)ofEis simply the graph of the function.

EXAMPLE 15.13

(a) Consider Boolean expressionsE=E(x, y, z)with three variables. The eight minterms (fundamental prod-
ucts involving all three variables) are as follows:

xyz, xyz′,xy′z, x′yz, xy′z′,x′yz′,x′y′z′

The truth tables for these minterms (using the special sequences forx,y,z) follow:

xyz= 00000001 ,xyz′= 00000010 ,xy′z= 00000100 ,x′yz= 00001000

xy′z′= 00010000 ,x′yz′= 00100000 ,x′y′z= 01000000 ,x′y′z′= 10000000

Observe that each minterm assumes the value 1 in only one of the eight positions.

(b) Consider the Boolean expressionE=xyz′+x′yz+x′y′z. Note thatEis a complete sum-of-products
expression containing three minterms. Accordingly, the truth tableT =T(E)forE, using the special
sequences forx,y,z, can be easily obtained from the sequences in part (a). Specifically, the truth tableT(E)
will contain exactly three 1’s in the same positions as the 1’s in the three minterms inE. Thus

T( 00001111 , 00110011 , 01010101 )= 01001010

or simplyT(E)=01001010.

15.12Karnaugh Maps

Karnaugh maps, where minterms involving the same variables are represented by squares, are pictorial
devices for finding prime implicants and minimal forms for Boolean expressions involving at most six variables.
We will only treat the cases of two, three, and four variables. In the context of Karnaugh maps, we will sometimes
use the terms “squares” and “minterm” interchangeably. Recall that a minterm is a fundamental product which
involves all the variables, and that a complete sum-of-products expression is a sum of minterms.
First we need to define the notion of adjacent products. Two fundamental productsP 1 andP 2 are said to
beadjacentifP 1 andP 2 have the same variables and if they differ in exactly one literal. Thus there must be
an uncomplemented variable in one product and complemented in the other. In particular, the sum of two such
adjacent products will be a fundamental product with one less literal.