Simplification of Boolean Functions  89 

a matter of fact, if an X is used as a 1 when combining the 1’s and again as a 0 when combining
the 0’s, the two resulting functions will not yield algebraically equal answers. The selection of the
don’t-care condition as a 1 in the first case and as a 0 in the second results in different minterm
expressions and thus different functions. This can be seen from Example 3-12. In the solution of
this example, the X chosen to be a 1 was not chosen to be a 0. Now, if in Fig. 3-26(a) we choose
the term w′ x′ instead of w′ z, we still obtain a minimized function:

F = w′ x′ + y z

But it is not algebraically equal to the one obtained in product of sums because the same X’s
are used as 1’s in the first minimization and as 0’s in the second.
This example also demonstrates that an expression with the minimum number of literals is
not necessarily unique. Sometimes the designer is confronted with a choice between two terms
with an equal number of literals, with either choice resulting in a minimized expression.

More Solved Problems

Simplify by K-Map 3. Simplify the following equation by K-Map
1. Simplify the following equation by K-Map F(A, B, C, D) = ∑m(2, 4, 5, 13, 14) + ∑d(0, 1,
F(A, B, C) = ∑m(0, 2, 4) + ∑d(1, 3, 5, 6, 7) 8, 10)
BC CD
00 01 11 10
AB
A 00 01 11 10 0 1 3 2

0 0 1 3 2 00 X X 1
1 X X 1
4 5 7 6
4 5 7 6
01 1 1
1 X X X X
12 13 15 14
11 1
F(A, B, C) = C′ 1

2. Simplify π(0, 2, 3.6) by K-Map 8 9 11 10

10 X
BC
00 01 11 10
A
0
0 1 3 2 Ans. F = A′C′ + BC′D + B′CD′ + ACD′
0 0 0
4 5 7 6
1 0

f = (A + C) (A + B′) (B′ + C)

3.9  The Tabulation Method

The map method of simplification is convenient as long as the number of variables does not ex-
ceed five or six. As the number of variables increases, the excessive number of squares prevents
a reasonable selection of adjacent squares. The obvious disadvantage of the map is that it is es-
sentially a trial-and-error procedure which relies on the ability of the human user to recognize
certain patterns. For functions of six or more variables, it is difficult to be sure that the best selec-
tion has been made.
90  Chapter 3

The tabulation method overcomes this difficulty. It is a specific step-by-step procedure that
is guaranteed to produce a simplified standard-form expression for a function. It can be applied
to problems with many variables and has the advantage of being suitable for machine computa-
tion. However, it is quite tedious for human use and is prone to mistakes because of its routine,
monotonous process. The tabulation method was first formulated by Quine (3) and later im-
proved by McCluskey (4). It is also known as the Quine-McCluskey method.
The tabular method of simplification consists of two parts. The first is to find by an exhaus-
tive search all the terms that are candidates for inclusion in the simplified function. These terms
are called prime-implicants. The second operation is to choose among the prime-implicants
those that give an expression with the least number of literals.

3.10 Determination of Prime-implicants
The starting point of the tabulation method is the list of minterms that specify the function. The
first tabular operation is to find the prime-implicants by using a matching process. This process
compares each minterm with every other minterm. If two minterms differ in only one variable,
that variable is removed and a term with one less literal is found. This process is repeated for
every minterm until the exhaustive search is completed. The matching-process cycle is repeated
for those new terms just found. Third and further cycles are continued until a single pass through
a cycle yields no further elimination of literals. The remaining terms and all the terms that did not
match during the process comprise the prime-implicants. This tabulation method is illustrated by
the following example.

EXAMPLE 3-13: Simplify the following Boolean function by using the tabulation method:
F = ∑(0, 1, 2, 8, 10, 11, 14, 15)
Step 1: Group binary representation of the minterms according to the number of 1’s
contained, as shown in Table 3-5, column (a). This is done by grouping the minterms into five
sections separated by horizontal lines. The first section contains the number with no 1’s in it.
The second section contains those numbers that have only one 1, The third, fourth, and fifth
sections contain those binary numbers with two, three, and four 1’s, respectively. The decimal
equivalents of the minterms are also carried along for identification.
Step 2: Any two minterms which differ from each other by only one variable can be
combined, and the unmatched variable removed. Two minterm numbers fit into this category
if they both have the same bit value in all positions except one. The minterms in one section
are compared with those of the next section down only, because two terms differing by more
than one bit cannot match. The minterm in the first section is compared with each of the three
minterms in the second section. If any two numbers are the same in every position but one, a
check is placed to the right of both minterms to show that they have been used. The resulting
term, together with the decimal equivalents, is listed in column (b) of the table. The vari-
able eliminated during the matching is denoted by a dash in its original position. In this case
m0 (0000) combines with m1, (0001) to form (000 -). This combination is equivalent to the
 Simplification of Boolean Functions  91 

Table 3-5  Determination of prime-implicants for Example 3-13

(a) (b) (c)

  wxyz wx y z w  x  y  z
0      0 0 0 0 √ 0, 1 0  0   0  - 0, 2, 8,  10 - 0  –  0
0, 2 0  0   - 0 √ 0, 8, 2,  10 - 0  - 0
1      0 0 0 1 √ 0, 8 - 0 0  0 √ 10,  11, 14,  15   1   - 1   -
2       0 0 1 0 √ 10,  14,  11, 15   1   - 1   -
8      1 0 0 0 √ 2,   10 - 0  1   0 √
8,   10 1  0  -  0 √
10 1 0 1 0 √
10, 11 1   0  1  - √
11 1 0 1 1 √ 10, 14 1  - 1  0 √
14 1 1 1 0 √
11, 15 1  - 1  1 √
15    1 1 1 1 √ 14, 15 1 1   1  - √

algebraic operation:
m0 + m1 = w′ x′ y′ z′ + w′ x′ y′ z = w′ x′ y′
Minterm m0 also combines with m2 to form (00-0) and with m8 to form (-000). The result of
this comparison is entered into the first section of column (b). The minterms of sections two
and three of column (a) are next compared to produce the terms listed in the second section of
column (b). All other sections of (a) are similarly compared and subsequent sections formed
in (b). This exhaustive comparing process results in the four sections of (b).
Step 3: The terms of column (b) have only three variables. A 1 under the variable means
it is unprimed, a 0 means it is primed, and a dash means the variable is not included in the
term. The searching and comparing process is repeated for the terms in column (b) to form
the two-variable terms of column (c). Again, terms in each section need to be compared only
if they have dashes in the same position. Note that the term (000-) does not match with any
other term. Therefore, it has no check mark at its right. The decimal equivalents are written
on the left-hand side of each entry for identification purposes. The comparing process should
be carried out again in column (c) and in subsequent columns as long as proper matching is
encountered. In the present example, the operation stops at the third column.
Step 4: The unchecked terms in the table form the prime-implicants. In this example
we have the term w′ x′ y′ (000-) in column (b), and the terms x′ z′(-0-0) and wy (1-1-) in
column (c). Note that each term in column (c) appears twice in the table, and as long as the
term forms a prime-implicants, it is unnecessary to use the same term twice. The sum of the
prime-implicants gives a simplified expression for the function. This is because each checked
term in the table has been taken into account by an entry of a simpler term in a subsequent
column. Therefore, the unchecked entries (prime-implicants) are the terms left to formulate
the function. For the present example, the sum of prime-implicants gives the minimized func-
tion in sum of products:

F = w′ x′ y′ + x′ z′ + w y
92  Chapter 3

y
yz
wx 00 01 11 10

00 1 1 1

01
x
11 1 1
w
10 1 1 1

Figure 3.27  Map for the function of Example 3.13: F = w′ x′ y′ + x′ z′ + w y

It is worth comparing this answer with that obtained by the map method. Figure 3-27 shows
the map simplification of this function. The combinations of adjacent squares give the three
prime-implicants of the function. The sum of these three terms is the simplified expression in
sum of products.
It is important to point out that Example 3-13 was purposely chosen to give the simplified
function from the sum of prime-implicants. In most other cases, the sum of prime-implicants
does not necessarily form the expression with the minimum number of terms. This is demon-
strated in Example 3-14.
The tedious manipulation that one must undergo when using the tabulation method is re-
duced if the comparing is done with decimal numbers instead of binary. A method will now be
shown that uses subtraction of decimal numbers instead of the comparing and matching of binary
numbers. We note that each 1 in a binary number represents the coefficient multiplied by a power
of 2. When two minterms are the same in every position except one, the minterm with the extra
1 must be larger than the number of the other minterm by a power of 2. Therefore, two mint-
erms can be combined if the number of the first minterm differs by a power of 2 from a second
larger number in the next section down the table. We shall illustrate this procedure by repeating
Example 3-13.
As shown in Table 3-6, column (a), the minterms are arranged in sections as before, except
that now only the decimal equivalents of the minterms are listed. The process of comparing min-
terms is as follows: Inspect every two decimal numbers in adjacent sections of the table. If the
number in the section below is greater than the number in the section above by a power of 2 (i.e.,
1, 2, 4, 8, 16, etc.), check both numbers to show that they have been used, and write them down
in column (b). The pair of numbers transferred to column (b) includes a third number in paren-
theses that designates the power of 2 by which the numbers differ. The number in parentheses
tells us the position of the dash in the binary notation. The result of all comparisons of column
(a) is shown in column (b).
The comparison between adjacent sections in column (b) is carried out in a similar fashion,
except that only those terms with the same number in parentheses are compared. The pair of
numbers in one section must differ by a power of 2 from the pair of numbers in the next section.
And the numbers in the next section below must be greater for the combination to take place. In
 Simplification of Boolean Functions  93 

Table 3-6  Determination of prime-implicants of

Example 3-13 with decimal notation

(a) (b) (c)

0 √ 0, 1 (1) 0, 2, 8, 10 (2, 8)
0, 2 (2) √ 0, 2, 8, 10 (2, 8)
1 √ 0, 8 (8) √
2 √ 2, 10 (8) √ 10, 11, 14, 15 (1, 4)
8 √ 8, 10 (2) √ 10, 11, 14, 15 (1, 4)
10, 11 (1) √
10 √
11 √ 10, 14 (4) √
14 √
15 √ 11, 15 (4) √
14, 15 (1) √

column (c), write all four decimal numbers with the two numbers in parentheses designating the
positions of the dashes. A comparison of Tables 3-5 and 3-6 may be helpful in understanding the
derivations in Table 3-6.
The prime-implicants are those terms not checked in the table. These are the same as be-
fore, except that they are given in decimal notation. To convert from decimal notation to binary,
convert all decimal numbers in the term to binary and then insert a dash in those positions desi-
gnated by the numbers in parentheses. Thus 0, 1 (1) is converted to binary as 0000, 0001; a dash
in the first position of either number results in (000-). Similarly, 0, 2, 8, 10 (2, 8) is converted to
the binary notation from 0000, 0010, 1000, and 1010, and a dash inserted in positions 2 and 8,
to result in (-0-0)

EXAMPLE 3-14: Determine the prime-implicants of the function:

F (w, x, y, z) = Σ(1, 4, 6, 7, 8, 9, 10, 11, 15)

The minterm numbers are grouped in sections as shown in Table 3-7, column (a). The binary
equivalent of the minterm is included for the purpose of counting the number of 1’s. The
binary numbers in the first section have only one 1; in the second section, two 1’s; etc. The
minterm numbers are compared by the decimal method and a match is found if the number in
the section below is greater than that in the section above. If the number in the section below
is smaller than the one above, a match is not recorded even if the two numbers differ by a
power of 2. The exhaustive search in column (a) results in the terms of column (b), with all
minterms in column (a) being checked. There are only two matches of terms in column (b).
Each gives the same two-literal term recorded in column (c). The prime-implicants consist of
all the unchecked terms in the table. The conversion from the decimal to the binary notation
is shown at the bottom of the table. The prime-implicants are found to be x′ y′ z, w′ x z′, w′ x
y, x y z, w y z, and w x′.
94  Chapter 3

Table 3-7  Determination of prime-implicants for Example 3-14

(a) (b) (c)

0001 1 √ 1, 9 (8) 8, 9, 10, 11 (1, 2)
0100 4 √ 4, 6 (2) 8, 9, 10, 11 (1, 2)
1000 8 √ 8, 9 (1) √
8, 10 (2) √
0110 6 √
1001 9 √ 6, 7 (1)
1010 10 √ 9, 11 (2) √
10, 11 (1) √
0111 7 √
1011 11 √ 7, 15 (8)
11,15 (4)
1111 15 √
Prime-implicants
Binary
Decimal w xy z Term
1, 9 (8) - 0  0  1 x′ y′ z
4, 6 (2) 0 1 -  0 w′xz′
6, 7(1) 0 1  1    - w′xy
7, 15 (8) - 1 1   1 xyz
11, 15(4) 1 - 1   1 wyz
8, 9, 10, 11 (1, 2) 1 0 -- wx′

The sum of the prime-implicants gives a valid algebraic expression for the function.
However, this expression is not necessaily the one with the minimum number of terms. This
can be demonstrated from inspection of the map for the function of Example 3-14. As shown in
Fig. 3-28, the minimized function is recognized to be:

F = x′ y′z + w′ x z′ + x y z + w x′

which consists of the sum of four of the six prime-implicants derived in Example 3-14. The tabu-
lar procedure for selecting the prime-implicants that give the minimized function is the subject
of the next section.

3.11  Selection Of Prime-implicants

The selection of prime-implicants that form the minimized function is made from a prime-im-
plicant table. In this table, each prime-implicant is represented in a row and each minterm in
a column. Crosses are placed in each row to show the composition of minterms that make the
 Simplification of Boolean Functions  95 

y
yz
wx 00 01 11 10

00 1

01 1 1 1
x
11 1
w
10 1 1 1 1

Figure 3.28  Map for the function of Example 3.14; F = x′ y′ z + w′ x z′ + x y z + w x′

prime-implicants. A minimum set of prime-implicants is then chosen that covers all the minterms
in the function. This procedure is illustrated in Example 3-15.

EXAMPLE 3-15: Minimize the function of Example 3-14. The prime-implicant table for
this example is shown in Table 3-8. There are six rows, one for each prime-implicant (derived
in Example 3-14), and nine columns, each representing one minterm of the function. Crosses
are placed in each row to indicate the minterms contained in the prime-implicant of that row.
For example, the two crosses in the first row indicate that minterms 1 and 9 are contained in
the prime-implicant x′ y′ z. It is advisable to include the decimal equivalent of the prime-im-
plicant in each row, as it conveniently gives the minterms contained in it. After all the crosses
have been marked, we proceed to select a minimum number of prime-implicants.
The completed prime-implicant table is inspected for columns containing only a single
cross. In this example, there are four minterms whose columns have a single cross: 1, 4, 8,
and 10. Minterm 1 is covered by prime-implicant x′ y′ z, i.e., the selection of prime-implicant
x′ y′ z guarantees that minterm 1 is included in the function. Similarly, minterm 4 is covered
by prime-implicant w′ x z′, and minterms 8 and 10, by prime-implicant w x′. Prime-implicants

Table 3-8  Prime-implicant table for Example 3-15

1 4 6 7 8 9 10 11 15
√ x′ y′ z 1, 9 X X
√ w′ x z′ 4, 6 X X
w′ x y 6, 7 X X
xyz 7, 15 X X
wyz 11, 15 X X
√ w x′ 8, 9, 10, 11 X X X X
√ √ √ √ √ √ √
96  Chapter 3

that cover minterms with a single cross in their column are called essential prime-implicants.
To enable the final simplified expression to contain all the minterms, we have no alternative
but to include essential prime-implicants. A check mark is placed in the table next to the es-
sential prime-implicants to indicate that they have been selected.
Next we check each column whose minterm is covered by the selected essential prime-
implicants. For example, the selected prime-implicant x′ y′ z covers minterms 1 and 9. A
check is inserted in the bottom of the columns. Similarly, prime-implicant w′ x z′ covers min-
terms 4 and 6, and w x′ covers minterms 8, 9, 10, and 11. Inspection of the prime-implicant
table shows that the selection of the essential prime-implicants covers all the minterms of
the function except 7 and 15. These two minterms must be included by the selection of one
or more prime-implicants. In this example, it is clear that prime-implicant x y z covers both
minterms and is therefore the one to be selected. We have thus found the minimum set of
prime-implicants whose sum gives the required minimized function:
F = x′ y′ z + w′ x z′ + w x′ + x y z

The simplified expressions derived in the preceding examples were all in the sum of prod-
ucts form. The tabulation method can be adapted to give a simplified expression in product of
sums. As in the map method, we have to start with the complement of the function by taking the
0’s as the initial list of minterms. This list contains those minterms not included in the original
function which are numerically equal to the maxterms of the function. The tabulation process
is carried out with the 0’s of the function and terminates with a simplified expression in sum
of products of the complement of the function. By taking the complement again, we obtain the
simplified product of sums expression.
A function with don’t-care conditions can be simplified by the tabulation method after a
slight modification. The don’t-care terms are included in the list of minterms when the prime-
implicants are determined. This allows the derivation of prime-implicants with the least number
of literals. The don’t-care terms are not included in the list of minterms when the prime-impli-
cant table is set up, because don’t-care terms do not have to be covered by the selected prime-
implicants.

3.12  Concluding Remarks

Two methods of Boolean function simplification were introduced in this chapter. The criterion
for simplification was taken to be the minimization of the number of literals in sum of products
or product of sums expressions. Both the map and the tabulation methods are restricted in their
capabilities since they are useful for simplifying only Boolean functions expressed in the stan-
dard forms. Although this is a disadvantage of the methods, it is not very critical. Most applica-
tions prefer the standard forms over any other form. We have seen from Fig. 3-15 that the gate
implementation of expressions in standard form consists of no more than two levels of gates.
Expressions not in the standard form are implemented with more than two levels. Humphrey (5)
shows an extension of the map method that produces simplified multilevel expressions.
One should recognize that the reflected-code sequence chosen for the maps is not unique. It
is possible to draw a map and assign a binary reflected-code sequence to the rows and columns
 Simplification of Boolean Functions  97 

x
yz 0 1

x 00 0 4
xy
z 00 01 11 10
01 1 5
0 0 2 6 4 z
11 3 7
z 1 1 3 7 5
y
10 2 6
y
(a) (b)
Figure 3.29  Variations of the three-variable map

different from the sequence employed here. As long as the binary sequence chosen produces a
change in only one bit between adjacent squares, it will produce a valid and useful map.
Two alternate versions of the three-variable maps which are often found in the digital logic
literature are shown in Fig. 3-29. The minterm numbers are written in each square for reference.
In (a), the assignment of the variables to the rows and columns is different from the one used in
this book. In (b), the map has been rotated in a vertical position. The minterm number assign-
ment in all maps remains in the order x y z. For example, the square for minterm 6 is found by
assigning to the ordered variables the binary number x y z = 110. The square for this minterm is
found in (a) from the column marked x y = 11 and the row with z = 0. The corresponding square
in (b) belongs in the column marked with x = 1 and the row with y z = 10. The simplification
procedure with these maps is exactly the same as described in this chapter except, of course, for
the variations in minterm and variable assignment.
Two other versions of the four-variable map are shown in Fig. 3-30. The map in (a) is very
popular and is used quite often in the literature. Here again, the difference is slight and is mani-
fested by a mere interchange of variable assignment from rows to columns and vice versa. The
map in (b) is the original Veitch diagram (1) which Karnaugh (2) modified to the one shown in

AB A
A
CD 00 01 11 10

00 0 4 12 8 12 14 6 4
B
01 1 5 13 9 13 15 7 5
D D
11 3 7 15 11 9 11 3 1
C
10 2 6 14 10 8 10 2 0

B C
(a) (b)

Figure 3.30  Variation of the four-variable map

98  Chapter 3

(a). Again, the simplification procedures do not change when these maps are used instead of the
one employed in this book. There are also variations of the five- and six-variable maps. In any
case, any map that looks different from the one used in this book, or is called by a different name,
should be recognized merely as a variation of minterm assignment to the squares in the map.
As is evident from Examples 3-13 and 3-14, the tabulation method has the drawback that
errors inevitably occur in trying to compare numbers over long lists. The map method would
seem to be preferable, but for more than five variables, we cannot be certain that the best simpli-
fied expression has been found. The real advantage of the tabulation method lies in the fact that
it consists of specific step-by-step procedures that guarantee an answer. Moreover, this formal
procedure is suitable for computer mechanization.
It was stated in Section 3-9 that the tabulation method always starts with the minterm list
of the function. If the function is not in this form, it must be converted. In most applications,
the function to be simplified comes from a truth table, from which the minterm list is readily
available. Otherwise, the conversion to minterms adds considerable manipulative work to the
problem. However, an extension of the tabulation method exists for finding prime-implicants
from arbitrary sum of products expressions. See, for example, McCluskey (7).
In this chapter, we have considered the simplification of functions with many input vari-
ables and a single output variable. However, some digital circuits have more than one output.
Such circuits are described by a set of Boolean functions, one for each output variable. A circuit
with multiple outputs may sometimes have common terms among the various functions which
can be utilized to form common gates during the implementation. This results in further simpli-
fication not taken into consideration when each function is simplified separately. There exists an
extension of the tabulation method for multiple-output circuits (6, 7). However, this method is
too specialized and very tedious for human manipulation. It is of practical importance only if a
computer program based on this method is available to the user.

REFERENCES

1. Veitch, E. W., “A Chart Method for Simplifying Truth Functions.” Proc. of the ACM (May 1952),
127-33.

2. Karnaugh, M., “A Map Method for Synthesis of Combinational Logic Circuits.” Trans. A1EE, Comm.
and Electronics, Vol. 72, Part I (November 1953), 593-99.

3. Quine, W. V., “The Problem of Simplifying Truth Functions.” Am. Math. Monthly, Vol. 59, No. 8
(October 1952), 521-31.

4. McCluskey, E. J., Jr., “Minimization of Boolean Functions.” Belt System Tech. J., Vol. 35, No. 6
(November 1956), 1417–44.

5. Humphrey, W, S., Jr., Switching Circuits with Computer Applications. New York; McGraw-Hill Book
Co, 1958, Chap. 4.

6. Hill, F. J, and G. R. Peterson, Introduction to Switching Theory and Logical Design, 2nd ed. New
York: John Wiley & Sons, Inc., 1974, Chapters. 6 and 7.

7. McCluskey, E. J., Jr., Introduction to the Theory of Switching Circuits. New York: McGraw-Hill Book
Co., 1965, Chap. 4.
 Simplification of Boolean Functions  99 

8. Kohavi, Z., Switching and Finite Automata Theory. New York: McGraw-Hill Book Co, 1970.

9. Nagle, H. T. Jr., B. D. Carrol, and J. D. Irwin, An Introduction to Computer Logic. Englewood Cliffs.
N.J.: Prentice-Hall, Inc., 1975.

PROBLEMS

3-1. Obtain the simplified expressions in sum of products for the following Boolean functions:
(a) F(x, y, z) = Σ(2, 3, 6, 7)
(b) F(A, B, C. D) = Σ(7, 13, 14, 15)
(c) F(A, B, C, D) = Σ(4, 6, 7, 15)
(d) F(w, x, y, z) = Σ(2, 3, 12, 13, 14, 15)
3-2. Obtain the simplified expressions in sum of products for the following Boolean functions;
(a) x y + x′ y′ z′ + x′ y z′
(b) A′B + BC′ + B′C′
(c) a′ b′ + bc + a′ b c′
(d) x y′ z + x y z′ + x′ y z + x y z
3-3. Obtain the simplified expressions in sum of products for the following Boolean functions:
(a) D (A′ + B)+ B′(C + AD)
(b) ABD + A′C′D′ + A′B + A′CD′ + AB′D′
(c) k′ l m′ + k′ m′ n + klm′n′ + lmn′
(d) A′B′C′D′ + AC′D′ + B′CD′ + A′BCD + BC′D
(e) x′ z + w′ x y′ + w(x′ y + x y′)
3-4. Obtain the simplified expressions in sum of products for the following Boolean functions:
(a) F(A, B, C, D, E) = Σ(0, 1, 4, 5, 16, 17, 21, 25, 29)
(b) BDE + B′C′D + CDE + A′B′CE + A′B′C + B′C′D′E′
(c) A′B′CE′ + A′B′C′D′ + B′D′E′ + B′CD′ + CDE′ + BDE′
3-5. Given the following truth table:

x y z F1 F2
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

(a) Express F1 and F2 in product of maxterms.

(b) Obtain the simplified functions in sum of products.
(c) Obtain the simplified functions in product of sums.
100  Chapter 3

3-6. Obtain the simplified expressions in product of sums:

(a) F(x, y, z) = Π (0, 1, 4, 5)
(b) F(A, B, C, D) = Π (0, 1, 2, 3, 4, 10, 11)
(c) F(w, x, y, z) = Π (1, 3, 5, 7, 13, 15)
3-7. Obtain the simplified expressions in (1) sum of products and (2) product of sums:
(a) x′ z′ + y′ z′ + yz′ + x y z
(b) (A + B′ + D) (A′ + B + D)(C + D)(C′ + D′)
(c) (A′ + B′ + D′)(A + B′ + C′)(A′ + B + D′)(B + C′ + D′)
(d) (A′ + B′ + D) (A′ + D′) (A + B + D′)(A + B′ + C + D)
(e) w′ y z′ + υ w′ z′ + υ w′ x + υ′ wz + υ′ w′ y′ z′
3-8. Draw the gate implementation of the simplified Boolean functions obtained in problem 3-7 using
AND and OR gates.
3-9. Simplify each of the following functions and implement them with NAND gates.
(a) F1 = AB′ + AB′C + A′BD + ABE′+ A′BE′+ A′D
(b) F2 = (A + C) (A′ + B′ + C)(A′ + B′ + C + D)(B′ + C + D′)
3-10. Simplify each of the following functions and implement them with NOR gates
(a) F1 = (A + B) (A′ + B′ + C + D′)(A′ + B′ + D′)(A+ B′ + C + D′)(C + D′)
(b) F2 = AB′C + A′BD + A′BE′ + A′BC′ + A′BC′ + CD
3-11. Implement the following functions with NAND gates. Assume that both the normal and complement
inputs are available.
(a) BD + BCD + AB′C′D′ + A′B′CD′ with no more than six gates, each having three inputs.
(b) (AB + A′B′)(CD′ + C′D) with two-input gates.
3-12. Implement the following functions with NOR gates. Assume that both the normal and complement
inputs are available.
(a) AB′ + C′D′ + A′CD′ + DC(AB + A′B′) + DB(AC′ + A′C)
(b) AB′CD′ + A′BCD′ + AB′C′D + A′BC′D
3-13. List the eight degenerate two-level forms and show that they reduce to a single operation. Explain
how the degenerate two-level forms can be used to extend the fan-in of gates.
3-14. Implement the functions of problem 3-9 with the following two-level forms:
NOR-OR, NAND-AND, OR-NAND, and AND-NOR.
3-15. Simplify the Boolean function F in sum of products using the don’t-care conditions d:
(a) F = y′ + x′ z′
d=yz+xy
(b) F = B′C′D′ + BCD′ + ABCD′
d = B′CD′ + A′BC′D
 Simplification of Boolean Functions  101 

3-16. Simplify the Boolean function F using the don’t-care conditions d, in (1) sum of products and (2)
product of sums:
(a) F = A′B′D′ + A′CD + A′BC
d = A′BC′D + ACD + AB′ D′
(b) F = w′ (x′ y + x′ y′ + x y z) + x ‘z′(y + w)
d = w′ x(y′ z + y z′) + wyz
(c) F = ACE + A′CD′E′ + A′C′DE
d = DE′ + A′D′E + AD′E′
(d) F = B′DE′ + A′BE + B′C′E′ + A′BC′D′
d = BDE′ + CD′E′
3-17. Implement the following functions using the don’t-care conditions. Assume that both the normal and
complement inputs are available.
(a) F = A′B′C′ + AB′D + A′B′CD′ with no more than two NOR gates.
d = ABC + AB′D′
(b) F = (A + D)(A′ + B)(A′ + C′) with no more than three NAND gates.
(c) F = B′D + B′C + ABCD with NAND gates.
d = A′BD + AB′C′D′
3-18. Implement the following function with either NAND or NOR gates. Use only four gates. Only the
normal inputs are available.
F = w′ x z + w′ y z + x′ y z′ + w x y′ z
d=wyz
3-19. The following Boolean expression:
BE + B′DE′
is a simplified version of the expression:
A′BE + BCDE + BC′D′E + A′B′DE′ + B′C′DE′
Are there any don’t-care conditions? If so, what are they?
3-20. Give three possible ways to express the function:
F = A′B′D′ + AB′CD′ + A′BD + ABC′D
with eight or less literals.
3-21. With the use of maps, find the simplest form in sum of products of the function F = fg, where f and
g are given by:
f = w x y′ + y′ z + w′ y z′ + x′ y z′
g = (w + x + y′ + z′) (x′ + y′ + z)(w′ + y + z′)

Hint: See problem 2-8(b).

3-22. Simplify the Boolean function of problem 3-2(a) using the map defined in Fig. 3-29(a). Repeat with
the map of Fig. 3-29(b).
3-23. Simplify the Boolean function of problem 3-3(a) using the map defined in Fig. 3-30(a). Repeat with
the map of Fig. 3-30(b).
102  Chapter 3

3-24. Simplify the following Boolean functions by means of the tabulation method.
(a) F(A, B, C, D, E, F, G)= ∑ (20. 28, 52, 60)
(b) F(A, B, C, D, E, F, G) = ∑ (20, 28, 38, 39, 52, 60, 102, 103, 127)
(c) F(A, B, C, D, E, F) = ∑ (6, 9, 13, 18, 19, 25, 27, 29, 41, 45, 57, 61)
3-25. Repeat problem 3-6 using the tabulation method.
3-26. Repeat problem 3-16 (c) and (d) using the tabulation method.
3-27. Simplify f(w, x, y, z) = ∑(0, 1, 2, 8, 12, 13, 14) + d(3, 5, 10, 15) with K-Map and implement using
two-variable NAND gates.
3-28. What are Prime-implicants? Minimize following equation using Quine-McCluskey method.
f(v, w, x, y, z) = ∑(1, 4, 12, 14, 16, 18, 21, 25, 26, 29, 31) + d(0, 2, 5, 30)