
9.9 Karnaugh Maps

Boolean functions can be diagrammatically represented by means
of Karnaugh maps. A n variable function has 24 or 8 rows in the truth table and a 4 variable function has 2^{4} of 16 rows in the truth table describing the function. A n variable function would have 2^{n }rows in its truth table. A Karnaugh map is so drawn such that each row of the table corresponds to a cell in the map. A 1 is placed in a cell corresponding to a row for which the function evaluates to 1 and 0 is placed in the cells corresponding to rows for which the function evaluates to 0.

The cells are so arranged that physically adjacent cells are also logically adjacent. Two terms are logically adjacent if they differ only in one literal. For example, ab c is adjacent to abc. ab c and abc, a compliment b is adjacent to ab and a b, abcd is adjacent to abcd. abcd, abcd and abcd compliment. Observe that a two variable term is logically adjacent to 2
terms, a three variablc term is logically adjacent to 3 terms and an
n variable term is logically adjacent to n terms. On the map. a cell
corresponding to a n variable term would be logically adjacent to n
other cells.

9.9.1 One and Two Variable Maps

A one variable map relates to function of one variable, for example. f (a) = a This function describes an inverter. The truth table is shown in Table 9.10


This table can be diagrammatically represented in a Karnaugh map as shown in fig. 9.3 with 21 or 2 cells.

Fig. 9.3 Karnaugh map of (a) a one variable function (b) f(a) a

Observe that the physically adjacent cells vary only in one variable (a and a) and hence are logically adjacent.

A two variable map relates to a function of two variables. Example
fa, b) = ab + ab. The truth table for the function is shown in Table
9.11.


Observe that cell corresponding to f(0, 0),ab is adjacent to a b and
ab.

9.9.2 Three and Four Variable Maps

A three variable map relates to a function of three variables, for example,
f (a, b, c)=a bc + abc + abc + abc. The truth table for this function is shown in Table 9.12. 

The three variable map is constructed on a cylinder such that the left hand and right hand edges of the map touch each other. We can ensure that all cells, including those at the left and right extremes are logically and physically adjacent to three other cells.

The Karnaugh map for the three variable function is shown in Fig.9.5 with 2^{3} or 8 cells.


Imagine folding the three variable map over a cylinder with edge WX in contact truth edge YZ as shown in Fig. 9.5(c).
This assures that
Cell 0 is adjacent to cells 1, 4 and 2
Cell 4 is adjacent to cells 0, 5 and 6
Cell 2 is adjacent to cells 3, 6 and 0
Cell 6 is adjacent to cclls 2 , 7 and 4

The cell numbers have been soarranged that physically adjacent cells are also logically adjecent. Cell 0 (abc ) and cell 2(abc ) different only in one literal ‘b’
A four variable map relates to a function of four variables, for example, f (a, b,c,d) = Σm (0, 3, 5, 11, 12, 14, 15). The truth table for this function is shown in Table 9.13.


The cells in the four variable Karnaugh map are so arranged that physically adjacent cells are also logically adjacent. Imagine that the map is rolled horizontally so that edge WY is in contract with edge. XZ and that the map is rolled vertically so that edge WX is in contact with edge YZ. The Karnaugh map for a four variable function is shown in Fig. 9.6 with 2^{4} or 16 cells.

It is easy to sec that
Cell 0 is adjacent to cells 1,4, 2 and 8
Cell 8 is adjacent to cells 12,9, 10 and 0
Cell 3 is adjacent to cells 1, 7, 2 and 11
and so on.
Observe that physically adjacent cells are also logically adjacent in the sense that they vary in only one literal.






Khannur's Book 

Arunkumar Khannur, Software Testing  Techniques and Applications,
Published by Pearson Publications, 2011
(ISBN:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO Forum

Contact Khannur 
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block,
Rajajinagar,
Bangalore  560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt 
