Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Karnaugh Maps


Date: 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/   
    
Associated Topics:
College Discrete Math
College Logic
High School Discrete Mathematics
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/