Karnaugh MapsDate: 05/07/2000 at 08:11:31 From: Edmond Goold Subject: Karnaugh Maps What are Karnaugh maps? Date: 05/12/2000 at 15:37:59 From: Doctor TWE Subject: Re: Karnaugh Maps Hi Edmond. Thanks for writing to Dr. Math. A Karnaugh map is a technique used to simplify Boolean expressions (and logic circuits) related to Venn diagrams. Two-, three-, and four-variable Karnaugh maps can easily be done with pencil-and-paper. Beyond four variables, they generally require a computer program, but the technique can be extended to any number of variables. I'm going to use a preceding tilde (~) to represent 'not', and a lowercase 'v' to represent 'OR'. 'AND' is implied when there is no binary operator. So the expression ~A~B v ~AB is read as 'not A and not B or not A and B'. The not operation has highest precedence, so it operates on only the next variable unless parentheses are used. Similarly, ANDs take precedence over ORs unless parentheses are used. In order to use a Karnaugh map, it is best if the Boolean expression is in Disjunctive Normal Form (DNF). This means that every variable should be represented in every term (for a variable X, either X or ~X should be in every term), the variables within a term are ANDed together, and the terms are ORed together. There should be no parentheses. For example, the expression ABC v ~ABC v ~A~B~C is in DNF, but the expressions AC v ~ABC v ~A~B~C [no B in the first term], (AvBvC)(~AvBvC)(~Av~Bv~C) [variables ORed and terms ANDed instead of vice-versa] and ABC v ~A(BCv~B~C) [use of parenthesis] are not in DNF. If the Boolean expression is not in DNF, either it must be converted to DNF or special rules have to be added to plot the expression on the Karnaugh map. The disjunctive normal form is also called the canonical sum of products. Suppose we have the Boolean expression ~A~B v ~AB v AB. To simplify the expression using a Karnaugh map, we first need to create a two-variable map. This is done by placing one variable horizontally and one variable vertically, and writing each possible state of the variables, like this: ||~A | A | ===++===+===+ ~B || | | ---++---+---+ B || | | ---++---+---+ Note that the labels on the top and left of the map aren't part of the map itself, but are there to help you plot on the map. (They're the map's legend, so to speak.) Next, we need to plot the terms of the expression into the boxes in the map. In our example we have three terms: ~A~B is the first term, ~AB is the second, and AB is the third. To plot ~A~B, we place a 1 where the ~A column and the ~B row intersect, like this: ||~A | A | ===++===+===+ ~B || 1 | | ---++---+---+ B || | | ---++---+---+ Similarly, we plot ~AB by placing a 1 where the ~A column and the B row intersect, and AB where the A column and the B row intersect. Our map now looks like: ||~A | A | ===++===+===+ ~B || 1 | | ---++---+---+ B || 1 | 1 | ---++---+---+ Once all terms have been plotted in the map, we fill in any remaining spots with 0's: ||~A | A | ===++===+===+ ~B || 1 | 0 | ---++---+---+ B || 1 | 1 | ---++---+---+ Now for the simplifying. On a two-variable map, we look for a pair of 1's that are either in the same row or column. If we find such a pair, we record the common variable. In our example, we can find the two ones in the ~A column and circle them. We record ~A as the first term of our simplified expression: ||~A | A | ===++===+===+ ~B ||{1}| 0 | ---++---+---+ Simplified expression: ~A v B ||{1}| 1 | ---++---+---+ We haven't circled all of the 1's, so we must keep going. Should we circle the 1 in the lower right by itself, or should we circle it in a pair along with the 1 in the lower left? (We can do this even though we've already circled the 1 in the lower left.) Since a pair of 1's leads to a single-variable term, but a solo 1 leads to a two-variable term, it's simpler to circle it with its partner. The common variable between them is B, so we have: ||~A | A | ===++===+===+ ~B ||{1}| 0 | ---++---+---+ Simplified expression: ~A v B B ||{1}|{1}| ---++---+---+ Note that we ORed the B with the ~A from the first circle. Our simplified expression is ~AvB. Since all of the 1's are now in at least one circle, we've accounted for all of our original terms and we can stop. The general rules are: * Circle ALL of the 1's, NEVER circle a 0. * Use as large a circle as possible each time (circling four 1's is preferable to circling two 1's, which is preferable to circling one 1 by itself.) * Use as few circles as possible. Never circle a group unless it contains at least one 1 that wasn't previously circled. For three variables the process is similar, but two of the variables have to share a direction. A three-variable Karnaugh map looks like this: ||~A~B|~AB | AB | A~B| ===++====+====+====+====+ ~C || | | | | ---++----+----+----+----+ C || | | | | ---++----+----+----+----+ Note the order of the column headings - it's very important! Every column MUST share a variable with its neighbor. There are a few other "tricks" to keep in mind as well: (1) On a three-variable map we begin by looking for groups of four 1's. The four squares must form a rectangle (i.e. four in a row or a 2x2 square) - 'L' shapes and zigzags aren't a valid group of 4. Here are two examples of valid groups of 4: ||~A~B|~AB | AB | A~B| ||~A~B|~AB | AB | A~B| ===++====+====+====+====+ ===++====+====+====+====+ ~C || 1 | 1 | 1 | 1 | ~C || | 1 | 1 | | ---++----+----+----+----+ ---++----+----+----+----+ C || | | | | C || | 1 | 1 | | ---++----+----+----+----+ ---++----+----+----+----+ (2) A group of four will have one common variable. A pair must have two common variables. In the examples above, the common variable for the left map is ~C and the common variable for the right group is B. In the examples below, the left pair has the common variables BC, while the right pair has the common variables A~B. Note that the common variables within a group of 1's are ANDed. A solo 1 must have all 3 variables. ||~A~B|~AB | AB | A~B| ||~A~B|~AB | AB | A~B| ===++====+====+====+====+ ===++====+====+====+====+ ~C || | | | | ~C || | | | 1 | ---++----+----+----+----+ ---++----+----+----+----+ C || | 1 | 1 | | C || | | | 1 | ---++----+----+----+----+ ---++----+----+----+----+ (3) The map "wraps around" from the left edge to the right, like the center of a paper towel roll. (Remember that the column with the ~B and B is not part of the map itself, just the legend.) Thus, the following are valid groups: ||~A~B|~AB | AB | A~B| ||~A~B|~AB | AB | A~B| ===++====+====+====+====+ ===++====+====+====+====+ ~C || 1 | | | 1 | ~C || 1 | | | 1 | ---++----+----+----+----+ ---++----+----+----+----+ C || | | | | C || 1 | | | 1 | ---++----+----+----+----+ ---++----+----+----+----+ The common variables for the pair on the left are ~B~C, while the group of four on the right has the common variable ~B. Note that the lower corners form a valid pair as well. Four-variable Karnaugh maps are similar to three-variable maps, but both vertical and horizontal directions need to be shared by two variables. A four-variable Karnaugh map looks like this: ||~A~B|~AB | AB | A~B| ====++====+====+====+====+ ~C~D|| | | | | ----++----+----+----+----+ ~CD || | | | | ----++----+----+----+----+ CD || | | | | ----++----+----+----+----+ C~D || | | | | ----++----+----+----+----+ Note the order of the row and column headings. Every row and every column MUST share a variable with its neighbor. Here's how the "tricks" affect four-variable maps: (1) On a four-variable map we begin by looking for groups of eight 1's. The eight squares must form a rectangle (i.e. a 2x4 rectangle) - odd shapes aren't a valid group of eight. Next we look for groups of four, then pairs, then solos. (2) A group of eight will have one common variable, a group of four will have two common variables, a pair will have three common variables, and a solo will have all four variables. (3) The map "wraps around" from the left edge to the right, AND from top to bottom, kind of like a map of the world. This means groups can overlap the left and right, or top and bottom edges. The four corners form a "double wraparound" group of four, with the common variables ~B~D: ||~A~B|~AB | AB | A~B| ====++====+====+====+====+ ~C~D|| 1 | | | 1 | ----++----+----+----+----+ ~CD || | | | | ----++----+----+----+----+ CD || | | | | ----++----+----+----+----+ C~D || 1 | | | 1 | ----++----+----+----+----+ Since it is impractical to share more than two variables in a direction, 2D "pencil-and-paper" maps are generally limited to no more than four variables. I hope this helps. If you have any more questions, write back. - Doctor TWE, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/