Chapter 2

Boolean algebra
and Logic functions
 Part 3
Karnaugh map
 Karnaugh map

Karnaugh map

Karnaugh map (or K-map) is a method used to simplify

the Boolean function. Each cell of K-map expresses a
value of function F (0, 1 or x), corresponding to a row of
the Truth Table
 Karnaugh map

2-variable K-map

The numbers in the cells of K-map

are the ordinal numbers of cells as
well as that of rows in the Truth
Table
 Karnaugh map

3-variable K-map
 Karnaugh map

4-variable K-map
 Karnaugh map
5-variable K-map
 Karnaugh map
Fill values in K-map:

1. If the function F is given in the Standard form 1 (-form)

 Fill “1” in cells having the ordinal numbers corresponding
to minterms,

 Fill “x” in cells having the ordinal numbers corresponding to

“don’t care”

 Fill “0” in the remained cells.

We can fill only two symbols “0” and “x” or “1” and “x” in the
K-map. The blank cells are implicit.
Fill in the K-map the following function

F(D,C,B,A) = (2,3,5,8,11,13,14) + d(1,4,15)

F DC F DC
00 01 11 10 00 01 11 10
BA BA
00 X 1 00 0 X 0
0 4 12 8 0 4 12 8

01 X 1 1 5 1 13 01 X 0
9
1 5 13 9

11 13 X15 1 11 11 0 X 15
7
3 7 11

10 12 6
1 14 10 0 0
10 2 6 14 10
 Karnaugh map
Fill values in K-map:
2. If the function F is given in the Standard form 2 (-form)
 Fill “0” in cells having the ordinal numbers corresponding
to maxterms,

 Fill “x” in cells having the ordinal numbers corresponding to

“don’t care”
 Fill “1” in the remained cells.
We can fill only two symbols “0” and “x” or “1” and “x” in the
K-map. The blank cells are implicit.
 Fill in the K-map the following function
F(A,B,C,D) = (4,5,12,14,15) . d(3,7,8,11)

F AB F AB
00 01 11 10 01 11 10
CD CD 00
00 0 4 0 12 X 8 00 1 X8
0 0 4 12

01 05 01 1 1 1
1 13 9 1 5 13 9

11 X 3 X 7 0 15 X 11 11 X3 X7 X 11
15

10 0 14 10 1 1 1
2 6 10 2 6 14 10
 Karnaugh map
Fill values in K-map:

3. If the function F is based on the Truth Table

 Fill “0”, “1” or “x” in cells having the same binary
combinations in Truth Table.
Given the Truth Table, fill in the K-map:

A B C F F AB
C 00 01 11 10
0 0 0 0
0 0
1 2
X 6
1 4
0 0 1 0
1 1 3 7
X 5
0 1 0 1
0 1 1 0 F AB
1 0 0 1 C 00 01 11 10
1 0 1 x 0 0 0 2
X 6 4
1 1 0 x 1 0 1
0 3
0 7
X 5
1 1 1 0
 Karnaugh map
Fill values in K-map:

4. If the function F is given in algebraic form

 Convert it into Standard from 1 or 2  fill in the K-map.

 If it has the form of SOP  transform it into Standard form 1.
 If it has the form of POS  transform it into Standard form 2.
 Part 4
Simplification using
K-map
 Simplify the Boolean function
using K-map

1. Definition of adjacent cells:

Two cells are adjacent if they lie close each other or they are
symmetric through axis. The feature of two adjacent cells is
they are corresponding to two minterms (or maxterms)
which are different in only 1 bit.
 Simplify the Boolean function
using K-map

Definition of adjacent cells:

 4 cells are adjacent if they consist of 2 adjacent cells and
each cell of this group is adjacent to one cell of the other.
The above definition is applied similarly for 8
adjacent cells and 2n adjacent cells.

The adjacent cells are grouped if they have the same

1 or 0.
 Simplify the Boolean function
using K-map
Example: 2 adjacent cells
 Simplify the Boolean function
using K-map

Example: 4 adjacent cells

 Simplify the Boolean function
using K-map

Example: 4 adjacent cells

 Simplify the Boolean function
using K-map

Example: 8 adjacent cells

 Simplify the Boolean function
using K-map
Grouping the adjacent cells
When grouping the adjacent cells having the same value “1”,
we obtain a product of variables having the same value:
 0 if variables are complemented.
1 if variables are not complemented.
(Variable with different values are omitted.)
Because two adjacent cells have the binary combinations
which are different in one variable  grouping two adjacent
cells can remove one variable.
 Simplify the Boolean function
using K-map

Grouping the adjacent cells

When grouping the adjacent cells having the same value “0”,
we obtain a sum of variables having the same value:
 0 if variables are not complemented.
 1 if variables are complemented.
(Variable with different values are omitted.)
Because two adjacent cells have the binary combinations
which are different in one variable  grouping two adjacent
cells can remove one variable.
 Simplify the Boolean function
using K-map

Similarly:

 When grouping 4 adjacent cells  remove 2 variables.

 When grouping 8 adjacent cells  remove 3 variables.
Generally:
When grouping 2n adjacent cells  n variables.
 Simplify the Boolean function
using K-map

Example: Grouping 2 adjacent cells having value “1”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 00 1 00

01 01 01

11 11 11 1 1

10 1 1 10 1 10
 Simplify the Boolean function
using K-map

Example: Grouping 4 adjacent cells having value “1”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 00 1 1 1 1 00

01 01 01 1 1

11 1 1 11 11 1 1

10 1 1 10 10
 Simplify the Boolean function
using K-map

Example: Grouping 4 adjacent cells having value “1”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 1 00 1 1 00 1 1

01 1 01 01

11 1 11 11

10 1 10 1 1 10 1 1
 Simplify the Boolean function
using K-map

Example: Grouping 8 adjacent cells having value “1”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 1 1 00 1 1 1 1 00 1 1

1 1 01 01 1 1
01
1 11 11 1 1
11 1
10 1 1 10 1 1 1 1 10 1 1
 Simplify the Boolean function
using K-map

Example: Grouping 2 adjacent cells having value “0”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 00 0 00

01 01 01

11 11 11 0 0

10 0 0 10 0 10
 Simplify the Boolean function
using K-map

Example: Grouping 4 adjacent cells having value “0”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 00 0 0 0 0 00

01 01 01 0 0

11 0 0 11 11 0 0

10 0 0 10 10
 Simplify the Boolean function
using K-map

Example: Grouping 4 adjacent cells having value “0”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 0 00 0 0 00 0 0

01 0 01 01

11 0 11 11

10 0 10 0 0 10 0 0
 Simplify the Boolean function
using K-map

Example: Grouping 8 adjacent cells having value “0”

F F F
AB AB AB
00 01 11 10 00 01 11 10 00 01 11 10
CD CD CD
00 0 0 00 0 0 0 0 00 0 0

0 0 01 01 0 0
01
0 11 11 0 0
11 0
10 0 0 10 0 0 0 0 10 0 0
 Simplify the Boolean function
using K-map

Simplify the following function:

F
AB
00 01 11 10
CD
00 1 1 1 1
01 1 1 1 1

11
10 1 1 1
 Simplify the Boolean function
using K-map

Simplify the following function:

F
AB
00 01 11 10
CD
00 1 1
01 1 1

11
10 1 1 1
 Simplify the Boolean function
using K-map

Simplify the following function:

F
AB
00 01 11 10
CD
00 0 0 0 0
01 0 0 0 0

11
10 0 0 0
 Simplify the Boolean function
using K-map

Simplify the following function:

F(D,C,B,A) = (2,3,5,8,11,13,14) + d(1,6,9,10,15)
F
AB
CD
00 01 11 10 C’D
B’D 00 1
x 1 1 x
01 AB’
11 1 x 1
10 1 x 1 x
CD’
 Simplify the Boolean function
using K-map

Simplify the following function:

F(D,C,B,A) = (2,3,5,8,11,13,14).d(1,6,9,10,15)
F
AB
CD
00 01 11 10 C+D’
B+D’ 00 0
x 0 0 x
01 A’+B
11 0 x 0
10 0 x 0 x
C’+D
 Simplify the Boolean function
using K-map

Simplify the following functions:

 Simplify the Boolean function
using K-map

Simplify the following functions:

0
 Simplify the Boolean function
using K-map

Simplify the following functions:

 Simplify the Boolean function
using K-map

Simplify the following functions: