Karnaugh Maps

concept

The Karnaugh map is a useful tool for simplifying boolean expressions without having to do a whole bunch of boolean algebra, which is often tedious. The Karnaugh map is a table of output values for given inputs, a lot like a multiplication table but instead of the numbers 1 to 12 on the top and left you have just 0 and 1 (or some more when you have three or more input variables). Once you have the Karnaugh map for a boolean expression we have a fairly simple method to create the simplified expression from the map. So we can go from a complex boolean expression to its simplified form all without having to do any actual boolean algebra.

fact

The Karnaugh map for a boolean expression is essentially a multiplication table for the inputs.

example

Create the Karnaugh map for the expression \(A + B\)

First we'll set up the map ready for us to fill in. Along the left side we'll list the values \(A\) can take (0, 1) and across the top we'll list the values \(B\) can take (0, 1) like so:

\(_A\)\\(\!^B\)	0	1
0
1

So the top left entry is for \(A = 0, B = 0\), when this is the case our output is 0 so we write a "0" in that cell:

\(_A\)\\(\!^B\)	0	1
0	0
1

Next the top right cell corresponds to \(A = 0, B = 1\) which gives us an output of 1 so we write "1" in that cell:

\(_A\)\\(\!^B\)	0	1
0	0	1
1

Now the bottom left cell is for \(A=1, B=0\) which gives us 1 and the bottom right cell has \(A=1,B=1\) which again gives 1:

\(_A\)\\(\!^B\)	0	1
0	0	1
1	1	1

And we're done, that's the Karnaugh map for \(A+B\).

To use the Karnaugh map to simplify an expression (which is its purpose after all), we want to find "groups" of 1s in the map. Ideally we'll have pairs of 1s next to each other or forming a rectangle. A single "1" could be part of two or more groups, there's no problem with overlapping groups. Once we've found the groups (a group could be a single '1' if it's sitting by itself) we find a rule to describe each one (like \(A\) or \(AB\)) and then sum all of these rules to get our final answer. An example will be clearer

example

Use a Karnaugh map to simplify \(A+AB\)

First we need to write out the Karnaugh map:

\(_A\)\\(\!^B\)	0	1
0	0	1
1	1	1

Which happens to be the same as the one in our example above. Now there's a group of 1s in the right column and a group of 1s in the bottom row.

The rule for the group of the right column is \(B\) since \(B=1\) for all of them and \(B=1\) doesn't contain any 0s. The rule for the group of the bottom row is \(A\) since it corresponds to \(A=1\) and \(A=1\) doesn't contain any 0s. This means that our expression can be written as \(A+B\) So \(A+AB = A+B\) And we got it without doing any algebra.

practice problems