Ultimate Digital Logic & Computer Architecture Study Guide – Clear, Concise & Exam-Ready!

COE211: Digital Logic Design
11/8/2023 1




Chapter 4

Simplification of Boolean
Functions
Karnaugh Maps




Overview
 Introduction to Karnaugh Maps
 Karnaugh Maps Rules and Methods
 Two and Three-Variable K-Maps
 Four-Variable K-Maps
 Simplification Techniques
 Don’t Cares Conditions




COE211: Digital Logic Design
11/8/2023 3




1

, Karnaugh Maps
● Alternate way of representing Boolean functions
● Each row in the truth table is represented by a square
● Each square represents a minterm
● Easy to convert between truth table, K-map, and SOP
● Un-optimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
● Optimized form: reduced number of minterms
F = Σ(m0,m1) = x’y + x’y’ x y F
y
y y 0 0 1
x 0 1 x 0 1
0 1 1
0 x’y’ x’y 0 1 1
1 0 0
x 1 xy’ xy 1 0 0 1 1 0



11/8/2023 4




Karnaugh Maps (cont’d)
● A Karnaugh map is a graphical tool for assisting in the
general simplification procedure
● Two variable maps
B0 1 B0 1
A A
00 1 00 1 F=AB +AB +AB
F=AB+AB
11 0 11 1
A B C F
● Three variable maps 0 0 0 0
0 0 1 1
BC 0 1 0 1
00 01 11 10 0 1 1 0
A
00 1 0 1 1
1
0
0
0
1
1
1
11 1 1 1 1 1 0 1
+
1 1 1 1

F=ABC +ABC +ABC + ABC + ABC + ABC
11/8/2023 5




Rules for K-Maps
● We can reduce functions by circling 1’s in the K-map
● Each circle represents minterm reduction
● After circling, deduce a minimized AND-OR form


Rules to consider
● Every cell containing a 1 must be included at least once
● The largest possible “power of 2 rectangle” should be used
● Use the smallest possible number of rectangles




11/8/2023 6




2