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
Truth Table for 2x1 Karnaugh Map
Input
|
Output
|
A
|
X
|
0
|
X0
|
1
|
X1
|
Example 1.2
2x1 Karnaugh Map
|
A
|
x0
|
x1
|
For the invertor example, this would have the values
Example 2.1
Truth Table for 2x1 Karnaugh Map
Input
|
Output
|
A
|
X
|
0
|
1
|
1
|
0
|
Example 2.2
2x1 Karnaugh Map
|
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
Truth Table for 4x4 Karnaugh Map
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
4x4 Karnaugh Map
|
|
|
A
|
|
|
|
|
|
B
|
|
|
x0
|
x1
|
x3
|
x2
|
C
|
|
x4
|
x5
|
x7
|
x6
|
D
|
x12
|
x13
|
x15
|
x14
|
|
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 (ABCD)(ABCD)(ABCD)(ABCD) 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 CD. 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
|
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
|
|
|
|
|
|
B
|
|
|
0
|
0
|
0
|
0
|
C
|
|
0
|
0
|
0
|
0
|
D
|
1
|
1
|
1
|
1
|
|
0
|
0
|
0
|
0
|