REFERRED BOOKS/SOURCE

05:01 AM
 Charles H Roth and Larry L Kinney, Analog
and Digital Electronics, Cengage
Learning,2019
 Charles H Roth and Larry L Kinney,
Fundamental of Logic Design, Cengage
Learning, 2017.
 Donald P Leach, Albert Paul Malvino &

Goutam Saha: Digital Principles and

Applications, 7th Edition, Tata McGraw Hill,
2015

1
 MODULE-2

05:01 AM
Karnaugh maps
&
Quine-McClusky Method

2
BASIC GATES-1
 A logic gate is a digital circuit with 1 or more
input voltages but only 1 output voltage.
 Logic gates are the fundamental building blocks of
digital systems.
 By connecting the different gates in different ways, we
can build circuits that perform arithmetic and other
functions associated with the human brain.
 Because the circuits simulate mental processes,
gates are often called logic circuits. NOT, OR &
AND gates are the basic types of gates.
 The inter-connection of gates to perform a
variety of logical operations is called logic
design.
 The operation of a logic gate can be easily understood
with the help of "truth table".
 A truth table lists all possible combinations of 3
inputs and the corresponding outputs.
BASIC GATES-2
 NOT GATE (INVERTER)
 It is a gate with only 1 input and a

complemented output.

4
BASIC GATES-3
 AND GATE
 This is a gate with 2 or more inputs.

 The output is HIGH only when all inputs are

HIGH.

5
BASIC GATES-4

6
BASIC GATES-5
 OR GATE
 This is a gate with 2 or more inputs.

 The output is HIGH when any input is HIGH.

7
BASIC GATES-6

8
BASIC GATES-9
 NOR GATE
 This represents an OR gate followed by an

inverter.

9
BASIC GATES-10
 Universality of NOR Gate

10
BASIC GATES-11
 NAND GATE
 This represents an AND gate followed by an

inverter.

11
BASIC GATES-12
 Universality of NAND Gate

12
EXCLUSIVE-OR GATES-1
 The exclusive-OR gate has a high output only
when an odd number of inputs is high.

 OR 13
 Y = A⨁B
EXCLUSIVE-OR GATES-2

14
EXCLUSIVE-OR GATES-2

A B Y
0 0 1 A
0 1 0 Y
B
1 0 0
1 1 1

15
INTRODUCTION

05:01 AM
 Each gate input is labelled with a variable.
 Each appearance of a variable or its
complement in an expression will be referred
to as a literal.
 The following expression, which has three
variables, has 10 literals
 ab′c + a′b + a′bc′ + b′c′
 A truth table (also called a table of
combinations) specifies the values of a
Boolean expression for every possible
combination of values of the variables in the
expression. 16
INTRODUCTION

05:01 AM
 An expression is said to be in sum-of-
products (SOP) form when all products are
the products of single variables.
 E.g.AB′ + CD′E + AC′E′
 A sum-of-products expression can be realized
using one or more AND gates feeding a single OR
gate at the circuit output.
 An expression is in product-of-sums (POS)
form when all sums are the sums of single
variables.
 E.g.(A + B′)(C + D′ + E)(A + C′ + E′)
 A product-of-sums expression can be realized
using one or more OR gates feeding a single AND
17
gate at the circuit output.
INTRODUCTION

05:01 AM
18
INTRODUCTION

05:01 AM
 Redundant Terms: The Term not or no
longer needed or useful.
 (A+ BC)(A + D + E)
 = A + AD + AE + ABC + BCD + BCE
 = A(1 + D + E + BC) + BCD + BCE
 = A + BCD + BCE

19
INTRODUCTION

05:01 AM
 The Consensus Theorem
 Useful in simplifying Boolean expressions.
 The consensus theorem can be used to eliminate
redundant terms from Boolean expressions.
 E.g. XY + X′Z + YZ,
 the term YZ is redundant and can be eliminated to form
the equivalent expression XY + X′Z. The term that was
eliminated is referred to as the consensus term.
 Given a pair of terms for which a variable appears in
one term and the complement of that variable in
another, the consensus term is formed by multiplying
the two original terms together, leaving out the
selected variable and its complement.
 E.g.
 The consensus of ab and a′c is bc;
 The consensus of abd and b′de′ is (ad)(de′) = ade′. 20
 The consensus of terms ab′d and a′bd′ is 0.
SUM-OF-PRODUCTS (SOP)
METHOD-1

05:01 AM
 Possible ways to AND two or more input
signals that are in complement and
uncomplement form.
 A SOP expression is two or more AND

functions ORed together.

21
SUM-OF-PRODUCTS (SOP)
METHOD-2

05:01 AM
 ANDing two variables and their
complements

22
SUM-OF-PRODUCTS (SOP)
METHOD-3

05:01 AM
23
SUM-OF-PRODUCTS (SOP)
METHOD-4

05:01 AM
 Example:
 Fundamental Products for Three Inputs

24
SUM-OF-PRODUCTS (SOP)
METHOD-5

05:01 AM
 The above three variable minterms can
alternatively be represented by mo, m1, m2,
m3, m4, m5, m6, and m7 respectively. Note
that, for n variable problem there can be 2n
number of minterms.
 The fundamental products by listing

each one next to the input condition

that results in a high output.
 For instance, when A = 1, B = 0 and C = 0,

the fundamental product results in an output

of
25
SUM-OF-PRODUCTS EQUATION-1

05:01 AM
26
SUM-OF-PRODUCTS EQUATION-2

05:01 AM
 To get the sum-of-products equation, all you
have to do is OR the fundamental products

 Alternate representation

27
SUM-OF-PRODUCTS EQUATION-3

05:01 AM
 where '∑:' symbolizes summation or logical
OR operation that is performed on
corresponding minterm’s and Y = F (A, B, C)
means Y is a function of three Boolean
variables A, B and C. This kind of
representation of a truth table is also known
as canonical sum form.

28
LOGIC CIRCUIT

05:01 AM
29
LAB EXPERIMENT

05:01 AM
Input Output
A B Sum (S) Carry (C)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

30
PRODUCT-OF-SUMS METHOD-1

05:01 AM
 Given a truth table, identify the fundamental
sums needed for a logic design. Then by
ANDing these sums, will get the product-of-
sums equation corresponding to the truth
table.
 But, in the sum-of-products method, the

fundamental product produces an output l for

the corresponding input condition.
 But with the product of- sums method, the

fundamental sum produces an output 0 for

the corresponding input condition.
31
PRODUCT-OF-SUMS METHOD-2

05:01 AM
 Converting a Truth Table to an Equation

32
PRODUCT-OF-SUMS METHOD-3

05:01 AM
 Logic Circuit

33
PRODUCT-OF-SUMS METHOD-4

05:01 AM
 Conversion between SOP and POS
 SOP and POS occupy complementary
locations in a truth table.
 Identifying
complementary locations,
 Changing minterm to maxterm or reverse, and
 Changing summation by product or reverse.

34
CONVERSION BETWEEN SOP AND
POS

05:01 AM
35
DON'T-CARE CONDITIONS-1

05:01 AM
 In digital systems, certain input conditions
never occur during normal operation;
therefore, the corresponding output never
appears. Since the output never appears, it is
indicated by an X in the truth table.
 The X is called a don 't-care condition.

Whenever you see an X in a truth table, you

can let it equal either 0 or 1, whichever
produces a simpler logic circuit.

36
DON'T-CARE CONDITIONS-2

05:01 AM
 Truth Table with Don’t-Cares
 In Minterm form
F =Σ m(0, 3, 7) +Σ d(1, 6)
 In Maxterm form
 F =Π M(2, 4, 5)· Π D(1, 6)

37
DON'T-CARE CONDITIONS-2

05:01 AM
 Truth Table with Don't-Care Conditions

 Y=F(A,B,C,D) = ∑m (9) + 38
d(10,11,12,13,14,15)
PROBLEMS

05:01 AM
 Design a logic circuit that has three inputs, A,
B, and C, and whose output will be HIGH only
when a majority of the inputs are HIGH.


39
KARNAUGH MAPS

05:01 AM
 Switching functions can generally be simplified
by using the algebraic techniques.
 However, two problems arise when algebraic
procedures are used:
 1. The procedures are difficult to apply in a systematic
way.
 2. It is difficult to tell when you have arrived at a
minimum solution.
 The Karnaugh map method and the Quine-
McCluskey procedure used to overcome these
difficulties by providing systematic methods for
simplifying switching functions.
 The Karnaugh map is useful tool for simplifying
and manipulating switching functions of three or 40
four variables (Literals).
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 When a function is realized using AND and OR
gates, the cost of realizing the function is directly
related to the number of gates and gate inputs
used.
 The Karnaugh map techniques developed that
lead directly to minimum cost two-level circuits
composed of AND and OR gates.
 An expression consisting of a sum of product
terms corresponds directly to a two-level circuit
composed of a group of AND gates feeding a
single OR gate.
 Similarly, a product-of-sums expression
corresponds to a two-level circuit composed of OR
gates feeding a single AND gate.
 Therefore, to find minimum cost two-level AND-OR
gate circuits, we must find minimum expressions 41
in sum-of-products or product-of-sums form.
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 A minimum sum-of-products expression for a
function is defined as a sum of product terms which
 (a) has a minimum number of terms and
 (b) of all those e xpressions which have the same
minimum number of terms, has a minimum number of
literals.
 The minimum sum of products corresponds directly
to a minimum two-level gate circuit which has
 (a) a minimum number of gates and
 (b) a minimum number of gate inputs.
 Unlike the minterm expansion for a function, the
minimum sum of products is not necessarily
unique; that is, a given function may have two
different minimum sum-of-products forms,
each with the same number of terms and the 42
same number of literals.
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 Given a minterm expansion, the minimum
sum-of-products form can often be obtained
by the following procedure:
 1.Combine terms by using the uniting theorem
XY′ + XY = X. Do this repeatedly to eliminate as
many literals as possible. A given term may be
used more than once because X + X = X.
 2. Eliminate redundant terms by using the
consensus theorem or other theorems.

 Note: Unfortunately, the result of this

procedure may depend on the order in which
terms are combined or eliminated so that the
43
final expression obtained is not necessarily
minimum.
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 Find a minimum sum-of-products expression
for F(a, b, c) = m Σ (0, 1, 2, 5, 6, 7)

44
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 A minimum product-of-sums expression
for a function is defined as a product of sum
terms which
 (a) has a minimum number of terms, and
 (b) of all those expressions which have the same
number of terms, has a minimum number of
literals.
 Unlike the maxterm expansion, the minimum
product-of-sums form of a function is not
necessarily unique.
 Minimum product of sums can often be

obtained by uniting theorem (X + Y)(X + Y′) 45

= X is
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING
FUNCTIONS

05:01 AM
 Minterms and products are represented in
algebraic notation or binary notation.
 The first four-variable example below illustrates
this for minterms and the second for products
containing three literals. The dash indicates a
missing variable.
 ab′cd′ + ab′cd = ab′c
 1 0 1 0 + 1 0 1 1 = 101–
 ab′c + abc = ac
 1 0 1– + 111– = 1–1–

 Note that minterms only combine if they differ in

one variable, and products only combine if they
have dashes in the same position (same missing 46

variables) and differ in one other variable.

KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
47
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
• Minterms in adjacent squares of
the map can be combined since
they differ in only one variable.
• Thus, A′B′ and A′B combine to form
A′, and this is indicated by looping
(Grouping) the corresponding 1’s
on the map in Figure 48
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Two-Variable Maps
 Example: Y =F(A,B)= ∑m(2,3)

49
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
The rows are labeled in the sequence 00, 01, 11, 10 so that
values in adjacent rows differ in only one variable. 50
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Location of Minterms on a Three-Variable
Karnaugh Map

51
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Three-Variable Maps
 Example: Y = F(A, B, C) = ∑m(2,6,7)

52
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Given the minterm expansion of a function, it can be
plotted on a map by placing 1’s in the squares which
correspond to minterms of the function and 0’s in the
remaining squares (the 0’s may be omitted if desired).
 E.g. Karnaugh Map of
F(a, b, c) = Σ m(1, 3, 5)
= Π M(0, 2, 4, 6, 7)

53
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Karnaugh Maps for Product Terms

54
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Simplification of a Three-Variable Function
 Terms in adjacent squares on the map differ in
only one variable and combine them.
 E.g. a′b′c and a′bc combine to form a′c, and a′b′c
and ab′c combine to form b′c,

55
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Karnaugh Maps that Illustrate the Consensus
Theorem
 XY + X′Z + YZ = XY + X′Z
 Note that the consensus term (YZ) is redundant
because its 1’s are covered by the other two
terms.

56
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Function with Two Minimum Forms
 Two minimum solutions for F = Σ m(0, 1, 2, 5, 6,
7).

57
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 The Karnaugh map method is easily
extended to functions with don’t-care
terms.
 The required minterms are indicated by 1’s

on the map, and the don’t-care minterms are

indicated by X’s.
 When choosing terms to form the minimum

sum of products, all the 1’s must be covered,

but the X’s are only used if they will simplify
the resulting expression.

58
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Exercise Problems:
1. Given F1 =Σ m(0, 4, 5, 6) and F2 =Σ m(0, 3,
6, 7) find the minterm expression for F1 and
F2 using K-map.

59
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Exercise Problems:
1. Work (a) and (b) with the following truth table:
a) Find the simplest expression for F, and specify the
values of the don’t-cares that lead to this
expression.
b) Repeat (a) for G. (Hint: Can you make G the same
as one of the inputs by properly choosing the
values for the don’t-care?)

60
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH
MAPS

05:01 AM
 Exercise Problems:
 Find the minimum sum of products for each

function using a Karnaugh map.

 (a) f1(a, b, c) = m0 + m2 + m5 + m6
 (b) f2(d, e, f ) = Σ m(0, 1, 2, 4)
 (c) f3(r, s, t) = rt′ + r′s′ + r′s
 (d) f4(x, y, z) = M0 · M5

61
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS

05:01 AM
 Location of Minterms on Four-Variable
Karnaugh Map

62
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS

05:01 AM
 Example: Y= F(A,B,C,D)= ∑m(1,6,7,14)

63
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS

05:01 AM
 Simplification of Four-Variable Functions

• Minterms can be combined in groups of two, four, or eight 64

to eliminate one, two, or three variables, respectively.
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS

05:01 AM
 Simplification of an Incompletely Specified
Function

65
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS

05:01 AM
 A minimum product of sums can also be obtained from the
map.
 Because the 0’s of f are 1’s of f′, the minimum sum of
products for f′ can be determined by looping the 0’s on a
map of f.
 The complement of the minimum sum of products for f′ is
then the minimum product of sums for f.
 The following example illustrates this procedure for
 f = x′z′ + wyz + w′y′z′ + x′y
 Then, from the 0’s,
 f ′ = y′z + wxz′ + w′xy
 and the minimum product of sums for f is
 f = (y + z′)(w′ + x′ + z)(w + x′ + y′)

66
KARNAUGH SIMPLIFICATIONS-1

05:01 AM
 The Karnaugh map uses the following rules for the
simplification of expressions
by grouping together adjacent cells
containing ones.
 After drawing a Kamaugh map,
 Encircle the octets first,
 The quads second, and
 The pairs last.

67
KARNAUGH SIMPLIFICATIONS-2

05:01 AM
 Groups may not include any cell
containing a zero.

 Groups may be horizontal or vertical,

but not diagonal.

68
KARNAUGH SIMPLIFICATIONS-3

05:01 AM
 Groups must contain 1, 2, 4, 8, or in general
2n cells.
 That is if n = 1, a group will contain two 1's
since 21 = 2.
 If n = 2, a group will contain four 1's since 2 2 =
4.

69
KARNAUGH SIMPLIFICATIONS-4

05:01 AM
 Each group should be as large as possible.

 Each cell containing a one must be in at least

one group.

70
KARNAUGH SIMPLIFICATIONS-5

05:01 AM
 Groups may overlap.

 Groups may wrap (Rolling the Map) around the table. The
leftmost cell in a row may be grouped with the rightmost cell and
the top cell in a column may be grouped with the bottom cell.

71
KARNAUGH SIMPLIFICATIONS-6

05:01 AM
 Rolling the Map

72
KARNAUGH SIMPLIFICATIONS-7

05:01 AM
 Always overlap groups if possible
 Use the 1s more than once to get the largest

groups you can.

73
KARNAUGH SIMPLIFICATIONS-8

05:01 AM
 There should be as few groups as
possible, as long as this does not
contradict any of the previous rules.

74
KARNAUGH SIMPLIFICATIONS-11

05:01 AM
1. No zeros allowed (Only in SOP).
2. No diagonals.
3. Only power of 2 number of cells in each
group.
4. Groups should be as large as possible.
5. Every one must be in at least one group.
6. Overlapping allowed.
7. Wrap around allowed.
8. If possible roll and overlap to get the largest
groups you can find.
75
9. Fewest number of groups possible.
K- MAP GROUPING EXAMPLES-1

05:01 AM
 Rolling and overlapping

76
K- MAP GROUPING EXAMPLES-2

05:01 AM
77
ELIMINATING REDUNDANT
GROUPS-2

05:01 AM
 A group whose 1s are already used by other
groups.

78
ELIMINATING REDUNDANT
GROUPS-2

05:01 AM
 A group whose 1s are already used by other
groups.

79
ELIMINATING REDUNDANT
GROUPS-2

05:01 AM
 A group whose 1s are already used by other
groups.

 All the 1 s of the quad are used by the pairs.

Because of this, the quad is redundant and
can be eliminated to get
80
ELIMINATING REDUNDANT
GROUPS-2

05:01 AM
 A group whose 1s are already used by other
groups.

81
SUMMARY OF THE KARNAUGH-MAP
METHOD FOR SIMPLIFYING BOOLEAN
EQUATIONS

05:01 AM
1. Enter a 1 on the Karnaugh map for each
fundamental product that produces a 1
output in the truth table. Enter 0s
elsewhere.
2. Encircle the octets, quads, and pairs.
Remember to roll and overlap to get the
largest groups possible.
3. If any isolated 1s remain, encircle each.
4. Eliminate any redundant group.
5. Write the Boolean equation by ORing the
products corresponding to the encircled 82
groups.
EXAMPLE-1

05:01 AM
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

83
EXAMPLE-1

05:01 AM
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

84
EXAMPLE-1

05:01 AM
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

85
EXAMPLE-1

05:01 AM
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

86
EXAMPLE-1

05:01 AM
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

87
EXAMPLE-2

05:01 AM
88
DON'T-CARE CONDITIONS-3

05:01 AM
89
DON'T-CARE CONDITIONS-4

05:01 AM
 Ideas about don't-care conditions:
1. Given the truth table, draw a Karnaugh map
with 0s, 1s, and don't-cares (X).
2. Encircle the actual 1s on the Karnaugh map
in the largest groups you can find by treating
the don't cares as 1s.
3. After the actual 1s have been included in
groups, disregard the remaining don't cares
by visualizing them as 0s.

90
DON'T-CARE CONDITIONS-5

05:01 AM
 What is the simplest logic circuit for the
following truth table?
A B C D Y

0 0 0 0 1

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 0

1 0 1 0 X

1 0 1 1 X

1 1 0 0 X

1 1 0 1 X

1 1 1 0 X 91
1 1 1 1 X
DON'T-CARE CONDITIONS-6

05:01 AM
 Give the simplest logic circuit for following
logic equation where d represents don't-care
condition for following locations.
F(A, B, C, D) = ∑m(7) + d(10, 11, 12, 13, 14,
15)

92
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 Any single 1 or any group of 1’s which can be
combined together on a map of the function
F represents a product term which is called
an implicant of F.
 A product term implicant is called a prime

implicant if it cannot be combined with

another term to eliminate a variable.

93
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 In Figure, a′b′c, a′cd′, and ac′ are prime implicants
because they cannot be combined with other terms to
eliminate a variable.
 a′b′c′d′ is not a prime implicant because it can be
combined with a′b′cd′ or ab′c′d′.
 Neither abc′, nor ab′c′ is a prime implicant because
these terms can be combined together to form ac′.

94
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 All of the prime implicants of a function can
be obtained from a Karnaugh map.
A single 1 on a map represents a prime implicant
if it is not adjacent to any other 1’s.
 Two adjacent 1’s on a map form a prime
implicant if they are not contained in a group of
four 1’s;
 four adjacent 1’s form a prime implicant if they
are not contained in a group of eight 1’s, etc.

95
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The minimum sum-of-products expression for
a function consists of some (but not
necessarily all) of the prime implicants of a
function.
 In other words, a sum-of-products expression

containing a term which is not a prime

implicant cannot be minimum.
 This is true because if a nonprime term

were present, the expression could be

simplified by combining the nonprime term
with additional minterms.
96
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The function plotted in Figure has six prime implicants.
 Three of these prime implicants cover all of the 1’s
on the map, and the minimum solution is the sum
of these three prime implicants.
 The shaded loops represent prime implicants which
are not part of the minimum solution.

97
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 All of the prime implicants of a function are generally
not needed in forming the minimum sum of products,
a systematic procedure for selecting prime implicants
is needed.
 If prime implicants are selected from the map in the
wrong order, a nonminimum solution may result.

98
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 For example, in Figure (a), if CD is chosen first, then
BD, B′C, and AC are needed to cover the remaining
1’s, and the solution contains four terms.
 If the prime implicants indicated in Figure (b) are
chosen first, all 1’s are covered and CD is not needed.

99
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 Note that some of the minterms on the map of Figure
(a) can be covered by only a single prime implicant,
but other minterms can be covered by two different
prime implicants.
 For example, m2 is covered only by B′C, but m5 is
covered by both B′C and CD.

100
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 If a minterm is covered by only one prime implicant,
that prime implicant is said to be essential prime
imlicant, and it must be included in the minimum
sum of products.
 B′C is an essential prime implicant because m2 is not
covered by any other prime implicant.
 CD is not essential prime implicant because each of the
1’s in CD can be covered by another prime implicant.
 The only prime implicant which covers m5 is BD, so BD is
essential.
 AC is essential because no other prime implicant covers
m14.

101
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 In general, in order to find a minimum sum of
products from a map, we should first loop all
of the essential prime implicants.
 One way of finding essential prime implicants
on a map is simply to look at each 1 on the
map that has not already been covered, and
check to see how many prime implicants
cover that 1.
 If there is only one prime implicant which
covers the 1, that prime implicant is essential.
 If there are two or more prime implicants
which cover the 1, we cannot say whether
these prime implicants are essential or not 102
without checking the other minterms.
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 For example, in Figure, m4 is covered only by
the prime implicant bc′, and m10 is covered
only by the prime implicant ac.
 All other 1’s on the map are covered by two

prime implicants; therefore, the only

essential prime implicants are bc′ and ac.

103
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 If the given minterm and all of the 1’s
adjacent to it are covered by a single term,
then that term is an essential prime
implicant.
 If all of the 1’s adjacent to a given minterm

are not covered by a single term, then there

are two or more prime implicants which
cover that minterm, and we cannot say
whether these prime implicants are essential
or not without checking the other minterms.

104
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The adjacent 1’s for
minterm m0 (10) are
11, 12, and l4.
 Because no single
term covers these four
1’s, no essential prime
implicant is yet
apparent.
 The adjacent 1’s for 11
are 10 and 15, so the
term which covers
these three 1’s (A′C′)
is an essential prime
implicant. 105
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The only 1 adjacent
to 12 is 10, A′B′D′ is
also essential.

 The only 1 adjacent

to 111 is 115, ACD is
essential.

106
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The 1’s adjacent to 17
(15 and 115) are not
covered by a single
term, neither A′BD nor
BCD is essential.
 To complete the
minimum solution, one
of the nonessential
prime implicants is
needed. So either A′BD
or BCD may be selected
 The final solution is

107
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
 The following procedure can be used to obtain a
minimum sum of products from a Karnaugh map:
1. Choose a minterm (a 1) which has not yet been
covered.
2. Find all 1’s and X’s adjacent to that minterm. (Check
the n adjacent squares on an n-variable map.)
3. If a single term covers the minterm and all of the
adjacent 1’s and X’s, then that term is an essential
prime implicant, so select that term. (Note that don’t-
care terms are treated like 1’s in steps 2 and 3 but not
in step 1.)
4. Repeat steps 1, 2, and 3 until all essential prime
implicants have been chosen.
5. Find a minimum set of prime implicants which cover
the remaining 1’s on the map. (If there is more than 108
one such set, choose a set with a minimum number of
literals.)
DETERMINATION OF MINIMUM
EXPRESSIONS USING ESSENTIAL PRIME
IMPLICANTS

05:01 AM
109
PROGRAMMED EXERCISE

05:01 AM
 Determine the minimum sum of products and
minimum product of sums for
 f = b′c′d′ + bcd + acd′ + a′b′c + a′bc′d

 First, plot the map for f.

110
PROGRAMMED EXERCISE

05:01 AM
 For problem on K-Map refer text book and
VTU question papers.
 What is the simplified Boolean equation for

the following logic equation expressed by

minterms?
 Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12, 13, 14, 15)
 F(w, x, y, z) = ∑m(0, 1, 2, 5, 8, 9, 10)
 Y= ∑m(1, 2, 6, 7)
 Y=F(p,q,r,s)=∑m(1, 3, 4, 10, 12, 13, 15)
 F (w, x, y, z) = ∑m (0, 1, 2, 4, 5, 6, 8, 9, 12, 13,
14)
111

F (A, B, C, D) = ∑m(0,1, 2, 5, 8, 9,10)

PROGRAMMED EXERCISE –
VTU QUESTIONS

05:01 AM
 Find the minimal SOP of the following
Boolean functions using K-Map:
 F(a,b,c,d)=∑m(6,7,9,10,13)+d(1,4,5,11)
 F(p,q,r,s)=∑m(6,7,9,10,13)+d(0,1,8,12)
 F(A,B,C,D)= ∑m(6,8,9,10,11,12,13,14,15)
 F(A,B,C,D)=∑m(1,3,5,7,8,10,12,14)
 F(a,b,c,d)=∑m(5,6,7,12,13)+d(4,9,14,15)

112
PROGRAMMED EXERCISE

05:01 AM
 Find the minimum sum of products for each
function using a Karnaugh map.
 (a) f1(a, b, c) = m0 + m2 + m5 + m6

 (b) f2(d, e, f ) = Σ m(0, 1, 2, 4)

 (c) f3(r, s, t) = rt ′ + r′s′ + r′s

 (d) f4(x, y, z) = M0 · M5

113
PROGRAMMED EXERCISE

05:01 AM
 Find the minimum sum-of-products expression
for each function. Underline the essential
prime implicants in your answer and tell which
minterm makes each one essential.
 f(a, b, c, d) =Σ m(0, 1, 3, 5, 6, 7, 11, 12,
14)
 f(a, b, c, d) =Π M(1, 9, 11, 12, 14)
 f(a, b, c, d) =Π M(5, 7, 13, 14, 15)· Π D(1,
2, 3, 9)
 f(a, b, c, d) =Σ m(0, 2, 3, 4, 7, 8, 14)
 f(a, b, c, d) =Σ m(1, 2, 4, 15) +Σ d(0, 3, 14)
 f(a, b, c, d) =Π M(1, 2, 3, 4, 9, 15)
114
 f(a, b, c, d) =Π M(0, 2, 4, 6, 8) ·Π D(1, 12, 9,
15)
PROGRAMMED EXERCISE

05:01 AM
 Find the minimum sum-of-products
expression for each function. Underline the
essential prime implicants in your answer
and tell which minterm makes each one
essential.
1. f(a, b, c, d) =Σm (0, 1, 3, 5, 6, 7, 11, 12,
14)
2. f(a, b, c, d) =ΠM (1, 9, 11, 12, 14)
3. f(a, b, c, d) =ΠM (5, 7, 13, 14, 15)· ΠD (1,
2, 3, 9)

115
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
 One of the input variable is placed inside
Karnaugh map
 This reduces the Karnaugh map size by one

degree.
 i.e.a three variable problem that requires 23 = 8
locations in Karnaugh map will require 2(3-l) = 4
locations in entered variable map.
 This technique is particularly useful for
mapping problems with more than four input
variables.

116
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
 Example
 Example: Y = F(A, B, C) = ∑m(2,6,7)

A B C Y
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0 K-MAP for
1 1 0 1 EVM Table

1 1 1 1
117
Truth Table EVM Table
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
118
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
 If choose A as map entered variable write the
corresponding entered variable map.

 If choose B as map entered variable write the

corresponding entered variable map.

119
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
120
SIMPLIFICATION USING MAP-
ENTERED VARIABLES

05:01 AM
 The product term representing each group is
obtained by including map entered variable
in the group as an additional ANDed term.

121
SIMPLIFICATION USING MAP-ENTERED
VARIABLES

05:01 AM
 By using map-entered variables, Karnaugh
map techniques can be extended to simplify
functions with more than four or five
variables.
 Below shows a four-variable map with two

additional variables entered in the squares in

the map
G(A, B, C, D, E, F ) = m0 + m2 + m3 + Em5 + Em7 +
Fm9 + m11 + m15 (+ don’t-care terms)

122
SIMPLIFICATION USING MAP-ENTERED
VARIABLES

05:01 AM
123
PRODUCT-OF-SUMS SIMPLIFICATION-1

05:01 AM
 SOP Simplification

 Complementary
Circuit

124
PRODUCT-OF-SUMS SIMPLIFICATION-2

05:01 AM
 Using Karnaugh map by grouping zeros

125
EXAMPLE-1

05:01 AM
 Give POS form of Y = F(A, B, C, D) = ∏M(0,3,
4, 5, 6, 7, 11, 15)

CD
AB
00 01 11 10
00 0 0
1 1
0 3
1 2

01 0 4
0 5
0 7
0 6

11 1 12
1 13
0 15
1 14

10 1 1 0 1
8 9 11 10

126
EXAM QUESTIONS

05:01 AM
BC
A
00 01 11 10 BC
A
00 01 11 10
0 0 0
1 1
0 3
1 2
0 0 0
1 1
0 3
1 2

1 1 4
1 5
1 7
0 6
1 1 4
1 5
1 7
0 6

127
QUINE-MCCLUSKY METHOD

05:01 AM
 Tabular Method of Minimisation
 Karnaugh map method is very simple and

intuitively appealing is somewhat subjective.

 It depends on the user's ability to identify

patterns that gives largest size.

 Also the method becomes difficult to adapt

for simplification of 5 or more variables.

 Quine-McClusky method involves preparation

of two tables; one determines prime

implicants and the other selects essential
prime implicants to get minimal 128
expression.
QUINE-MCCLUSKY METHOD

05:01 AM
 The Quine-McCluskey method reduces the
minterm expansion (standard sumof-products
form) of a function to obtain a minimum sum
of products. The procedure consists of two
main steps:
1. Eliminate as many literals as possible from
each term by systematically applying the
theorem XY + XY′ = X. The resulting terms are
called prime implicants.
2. Use a prime implicant chart to select a
minimum set of prime implicants which, when
ORed together, are equal to the function being
simplified and which contain a minimum 129

number of literals.
QUINE-MCCLUSKY METHOD

05:01 AM
 Literal: Each appearance of a variable, either
uncomplemented or complemented, is called a
literal.
 Implicant: A product term that indicates the input
valuation(s) for which a given function is equal to 1
is called an implicant of the function.
 Prime Implicant
 An implicant is called a prime implicant if it cannot
be combined into another implicant that has fewer
literals. Another way it is impossible to delete any
literal in a prime implicant and still have a valid
implicant.
 Prime implicants are expressions with least
number of literals that represents all the terms
given in a truth table. Prime implicants are
examined to get essential prime implicants for a 130
particular expression that avoids any type of
duplication.
QUINE-MCCLUSKY METHOD
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 The function must be given
as a sum of minterms. (If
the function is not in
maxterm form, convert to
the minterm expansion)
 In the first part of the

QuineMcCluskey method,
all of the prime implicants
of a function are
systematically formed by
combining minterms.
131
QUINE-MCCLUSKY METHOD-4
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 Stage-1, in order to find all of
the prime implicants, all
possible pairs of minterms
should be compared and
combined whenever possible.
 To reduce the required number
of comparisons put minterns in
different groups depending
on how many 1s input
variable combinations
(ABCD) have.
 For example, first group has no l
in input combination, second
group has only one 1, third two 1 132
s, fourth three ls and fifth four 1s.
QUINE-MCCLUSKY METHOD-5
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 In Stage 2, we first try to combine first and second group of
Stage1, on a member to member basis.
 The rule is to see if only one binary digit is differing between
two members and we mark that position by ‘−’. This means
corresponding variable is not required to represent those
members.
 Thus (0) of first group combines with (1) of second group to
form (0,1) in Stage 2 and can be represented by
A'B'C' (0 0 0 −).
 Proceed in the same manner to find rest of the combinations in
successive groups of Stage 1 and table them as in figure.
 Note that, we need not look beyond successive groups to find
such combinations as groups that are not adjacent, differ by
more than one binary digit. Also note that each combination of
Stage 2 can be represented by three literals.
 All the members of particular stage, which finds itself in
at least one combination of next stage are tick (√) 133
(checked off) marked. This is followed for Stage 1 terms
as well as terms of other stages.
QUINE-MCCLUSKY METHOD-5
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 Two terms can be combined if they differ in exactly
one variable.
 Comparison of terms in nonadjacent groups is
unnecessary because such terms will always differ
in at least two variables and cannot be combined
using XY + XY′ = X.
 Similarly, the comparison of terms within a group
is unnecessary because two terms with the same
number of 1’s must differ in at least two variables.
 Thus, only terms in adjacent groups must be
compared.
 Each time a term is combined with another
term, it is checked off. 134
QUINE-MCCLUSKY METHOD-5
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 A term may be used more than once because
X + X = X.
 Even though two terms have already been

combined with other terms, they still must be

compared and combined if possible.
 This is necessary because the resultant term

may be needed to form the minimum sum

solution.
 At this stage, we may generate
redundant terms, but these redundant
terms will be eliminated later.
135
QUINE-MCCLUSKY METHOD-6
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
136
QUINE-MCCLUSKY METHOD
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 In Stage 3, we combine members of different
groups of Stage 2 in a similar way. Now it will
have two '−‘ elements in each combination.
This means each combination requires two
literals to represent it.
 For example (0,1,2,3) is represented by A'B'
(0 0 − −).
 There are three other groups in Stage 3;
(2,10,3,11) represented by B'C, (10,14,11,15)
by AC and (12,13,14,15) by AB.
 Note that, (0,2,1,3), (10,11,14,15) and
(12,14,13,15) get represented by A'B, AC and
AB respectively and do not give any new 137
term.
QUINE-MCCLUSKY METHOD
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
138
QUINE-MCCLUSKY METHOD
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 If any duplicate terms are formed in each case by
combining the same set of minterms in a
different order.
 These duplicate term must be deleting,
 Now compare terms from the two groups.
 If no further combination is possible, the process
terminates.
 There is no Stage 4 for this problem as no two
members of Stage 3 has only one digit changing
among them. This completes the process of
determination of prime implicants.
 The rule is all the terms that are not ticked
(checked off) at any stage is treated as
prime implicants. 139
QUINE-MCCLUSKY METHOD
DETERMINATION OF PRIME
IMPLICANTS

05:01 AM
 Because every minterm has been included in at least
one of the prime implicants, the function is equal to
the sum of its prime implicants.
 Each term has a minimum number of literals, but the
number of terms is not minimum. So method of
eliminating redundant prime implicants using a prime
implicant chart.

 Given a function F of n variables, a product term P is

an implicant of F iff for every combination of values
of the n variables for which P = 1, F is also equal to 1.
 A prime implicant of a function F is a product term
implicant which is no longer an implicant if any literal
140
is deleted from it.
QUINE-MCCLUSKY METHOD
THE PRIME IMPLICANT CHART

05:01 AM
 Selection of Prime Implicants
 Once we are able to determine prime implicants

that covers all the terms of a truth table we try to

select essential prime implicants and remove
redundancy or duplication among them.
 To find a minimum expression we construct a

prime implicant table in which there is a row for

each prime implicant and a column for each
minterm that must be covered.
 Note- don't care values are not included.

 Then we place check marks (√) or (X) to indicate

the minterms covered by each prime implicant. 141

QUINE-MCCLUSKY METHOD-11

05:01 AM
 Selection of essential prime implicants from this table is
done in the following way.
1. If a minterm is covered by only one prime implicant, then that prime
implicant is called an essential prime implicant and must be
included in the minimum sum of products.
2. Essential prime implicants are easy to find using the prime implicant
chart. If a given column contains only one √ or X, then the
corresponding row is an essential prime implicant. (Encircle the √ or
X)
3. Each time a prime implicant is selected for inclusion in the minimum
sum, the corresponding row should be crossed out.
4. After doing this, the columns which correspond to all minterms
covered by that prime implicant should also be crossed out.
1. The essential prime implicants and the corresponding rows and columns are
crossed out.
5. A minimum set of prime implicants must now be chosen to cover
the remaining columns.
 Find minimum set of rows that cover the remaining columns OR Find
minimum number of prime implicants that covers all the minterms
 E.g. Find A' B' and AB cover terms that are not covered by others and they
are essential prime implicants. B'C and AC among themselves cover 10, 11
which are not covered by others.
 So, one of them has to be included in the list of essential prime implicants 142
making it three.
QUINE-MCCLUSKY METHOD-11

05:01 AM
 Selection of essential prime implicants from this table is done in
the following way.
1. If a minterm is covered by only one prime implicant, then that prime implicant is
called an essential prime implicant and must be included in the minimum sum of
products.
2. Essential prime implicants are easy to find using the prime implicant chart. If a
given column contains only one √ or X, then the corresponding row is an
essential prime implicant. (Encircle the √ or X)
3. Each time a prime implicant is selected for inclusion in the minimum sum, the
corresponding row should be crossed out.
4. After doing this, the columns which correspond to all minterms covered by that
prime implicant should also be crossed out.
 The essential prime implicants and the corresponding rows and columns are crossed out.
5. A minimum set of prime implicants must now be chosen to cover the remaining
columns.
 Find minimum set of rows that cover the remaining columns OR Find minimum number of
prime implicants that covers all the minterms
 E.g. Find A' B' and AB cover terms that are not covered by others and they are essential 143
prime implicants. B'C and AC among themselves cover 10, 11 which are not covered by
others.
 So, one of them has to be included in the list of essential prime implicants making it three.
QUINE-MCCLUSKY METHOD

05:01 AM
 Example Problem
 f(a, b, c, d) =Σ m(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)
 Determination of Prime Implicants

144
QUINE-MCCLUSKY METHOD

05:01 AM
 Prime Implicant Chart

 f = b′c′ + cd′ + a′bd

145
QUINE-MCCLUSKY METHOD

05:01 AM
 Prime Implicant Chart

 f = b′c′ + cd′ + a′bd

146
QUINE-MCCLUSKY METHOD-12

05:01 AM
 Get a minimized expression for
using K-map, EVM and quine mc-clusky
method

147
QUINE-MCCLUSKY METHOD-12

05:01 AM
 Get a minimized expression for
using K-map, EVM and quine mc-clusky
method

148
QUINE-MCCLUSKY METHOD-12

05:01 AM
 Get a minimized expression for
using K-map, EVM and quine mc-clusky
method

149
QUINE-MCCLUSKY METHOD-13

05:01 AM
 Example Problem
 F =Σ m(0, 1, 2, 5, 6, 7)

 A prime implicant chart which has two or more X’s

in every column is called a cyclic prime implicant
chart. 150

 F = a′b′ + bc′ + ac.

QUINE-MCCLUSKY METHOD-13

05:01 AM
 All columns have two X’s, so we will proceed by
trial and error.
 Both (0, 1) and (0, 2) cover column 0, so we will
try (0, 1).
 After crossing out row (0, 1) and columns 0 and 1,
we examine column 2, which is covered by (0, 2)
and (2, 6). The best choice is (2, 6) because it
covers two of the remaining columns while (0, 2)
covers only one of the remaining columns.
 After crossing out row (2, 6) and columns 2 and 6,
we see that (5, 7) covers the remaining columns
and completes the solution.
 However, we are not guaranteed that this
solution is minimum. We must go back and
solve the problem over again starting with
151
the other prime implicant that covers
column 0.
QUINE-MCCLUSKY METHOD-13

05:01 AM
 F = a′c′ + b′c + ab
 Note that in K-Map if each minterm on the map can be
covered by two different loops.
 Similarly, each column of the prime implicant chart
has two X’s, indicating that each minterm can be 152
covered by two different prime implicants.
QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
 Get simplified expression of f(A, B, C, D, E) =
Σ m (0, 2, 3, 5, 7, 9, 11, 13, 14, 16, 18, 24,
26, 28, 30) using Quine-Mc-Clusky method.

153
QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
154
QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
155
QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
 Find a first minimum sum-of-products solution.

156
 f = B′C′E′ + ABE′ + A′C′DE + A′B′CE + A′BD′E + BCDE′
QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
 Find a second minimum sum-of-products solution.

 f = BCDE′ + B′C′E′ + ABE′ + A′B′DE + A′CD′E + A′BC′E 157

QUINE-MCCLUSKY METHOD
PROGRAMMED EXERCISE

05:01 AM
 For this function, find a minimum sum-of-
products solution, using the QuineMcCluskey
method.
 (a) f(a, b, c, d) =Σ m(1, 5, 7, 9, 11, 12, 14,

15)
 (b) f(a, b, c, d) =Σ m(0, 1, 3, 5, 6, 7, 8, 10,

14, 15)

158
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 Petrick’s method is a technique for determining all
minimum sum-of-products solutions from a prime
implicant chart.
 As the number of variables increases, the number of
prime implicants and the complexity of the prime
implicant chart may increase significantly.
 In such cases, a large amount of trial and error may
be required to find the minimum solution(s).
 Petrick’s method is a more systematic way of finding
all minimum solutions from a prime implicant chart
than the method used previously.

159
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 Petrick’s method is as follows:
 Reduce the prime implicant chart by eliminating the essential
prime implicant rows and the corresponding columns.
 Label the rows of the reduced prime implicant chart P1, P2, P3,
etc.
 Form a logic function P which is true when all columns are
covered. P consists of a product of sum terms, each sum term
having the form (Pi0 + Pi1 +· · · ), where Pi0, Pi1 . . . represent
the rows which cover column i.
 Reduce P to a minimum sum of products by multiplying out and
applying X + XY = X.
 Each term in the result represents a solution, that is, a set of
rows which covers all of the minterms in the table. To determine
the minimum solutions find those terms which contain a
minimum number of variables. Each of these terms represents a
solution with a minimum number of prime implicants.
 For each of the terms found in step 5, count the number of
literals in each prime implicant and find the total number of
literals. Choose the term or terms which correspond to the 160
minimum total number of literals, and write out the
corresponding sums of prime implicants.
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 The example shown in below tables has two
minimum solutions.
 F = a′b′ + bc′ + ac OR F = a′c′ + b′c
+ ab

161
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 Petrick’s method, If all essential prime implicants and the
minterms they cover should be removed from the chart.
 Then label the rows of the table P1, P2, P3, etc.
 We will form a logic function, P, which is true when all of
the minterms in the chart have been covered.
 Let P1 be a logic variable which is true when the prime
implicant in row P1 is included in the solution, P2 be a logic
variable which is true when the prime implicant in row P2 is
included in the solution, etc.
 Because column 0 has X’s in rows P1 and P2, we must
choose row P1 or P2 in order to cover minterm 0.
Therefore, the expression (P1 + P2) must be true.
 In order to cover minterm 1, we must choose row P1 or
P3; therefore, (P1 + P3) must be true.
 In order to cover minterm 2, (P2 + P4) must be true.
 Similarly, in order to cover minterms 5, 6, and 7, the
expressions (P3 + P5), (P4 + P6) and (P5 + P6) must
be true. 162
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 Because we must cover all of the minterms, the
following function must be true:
P = (P1 + P2)(P1 + P3)(P2 + P4)(P3 + P5)(P4 + P6)(P5 +
P6) = 1
 The expression for P in effect means that we must
choose row P1 or P2, and row P1 or P3, and row P2 or
P4, etc.

163
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 The next step is to reduce P to a minimum sum of
products. This is easy because there are no
complements. First, we multiply out, using (X + Y)(X +
Z) = X + YZ and the ordinary distributive law:
P = (P1 + P2P3)(P4 + P2P6)(P5 + P3P6)
= (P1P4 + P1P2P6 + P2P3P4 + P2P3P6)(P5 + P3P6)
= P1P4P5 + P1P2P5P6 + P2P3P4P5 + P2P3P5P6 +
P1P3P4P6 + P1P2P3P6 + P2P3P4P6 +
P2P3P6
= P1P4P5 + P1P2P5P6 + P2P3P4P5 + P1P3P4P6
+ P2P3P6
 Next, we use X + XY = X to eliminate redundant terms
from P, which yields
164
P = P1P4P5 + P1P2P5P6 + P2P3P4P5 + P1P3P4P6 +
P2P3P6
QUINE-MCCLUSKY METHOD
PETRICK’S METHOD

05:01 AM
 Because P must be true (P = 1) in order to cover all of
the minterms, we can translate the equation back into
words as follows.
 In order to cover all of the minterms, we must choose
rows P1 and P4 and P5, or rows P1 and P2 and P5 and
P6, or . . . or rows P2 and P3 and P6.
 Although there are five possible solutions, only two of
these have the minimum number of rows.
 Thus, the two solutions with the minimum number of
prime implicants are obtained by choosing rows P1,
P4, and P5 or rows P2, P3, and P6.
 The first choice leads to F = a′b′ + bc′ + ac, and the
second choice to F = a′c′ + b′c + ab, which are the
165
two minimum solutions.
QUINE-MCCLUSKY METHOD
SIMPLIFICATION OF INCOMPLETELY
SPECIFIED FUNCTIONS

05:01 AM
 Given an incompletely specified function, the proper assignment
of values to the don’t-care terms is necessary in order to obtain
a minimum form for the function.
 In this section will show how to modify the Quine-McCluskey
method in order to obtain a minimum solution when don’t-care
terms are present.
 In the process of finding the prime implicants, we will treat the
don’t-care terms as if they were required minterms.
 In this way, they can be combined with other minterms to eliminate
as many literals as possible.
 If extra prime implicants are generated because of the don’t-cares,
this is correct because the extra prime implicants will be eliminated
in the next step anyway.
 When forming the prime implicant chart, the don’t cares are not
listed at the top.
 This way, when the prime implicant chart is solved, all of the
required minterms will be covered by one of the selected prime
implicants.
 However, the don’t-care terms are not included in the final solution
unless they have been used in the process of forming one of the 166
selected prime implicants.
QUINE-MCCLUSKY METHOD
SIMPLIFICATION OF INCOMPLETELY
SPECIFIED FUNCTIONS

05:01 AM
 F(A, B, C, D) =Σ m(2, 3, 7, 9, 11, 13) +Σ d(1, 10, 15)
 The don’t-care terms are treated like required
minterms when finding the prime implicants:

167
QUINE-MCCLUSKY METHOD
SIMPLIFICATION OF INCOMPLETELY
SPECIFIED FUNCTIONS

05:01 AM
 The don’t-care columns are omitted when
forming the prime implicant chart:

 F = B′C + CD + AD

168
QUINE-MCCLUSKY METHOD
SIMPLIFICATION OF INCOMPLETELY
SPECIFIED FUNCTIONS

05:01 AM
 In the process of simplification, we have
automatically assigned values to the don’t-cares
in the original truth table for F.
 If we replace each term in the final expression for
F by its corresponding sum of minterms, the
result is
F = (m2 + m3 + m10 + m11) + (m3 + m7 + m11
+ m15) + (m9 + m11 + m13 + m15)
 Because m10 and m15 appear in this expression
and m1 does not, this implies that the don’t-care
terms in the original truth table for F have been
assigned as follows:
for ABCD = 0001, F = 0;
169
for 1010, F = 1;
for 1111, F = 1
PROBLEMS

05:01 AM
 Find all prime implicants of the following
function and then find all minimum solutions
using Petrick’s method:
1. F(A, B, C, D) = Σ m(9, 12, 13, 15) + Σ d(1,
4, 5, 7, 8, 11, 14)
2. F(A, B, C, D) = Σ m(7, 12, 14, 15) + Σ d(1, 3,
5, 8, 10, 11, 13)

170