Simplification using K-map
Rules of taking variables
• If a variable changes the state within a group,
don’t take it
• Otherwise, take it.
Use the 2-Variable Karnaugh Map
for Minimization
Example: Given f (X,Y) = (0, 2)
Find: Simplified sum of products
Y
Y
X
m0 m1
X m2 m3
2-Variable Karnaugh Map
2. Now group the 1’s into columns or rows; in this case
we can group them in the first column.
f (X,Y) = (0, 2)
Y
Y
X
1 0
X 1 0
3. This column is Y´ so the simplified function f (X,Y) = Y´
Example
AB
A B C Y
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
AB C
Example: Simplify
f = X´Y´ Z´ + X Y Z + X´Y´ Z + X´ Y Z
YZ
X 00 01 11 10
1 1 1
0
1
X 1
f = X´Y´ + Y Z
3-Variable Karnaugh Map
Example: Given f (X,Y,Z) = (0, 2, 3, 4, 7)
Find: Simplified sum of products
YZ Y
X
m0 m1 m3 m2
m4 m5 m7 m6
X
Z
3-Variable Karnaugh Map
Example: Given f (X,Y,Z) = (0, 2, 3, 4, 7)
Simplified sum of products: f = Y`Z` + YZ + XY
YZ Y
X
1 0 1 1
1 0 1 0
X
Z
K-Map for 3 variables
(Minterms)
BC
00 01 11 10
A 0 1 3 2
___ __ _ _ _
0 ABC ABC ABC ABC
4 5 7 6
__ _ _
1 ABC ABC ABC ABC
K-Map for 3 variables
(Maxterms)
BC
00 01 11 10
A 0 1 3 2
_ _ _ _
0 A+B+ A+B+ A+B+ A+B+
C C C C
4 5 7 6
_ _ _ _ _ _ _ _
1
A+B+ A+B+ A+B+ A+B+
C C C C
K-Map for 3 variables
(Examples)
BC BC
A 00 01 11 10 A 00 01 11 10
0 1 0 0 1 0 0 1 1 0
1 0 1 1 1 1 0 1 1 1
F = AˊCˊ+ AC + AB F = C + AB
BC BC
00 01 11 10 00 01 11 10
A A
0 1 1 0 0 0 1 1 1 1
1 0 1 0 1 1 0 1 1 0
F = AˊBˊ + BˊC + ABCˊ F = Aˊ + C
K-Map for 4 variables
Number of cell = 24 , i.e. 16 cells
The row of the table contains 2 variable and the column
contains 2 variables
The possible grouping sets of 1’s for 4 variables are in 16,
8s, 4s and 2s
Priority sets: 16 cells > 8 cells > 4 cells > 2 sells > 1 cell
Only the adjacent cells are allowed to group together
Follows folding method as per necessity
Both minterms and maxterms can be simplified
Adjacent cells varies by 1 bit
K-Map for 4 variables
(Cell Layout)
CD 00 01 11 10
AB 0000 0001 0011 0010
00 m0 / M0 m1 / M1 m3 / M3 m2 / M2
01 0100
m4 / M4
0101
m5 / M5
0111
m7 / M7
0110
m6 / M6
11 1100 1101 1111 1110
m12 / M12 m13 / M13 m15 / M15 m14 / M14
10 1000 1001 1011 1010
m8 / M8 m9 / M9 m11 / M11 m10 / M10
Four Variable K-Map
C
CD 00 01 11 10
AB AʹBʹCʹDʹ AʹBʹCʹD AʹBʹCD AʹBʹCDʹ
00 0000 0001 0011 0010
AʹBCʹDʹ AʹBCʹD AʹBCD AʹBCDʹ
01 0100 0101 0111 0110
ABCʹDʹ ABCʹD ABCD ABCDʹ B
1100 1101 1111 1110
11
A ABʹCʹDʹ ABʹCʹD ABʹCD ABʹCDʹ
1000 1001 1011 1010
10
D
Simplify the Boolean Function Using K-
Map.
F=∑(0,1,2,4,5,6,8,9,12,13,14)
Solution: Using K-Map
C
CD
00
01 11 10
AB 1 1 0 1
00
1 1 0 1
01
B
1 1 0 1
11
A
1 1 0 0
10
15
D
The Simplified function is :
F= Cʹ+ AʹDʹ +BDʹ
K-Map for 4 variables
(Examples)
CD CD
00 01 11 10 00 01 11 10
AB AB
00 1 1 0 1 00 1 1 0 1
01 0 1 1 0 01 0 1 1 0
11 0 1 1 0 11 0 1 1 0
10 1 1 0 1 10 1 1 0 1
F = BD + BˊDˊ + CˊD F = BD + BˊDˊ + BˊCˊ
Both are correct for the same given function
K-Map for 4 variables
(Examples)
CD CD
00 01 11 10 00 01 11 10
AB AB
00 1 0 0 1 00 1 0 1 1
01 1 1 1 1 01 0 1 1 1
11 1 1 1 1 11 0 1 1 1
10 1 0 0 1 10 1 0 0 1
F = B + Dˊ F = BD + BˊDˊ + AˊC + BC
Thank You
