# Karnaugh Maps

It may be necessary to read the section on Boolean Algebra in order to understand some of the notation used within this article.
A Karnaugh Map makes simplification of truth tables into functions much easier, but it is quite an involved concept to learn. You get all the minterms, and draw a rectangle around them using the fewest rectangles possible that include all the selected minterms. A rectangle must have 2^N minterms within it (so 1,2,4,8,16 etc.) The size of Karnaugh map depends on the number of variables dealt with.
In order to begin teaching the concepts behind Karnaugh maps, I will start with a 2x1 grid. This would not actually be used, but gives an example of how Karnaugh Maps work. I will use the example of an inverter. If a 1 is put in, a 0 is given out. If a 0 is put in, a 1 is given out. I will use the term xn to describe the letter x followed by a number. xn would normally be replaced by a 0, a 1 or a don't care term, represented by a - as is shown in examples 2.1 and 2.2 below. As you can see, everything below the the A is the value for when A = 1. Everything which doesn't have an A above is the value for when A = 0. This may not make much sense yet, but should start to when we deal with larger maps.
Example 1.1 :
| Input | Output |
| A | X |
| 0 | X0 |
| 1 | X1 |
Example 1.2 :
| | A |
| x0 | x1 |
For the invertor example, this would have the values
Example 2.1 :
| Input | Output |
| A | X |
| 0 | 1 |
| 1 | 0 |
Example 2.2 :
| | A |
| 1 | 0 |
Below, I've shown how the output(X) of the truth table (normally 0s or 1s) are mapped onto a 4x4 karnaugh map.
Example 3.1 :
| Inputs | Inputs | Inputs | Inputs | Output |
| A | B | C | D | X |
| 0 | 0 | 0 | 0 | X0 |
| 0 | 0 | 0 | 1 | X1 |
| 0 | 0 | 1 | 0 | X2 |
| 0 | 0 | 1 | 1 | X3 |
| 0 | 1 | 0 | 0 | X4 |
| 0 | 1 | 0 | 1 | X5 |
| 0 | 1 | 1 | 0 | X6 |
| 0 | 1 | 1 | 1 | X7 |
| 1 | 0 | 0 | 0 | X8 |
| 1 | 0 | 0 | 1 | X9 |
| 1 | 0 | 1 | 0 | X10 |
| 1 | 0 | 1 | 1 | X11 |
| 1 | 1 | 0 | 0 | X12 |
| 1 | 1 | 0 | 1 | X13 |
| 1 | 1 | 1 | 0 | X14 |
| 1 | 1 | 1 | 1 | X15 |
Example 3.2 :
| | | | A | A | |
| | | | | B | B |
| | | x0 | x1 | x3 | x2 |
| C | | x4 | x5 | x7 | x6 |
| C | D | x12 | x13 | x15 | x14 |
| | D | x8 | x9 | x11 | x10 |
In use, each occurrence of X and a number (Xn) would be replaced with a 0, 1 or - (don't care) term.
The letters at the top and sides show where each of the input variables (A,B,C and D) equal 1. For the Karnaugh map to be translated into a function, it is necessary to group similar terms. An example of this is shown below. The function ($\lnot$A$\land$$\lnot$B$\land$C$\land$D)$\lor$($\lnot$A$\land$B$\land$C$\land$D)$\lor$(A$\land$$\lnot$B$\land$C$\land$D)$\lor$(A$\land$B$\land$C$\land$D) is mapped below. It can be seen that are equal to 1 are shaded. All the shaded cells fall into both C and D. Therefore, the simplified function is C$\land$D. Don't care terms can be assigned to either a 1 or a 0 depending on which leads to a more simplified solution.
Truth Table for 4x4 Karnaugh Map :
| Inputs | Inputs | Inputs | Inputs | Output |
| A | B | C | D | X |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
4x4 Karnaugh Map :
| | | | A | A | |
| | | | | B | B |
| | | 0 | 0 | 0 | 0 |
| C | | 0 | 0 | 0 | 0 |
| C | D | 1 | 1 | 1 | 1 |
| | D | 0 | 0 | 0 | 0 |