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
Math Forum Home || Math Library || Quick Reference || Math Forum Search