Three and Four Variable Karnaugh Maps

concept

Karnaugh maps wouldn't be very useful if you could only use them to simplify expressions of two variables. The real power comes in simplifying expressions with three or more variables, where the boolean algebra is confusing and it's rarely clear what you should do. When you have three or more variables a Karnaugh map makes simplifying an expression much, much simpler (and faster as well!)

fact

When creating a Karnaugh map for a three variable expression of variables $A,\: B,\: C$ we draw the Karnaugh map like so:

$_A\text{\\}^{BC}$	00	01	11	10
0
1

The top row combines $B$ and $C$, so the $01$ column corresponds to $B=0$ and $C=1$.

The order of the $BC$ numbers isn't just counting up in binary and it is done the way it is on purpose. It's called a "Gray Code" and it's important for using the Karnaugh map to simplify expressions later. In a Gray code only one digit in the number ever changes at a time. Going from $01$ to $10$ would involve changing both bits, so instead we count $00,\: 01,\: 11,\: 10$, in each case only one bit is changing.

example

Fill out the Karnaugh map for $AB + C$

Starting out with the empty map we'll look at the first column corresponding to $B = 0$ and $C = 0$. In this case we're always 0 so write those in.

$_A\text{\\}^{BC}$	00	01	11	10
0	0
1	0

Now the columns $01$ and $11$ both correspond to $C=1$ which always results in a 1 so fill those in.

$_A\text{\\}^{BC}$	00	01	11	10
0	0	1	1
1	0	1	1

And finally we have the column $10$ which corresponds to $B = 1$ and $C = 0$. So for $A = 0$ we'll get 0 and for $A=1$ we'll get a 1.

$_A\text{\\}^{BC}$	00	01	11	10
0	0	1	1	0
1	0	1	1	1

That's great and all, but how do we use Karnaugh maps to actually simplify an expression? Well remember when I said we look for rectangles of 1s together in a Karnaugh map? It didn't make much sense for 2 variable maps but it makes more sense now. Look at the map in the example above and you'll notice a nice block of four 1s right smack in the middle of that table. That's telling us that we've got a simple little rule to account for all of those 1s. In fact just by looking at the table we can see that that block comes from the rule $C=1$ Just from that one block we know that the expression that this Karnaugh map comes from has a $+C$ in it. Now there's still one 1 not accounted for, but the trick is actually to see it as a block of two 1s including the 1 to its left (all blocks have to be rectangles and the dimensions being a power of 2 helps). That block of two 1s corresponds to the rule $AB$. So we know that the map's simplified expression is $AB + C$ just like we started with. This technique takes a little practice to get used to but makes simplifying large boolean expressions a breeze once you're used to it.

example

Draw the Karnaugh map for the expression $\not{A} + B\not{C}$

This time we've got some nots in there, don't worry it doesn't make things any trickier. We'll again start by drawing out the empty Karnaugh map:

$_A\text{\\}^{BC}$	00	01	11	10
0
1

Then start with $\not{A}$ and mark everywhere that gives a 1 (whenever $A=0$)

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1	1	1
1

Cool, next we'll find everywhere that $B\not{C}=1$ (which is whenever $B=1,\: C=0$).

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1	1	1
1				1

And everywhere else must be 0s:

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1	1	1
1	0	0	0	1

example

Use a Karnaugh map to simplify $\not{A(\not{B}+C)}$

Starting with our empty map:

$_A\text{\\}^{BC}$	00	01	11	10
0
1

This time we'll go through the cells in the table one by one and figure out if this expression gives 1 or 0. So starting with the top of the first column we have $A=0,\; B=0,\; C=0$ That gives us $\not{0(\not{0}+0)} = 1$ So stick in a 1

$_A\text{\\}^{BC}$	00	01	11	10
0	1
1

Then the bottom row of the first column is $A=1,\; B=0,\; C=0$ That gives $\not{1(\not{0}+0)} = 0$

$_A\text{\\}^{BC}$	00	01	11	10
0	1
1	0

Then the top row of the second column is $A=0,\; B=0,\; C=1$ $\not{0(\not{0}+1)} = 1$

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1
1	0

And the bottom for for the second column is $A=1,\; B=0,\; C=1$ Now $\not{1(\not{0}+1)} = 0$

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1
1	0	0

Filling in the rest of the table we get:

$_A\text{\\}^{BC}$	00	01	11	10
0	1	1	1	1
1	0	0	0	1

Now there are two groups we can make. The first is the entire top row corresponding to $\not{A}$. The second is the very right column which corresponds to $B\not{C}$ So the entire expression simplifies to: $$\not{A(\not{B}+C)} = \not{A} + B\not{C}$$ This is much, much simpler than having to go through the pain of simplifying the expression using boolean algebra.

practice problems

\(_A\text{\\}^{BC}\)	00	01	11	10
0
1

\(_A\text{\\}^{BC}\)	00	01	11	10
0	0
1	0

\(_A\text{\\}^{BC}\)	00	01	11	10
0	0	1	1
1	0	1	1

\(_A\text{\\}^{BC}\)	00	01	11	10
0	0	1	1	0
1	0	1	1	1