Processing math: 100%

Content

Karnaugh Maps

We have already seen two methods for simplifying switching circuits. These are manipulation using the properties of Boolean algebra and the function approach that reduces the problem down to looking at values of the function at specific points. (Of course these two methods can be used together.) Karnaugh maps
(see https://en.wikipedia.org/wiki/Karnaugh_map and
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html#KMapsIntro)
are a third method that is more efficient than the function approach and which are often used for relatively small numbers of switches (or propositions). Once the number of switches gets past a certain point, however, computer algorithms need to come into play.

Example of a Karnaugh Map: The switching circuit for Voting for Three (see Q3) can be rewritten as

Table 9: Voting for three

x y z Light
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

The Karnaugh map (K-map) of this is presented below. It contains all the information of the original table but that information is represented differently. The result is a decrease in the number of cells that need to be considered.

Table 10: an example of a K-map

x yz
  00 01 11 10
0 0 0 1 1
1 0 1 1 1

Note:

Now the entry in Table 10 in column 2 row 2, represent the value of xyz and the entry in column 3 row 2 represent xyz. But as these have both got a value of 1 (and in the disjunctive normal form) they give xyz+xyz which simplifies to xz. This always happens when two ones are next to each other in a K-map. From Table 10 above we can see that we could have combined xyz with xyz to get xy. This happens whenever there are two adjacent ones in the same row or column. So working with columns the third column of Table 10 shows that xyz+xyz=yz. As a result the switching circuit can be simplified to xz+xy+yz.

For groups of 1s that have area that is a power of 2, more substantial savings can be made in the simplification process

(see https://en.wikipedia.org/wiki/Karnaugh_map#Solution).

Questions

  1. Use the K-map method to simplify the switching circuits for Q42(c) (page reference).
  2. Use the K-map method to simplify the logic circuits in Q60.
    Note that other questions can be found on the site
    https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html#KMapsIntro.
  3. Simplify the following partial table using the Karnaugh approach. Check that the disjunctive normal form gives the same result.
  4. x yz
      01 11
    01 1 1
    11 1 1

Next page - Answers to switching circuits