K-Map (Karnaugh Map)

➢A Karnaugh map provides a pictorial method of grouping together

➢ The Karnaugh map can also be described as a special arrangement of a

➢We can minimize Boolean expressions of 3, 4 variables very easily

➢ K-map can take two forms Sum of Product (SOP) and Product of Sum
(POS) according to the need of problem.

➢ In K-map, we fill grid of K-map with 0’s and 1’s then solve it by
making groups.
Mr. P. D. Sawant 1
Steps to solve expression using K-map
➢ Select K-map according to the number of variables.

➢ Identify minterms or maxterms as given in problem.

➢ For SOP put 1’s in blocks of K-map respective to the minterms (0’s
elsewhere).

➢ For POS put 0’s in blocks of K-map respective to the maxterms(1’s

➢ Make rectangular groups containing total terms in power of two like

➢ From the groups made in step 5 find the product terms and sum them
up for SOP form. Mr. P. D. Sawant 2
Two variable K-Map

Figure 1: Truth Table 2-variable function And K-Map 2 Variable

❖ Table in figure-1 on the left is a truth table for two input variables.
❖ The output is shown in column marked ‘F’.
❖ m0, m1, m2, m3 are the four minterms (or the product terms )for high ‘1’ outputs.

Mr. P. D. Sawant 3
K-Map (Karnaugh Map)

0 1 0 1

2 3 2 3

Mr. P. D. Sawant 4
Three Variable K-Map

Figure : (a) Truth Table 0f 3-variable function (b) K-Map of 3-variable

➢ Table on the left is a truth table for three input (x,y,z) and one output variables(F).

➢ The minterms are marked m0, m1, m2, m3 m4, m5, m6, m7 are the eight minterms (or the
product terms )for high ‘1’ outputs. K

➢ Note the naming of cells. Minterms in upper row is m0,m1,m3, m2 with binary value as 00,
01,11,10 and the lower row cell numbers being m4,m5, m7, m6.
Mr. P. D. Sawant 5
Example: Show the representation of the minterms of a three variable majority function using a K-
Map.
The table below shows the relationship for the input and output of the majority function.

The K-map in figure shows the position of the minterms and the K-map filled with the minterms
values ‘1’ for the high outputs

Mr. P. D. Sawant 6
4-variable K-Map

❖ Figure above shows the K-map for four variables. There are 16 number of cells each marked
for one minterm.

❖ Note down the position of the cells carefully. There cell numbering follow the unit distance
/gray code pattern so that only one variable change as we move from any position to any next up
or down or left or right of current cell. This method as we’ll see helps in simplification.

Mr. P. D. Sawant 7
Karnaugh Maps - Rules of Simplification
❖ The Karnaugh map uses the following rules for the simplification of expressions by
grouping together adjacent cells containing ones.

▪ Groups may not include any cell containing a zero

▪ Groups may be horizontal or vertical, but not diagonal.

Mr. P. D. Sawant 8
Karnaugh Maps - Rules of Simplification
▪ Groups must contain 1, 2, 4, 8, or in general 2n cells.

▪ That is if n = 1, a group will contain two 1's since 21 = 2.

▪ If n = 2, a group will contain four 1's since 22 = 4.

Mr. P. D. Sawant 9
Karnaugh Maps - Rules of Simplification
▪ Each group should be as large as possible..

▪Each cell containing a one must be in at least one group.

Mr. P. D. Sawant 10
Karnaugh Maps - Rules of Simplification
▪ Groups may overlap.

Mr. P. D. Sawant 11
Karnaugh Maps - Rules of Simplification
▪ Groups may wrap around the table. The leftmost cell in a row may be
grouped with the rightmost cell and the top cell in a column may be
grouped with the bottom cell.

Mr. P. D. Sawant 12
Karnaugh Maps - Rules of Simplification
▪ There should be as few groups as possible, as long as this does not
contradict any of the previous rules.

Mr. P. D. Sawant 13
SOP FORM

F(ABC)= ∑ m (1,3,6,7)

From red group we get product term— A’C

From green group we get product term—AB

Final expression F=(A’C+AB)

x from vertical pair; so it reduces to “yz”

y from 1st lower horizontal pair; which reduces to “xz”

z from lower 2nd pair; which reduces to “xy”

So the solution is :Y = yz + xz + xy

Mr. P. D. Sawant 15
SOP FORM
K-map for 4 variables F(P,Q,R,S)=∑(0,2,5,7,8,10,13,15)

From red group we get product term— Q.S

Final expression (Q.S + Q’.S’)

Mr. P. D. Sawant 16
POS FORM
K-map of 3 variables- F(A,B,C) = π (0,3,6,7)

Final expression F= (A + B + C) (A’ + B’ + C) (B’ + C’)

Mr. P. D. Sawant 17
POS FORM
K-map of 4 variables- F(A,B,C,D)=π(3,5,7,8,10,11,12,13)

Final expression F= (C’+A+B) . (D’+A+B’) . (C+A’+B’).(A’+C’+D)

Mr. P. D. Sawant 18
Examples – SOP Form

Out(A,B,C,D)=∑(3,7,11,12,13,14,15)

Mr. P. D. Sawant 19
Examples – SOP Form

Out(A,B,C,D)=∑(0,1,2,3,8,9,10,11)

Mr. P. D. Sawant 20