CPE 6204 – Logic Circuits and Switching Theory
1
Karnaugh Maps
Module 5: Karnaugh Maps
Course Learning Outcomes:
1. Plot a function in a Karnaugh map
2. Obtain the minimum sum-of-products or products-of-sums form of a
function
3. Incorporate don’t-care conditions in obtaining the minimum SOP or POS
form of the function
Introduction
It is important that we keep Boolean functions simple because they will ultimately be
translated into hardware components.
We have already seen that we can simplify Boolean functions with the help of postulates and
theorems. The downsides to using algebraic processes are (1) you can’t really tell if the
expression that you have obtained is the optimal solution, and (2) it is very difficult to
systematize the process, oftentimes resulting to trial and error.
Karnaugh Mapping
The map method, also called the Karnaugh map or K-map provides a simple way to simplify
Boolean functions. It is a table or diagram made up of squares. Each square represents a
minterm of the function that is to be simplified.
Simplifying a function entails marking all squares that represent the minterms of the
function with 1’s (or 0’s), and using patterns of adjacent marked minterms to arrive at the
simplified algebraic expression of the same function.
Two-Variable K-Map
Functions with two input variables, 𝑥 and 𝑦, will produce a maximum of four minterms: 𝑥 ′ 𝑦 ′,
𝑥′𝑦, 𝑥𝑦′, 𝑥𝑦. They are represented in the K-map as follows:
𝑦
𝑥 0 1
𝑚0 𝑚1
0 𝑥′𝑦′ 𝑥′𝑦
𝑚2 𝑚3
1 𝑥𝑦′ 𝑥𝑦
Figure 1. A two-
variable K-map
Course Module
If we wish to simplify the function 𝑓 = 𝑥 ′ 𝑦 + 𝑥𝑦 ′ + 𝑥𝑦, we first need to mark with 1’s all the
squares that correspond to the minterms of 𝑓. Squares with 1’s are called implicants.
𝑦
𝑥 0 1
𝑚0 𝑚1
0 1
𝑚2 𝑚3
1 1 1
Figure 2. Map of f=x'y+xy'+xy
Notice that two adjacent squares in the map differ only by one variable. For example, 𝑥 and
𝑦 are both primed in 𝑚0 , and only 𝑦 is unprimed in 𝑚1 . Similarly, only 𝑥 is unprimed in 𝑚2 .
Once we have found our implicants, we then group together horizontally or vertically
adjacent squares (never diagonally):
𝑦
𝑥 0 1
𝑚0 𝑚1
0 1
𝑚2 𝑚3
1 1 1
Figure 3. 𝑓 = 𝑥 ′ 𝑦 + 𝑥𝑦 ′ + 𝑥𝑦
As a rule, the number of adjacent squares we can combine must be in a power of two (1, 2, 4,
8, 16, …). We prioritize the biggest combinations of implicants we can find. This is because
the more implicants in a combination, the lesser the literals in the product terms.
So in Figure 3 above, we have two groups of two, not one group of three. The largest number
of combined squares in power of two is 2.
Because adjacent squares differ by only one variable, the variable that changes from primed
to unprimed, or vice versa, is eliminated when the minterms are summed. This leaves us with
a sum of products with the fewest possible number of literals.
As an example, let us find the sum of the minterms of adjacent square combinations in Figure
3. The group consisting of 𝑚1 and 𝑚3 consists the minterms 𝑥𝑦′ and 𝑥𝑦. Since the variable 𝑥
changed from being primed to being unprimed, this causes it to be eliminated. That leaves
us now with 𝑦.
Similarly, the group consisting of 𝑚2 and 𝑚3 consists of the minterms 𝑥𝑦′ and 𝑥𝑦 . The
variable 𝑦 changed from being primed to unprimed so it is eliminated, leaving only 𝑥.
𝑦
𝑥 0 1 𝑥 ′𝑦 + 𝑥𝑦 = 𝑦(𝑥 + 𝑥 ′ ) = 𝑦
𝑚0 𝑚1
0 1
′ ′
𝑥𝑦 + 𝑥𝑦 = 𝑥(𝑦 + 𝑦) = 𝑥 𝑚2 𝑚3
1 1 1
Figure 4. Summing adjacent minterms
Finally, we produce the sum of products form 𝑥 + 𝑦, which is the optimized form of the
original function. To check, we can always use the truth table and compare the outputs of the
two functions.
CPE 6204 – Logic Circuits and Switching Theory
3
Karnaugh Maps
You might have noticed that 𝑚3 is combined to more than one group of adjacent squares. As
much as possible, we want the implicants to be combined with the largest possible number
of other implicants. The only time an implicant is left ungrouped is when it has no horizontal
or vertical neighbor.
Three-Variable K-Map
A function with three binary variables has 8 minterms. Our K-map will also consist of 8
squares. However, the arrangement of the minterms is different. We maintain that only one
bit changes from any two adjacent squares, similar to the Gray code.. The arrangement of
minterms is shown below:
𝑦𝑧
𝑥 00 11 10
𝑚0 𝑚1 𝑚3 𝑚2
01
0 𝑥′𝑦′𝑧′ 𝑥′𝑦′𝑧 𝑥′𝑦𝑧 𝑥′𝑦𝑧′
𝑚4 𝑚5 𝑚7 𝑚6
1 𝑥𝑦′𝑧′ 𝑥𝑦′𝑧 𝑥𝑦𝑧 𝑥𝑦𝑧′
Figure 5. A three-variable K-Map
The binary numbers on top of the squares signify the binary values of 𝑦 and 𝑧 for each
column of squares below the numbers. This means 𝑦 = 0 and 𝑧 = 0 in the minterms 𝑚0 and
𝑚4 , and so on.
The binary numbers to the left of 𝑚0 and 𝑚4 signify the binary values of 𝑥 for each row of
squares to the right of the numbers. This means 𝑥 = 0 in the minterms 𝑚0 , 𝑚1 , 𝑚2 , and 𝑚3 ,
and 𝑥 = 1 in the minterms 𝑚4 , 𝑚5 , 𝑚6 , and 𝑚7 .
Before we see an example, it is good to note that while each square is equivalent to a
minterm, that is, a product term with three literals, the number of literals decrease as the
number of adjacent squares grouped together increase. We can summarize this in the
following:
1 square = 1 minterm (3 literals)
2 adjacent squares = 1 product term with 2 literals
4 adjacent squares = 1 product term with 1 literal
8 adjacent squares = 1
Let us now simplify the Boolean function 𝑓 (𝑥, 𝑦, 𝑧) = ∑(0,2,3,4,6).
We mark the minterms indicated with 1’s.
Course Module
𝑦𝑧
𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
0 1 1 1
𝑚4 𝑚5 𝑚7 𝑚6
1 1 1
Figure 6. 𝑓(𝑥, 𝑧, 𝑦) = ∑(0, 2,3, 4, 6)
In this example, the largest number of adjacent squares that we can combine is 4. One other
characteristic of the K-map is that edges are considered adjacent squares. So 𝑚0 , 𝑚2 , 𝑚4 , and
𝑚6 are adjacent. These adjacent squares will produce a product term with 1 literal. Looking
at the squares in this combination, only the variable 𝑧 did not change. It has consistently
remained complemented.
The remaining two minterms grouped together forms a product term of 2 literals. In this
combination, 𝑥′ and 𝑦 are constant. Therefore, the product term is 𝑥′𝑦.
Finally, we produce the sum of the products, simplified: 𝑓 = 𝑥 ′ 𝑦 + 𝑧.
Redundant Terms
Sometimes we may come across a mapping such as the one in Figure 7.
𝑦𝑧
𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
0 1 1
𝑚4 𝑚5 𝑚7 𝑚6
1 1 1
Figure 7. A Boolean function
It is best to inspect the diagram before grouping the 1’s. If not, we might make the mistake
of including redundant terms, the result of combining squares that are already covered by
other combinations. For example,
𝑦𝑧
𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
0 1 1
𝑚4 𝑚5 𝑚7 𝑚6
1 1 1
Figure 8. 𝑓 = 𝑥 ′ 𝑦 ′ + 𝑦 ′ 𝑧 + 𝑥𝑧
We don’t need to combine the minterms 𝑚1 and 𝑚5 because both are already covered by
other combinations. If we include this combination, we will produce the expression 𝑥 ′ 𝑦 ′ +
𝑦 ′𝑧 + 𝑥𝑧 (looks familiar? Hint: The Consensus Theorem). The product term 𝑦′𝑧 is our
consensus term, which can be eliminated, leaving us with 𝑥 ′ 𝑦 ′ + 𝑥𝑧.
CPE 6204 – Logic Circuits and Switching Theory
5
Karnaugh Maps
𝑦𝑧
𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
0 1 1
𝑚4 𝑚5 𝑚7 𝑚6
1 1 1
Figure 9. f=x'y'+xz
Four-Variable K-Map
The rules for simplifying four-variable Boolean functions using K-maps is the same as the
rules discussed in the two- and three-variable K-maps. We simply need to watch out for the
arrangement of the minterms.
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
′ ′ ′ ′
00 𝑤 𝑥 𝑦 𝑧 𝑤 ′ 𝑥 ′ 𝑦 ′ 𝑧 𝑤 ′ 𝑥 ′ 𝑦𝑧 𝑤′𝑥′𝑦𝑧′
𝑚4 𝑚5 𝑚7 𝑚6
01 𝑤 ′ 𝑥𝑦 ′ 𝑧 ′ 𝑤 ′ 𝑥𝑦 ′ 𝑧 𝑤 ′ 𝑥𝑦𝑧 𝑤 ′ 𝑥𝑦𝑧 ′
𝑚12 𝑚13 𝑚15 𝑚14
11 𝑤𝑥𝑦 ′𝑧 ′ 𝑤𝑥𝑦 ′ 𝑧 𝑤𝑥𝑦𝑧 𝑤𝑥𝑦𝑧 ′
𝑚8 𝑚9 𝑚11 𝑚10
10 𝑤𝑥 ′ 𝑦 ′ 𝑧 ′ 𝑤𝑥 ′ 𝑦 ′ 𝑧 𝑤𝑥 ′ 𝑦𝑧 𝑤𝑥′𝑦𝑧′
Figure 10. Four-variable K-map
We must also be aware of the number of literals that each product term has after combining
adjacent squares:
1 square = 1 minterm (4 literals)
2 adjacent squares = 1 product term with 3 literals
4 adjacent squares = 1 product term with 2 literals
8 adjacent squares = 1 product term with 1 literal
16 adjacent squares = 1
Try This!
Now try to simplify 𝐹 (𝑤, 𝑥, 𝑦, 𝑧) = ∑(0,1,2,4,5,6,8,9,12,13,14). Try finding the biggest group
of adjacent squares first. Remember that edges are considered adjacent squares.
Course Module
You may want to visualize “rolling” the left edge (minterms 0, 4, 8, and 12) so that it touches
the right edge (minterms 2, 6, 10, and 14), and the top edge (minterms 0, 1, 2, and 3) so that
it touches the bottom edge (minterms 8, 9, 10, and 11).
The answer to this problem is found in the Appendix.
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
00 1 1 1
𝑚4 𝑚5 𝑚7 𝑚6
01 1 1 1
𝑚12 𝑚13 𝑚15 𝑚14
11 1 1 1
𝑚8 𝑚9 𝑚11 𝑚10
10 1 1
Mapping 𝒏-variable Functions
Even though the map method is a great improvement over using Boolean algebra postulates
and theorems, it gets complicated as the number of variables increases. So, we stop here at
four-variable K-mapping. For functions with more than 5 or 6 variables, a computer program
is necessary.
Prime Implicants and Essential Prime Implicants
A prime implicant is a product term obtained by combining the maximum possible number
of adjacent squares in the map. In the above discussion, we have been prioritizing finding
these prime implicants. If a minterm in a square is covered by only one prime implicant, that
prime implicant is said to be essential.
In simplifying, we first find all essential prime implicants. The simplified expression is
obtained from their logical sum, plus other prime implicants needed to cover any remaining
minterms that are not included in the essential prime implicants.
There are cases when we arrive at several ways that a simplified function can be expressed.
Identifying prime implicants in the map helps determine the best of these alternatives (it is
possible that all are valid!).
Product-of-Sums Simplification
The simplified Boolean functions produced from the map previously were expressed in sum-
of-products form. To obtain the product-of-sums form, Mano and Ciletti (2018) outlined the
following steps:
1. Place 0’s in the squares that are NOT included in the function.
2. Combine these 0’s into valid adjacent squares, much like combining the 1’s.
3. The simplified form gives us the complemented function 𝑓′.
4. Obtain the complement of 𝑓′ to give us back the function 𝑓 in product-of-sum form.
CPE 6204 – Logic Circuits and Switching Theory
7
Karnaugh Maps
Example 1:
Simplify the Boolean function 𝐹 (𝐴, 𝐵, 𝐶, 𝐷 ) = ∑(0,1,2,5,8,9,10) into (a) sum-of-products
form, and (b) product-of-sums form.
1. Place 1’s in the squares corresponding to the minterms of the function. Place 0’s in the
remaining squares.
2. Combine the squares with 1’s to produce the simplified function in sum-of-products
form:
𝐹 = 𝐵′ 𝐷 ′ + 𝐵′𝐶 ′ + 𝐴′𝐶′𝐷
3. Combine the squares with 0’s to produce the simplified complement of the function.
Apply DeMorgan’s Theorem to obtain the product-of-sums form.
𝐹′ = 𝐴𝐵 + 𝐶𝐷 + 𝐵𝐷′
𝐹 = (𝐴𝐵 + 𝐶𝐷 + 𝐵𝐷 ′)′
′′
𝐹 = (𝐴′ + 𝐵′ )(𝐶 ′ + 𝐷 ′)(𝐵′ + 𝐷 )
𝐶𝐷
𝐴𝐵 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2 𝐶𝐷
00 1 1 0 1
𝑚4 𝑚5 𝑚7 𝑚6
01 0 1 0 0
𝑚12 𝑚13 𝑚15 𝑚14
11 0 0 0 0
𝑚8 𝑚9 𝑚11 𝑚10
10 1 1 0 1 𝐵𝐷′
𝐴𝐵
Don’t-Care Conditions
Don’t-care conditions are minterms of the function with unspecified values. Let’s go back a
bit to the binary codes. The equivalent binary codes of decimal numbers use only 10 out of
16 combinations. The six remaining are unused and will produce unspecified outputs.
Functions with unspecified outputs are called incompletely specified functions. In many cases,
we don’t care what values these minterms take. Hence, we call them don’t-care conditions.
They are, however, useful in further simplifying Boolean functions. We mark them in the K-
map with 𝑋’s.
Course Module
In simplifying functions with don’t-care conditions, we assume 𝑋 to be either 1 or 0 and
include any don’t-care minterm with either the 1’s or the 0’s, depending on which
combination will produce the simplest expression. Not all don’t-care minterms need to be
combined.
Example 2:
Simplify the Boolean function 𝐹 (𝑤, 𝑥, 𝑦, 𝑧) = ∑(1,3,7,11,15) which has don’t-care conditions
𝑑 (𝑤, 𝑥, 𝑦, 𝑧) = ∑(0,2,5).
1. We first draw the diagram. We choose to produce the simplified SOP form of the function,
so we mark the indicated minterms with 1’s and the don’t-care conditions with 𝑋’s.
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
00 𝑋 1 1 𝑋
𝑚4 𝑚5 𝑚7 𝑚6
01 X 1
𝑚12 𝑚13 𝑚15 𝑚14
11 1
𝑚8 𝑚9 𝑚11 𝑚10
10 1
2. We group together adjacent minterms, including both 1’s and X’s to maximize the number
of squares to combine. There are two possible solutions and either will suffice.
a. These combinations will produce the simplified function 𝑓 = 𝑤 ′ 𝑥 ′ + 𝑦𝑧
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
00 𝑋 1 1 𝑋
𝑚4 𝑚5 𝑚7 𝑚6
01 X 1
𝑚12 𝑚13 𝑚15 𝑚14
11 1
𝑚8 𝑚9 𝑚11 𝑚10
10 1
b. These combinations will produce the simplified function 𝑓 = 𝑤 ′ 𝑧 + 𝑦𝑧
CPE 6204 – Logic Circuits and Switching Theory
9
Karnaugh Maps
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
00 𝑋 1 1 𝑋
𝑚4 𝑚5 𝑚7 𝑚6
01 X 1
𝑚12 𝑚13 𝑚15 𝑚14
11 1
𝑚8 𝑚9 𝑚11 𝑚10
10 1
References and Supplementary Materials
Recommended Reading
Implicants, Prime Implicants, and Essential Prime Implicants
Books and Journals
1. Mano, M. M., Ciletti, M.D. (2018). Digital Design: With an Introduction to the Verilog HDL,
VHDL, and SystemVerilog (6th ed.). New Jersey: Pearson.
2. Harris, D.M, Harris, S.L. (2016). Digital Design and Computer Architecture: ARM Edition.
Massachusetts: Elsevier Inc.
3. Roth, C.H. Jr., Kinney, L.L. (2014). Fundamentals of Logic Design (7th ed.). Connecticut:
Cengage Learning
Online Supplementary Reading Materials
1. Karnaugh Maps, Truth Tables, and Boolean Expressions,
https://www.allaboutcircuits.com/textbook/digital/chpt-8/karnaugh-maps-truth-
tables-boolean-expressions/. Date Accessed: 16 October 2019
2. Don’t Care Cells in the Karnaugh Map,
https://www.allaboutcircuits.com/textbook/digital/chpt-8/dont-care-cells-karnaugh-
map/. Date Accessed: 16 October 2019
Online Instructional Videos
1. Karnaugh Maps, https://ocw.mit.edu/courses/electrical-engineering-and-computer-
science/6-004-computation-structures-spring-2017/c4/c4s2/c4s2v5/karnaugh-
maps-10-57-/. Date Accessed: 10 October 2019
Course Module
Appendix
Answer to the Try This! Problem
𝑦𝑧
𝑤𝑥 00 01 11 10
𝑚0 𝑚1 𝑚3 𝑚2
00 1 1 1
𝑚4 𝑚5 𝑚7 𝑚6
01 1 1 1
𝑚12 𝑚13 𝑚15 𝑚14
11 1 1 1
𝑚8 𝑚9 𝑚11 𝑚10
10 1 1
There are 3 groups of adjacent squares. The biggest is composed of 8 squares. This produces
a product term of 1 literal. In the combination of squares, the only variable that never
changed is the complemented 𝑦, therefore the product term is simply 𝑦′.
The remaining two smaller groups are those colored yellow and red, both having four
adjacent squares combined. The product term of the red group is 𝑤′𝑧′, while the product
term for the yellow group is 𝑥𝑧′.
Finally, the simplified sum-of-products form of the function is 𝑓 = 𝑦 ′ + 𝑤 ′ 𝑧 ′ + 𝑥𝑧′
