09/14/2025 Computer Architecture 1
Khana-e-Noor University
Computer Science Faculty
Computer Architecture
LECTURE #3:
MAP SIMPLIFICATION
In this lecture you will learn about
1. Two-variable Map Simplification
2. Three-variable Map Simplification
3. Four-variable Map Simplification
Prepared by: Mr. Rahimullah Pashay (rahimullahpashay@gmail.com)
References: M. Morris Mano, “Computer System Architecture”, Third Edition
09/14/2025 Computer Architecture 2
Karnaugh Map
A Karnaugh Map (K-Map) is a visual tool used for simplifying
Boolean functions and minimizing logic circuit designs.
It helps in organizing truth values in a way that makes it easy to
identify patterns and reduce complex expression
09/14/2025 Computer Architecture 3
Two Variable K-Map
• The two-variable map is shown in the figure.
• There are four minterms for two variables; hence,
the map consists of four squares, one for each
minterm.
• The 0 and 1 marked in each row and column
designate the values of variables.
• Variable x appears primed in row 0 and unprimed
in row 1.
• Similarly, y appears primed in column 0 and
unprimed in column 1.
09/14/2025 Computer Architecture 4
Two Variable K-Map
• As an example, the function xy is shown on the top map.
• Since xy is equal to m3, a 1 is placed inside the square that
belongs to m3.
• Similarly, the function x + y is represented in the bottom
map by three squares marked with 1’s.
• These squares are found from the minterms of the
function:
09/14/2025 Computer Architecture 5
Three Variable K-Map
• There are eight minterms for three binary
variables; therefore, the map consists of eight
squares.
• Note that the minterms are arranged, not in a
binary sequence, but in a sequence similar to
the Gray code.
• The characteristic of this sequence is that only
one bit changes in value from one adjacent
column to the next.
• Any two adjacent squares in the map differ by
only one variable.
09/14/2025 Computer Architecture 6
Three Variable K-Map
• Example 1:
• Simplify the Boolean function F (x, y, z) = ∑(2, 3, 4, 5)
F = x’yz’ + x’yz + xy’z’ + xy’z
09/14/2025 Computer Architecture 7
Three Variable K-Map
• Example 2:
• Simplify the Boolean function F (x, y, z) = ∑(3, 4, 6, 7)
09/14/2025 Computer Architecture 8
Three Variable K-Map
• Example 3:
• Simplify the Boolean function F (x, y, z) = ∑(0, 2, 4, 5, 6)
09/14/2025 Computer Architecture 9
Three Variable K-Map
• Example 4:
• Simplify the Boolean function F (A, B, C) = F = A’C + A’B + AB’C + BC
a) Express this function as a sum of minterms.
b) Find the minimal sum-of-products expression.
09/14/2025 Computer Architecture 10
Three Variable K-Map
• Note that in three variable k-map:
• One square represents one minterm, giving a term with three literals.
• Two adjacent squares represent a term with two literals.
• Four adjacent squares represent a term with one literal.
• Eight adjacent squares encompass the entire map and produce a function that is
always equal to 1.
09/14/2025 Computer Architecture 11
Four-variable K-map
• In a four variable k-map, there are16 minterms and hence 16 squares.
• The rows and columns are numbered in a Gray code sequence, with only one digit
changing value between two adjacent rows or columns.
09/14/2025 Computer Architecture 12
Four-variable K-map
• Example 1:
• Simplify the Boolean function,
F (w, x, y, z) = ∑(0, 1, 2, 4, 5, 6,
8, 9, 12, 13, 14)
09/14/2025 Computer Architecture 13
Four-variable K-map
• Example 2:
• Simplify the Boolean function, F =
A’B’C’ + B’CD’ + A’BCD’ + AB’C’
F
09/14/2025 Computer Architecture 14
Four-variable K-map
• Considerations for combining squares:
• In choosing adjacent squares in a map, we must ensure that
• (1) all the minterms of the function are covered when we combine the squares,
• (2) the number of terms in the expression is minimized, and
• (3) there are no redundant terms (i.e., minterms already covered by other terms).
• Sometimes there may be two or more expressions that satisfy the simplification
criteria.
09/14/2025 Computer Architecture 15
Four-variable K-map
• The procedure for combining squares in the map may be made more systematic if
we understand the meaning of two special types of terms.
• A prime implicant is a product term obtained by combining the maximum
possible number of adjacent squares in the map.
• If a minterm in a square is covered by only one prime implicant, that prime
implicant is said to be essential.
• This means that a single 1 on a map represents a prime implicant if it is not
adjacent to any other 1’s.
09/14/2025 Computer Architecture 16
Four-variable K-map
09/14/2025 Computer Architecture 17
Four-variable K-map
• The combination of adjacent squares that is useful during the simplification process
is easily determined from inspection of the four-variable map:
• One square represents one minterm, giving a term with four literals.
• Two adjacent squares represent a term with three literals.
• Four adjacent squares represent a term with two literals.
• Eight adjacent squares represent a term with one literal.
• Sixteen adjacent squares produce a function that is always equal to 1.
09/14/2025 Computer Architecture 18
Four-variable K-map
• Example 3:
• Simplify the following Boolean
function into (a) sum-of-products
form and (b) product-of-sums form:
F (A, B, C, D) = ∑(0, 1, 2, 5, 8, 9, 10)
09/14/2025 Computer Architecture 19
Four-variable K-map
• Example 3: Gate Implementation
09/14/2025 Computer Architecture 20
Four-variable K-map
09/14/2025 Computer Architecture 21
Four-variable K-map
• Don’t Care Conditions:
• Functions that have unspecified outputs for some input combinations are called
incompletely specified functions .
• In most applications, we simply don’t care what value is assumed by the function
for the unspecified minterms.
• For this reason, it is customary to call the unspecified minterms of a function
don’t-care conditions .
• These don’t-care conditions can be used on a map to provide further
simplification of the Boolean expression.
09/14/2025 Computer Architecture 22
Four-variable K-map
• Example 4:
• Simplify the Boolean function, F (w, x, y, z) = ∑(1, 3, 7, 11, 15) which has the don’t-
care conditions d (w, x, y, z) = ∑(0, 2, 5).
