The Karnaugh map (K map) provides a systematic method for simplifying a Boolean expression or a truth table function. When used properly, the K map will produce the simplest SOP or POS expression possible. Familiarity with the law and rules of Boolean algebra is not required. Instead, simplification is done graphically using the K mapping technique.
The K map is a table consisting of N = 2n cells, where n is the number of input variables. For a SOP expression each cell represents one particular combination of the variables in product form. The table format is such that there is a single variable change between any adjacent cells. This is the characteristic the will determine adjacency. To illustrate the above points let us consider an example where n = 2 and N = 4. Assuming the input variable are A and B then the K map illustrating the four (4) possible variable combinations 
is show below in Table 1-15.
Table 1-15 Two variable K map format
If we extend our example to consider the case where n = 3 and N = 8 then assuming that our input variables are A, B and C the associated K Map is shown in Table 1-16.
Table 1-16 Three Variable K-Map
For n>5 the K map technique becomes impractical unless implemented on computer.
Simplifying using the K-Map
To simplify a SOP for of a Boolean expression using a K map, first identify all the input combinations that produce an output of logic level 1 and place them in their appropriate K map cell. Consequently, all other cells must contain zero (0). Second, group the adjacent cells that contain 1 in a manner that maximises the size of the groups but also minimises the total number of groups. All 1’s in the output must be included in a group even if the group is only one cell. Third, as each SOP term represents an AND expression, each (AND) grouping is written with only the input variables that are common to the group. Finally, the simplified expression is formed by ORing each of the (AND) groups. To illustrate lets consider the function 
whose truth table and K map are illustrated in Table 1-17 and Table 1-18 respectively.
Input | Output | ||
A | B | C | X |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Table 1-17 Truth Table of
Table 1-18 K-Map for
By examination of the K map, the simplified expression for is 
.
Let us now use the K map technique to simplify the SOP Boolean expression 
. The associated truth table and K map are presented in Table 1-19 and Table 1-20, respectively.
Input | Output | ||
A | B | C | X |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Table 1-19 Truth Table of
Table 1-20 K-Map for
By examination of the K map, the simplified expression for is 
.
Suppressed Variables
Sometimes a SOP expression does not have a complete set of variables in each of its terms. For example, the expression 
contains a term that does not include the variable A or its complement. A missing variable in a SOP expression is called a suppressed variable.
Before plotting an expression with suppressed variables on a K-MAP we must first expand out all of the shortened terms to include the missing variables and its complement. To illustrate let us consider use our example above:
Then our expanded expression becomes
and we may now use the truth table and the associated K map, as illustrated in Table 1-21 and Table 1-22, to simplify.
Input | Output | ||
A | B | C | X |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Table 1-21 Truth Table of
Table 1-22 K-Map for
From the three groupings shown in the K map we form the expression 
.
Don’t Care States
Truth table specifications for a logic function may not to include all possible combinations of the input binary digits for the input variables, yet they may still be complete specifications of the logic function for the prescribed application. In these situations certain input combinations will not occur due to the nature of the application. When the input combinations are irrelevant or cannot occur, the output states are in the Truth table and the K map are filled with an X and are referred to as don’t care states.
When simplifying K maps with don’t care states, the contents of the undefined cells (1 or 0) are chosen according to preference. The aim is to enlarge group sizes thereby eliminating as many input variables from the simplified expression as possible. Only those X’s that assist in simplifying the function should be included in the groupings. No additional X’s should be added that would result in additional terms in the expression.
To illustrate let us consider the function specified by Table 1-23 and its corresponding K map shown in Table 1-24. Note that the two groupings determine that the simplified expression is expressed as 
Input | Output | ||
A | B | C | X |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | X |
1 | 1 | 0 | X |
1 | 1 | 1 | X |
Table 1-23 Truth Table of the Function J
K-Map for the function J
ශිල්ප 64