The three-variable K-map is shown in Fig. 2.18. Notice the way in which the cells are designated. The cells 4 and 5, as well as 6 and 7, are designated in a reversed order. This is done in order to bring together the adjacent cells that differ from each other in one variable only. For example, cells 00 and 01 differ in the position of the variable b, a being the same for both the cells. Similarly, cells 01 and 11 differ in the position of a, and cells 11 and 10 differ in the position of b. This means that K-map makes use of Gray code to designate its cells.
The final answer can now be obtained as follows:
In the discussion given above, we have explained the K-map reduction process in detail. In actual practice, we don’t follow such detailed steps on the paper, but make the eliminations mentally. For this we notice (as explained previously) that the element that appears in complemented and uncomplemented forms gets eliminated in a pairing process. For example, when the cells 00 and 10 are paired together, the first variable gets eliminated, as it appears in the complemented and uncomplemented forms. Thus, by visual inspection of the K-map, we can perform logic reduction. It can be easily seen that the K-map method of logic simplification is very fast and simple.
It may also be noted from Fig. 2.18 that cells 10 and 00 are adjacent, since they differ in one position only. Therefore we can club (or group or pair) the entries in these two cells for the elimination of the variable a that appears as complemented and uncomplemented in the map.
Example 2: Simplify the logic expression, S = S (m0, m1, m2, m4, m7).
Solution: The given logic function has eight minterms and hence requires a three-varible K-map for its reduction. The relevant map is drawn as shown in Fig. 2.19. and grouping of the entries are done as shown. The 1-entry cells are m0 = 000, m1= 001, m2 = 010, m4 = 100, and m7 = 111. These are the given minterms. The cells not mentioned in the given example will have 0s as entries. Thus cells m3, m5, and m6 have 0 as entry, as shown. It is important that in a K-map all the cells must be filled with entries; no cells must be left empty.
There are four groups in the map. Of these, we notice that Pair 1 eliminates the variable c, as this is an encirclement covering cells 000 and 001. Similarly, Pair 2 covers cells 000 and 011; this eliminates the variable b. In the same fashion, Pair 3 eliminates the variable a since this is an encirclement between cells 000 and 100. Finally, Group 4 has only one member in it, and it can be seen that this member cannot be paired with any other member for want of adjacency. So, no elimination is possible in this case. Such an entry with only one element in it is called a singleton.
The final answer can now be obtained as follows:
Pair 1: a'b'c' + a'b'c = a'b'(c + c') = a'b'
Pair 2: a'b'c' + a'bc' = a'c' (b + b') = a'c'
Pair 3: a'b'c' + ab'c' = (a'+ a)'b'c' = b'c'
Singleton: abc
We get the final sum as:
S = Pair 1 + Pair 2 + Pair 3 + Singleton
= a'b' + a'c'+ b'c' +abc (2.23)