

CS302 
Digital Logic & Design
Lesson
No. 11
KARNAUGH MAP &
BOOLEAN EXPRESSION
SIMPLIFICATION
Mapping a
Standard POS
Expression
For a
Standard POS expression, a 0 is
placed in the cell
corresponding to the
product
term
(maxterm) present in the
expression. The cells are
not filled with 0s have
1s. The
Standard
POS
expression
having
a
Domain
of
three
variables
(A + B + C).(A + B + C).(A + B + C).(A + B + C) uses a
3Variable Karnaugh Map. The
sum
terms or
the Maxterms are 1, 2, 5 and
7. The expression can be
represented by a KMap by
placing a 0 at
Maxterm locations 1, 2, 5 and 7
and placing 1 at remaining
places. Any of the
two
Kmaps can be used. Figure
11.1.
AB\C
0
1
00
1
0
A\BC
00
01
11
10
01
0
1
0
1
0
1
0
11
1
0
1
1
0
0
1
10
1
0
Figure
11.1
Mapping a
Standard POS
expression
Karnaugh
Map simplification of POS
expressions
POS
expressions can be easily
simplified by use of the
KMap in a manner similar
to
the
method adopted for
simplifying SOP expressions.
After the POS expression is
mapped on
the
Kmap, groups of 0s are
marked instead of 1s based on
the rules for forming
groups used
for
simplifying SOP.
In the
next step minimal sum
terms are determined. Each
group, including a
group
having a
single cell, represents a
sum term having variables
that occur in only one
form either
complemented or
uncomplemented.
A 3variable
Kmap yields
· A sum
term of three variables for
a group of 1 cell
· A sum
term of two variables for a
group of 2 cell
· A sum
term of one variable for a
group of 4 cell
· A group of
8 cells yields a value of 0
for the expression.
A 4variable
Kmap yields
· A sum
term of four variables for a
group of 1 cell
· A sum
term of three variables for
a group of 2 cell
· A sum
term of two variables for a
group of 4 cell
· A sum
term of one variable for a
group of 8 cell
· A group of
16 cells yields a value of 0
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
11.2
Simplification
of POS expression using a
3variable KMap
99
CS302 
Digital Logic & Design
A POS
expression having 3 Maxterms is
mapped to a 3variable column
based Kmap.
A single
group of two cells and a
group of one cell are
formed.
· The
first group of 0s comprising of
cells 0 and 4 forms the
sum term (B + C)
The
second group comprising of
cell 3 forms the sum
term (A + B + C)
·
The
three term POS expression
simplifies to a 2 term POS
expression (B + C).(A + B + C) .
A POS
expression having 4 Maxterms is
mapped to a 3variable column
based Kmap.
Two
groups of 2 cells each and a
third group of single cell
are formed.
· The
single cell group comprising
of cell 0 forms the sum
term (A + B + C)
The
second group of 0s comprising of
cells 5 and 7 forms the
sum term (A + C)
·
· The
third group of 0s comprising of
cells 6 and 7 forms the
sum term (A + B)
The
four term POS
expression simplifies to a
3 term POS
expression
(A + B + C).(A + C).(A + B) .
Example 3 &
4
0
1
AB\C
00
01
11
10
A\BC
0
0
00
0
0
0
1
1
1
1
01
1
1
1
1
0
1
1
11
0
1
10
Figure
11.3
Simplification
of POS expression using a
3variable KMap
A POS
expression having 3 Maxterms is
mapped to a 3variable column
based Kmap.
Two
groups of two cells are
formed.
· The
first group of 0s comprising of
cells 0 and 1 forms the
sum term (A + B)
· The
second group of 0s comprising of
cells 0 and 4 forms the
sum term (B + C)
The
three term POS expression
simplifies to a 2 terms POS
expression (A + B).(B + C)
A POS
expression having 3 Maxterms is
mapped to a 3variable column
based Kmap.
One
group of 2 cells and another
group of single cell are
formed.
· The
first group of 0s comprising of
cell 0 and 1 forms the
sum term (A + B)
The
second group comprising of
cell 6 forms the sum
term (A + B + C)
·
The
three term POS expression
simplifies to a 2 term POS
expression (A + B).(A + B + C)
Example
5
AB\CD
00
01
11
10
0
0
00
1
1
01
0
0
1
1
1
11
1
1
1
10
1
1
1
0
100
CS302 
Digital Logic & Design
Figure
11.4
Simplification
of POS expression using a
4variable KMap
A POS
expression having 5 Maxterms is
mapped to a 4variable column
based Kmap.
Three
groups of two cells are
formed.
The
first group of 0s comprising of
cells 4 and 5 forms the
sum term (A + B + C)
·
The
second group of 0s comprising of
cells 0 and 4 forms the
sum term (A + C + D)
·
· The
third group of 0s comprising of
cells 2 and 10 forms the
sum term (B + C + D)
The
five term POS
expression has reduced
to a 3 term POS
expression
(A + B + C).(A + C + D).(B + C + D)
Example
6
11
10
AB\CD
00
01
00
0
0
1
0
01
0
0
1
1
11
1
0
1
1
0
10
1
0
1
Figure
11.5
Simplification
of POS expression using a
4variable KMap
A POS
expression having 8 Maxterms is
mapped to a 4variable column
based Kmap.
Two
groups of 4 cells and one
group of two cells are
formed.
· The
first group of 0s comprising of
cells 0, 1, 4 and 5 forms
the sum term (A + C)
The
second group of 0s comprising of
cells 1, 5, 9 and 13 forms
the sum term (C + D)
·
· The
third group of 0s comprising of
cells 2 and 10 forms the
sum term (B + C + D)
The
eight
term
POS
expression
has
reduced
to
a
3
term
POS
expression
(A + C).(C + D).(B + C + D) .
Example
7
01
AB\CD
00
11
10
00
1
0
1
1
0
01
0
0
1
11
1
0
1
1
10
1
0
1
1
Figure
11.6
Simplification
of POS expression using a
4variable KMap
A POS
expression having 6 Maxterms is
mapped to a 4variable column
based Kmap.
Three
groups of 2 cells and one
group of a single cell are
formed.
· The
first group of 0s comprising of
cells 4 and 5 forms the
sum term (A + B + C)
The
second group of 0s comprising of
cells 5 and 7 forms the
sum term (A + B + D)
·
The
third group of 0s comprising of
cells 1 and 9 forms the
sum term (B + C + D)
·
101
CS302 
Digital Logic & Design
· The
fourth group comprising of
cell 14 forms the sum
term (A + B + C + D)
The
six
term
POS
expression
has
reduced
to
a
4
term
POS
expression
(A + B + C).(A + B + D).(B + C + D).(A + B + C + D)
Converting
between POS and SOP
using the Kmap
Converting
between the two forms of
standard expressions is very
simple. If the 1s
mapped on
the Kmap are grouped
together they form the
product terms of the
SOP
expression.
Similarly, if the 0s mapped on
the Kmap are grouped
together they form the
sum
terms of
the POS expression
Consider
the POS expression (A + B + C).(A + B + D).(B + C + D).(A + B + C + D)
01
AB\CD
00
11
10
00
01
10
AB\CD
11
00
1
0
1
1
00
1
0
1
1
01
0
0
0
1
01
0
0
0
1
11
1
0
1
1
11
1
1
1
0
1
1
1
10
1
0
1
1
10
0
Figure
11.7
Converting
between SOP and POS
using Kmap
An equivalent
SOP expression can be
obtained by grouping the 1s
together.
BD + BC + ABC + ABD + ACD
FiveVariable
Karnaugh Map
A Kmap
for 5 variables can be
constructed by using two
4variable Kmaps.
Figure
11.8.
The cells 0 to 15 lie in the
4variable map A=0 and
cells 16 to 31 lie in the
4variable map
A=1.
The
two, 4variable maps are
considered to be lying on top of
each other. Thus a
two
dimensional
map is formed. Rules for
grouping of 0s and 1s remain
unchanged. In a 2
dimensional
map, the groups of adjacent
0s or 1s can also span both
the maps. In a
5variable
Karnaugh
map groups of 2, 4, 8, 16 and 32
can be formed.
BC\DE
00
01
11
10
BC\DE
00
01
11
10
00
0
1
3
2
00
16
17
19
18
01
4
5
7
6
01
20
21
23
22
11
12
13
15
14
11
28
29
31
30
10
8
9
11
10
10
24
25
27
26
Figure
11.8
5variable
Karnaugh Map using A=0 and
A=1 maps
Mapping,
Grouping and Simplification
using 5variable Karnaugh
maps is identical to
those of 3
and 4 variable Karnaugh
maps.
102
CS302 
Digital Logic & Design
Simplification of
5Variable Karnaugh
Map
BC\DE
00
01
11
10
BC\DE
00
01
11
10
00
0
1
0
1
00
1
1
0
0
01
0
1
0
0
01
1
1
0
0
11
0
0
0
1
11
0
0
0
1
10
0
0
1
1
10
0
1
1
1
Figure
11.9
5variable
Karnaugh Map Simplification
The
5variable Karnaugh map is
mapped with Minterms in
plane A=0 and
A=1
respectively.
Consider the groups that
are formed.
·
Starting
with A=0 map. The
cells 1 and 5 form a group
of two cells. These two
cells along
with
cells 17 and 21 in map A=1
from a group of 4 cells.
This group of 4 cells
represents
the
term BDE
·
The
cell 2 in map A=0. Cell 2
does not form a group
with any adjacent cells.
Therefore it is
a group of
single cell having the
product term ABCDE
·
The
cells 10 and 11 in map A=0.
These two cells form a
group of four with adjacent
cells
26 and 27 in
map A=1. Therefore the
group of 4 cells represents
the product term BCD
·
Tthe
cells 11 and 14 in map A=0
and cells 26 and 30 in map
A=1represent a group of 4
cells
representing the product
term BDE
Now
considering the map
A=1.
· The 4
cells 16, 17, 20 and 21
represent the product term
ABD
· The
cell 25 along with cell 27
in map A=1 represent the
product term ABCE
Functions
having multiple
outputs
In the
discussions on Boolean expressions
and Function Tables that
represent
Boolean
functions it has been
assumed that Logic Circuits
have multiple inputs and
single
output.
Practical Logic circuits
however, have multiple
inputs and multiple outputs.
Circuits
having a
single output or multiple
outputs are treated in the
same manner.
Circuits
having multiple outputs are
represented by multiple function
tables one for
each
output or a single function
table having multiple output
columns. The example of a
BCD
to 7Segment
Decoder circuit which has 4
inputs and 7 outputs is
considered to explain
functions
having multiple
outputs.
7Segment
Display
The
7segment display digit is
shown. Figure 11.10.
7Segment Display is used
to
display
the decimal numbers 0 to 9. A
7segment display digit has
7 segments a, b, c, d, e, f
and g
that are turned on/off by a
digital circuit depending
upon the number that is to
be
displayed.
103
CS302 
Digital Logic & Design
Digit
Segments
0
a, b, c, d, e,
f
1
b, c
2
a, b, d, e,
g
3
a, b, c, d,
g
4
b, c, f,
g
5
a, c , d, f,
g
6
a, c, d, e, f,
g
7
a, b, c
8
a, b, c, d, e, f,
g
9
a, b, c, d, f,
g
Figure
11.10 7Segment
Display
Different
set of segments have to be
turned on to display different
digits. For example,
to display
the digit 3, segments a, b, c, d
and g have to be turned on.
To display the digit
7,
segments a, b
and c have to be turned on.
The table indicates the
segments that are turned
on
for
each digit.
The
circuit that turns on the
appropriate segments to display a
digit is known as a
BCD
to 7Sement
Decoder. The input to the
BCD to 7Segment decoder
circuit is a 4bit
BCD
number
between 0 and 9. The seven
output lines of the decoder
connect to the 7
segments.
Figure
11.11.
7segment
output
4bit
a
Logic
BCD
f
b
Circuit
g
input
e
c
d
Figure
11.11 BCD to 7Segment
Decoder
To implement
the decoder circuit having 4
inputs and 7 outputs,
function tables have
to
be drawn
which represent the output
status of each output line
for all combinations of
inputs.
For
example, the segment a is
turned on when the 4bit
input is 0, 2, 3, 5, 6, 7, 8 and
9.
Similarly,
the segment b is turned on
for 0, 2, 3, 4, 7, 8 and 9 combinations
of inputs. Thus
seven
expressions, one for each
segment has to be be determined
before the decoder
circuit
can be
implemented.
Seven
function tables are required
to represent the input/output
combinations for each
segment.
The seven function tables
for segments a, b, c, d, e, f and g
are shown. Figure
11.12ag. To
determine the seven
expressions for each of the
seven outputs, seven
4variable
Karnaugh
maps are used. The
Karnaugh maps and the
simplified expressions are
shown.
Figure
11.13ag. An alternate way of
representing the seven
Function tables is to have
a
single
function table with the
four columns representing
the 4bit input BCD
number and seven
104
CS302 
Digital Logic & Design
output
columns each representing
one of the seven segments a,
b, c, d, e, f and g
respectively.
Since
the 4bit input to the
decoder circuit can have 16
possible input
combinations,
therefore
each of the seven Function
tables have sixteen input
combinations. However,
the
last 6
input combinations are don't
care as these combinations
never occur because the
input
to the
circuit is a 4bit BCD
number. The don't care
states help in simplifying
the Boolean
expressions
for the seven
segments.
Input
Output
Input
Output
A
B
C
D
Seg.
a
A
B
C
D
Seg.
a
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
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
1
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
Figure
11.12a
Function
Table for Segment a
Input
Output
Input
Output
A
B
C
D
Seg.
b
A
B
C
D
Seg.
b
0
0
0
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
0
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
Figure
11.12b
Function
Table for Segment b
Input
Output
Input
Output
A
B
C
D
Seg.
c
A
B
C
D
Seg.
c
0
0
0
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
X
0
0
1
1
1
1
0
1
1
X
0
1
0
0
1
1
1
0
0
X
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
105
CS302 
Digital Logic & Design
Figure
11.12c
Function
Table for Segment c
Input
Output
Input
Output
A
B
C
D
d
A
B
C
D
d
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
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
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure
11.12d
Function
Table for Segment d
Input
Output
Input
Output
A
B
C
D
Seg.
e
A
B
C
D
Seg.
e
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
1
0
x
0
0
1
1
0
1
0
1
1
x
0
1
0
0
0
1
1
0
0
x
0
1
0
1
0
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure
11.12e
Function
Table for Segment e
Input
Output
Input
Output
A
B
C
D
Seg.
f
A
B
C
D
Seg.
f
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
x
0
0
1
1
0
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure
11.12f
Function
Table for Segment f
106
CS302 
Digital Logic & Design
Input
Output
Input
Output
A
B
C
D
Seg.
g
A
B
C
D
Seg.
g
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure
11.12g
Function
Table for Segment g
00
11
11
10
AB\CD
01
10
AB\CD
00
01
00
1
0
1
1
1
1
00
1
1
0
01
1
0
1
0
01
1
1
1
11
x
x
x
x
11
x
x
x
X
10
1
x
1
1
x
x
10
1
x
a = A + C + BD + BD
b = B + CD + CD
AB\CD
01
10
00
11
10
AB\CD
00
01
11
00
00
0
1
1
1
1
1
0
1
01
0
1
0
1
01
1
1
1
1
11
x
x
x
x
11
x
x
x
x
1
x
x
10
1
1
x
x
10
1
c = C+D+B
d = A + BD + BC + CD + BCD
00
10
AB\CD
01
11
AB\CD
00
01
11
10
00
1
0
0
1
00
1
0
0
0
01
0
0
0
1
01
1
1
0
1
x
x
11
x
x
11
x
x
x
x
10
1
0
x
x
10
1
1
x
x
e = BD + CD
f = B + CD + BC + BD
11
10
AB\CD
00
01
00
0
0
1
1
1
01
1
0
1
x
11
x
x
x
10
1
1
x
x
g = A + BC + CD + BC
107
CS302 
Digital Logic & Design
Figure
11.13ag
Karnaugh
Maps and Simplified Boolean
Expressions for Display
Segments
a to g
108
Table of Contents:

