Module-1

Principles of combinational
logic

1
Principles of combination logic, ECE Dept., VCET, Puttur
 TOPICS COVERED:

•
Introduction
•
Definition of combinational logic
•
Canonical forms
•
Generation of switching equations from truth tables
•
Karnaugh maps-3, 4 and 5 variables
•
Incompletely specified functions (Don’t Care terms)
•
Simplifying Max term equations.
•
Q-M technique

2
Principles of combination logic, ECE Dept., VCET, Puttur
 INTRODUCTION

We have learned all the prerequisites material:
- Logic gates, Truth tables
- Simplification of logic expression using laws and
postulates

●
Now, let us put all these foundations for good use, to analyze and design complex
logic circuits.

3
Principles of combination logic, ECE Dept., VCET, Puttur
INTRODUCTION
●
Logic circuits may be combinational or sequential
- Combinational circuits:
*Consist of logic gates only
*Outputs are determined from the present values of inputs
*Operations can be specified by a set of Boolean functions

- Sequential circuits:
*Consist of logic gates and storage elements
*Outputs are a function of the inputs and the state of the
storage elements
*Depend not only on present inputs, but also on past values
*Circuit behavior must be specified by a time sequence of
inputs and internal states
4
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 DEFINITION OF COMBINATIONAL CIRCUIT
Definition: Logic circuits without X0 Y0
feedback from output to the input,
constructed from a functionally complete
gate set, are said to be combinational.
A combinational circuit consists of Xn Ym
- Input variables
- Logic gates
- Output variables
Each input and output variable is a binary signal
- Represent logic 1 and logic 0
- There are 2 n possible binary input combinations for n input variable
- Only one possible output value for each possible input combination
- Can be specified with a truth table
- Can also be described by m Boolean functions, one for each output variable
- Each output function is expressed in terms of n input variables 5
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 Explanation
• Let X be the set of all input variables{X0,X1,……..,Xn} & Y be the set of all
output variables{Y0,Y1,…..Ym}.
• The combinational function F, operates on the input variable set X, to produce
the output variable set, Y.
• The output variables Y0 through Ym are not feedback to the input.
• The output is related to the input as Y=F(X)
General logic design sequence

7
 Problem Statements to truth tables
• Proper Statement of a problem is the most important part of any digital design
task.
• Once it is correctly stated any problem can be converted to the necessary logic
for implementation.
• The problem is stated initially and it is rewritten in the form of truth table.
• From the truth table, the switching equations can be written and simplified and
logic diagram can be drawn.
• Logic diagram can be realized using any one of the main digital integrated
circuit families: TTL, ECL or CMOS.
• Truth table must be constructed from verbal statement.
M

0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
 Classwork
Design a Combinational logic truth table so that an
output is generated indicating when a majority of
four inputs is true.
 Home Work
1. Construct the truth table for the following problem statement:
a. A single output variable “Z”, is to be true when the input variables a and b are
true and when b is false but a and c are true.
b. An output is to be true(logical 1) when the value of the inputs exceeds 3. The
weighting for each input variable is as follows:
W=3, x=3,y=2,z=-1
c. Two motors M2 and M1 are controlled by three sensors S3,S2 and S1. One
motor M2 is to run any time all three sensors are on (true). The other motor is to
run whenever sensors S2 or S1, but not both, are on and S3 is off. For all sensor
combinations where M1 is on, M2 is to be off and then both motors must remain
off.
 Deriving Switching Equations
• Logic can be described in several ways.
• One way is in truth table, another is in logic
diagrams and a third is by Boolean equations.
• Boolean equations can be derived directly from a
truth table or from the logic diagram.
• Likewise truth table or logic diagram can be
constructed from the Boolean equations.
Each input variable that produces logical 1 in a
truth table output column can form a term in a
Boolean switching equation.
For eg:
Notice that each AND term (also called product
term) identifies one input condition where output is
a 1.
Some necessary definitions
●
Literal: A literal is a boolean variable or its complement. For Eg: X and X’
would be literal.
●
Product term: It is a literal or the logical product(AND) of multiple literals.
For Eg: X, XY or X’YZ
●
Sum term: It is a literal or the logical OR of multiple literals. For Eg: X,
X+Y or X’+Y’+Z
●
Sum of Product(SOP): It is a logical OR of multiple product terms. For Eg:
X+XY+X’YZ
●
Product of Sum(POS):It is a logical and of multiple product terms. For Eg:
X(X+Y)(X’+Y’+Z)
●
Minterm: It is a special case product term. A minterm is a product term that
contains all input variables(each literal no more than once) that make up a
Boolean expression.
●
19
●
Maxterm: It is a special case Sum term. A maxterm is a sum term that
contains all input variables(each literal no more than once) that make up a
Boolean expression.
●
Canonical SOP: It is a complete set of minterms that defines when an
output variable is a logical 1.
●
For Eg:
●
Canonical POS: It is a complete set of maxterms that defines when an
output variable is a logical 0.
●
For Eg: M=(a+b+m’+s)(a’+b+m+s’)
 Minterm
Represents exactly one combination in the truth table.
Denoted by mj, where j is the decimal equivalent of the
minterm’s corresponding binary combination (bj).
A variable in mj is complemented if its value in bj is 0,
otherwise is uncomplemented.
M(a,b,m,s)=a’bms+ab’ms+abms
(m7) (m11) (m15)
 Maxterm
Represents exactly one combination in the truth table.
Denoted by Mj, where j is the decimal equivalent of the
maxterm’s corresponding binary combination (bj).
A variable in Mj is complemented if its value in bj is 1,
otherwise is uncomplemented.
F(a,b,c)=(a’+b+c’)(a+b+c’)(a+b’+c’)
101 001 011
M5 M1 M3
Maxterm and Minterm designations for three variables

Truth Table notation for Minterms and Maxterms

 3.2 Canonical Forms
Any Boolean function F( ) can be expressed as a unique sum of
minterms and a unique product of maxterms (under a fixed
variable ordering).
Every function F() has two canonical forms:
• Canonical Sum-Of-Products (sum of minterms)
• Canonical Product-Of-Sums (product of maxterms)
Convert switching equations to canonical form
To place a SOP equation into canonical form using Boolean algebra
following steps to be followed:
1. Identify the missing variable(s) in each AND term
2. AND the missing term and its complement with the original AND
term, xy(z+z’). Because (z+z’)=1, the original AND term value is
not changed.
3. Expand the term by application of the property of distribution,
xyz+xyz’
f1(a,b,c) = a’b’c + bc’ + ac’
= a’b’c + (a+a’)bc’ + a(b+b’)c’
= a’b’c + abc’ + a’bc’ + abc’ + ab’c’
= a’b’c + abc’ + a’bc + ab’c’
Convert switching equations to canonical
form
SOP
E.g. 1. P=f(a,b,c)=ab’+ac’+bc
=ab’(c+c’)+ac’ (b+b’)+bc(a+a’)
=ab’c+ab’c’+abc’+ab’c’+abc+a’bc
=ab’c+ab’c’+abc’+abc+a’bc
Convert switching equations to canonical
form
To place a POS equation into canonical form using Boolean
algebra following steps to be followed:
1. Identify the missing variable(s) in eachOR term
2. OR the missing term and its complement with the original OR
term, x+y’+(zz’). Because (zz’)=0, the original OR term
value is not changed.
3. Expand the term by application of the property of
distribution, (x+y’+z)(x+y’+z’)
f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’)

= (a+b+c)•(aa’+b’+c’)•(a’+bb’+c’)
= (a+b+c)•(a+b’+c’)•(a’+b’+c’)•
(a’+b+c’)•(a’+b’+c’)
= (a+b+c)•(a+b’+c’)•(a’+b’+c’)•(a’+b+c’)
Convert switching equations to canonical
form
POS
E.g. 1. T=f(a,b,c)=(a+b’)(b’+c)
=(a+b’+cc’)(b’+c+aa’)
=(a+b’+c) (a+b’+c’)(a+b’+c)(a’+b’+c)

=(a+b’+c) (a+b’+c’)(a’+b’+c)
 Class Work
Convert switching equations to canonical
form
Exe:
P=f(w,x,y,z)=w’x+yz’
T=f(a,b,c,d)=(a+b’+c)(a’+d)
 Ans:
P=f(w,x,y,z)=wxyz’+wx’yz’+w’xyz+w’xyz’+w’xy’z
+w’xy’z’+w’x’yz’
T=f(a,b,c,d)= (a+b’+c+d) (a+b’+c+d’) (a’+b+c+d)
(a’+b’+c+d) (a’+b+c’+d) (a’+b’+c’+d)
3.3 GENERATION OF SWITCHING EQUATIONS
FROM TRUTH TABLES
Canonical Sum-Of-Products:
The minterms included are those mj such that F( ) = 1
in row j of the truth table for F( ).
Canonical Product-Of-Sums:
The maxterms included are those Mj such that F( ) = 0
in row j of the truth table for F( ).
 Example
Truth table for f1(a,b,c) at right
a b c f1
The canonical sum-of-products form for f 1 0 0 0 0
is
f1(a,b,c) = m1 + m2 + m4 + m6 0 0 1 1
= a’b’c + a’bc’ + ab’c’ + abc’ 0 1 0 1
The canonical product-of-sums form for f 1 0 1 1 0
is 1 0 0 1
f1(a,b,c) = M0 • M3 • M5 • M7
= (a+b+c)•(a+b’+c’)• 1 0 1 0
(a’+b+c’)•(a’+b’+c’). 1 1 0 1
Observe that: mj = Mj’ 1 1 1 0
 Shorthand: ∑ and ∏
f1(a,b,c) = ∑ m(1,2,4,6), where ∑ indicates that this is a
sum-of-products form, and m(1,2,4,6) indicates that the
minterms to be included are m1, m2, m4, and m6.
f1(a,b,c) = ∏ M(0,3,5,7), where ∏ indicates that this is a
product-of-sums form, and M(0,3,5,7) indicates that the
maxterms to be included are M0, M3, M5, and M7.
∑ m(1,2,4,6) = ∏ M(0,3,5,7) = f1(a,b,c)
 Conversion Between Canonical Forms

Replace ∑ with ∏ (or vice versa) and replace those j’s that appeared in
the original form with those that do not.
Example:
f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’
= m1 + m2 + m4 + m6
= ∑(1,2,4,6)
= ∏(0,3,5,7)
= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)
 Karnaugh Maps
Why Karnaugh maps ？
to simplify boolean equations
Karnaugh maps (K-maps) are graphical
representations of boolean functions.
One map cell corresponds to a row in the truth
table.
one map cell corresponds to a minterm or a
maxterm in the boolean expression
 Karnaugh Maps
A AB
B 0 1 00 01 11 10
C
0 m0 m2 0 m0 m2 m6 m4

1 m1 m3 1 m1 m3 m7 m5

AB
CD 00 01 11 10  Logic adjacency : Any two
adjacent cells in the map
00 m0 m4 m12 m8 differ by ONLY one.
01 m1 m5 m13 m9  Example:
m0 (=x1’x2’) is adjacent to m1
11 m3 m7 m15 m11 (=x1’x2) and m2 (=x1x2’) but
10 m2 m6 m14 m10 NOT m3 (=x1x2)
 2-Variable Map -- Example
E.g.
f(x1,x2) = x1’x2’+ x1’x2 + x1x2’
= m 0 + m 1 + m2 x1
x2 0 1
0 2
What (simpler) function is
represented by each dashed 0 1 1
rectangle? 1 3
• x1’x2’+ x1’x2 =x1’(x2’+x2)=x1’ 1 1 0
• x1’x2’+ x1x2’=x2’(x1’+x1) =x2’

f(x1,x2) =x1’+x2’
 Minimization as SOP using K-map
Enter 1s in the K-map for each product term in the
function
Group adjacent K-map cells containing 1s to obtain
a product with fewer variables. Groups must be in
power of 2 (2, 4, 8, …)
Handle “boundary wrap” for K-maps of 3 or more
variables.
 Three-Variable Map
yz
x 00 01 11 10
0 1 3 2
0 m0 m1 m3 m2
4 5 7 6
1 m4 m5 m7 m6

-Note: variable ordering is (x,y,z); yz specifies column, x

specifies row.
-Each cell is adjacent to three other cells (left or right or top
or bottom or edge wrap)
 Three-Variable Map (cont.)
minterm

The types of structures that are

either minterms or are generated
by repeated application of the
minimization theorem on a three
variable map are shown at right.
Groups of 1, 2, 4, 8 are possible.

group of 2 terms

group of 4 terms
 Simplification
Example: f(a,b,c) = ac’ + abc + bc’
=a(b+b’)c’+abc+(a+a’)bc’
=abc’+ab’c’+abc+abc’+a’bc’
=abc’+ab’c’+abc+a’bc’
Result: ab
f(a,b,c) = ac’+ab+bc’
c 00 01 11 10
0 1 1 1
1 1
 More Examples
xy
00 01 11 10
z
f1(x, y, z) = ∑ m(2,3,5,7) 0 1
1 1 1 1
f1(x, y, z) = x’y + xz

xy00 01 11 10
f2(x, y, z) = ∑ m (0,1,2,3,6) z
0 1 1 1
f2(x, y, z) = x’+yz’
1 1 1
 Four-Variable Maps
YZ
00 01 11 10
WX

00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

Top cells are adjacent to bottom cells. Left-edge

cells are adjacent to right-edge cells.
Note variable ordering (WXYZ).
Four-variable Map Simplification
One square represents a minterm of 4 literals.
A rectangle of 2 adjacent squares represents a product
term of 3 literals.
A rectangle of 4 squares represents a product term of 2
literals.
A rectangle of 8 squares represents a product term of 1
literal.
A rectangle of 16 squares produces a function that is
equal to logic 1.
 Example
Simplify the following Boolean function (A,B,C,D) =
∑m(0,1,2,3,4,5,6,7,8,10,13).
First put the function g( ) into the map, and then group
as many 1s as possible.
cd ab
00 01 11 10
00 1 1 1 1 1 1

01 1 1 1 1 1 1

11 1 1 1 1

1 1 1 1 1 1
10

g(A,B,C,D) = a’+b’d’+bc’d
 Implicants ,Prime Implicants (PIs) and
Essential Prime Implicant (EPI)
Implicant: any single A
minterm CD B 00 01 11 10
Prime Implicant (PI): a group 00 1
of minterms that cannot be 1
combined with any other 01
minterms or groups 1 1

Essential Prime Implicant 11 1 1

(EPI): a PI in which one or
more miniterms are unique
10 1?
How to find PI and EPI?
BCD ABC’
A’BC’D BD AC’D’
 Example
a’b’ is not a prime implicant
because it is contained in b’. b’
ad
acd is not a prime implicant cd ab
because it is contained in ad. 1 1

1 1 1
b’, ad, and a’cd’ are prime
1 1 1
implicants.
a’b’ 1 1 1
b’, ad, and a’cd’ are essential prime
implicants. acd
a’cd’
 Another Example
Consider f2(a,b,c,d), whose K-map
is shown below.
The only essential PI is b’d.
ab
cd
1
1 1 1
1 1
1 1 1
 Systematic Procedure for
Simplifying Boolean Functions
1. Load the minterms into the K-map by placing a 1 in
the appropriate square.
2. Look for groups of minterms (PI)
1. The group size must be a power of 2
2. Find the largest groups of minterms first, then smaller
collections until all groups are found.
3. Find all essential PIs.
4. For remaining min-terms not included in the essential
PIs, select a set of other PIs to cover them.
5. The resulting simplified function is the logical OR of
the product terms selected above.
 Example
f(a,b,c,d) =
ab
∑m(0,1,4,5,8,11,12,13,15). cd
1 1 1 1
F(a,b,c,d) = c’d’ + a’c’ + bc’ + 1 1 1
acd 1 1
 Homework
Simplifying Boolean Functions
F(x,y,z)=∑(0,2,3,4,5,7)
F(a,b,c,d)=∑(0,3,4,5,7,11,13,15)
F(w,x,y,z)=∑(0,1,4,5,9,11,13,15)
F(a,b,c,d)=∑(0,1,2,4,5,6,8,9,12,13,14)
F(a,b,c,d)=∑(1,3,4,5,7,8,9,11,15)
F(w,x,y,z)=∑(1,5,7,8,9,10,11,13,15)
P151: 4-c, 4-e
 CANONICAL FORMS
There are two standard or canonical ways of expressing Boolean functions:
1. Canonical Sum-of-products (SOP) Eg:
2. Canonical Product-of-sums (POS) Eg:
These representations are useful for direct implementation, and starting
logic function minimization.
We will focus on SOP.
Consider

Where
product terms

minterms
53
A minterm is any ANDed term containing all of the varibles
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 Any Boolean function can be expressed in canonical SOP form.

Simplification and Implementation of Boolean Functions:

Boolean functions can be implemented in hardware in a number of ways. For
instance, standard discrete TTL or CMOS ICs could be used, in which case it is useful
to find the simplest expression for the function being implemented. Or if
programmable devices are to be used, then a more direct representation of the
function may be useful
.
Direct Implementation:
Consider the function

expressed in canonical SOP form. Then assuming all variables and their complements
are available
54
we can implement this function with the AND-OR circuit of Figure as shown.
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 This implementation is not minimal in general (i.e. can realize f with fewer gates).

55
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 KARNAUGH MAPS (K-MAPS)

●
A method for graphically determining implicants and implicates of a
Boolean function was developed by Veitch and modified by Karnaugh . The
method involves a diagrammatic representation of a Boolean algebra. This
graphic representation is called map.

●
It is seen that the truth table can be used to represent complete function of n
variables. Since each variable can have value of 0 or 1. The truth table has 2n
rows. Each rows of the truth table consist of two parts (1) an n-tuple which
corresponds to an assignment to the n-variables and (2) a functional value.

●
A Karnaugh map (K-map) is a geometrical configuration of 2n cells such
that each of the n-tuples corresponds to a row of a truth table uniquely
locates a cell on the map. The functional values assigned to the n-tuples are
placed as entries in the cells, i.e. 0 or 1 is placed in the associated cell. 56
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 ●
An significant about the construction of K-map is the arrangement of the
cells. Two cells are physically adjacent within the configuration if and only if
their respective n tuples differ in exactly by one element. So that the Boolean
law x+x=1 can be applied to adjacent cells.

●
Ex. Two 3- tuples (0,1,1) and (0,1,0) are physically a adjacent since these
tuples vary by one element.

One variable : One variable needs a map of 21= 2 cells map as shown below
two variables: Two variables needs a map of 22 = 4 cells
three variables: Three variables need a map of 23 = 8 cells.
four variable : Four variable needs a map of 24 = 16 cells.

Four variable K-map:

57
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 KARNAUGH MAPS (K-MAPS)
Karnaugh or K- maps are useful tool for Boolean function minimization, and for
visualization of the Boolean function. In brief,
􀁸 K-maps provide a graphical method for minimizing Boolean functions via pattern
recognition for up to about n=6 variables.
􀁸 For larger numbers of variables, there are computer algorithms which can yield
nearminimal implementations.
􀁸 K-maps are a way of expressing truth tables to make minimization easier. They
are constructed from minterm codes.
Consider the Boolean function
A B F
0 0 1 m0
0 1 1 m1
1 0 1 m0
58
1 1 0 m3
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 The K-map is shown in Figure .The essence of the K-map is the two dimensional
representation of f, which is equivalent to the truth table but more visual.
To minimize f, we loop out logical adjacencies, Figure.

Therefore the
expression
59

Principles of combinational logic-1, ECE Dept., VCET, Puttur

 The K-map method is to loop out groups of 2n logically adjacent minterms. Each
looped out group corresponds to a product term in a minimal SOP expression.
1. Loop out single 1s (n=0) which have no logical adjacencies.
2. Loop out all pairs of 1s (n=1) which cannot be included in a larger group.
3. Loop out all quads of 1s (n=2) which cannot be included in a larger group. Etc.
Example. The K-map is shown in Figure.

60
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 Moving left to right or up to down in the K-map changes only one digit in the
minterm code. Note the wrap-around at the ends: because of logical adjacency,
the top and bottom are joined, and the left and right are joined.
n=0: none
n=1:
n=2:
Therefore the minimal SOP representation is
Example.
The K-map is shown in Figure.

Therefore the minimal SOP

representation is
61

Principles of combinational logic-1, ECE Dept., VCET, Puttur

 a b c d E1 E2 E3 E4
Don't cares. In some
0 0 0 0 0 0 1 1
applications it doesn't matter
what the output is for certain 0 0 0 1 0 1 0 0
input values. These are called 0 0 1 0 0 1 0 1
don't cares. 0 0 1 1 0 1 1 0
For instance, in the Binary 0 1 0 0 0 1 1 1
Coded Decimal code, not all 0 1 0 1 1 0 0 0
input values occur: 0 1 1 0 1 0 0 1
0, 1, ....9 :The decimal numbers
0 1 1 1 1 0 1 0
are those in the range, and a
minimum of 4 bits is needed to 1 0 0 0 1 0 1 1
encode these. 1 0 0 1 1 1 0 0
10,...,15 : The remaining 1 0 1 0 - - - -
numbers correspond to code 1 0 1 1 - - - -
values which are not used in 1 1 0 0 - - - -
BCD. 1 1 0 1 - - - -
We shall use the symbols or X
1 1 1 0 - - - - 62
to denote don't cares.
Don't cares can be exploited to 1 1 1 1 - - - -
help minimize boolean
 Example. K-map

The minimal SOP representation is

63
Principles of combinational logic-1, ECE Dept., VCET, Puttur
Using k-map to obtain minimal expression for complete boolean functions :
1. How to obtain a minimal expression of SOP or POS of given function is
discussed.
PRIME IMPLICANTS and K-MAPS : concept of essential prime implicant
ALGORITHM TO FIND ALL PRIME IMPLICANTS
A General procedure is listed below
1. For an n-variable map make 2n entries of 1’s. or 0’s.
2. Assign I = n , so that find out biggest rectangular group with dimension 2ax2b
= 2n-1.
3. If bigger rectangular group is not possible I = I-1 form the subcubes which
consist
of all the previously obtained subcube repeat the step till all 1-cell or 0’s are
covered.
Remaining is essential prime implicants
1. Essential prime implicants
2. Minimal sums 64
3. Minimal
Principles products
of combinational logic-1, ECE Dept., VCET, Puttur
 MINIMAL EXPRESSIONS OF INCOMPLETE BOOLEAN FUNCTIONS
1. Minimal sums
2. Minimal products

Entered-Variable K-Maps
A generalization of the k-map method is to introduce variables into the k-map
squares. These are called entered variable k-maps. This is useful for functions
of large numbers of variabes, and can generally provide a clear way of
representing Boolean functions.

An entered variable k-map is shown in Figure.

Note the variable C in the top left square.
It corresponds to

It can be looped out with the 1, since 1=1+C,

and we can loop out the two terms 65
to getof combinational logic-1, ECE Dept., VCET, Puttur
Principles
 The remaining term needs to be added to the cover, or more simply,
just loop out the 1. The outcome is

Recommended Questions:

l. Convert the given boolean function f(x, y, z) = [x + x Z (y + z)] into

maxterm canonical formula and hence highlight the importance of canonical
formula
2. Distinguish the prime implicants and essential prime implicants. Determine
the same of the Function f(w, x, y, z) = I m(O, 1, 4, 5, -9, 11, 13, 15) using K-
map and hence the minimal sum expression.
3. Two motors M2 and !v1; are controlled by three sensors 531 52 and 51' One
motor M2 is to run any time all three sensors are on. The other motor is to run
whenever sensors 52 or 51 but not both are on and 53 is off For all sensor
combinations where M1 is an, M2 is to be off except when all the three sensors
are off and then both .motors must remain off Construct the truth table and 66
write the Boolean output equation.
4. Simplify P = f(a, b, c) = L (0,1, 4, 5, 7) using two variable Karnaugh map.
Principles of combinational logic-1, ECE Dept., VCET, Puttur
 Q-M technique
The Quine-McCluskey method is an exact algorithm which finds a
minimum-cost sum-of-products implementation
of a Boolean function. This handout introduces the method and
applies it to several examples.
There are 4 main steps in the Quine-McCluskey algorithm:
1. Generate Prime Implicants
2. Construct Prime Implicant Table
3. Reduce Prime Implicant Table
(a) Remove Essential Prime Implicants
(b) Row Dominance
(c) Column Dominance
4. Solve Prime Implicant Table

67
Example 1:
F(A,B,C,D) =∑ m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)
The Notation. The above notation is a shorthand to describe the Karnaugh map for F. First, it
indicates that F is a Boolean function of 4 variables: A, B, C, and D. Second, each ON-set
minterm of F is listed above, that is, minterms where the function is 1: 0, 2, 5, . . .. Each of
these numbers corresponds to one entry (or square) in the Karnaugh map. For example, the
decimal number 2 corresponds to the minterm ABCD = 0010, (0010 is the binary
representation of 2). That is, ABCD = 0010 is an ON-set minterm of F; i.e., it is a 1 entry.
All remaining minterms, not listed above, are assumed to be 0.

Step 1: Generate Prime Implicants.

Note: You should learn this basic method for generating prime implicants (Step #1), but I
will not ask you to reproduce it. See Roth book on reserve for more details. (Instead, you
will soon learn the more advanced fast recursive algorithm for prime generation.)

68
69
70
Column III contains a number of duplicate entries, e.g. (0,2,8,10) and (0,8,2,10).
Duplicate entries appear because a product in Column III can be formed in several
ways. For example, (0,2,8,10) is formed by combining products (0,2) and (8,10)
from Column II, and (0,8,2,10) (the same product) is formed by combining products
(0,8) and (2,10).
Duplicate entries should be crossed out. The remaining unchecked products cannot
be combined with other products. These are the prime implicants: (0,2,8,10),
(2,6,10,14), (5,7,13,15), (6,7,14,15), (8,10,12,14) and (12,13,14,15); or, using the
usual product notation: B′D′, CD′, BD, BC, AD′ and AB.

71
72
73
In step #1, primary essential prime implicants are identified. These are implicants
which will appear in any solution. A row which is covered by only 1 prime implicant
is called a distinguished row. The prime implicant which covers it is an essential
prime implicant. In this step, essential prime implicants are identified and removed.
The corresponding column is crossed out. Also, each row where the column contains
an X is completely crossed out, since these minterms are now covered. These
essential implicants will be added to the final solution. In this example, B′D′ and BD
are both primary essentials.
(ii) Row Dominance
The table is simplified by removing rows and columns which were crossed out in
step (i). (Note: you do not need to do this, but it makes the table easier to read.
Instead, you can continue to mark up the original table.)

74
Row 14 dominates both row 6 and row 12. That is, row 14 has an “X” in every column
where row 6 has an “X” (and, in fact, row 14 has “X”’s in other columns as well).
Similarly, row 14 has in “X” in every column where row 12 has an “X”. Rows 6 and
12 are said to be dominated by row 14. A dominating row can always be eliminated. To
see this, note that every product which covers row 6 also covers row 14. That is, if
some product covers row 6, row 14 is guaranteed to be covered. Similarly, any product
which covers row 12 will also cover row 14. Therefore, row 14 can be crossed out.

75
Column CD′ dominates column BC. That is, column CD′ has an “X” in every row
where column BC has an “X”. In fact, in this example, column BC also dominates
column CD′, so each is dominated by the other. (Such columns are said to co-dominate
each other.) Similarly, columns AD′ and AB dominate each other, and each is
dominated by the other. A dominated column can always be eliminated. To see this,
note that every row covered by the dominated column is also covered by the
dominating column. For example, C′D covers every row which BC covers.
Therefore, the dominating column can always replace the dominated column, so the
dominated column is crossed out. In this example, CD′ and BC dominate each other, so
either column can be crossed out (but not both). Similarly, AD′ and AB dominate each
other, so either column can be crossed out.

76
In iteration #2 and beyond, secondary essential prime implicants are identified.
These are implicants which will appear in any solution, given the choice of
column-dominance used in the previous steps (if 2 columns co-dominated each
other in a previous step, the choice of which was deleted can affect what is an
“essential” at this step). As before, a row which is covered by only 1 prime
implicant is called a distinguished row. The prime implicant which covers it is a
(secondary) essential prime implicant. Secondary essential prime implicants are
identified and removed. The corresponding columns are crossed out. Also, each
row where the column contains an X is completely crossed out, since these
minterms are now covered. These essential implicants will be added to the final
solution. In this example, both CD′ and AD′ are secondary essentials.

Step 4: Solve Prime Implicant Table.

No other rows remain to be covered, so no further steps are required. Therefore,
the minimum-cost solution consists of the primary and secondary essential prime
implicants B′D′, BD, CD′ and AD′:
F = B′D′ + BD + CD′ + AD′
77
Thankyou

78