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
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.
x | yz | ||||
00 | 01 | 11 | 10 | ||
0 | 0 | 0 | 1 | 1 | |
1 | 0 | 1 | 1 | 1 |
Note:
- The entries 00, 01 etc. along the top of Table 10 represent the values of y and z together. So the entry in column 4 row 2 is the value for x=1,y=1,z=0.
- The headings of the columns differ by 1 in each place as you move from left to right. (The same is true for rows regardless of how many rows there are.)
- The headings increase in an unnatural way in that they do not increase in the way that binary numbers would. However, this enables a term and its complement to be next to each other and so reductions of the form w+w′ are easier to spot and combine.
- K-maps can be produced for any number of switches or propositions. It is probably more efficient to divide the numbers so that about half are along the top and the rest down the side.
Now the entry in Table 10 in column 2 row 2, represent the value of xy′z 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 xy′z+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 x′yz+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
- Use the K-map method to simplify the switching circuits for Q42(c) (page reference).
- 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. - Simplify the following partial table using the Karnaugh approach. Check that the disjunctive normal form gives the same result.
x | yz | ||||
01 | 11 | ||||
01 | 1 | 1 | |||
11 | 1 | 1 |