

CS302 
Digital Logic & Design
Lesson
No. 10
KARNAUGH MAP &
BOOLEAN EXPRESSION
SIMPLIFICATION
Simplifying
Boolean Expressions using
the laws, rules and
theorems do not
guarantee
the
simplest form of expression as
sometimes simplification of certain
terms is not so
obvious
or the
person doesn't have the
necessary experience in applying
the laws and rules.
The
Karnaugh Map
provides a systematic method
for simplifying Boolean
expressions.
A Karnaugh Map
is organized in the form of an
array. Adjacent cells of the
array can be
grouped
together to result in simplification of a
given expression. Karnaugh
Maps can be used
to simplify
expressions of 2, 3, 4 and 5
variables.
The
3variable Karnaugh
Map
AB\C
0
1
A\BC
00
01
11
10
00
0
1
0
0
1
3
2
01
2
3
1
4
5
7
6
11
6
7
10
4
5
Figure
10.1
Column
and Row based 3variable
Karnaugh Maps
·
A 3variable
KMap has an array of 8
cells. The 8 cells can be
arranged in 2 columns and
4
rows
representing the column form
of the Karnaugh Map.
·
Alternately,
the 8 cells can be organized
in 2 rows and 4 columns
representing the row
form of
the Karnaugh map.
·
Any of the
two forms of the Karnaugh
Map can be used to simplify
Boolean expressions.
The
simplified expressions using
either of the two Kmaps
are identical.
·
Considering
first the column based
3variable Karnuagh map. The
binary values 00, 01,
11
and 10 in
the left most column of
the Kmap represent the
binary values of variables A
and
B. The
binary values 0 and 1 in the
top row of the Kmap
represent the binary values
of
variable
C.
·
The
3variable KMap based on
the row representation is
considered next. The
binary
values 0
and 1 in the left most
column of the Kmap
represent the binary values
of variable
A. The
binary values 00, 01, 11
and 10 in the top row of
the Kmap represent the
binary
values of
variables B and C
·
The
numbers in the cells
represent the Minterms or
Maxterms of an expression that is
to
be represented
using the Kmap. The
cell marked 0 for example,
represents the minterm
0
or the
maxterm 0 having binary
value of variables A, B and C
equal to 000. Similarly
cell
marked 5
represents the minterm 5 or
the maxterm 5 having binary
values of variables A,
B and C
equal to 101.
The
4variable Karnaugh
Map
AB\CD
00
01
11
10
00
0
1
3
2
01
4
5
7
6
11
12
13
15
14
10
8
9
11
10
Figure
10.2
4variable
Karnaugh Map
89
CS302 
Digital Logic & Design
·
A 4variable
KMap has an array of 16
cells
·
The
numbers in the cells
represent the Minterms and
Maxterms of an expression that is
to
be represented
using the Kmap.
·
The
4variable KMap has a
square format with four
rows and four columns of
cells.
·
The
binary values 00, 01, 11
and 10 in the left most
column of the Kmap
represent the
binary
values of variables A and B.
The binary values 00,
01, 11 and 10 in the top
row of
the
Kmap represents the binary
values of variables C and
D
·
The 16
cells marked with numbers 0
to 15 represent the cells 0 to 15
corresponding to the
minterms 0 to 15
or the maxterms 0 to 15 in a 4 variable
Boolean expression.
·
The
cell marked 6 for example,
represents the minterm 6 or
the maxterm 6 having
binary
value of
variables A, B, C and D equal to
0110. Similarly cell marked
13 represents the
minterm 13 or
the maxterm 13 having binary
values of variables A, B, C and D
equal to
1101.
Grouping
and Adjacent
Cells
Karnaugh Map
Array is considered to be wrapped
around were all sides
are adjacent
to each
other. Groups of 2, 4, 8, 16, 32
etc. adjacent cells are
formed. Adjacent cells can
be
· row
wise
· column
wise
· four
corner cells
· rowcolumn
groups of 4, 8, 16, 32
etc
Groups
are formed on the basis of
1s (Minterms) or 0s (maxterms). A group
is selected
to have
maximum number of cells of
Minterms or Maxterms, keeping in
view that the size
of
the
group should be a power of 2.
The idea is to form minimal
number of largest groups
that
uniquely
cover all the cells,
thereby ensuring that all
minterms or maxterms are
included.
Mapping a
standard SOP
Expression
The
first step in simplification of
Boolean expressions is to map
the expressions to
the
Karnaugh
maps. For a Standard SOP
expression, a 1 is placed in the
cell corresponding to
the
product
term (Minterm) present in
the expression. The cells
that are not filled
with 1s have 0s.
The
Standard SOP expression
having a Domain of
three variables
ABC + ABC + ABC is mapped to a
3Variable Karnaugh Map. The
product terms or the
Minterms
are 2, 4 and 6. The
expression is mapped on a KMap by
placing a 1 at Minterm
cells 2, 4
and 6 and placing 0 at
remaining cells.
AB\C
0
1
A\BC
00
01
11
10
00
0
0
0
0
0
0
1
01
1
0
1
1
0
0
1
11
1
0
10
1
0
Mapping
the expression ABC + ABC + ABC to a 3variable
KMap
Figure
10.3
The
Standard
SOP
expression
having
a
domain
of four
variables
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 is mapped to a
4
variable
Karnaugh Map. The product
terms or the Minterms are 1,
4, 5, 6, 8, 13 and 14.
The
90
CS302 
Digital Logic & Design
expression is
mapped on a KMap by placing a 1 at
Minterm cells 1, 4, 5, 6, 8, 13 and 14
and
placing 0 at
remaining cells.
AB\CD
00
01
11
10
00
0
1
0
0
01
1
1
0
1
11
0
1
0
1
10
1
0
0
0
Figure
10.4
Mapping
the 7 term SOP expression to
a 4variable KMap
Mapping a
nonstandard SOP
Expression
In many
practical cases, SOP
expressions are not in a
standard format. To map
them
to Kmaps
they have to be either
converted into Standard SOP
expressions or they can
be
directly
mapped.
Example
1
The
expression A
+
BC is a nonstandard
SOP expression having a
domain of 3
variables. If
the expression is converted
into a standard SOP
expression then there will
be four
product
terms having the variable
A . Similarly, there
would be two product terms
having the
variable
combination BC
. Two of
the product terms ABC are identical. The
expression
A + BC can be directly
mapped to a Kmap without
first converting the
expression to the
standard
form.
The
term A is mapped first. A
`1' is marked in cells where
the variable A is
present.
AB\C
0
1
00
A\BC
00
01
11
10
01
0
11
1
1
1
1
1
1
1
10
1
1
Figure
10.5
Mapping
the expression A to a 3variable
KMap
Consider
the mapping of the term
BC . A `1' is marked
in cells where the variable
BC is
present.
The cells are marked
with 1. One of
the cells ABC has already been
marked when
mapping
the terms containing
variable A
.
AB\C
0
1
A\BC
00
01
11
10
00
0
0
0
0
0
0
1
01
0
1
1
1
1
1
1
11
1
1
10
1
1
Mapping
the expression BC to a
3variable KMap
Figure
10.6
91
CS302 
Digital Logic & Design
The
Kmap shows that if the
nonstandard SOP expression A + BC is converted into
a
standard
SOP expression it would have
five product terms as
represented by the Kmap
cells.
Example
2
The
expression A
+
C is a nonStandard
SOP expression having a
domain of 3
variables. It is
mapped directly to a 3variable
Kmap. The term A is mapped first by
marking
cells
having A
with
`1'.
AB\C
0
1
A\BC
00
01
11
10
00
1
1
0
1
1
1
1
01
1
1
1
0
0
0
0
11
0
0
10
0
0
Mapping
the expression A to a
3variable KMap
Figure
10.7
The
term C
is mapped
next. A `1' is marked in
cells where the term
C is present.
AB\C
0
1
A\BC
00
01
11
10
00
1
1
0
1
1
1
1
01
1
1
1
0
0
1
1
11
0
1
10
0
1
Mapping
the expression C to a
3variable KMap
Figure
10.8
Mapping of
nonstandard SOP expressions
having a domain of 4 variables is
similar.
Consider
the expression D + AC + BC . The terms
D , AC and BC are mapped one
after the
other by
marking cells with `1's
where these terms are
present.
AB\CD
00
01
11
10
00
0
1
1
0
01
0
1
1
0
11
0
1
1
0
10
0
1
1
0
Figure
10.9a Mapping the expression
D to a 4variable
KMap
AB\CD
00
01
11
10
00
0
1
1
0
01
0
1
1
0
11
1
0
1
1
10
1
0
1
1
Figure
10.9b Mapping the expression
AC to a 4variable
KMap
92
CS302 
Digital Logic & Design
AB\CD
00
01
11
10
00
0
1
1
0
01
0
1
1
1
11
1
1
1
1
10
1
1
1
0
Figure
10.9c Mapping the expression
BC to a 4variable
KMap
Simplification of
SOP expressions using the
Karnaugh Map
SOP
expressions can be very
easily simplified using the
KMap method. In the
first
step of
the simplification process,
the SOP expression is mapped
on the Kmap. In the
next
step,
groups of 1s are formed
starting with the largest
group of 1s. The group
should be of size
2, 4, 8, 16 etc.
having adjacent 1s. Multiple
(unique) groups of 1s are
formed. All the
groups
formed
can either be separate
groups or they could share
common 1s each having at
least a
single 1
that is not common to any
other group. A single 1 that
is not adjacent to any other
1 is
considered as a
group having only a single
cell.
In the
next step minimal product
terms are determined. Each
group, including a
group
having a
single cell, represents a
product term having
variables that occur in only
one form
either
complemented or uncomplemented.
A 3variable
Kmap yields
· A product
term of three variables for
a group of 1 cell
· A product
term of two variables for a
group of 2 cell
· A product
term of one variable for a
group of 4 cell
· A group of
8 cells yields a value of 1
for the expression.
A 4variable
Kmap yields
· A product
term of four variables for a
group of 1 cell
· A product
term of three variables for
a group of 2 cell
· A product
term of two variables for a
group of 4 cell
· A product
term of one variable for a
group of 8 cell
· A group of
16 cells yields a value of 1
for the expression.
Example 1 &
2
0
1
AB\C
00
01
11
10
A\BC
00
0
1
0
0
1
1
1
01
1
0
1
1
0
0
0
11
1
1
10
0
1
Figure
10.10 Simplification of SOP
expression using a 3variable
KMap
93
CS302 
Digital Logic & Design
An SOP
expression having 5 minterms is
mapped to a 3variable column
based K
map.
Three groups of two cells
each are formed.
· The
first group of 1s comprising of
cells 2 and 6 forms the
product term BC
· The
second group of 1s comprising of
cells 5 and 7 forms the
product term AC
·
The
third group of 1s comprising of
cells 1 and 5 forms the
product term BC
The
five term SOP expression
simplifies to a 3 term SOP
expression B.C + A.C + B.C
An SOP
expression having 4 minterms is
mapped to a 3variable row
based Kmap.
Two
groups of 2 cells each and a
third group of single cell
are formed.
· The
single cell group comprising
of cell 4 forms the product
term ABC
·
The
second group of 1s comprising of
cells 1 and 3 forms the
product term AC
· The
third group of 1s comprising of
cells 2 and 3 forms the
product term AB
The
four term SOP simplifies to
a 3 term SOP expression A.B.C + A.C + A.B
Example 3 &
4
0
1
AB\C
A\BC
00
01
11
10
0
0
00
0
0
0
1
1
1
1
01
1
1
1
1
0
1
1
11
0
1
10
Figure
10.11 Simplification of SOP
expression using a 3variable
KMap
An SOP
expression having 5 minterms is
mapped to a 3variable column
based K
map.
One group of 4 cells and
another group of 2 cell are
formed.
· The
first group of 1s comprising of
cells 2, 3, 6 and 7 forms
the product term B
· The
second group of 1s comprising of
cells 5 and 7 forms the
product term AC
The
five term SOP simplifies to
a 2 term SOP expression B + AC
An SOP
expression having 5 minterms is
mapped to a 3variable row
based Kmap.
Three
groups of 2 cells each are
formed.
· The
first group of 1s comprising of
cell 4 and 5 forms the
product term A.B
· The
second group of 1s comprising of
cells 3 and 7 forms the
product term B.C
·
The
third group of 1s comprising of
cells 2 and 3 forms the
product term A.B
The
five term SOP simplifies to
a 3 term SOP expression A.B + B.C + A.B
Example
5
AB\CD
00
01
11
10
00
0
1
1
0
1
01
0
0
1
1
11
1
1
1
10
1
1
1
0
Figure
10.12 Simplification of SOP
expression using a 4variable
KMap
94
CS302 
Digital Logic & Design
An SOP
expression having 11 minterms is
mapped to a 4variable based
Kmap.
Three
groups of 4 cells each are
formed.
· The
first group of 1s comprising of
cells 8, 9, 12 and 13 forms
the product term A.C
·
The
second group of 1s comprising of
cells 1, 3, 9 and 11 forms
the product term B.D
·
The
third group of 1s comprising of
cells 6, 7, 14 and 15 forms
the product term B.C
The
eleven term SOP expression
has simplified to a 3 term
expression A.C + B.D + B.C
Example
6
An SOP
expression having 8 minterms is
mapped to a 4variable based
Kmap. One
group of
two cells and two
groups of four cells are
formed.
· The
first group of 1s comprising of
cells 8 and 12 forms the
product term A.C.D
· The
second group of 1s comprising of
cells 3, 7, 11 and 15 forms
the product term C.D
· The
third group of 1s comprising of
cells 6, 7, 14 and 15 forms
the product term B.C
The
eight term SOP expression
has simplified to a 3 term
expression A.C.D + C.D + B.C
11
AB\CD
00
01
10
00
0
0
1
0
01
0
0
1
1
1
11
0
1
1
10
1
0
1
0
Figure
10.13 Simplification of SOP
expression using a 4variable
KMap
Example
7
An SOP
expression having 9 minterms is
mapped to a 4variable based
Kmap. Two
group of
two cells and two
groups of four cells are
formed.
· The
first group of 1s comprising of
corner cells 0, 2, 8 and 10
forms the product term
B.D
·
The
second group of 1s comprising of
cells 2, 3, 10 and 11 forms
the product term B.C
·
The
third group of 1s comprising of
cells 13 and 15 forms the
product term A.B.D
· The
fourth group of 1s comprising of
cells 2 and 6 forms the
product term A.C.D
The
nine term SOP
expression has
simplified to a 4 term
SOP expression
B.D + B.C + A.B.D + A.C.D
AB\CD
00
01
11
10
1
00
1
0
1
01
0
0
0
1
11
1
1
0
10
1
0
1
1
Figure
10.14 Simplification of SOP
expression using a 4variable
KMap
Mapping
Directly from Function
Table
Practically,
when a digital circuit is to be
implemented to perform some
operation, its
function is
first defined using a
function table. The
information in the function
table is directly
95
CS302 
Digital Logic & Design
mapped to a
Kmap of appropriate variables
which is then simplified.
The simplified
expression
obtained
from the Kmap is directly
implemented using logic
Gates.
Consider a
logical circuit that accepts
4bit binary numbers
representing decimal
numbers 0 to
15. The circuit checks
the four bit binary
equivalent of the decimal
number. If the
number is
odd and it is a prime number
the function outputs a one.
Before designing the
logic
circuit a
function table is implemented
with all the input
output combinations. The
function table
for
the odd prime number
checker is shown. Table 10.1
The output is a 1 for inputs
1, 3, 5, 7,
11 and
13.
Input
Output
Input
Output
A
B
C
D
F
A
B
C
D
F
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
1
1
1
0
1
0
0
0
1
1
0
0
0
0
1
0
1
1
1
1
0
1
1
0
1
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
0
Table
10.1
Function
Table for OddPrime Checker
Circuit
The 4
variable Function Table,
Table 10.1 can be directly
mapped to a 4 variable K
map by
marking the Kmap cells
with 1s corresponding to the
minterms marked as 1s in
the
function
table. Figure 10.14.
Simplifying the expression
using the Kmap results
in
A.D + B.C.D + B.C.D . The expression
can be directly implemented
using logic gates.
01
AB\CD
00
11
10
00
0
1
1
0
1
01
0
1
0
0
11
0
1
0
10
0
0
1
0
Figure
10.14 Simplification of expression
using a 4variable
KMap
Don't
care Conditions
Function
Tables represent the
function by listing all the
possible inputs and marking
the
corresponding
outputs with 1s and 0s.
Thus a circuit having four
inputs can be described by
a
4variable
function table having 16
possible input combinations.
For each of the 16
possible
input
conditions the corresponding
output bits are marked as 1s
and 0s depending upon
the
minterms or
maxterms. It is however, possible
that out of the 16 possible
input combinations,
three
input combinations never
occur. Since these three
input combinations never
occur so
should
their corresponding outputs be
marked as 0s or 1s? Since
these inputs never
care
therefore we
don't need to worry about
the output of these input
states. They are considered
to
be don't
care conditions.
Don't
care conditions are marked
as x in the output column of
the function table
corresponding to
the don't care conditions.
When the function table is
mapped to the
96
CS302 
Digital Logic & Design
corresponding
Kmap, the don't care
conditions are marked as x.
However during the
grouping
process
for simplification of the
SOP expression the x outputs
can be considered as 0 or 1. By
assigning a 0 or
1 to the cells marked with
x, the final expression can
be significantly
simplified.
Reconsider
the last example of the
OddPrime Number checker
circuit. Assuming
that
only
the first ten input (0 to 9)
states can occur and
the last 6 inputs never
occur. The function
table
for the conditions that
never occur is shown. Table
10.2
Input
Output
Input
Output
A
B
C
D
F
A
B
C
D
F
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
0
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
0
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
The
function table can be
directly mapped to a 4 variable
Kmap. Figure 10.15. The
cells
marked
with x are considered to be
0s. Thus the function
expression is simplified to A.D
AB\CD
00
01
11
10
1
00
0
1
0
01
0
1
1
0
11
x
x
x
x
10
0
0
x
x
Figure
10.15 Simplification of expression
with Don't care
states
If the
OddParity Checker Circuit
checks for numbers between 0
and 8, and states 9
to
15 never
occur then the Boolean
expression representing the
function reduces to a
single
literal
D Figure 10.16.
The cells 9, 10, 11,
13, 14 and 15 marked as `x'
as they represent the
don't
care states are considered
as 1's to form a group of 8
cells. Remaining cells
marked with
`x'
are considered as 0's and
are not involved in
grouping.
01
AB\CD
00
11
10
00
0
1
1
0
01
0
1
1
0
11
x
x
x
x
10
0
x
x
x
Figure
10.16 Simplification of expression
with Don't care
states
Consider
the Kmap considered earlier
in Example 6. Figure 10.13.
Assume that the
input
conditions A.B.C.D , A.B.C.D and A.B.C.D never occur so
they are marked as x in the
K
97
CS302 
Digital Logic & Design
map
cells corresponding to the
minterms that never occur.
Redefining the groups using
x as 0
or 1 results in
a simpler expression C + A.D instead of A.B.C + C.D + B.C . Figure
10.17.
11
AB\CD
00
01
10
x
00
0
1
x
01
0
0
1
1
1
11
0
1
1
10
1
0
1
x
11
AB\CD
00
01
10
00
0
x
1
x
01
0
0
1
1
11
1
0
1
1
10
1
0
1
x
Figure
10.17
Simplified
expression by incorporating the
don't care states
98
Table of Contents:

