Karnaugh Map (K-map) – How to simplify Boolean functions

Apr 162024

What is Karnaugh Map?

The Karnaugh map (K-map) is a widely used tool for simplifying logic circuits. When you have a logical function with its truth table, and you want to implement this function in the simplest and most economical way, this method is used.

Examples of how to use the Karnaugh Map

Example 1: We have the following truth table for three variables. Based on this, the logical function is developed. (first canonical form).

Note that the formula includes the variables (A, B, C) only if F is equal to “1”, and

If A is “0”, it is set to A,
If B = “1”, it is set to B,
If C = “0”, it is set to C, etc.

Once the logic function is obtained, the Karnaugh map is implemented. It has 8 boxes, a number obtained by the formula 2ⁿ, where n = 3 (number of variables (A, B, C)). See the diagram below.

The first row corresponds to A = 0.
The second row corresponds to A = 1.

The first column corresponds to BC = 00 (B = 0 and C = 0).
The second column corresponds to BC = 01 (B = 0 and C = 1).
The third column corresponds to BC = 11 (B = 1 and C = 1).
The fourth column corresponds to BC = 10 (B = 1 and C = 0).

In the K-map, a “1” has been placed in the boxes corresponding to the values of F = “1” in the truth table.

Note the numbering of the rows in the truth table and the numbering of the boxes in the Karnaugh map.

To continue with the simplification, groups of “1”s are created that have 1, 2, 4, 8, 16, etc. (powers of 2 only). The “1”s must be adjacent (not diagonal), and the more “1”s the group has, the better.

The function with the least number of groups and the greatest number of “1”s
in each group is the best simplified function.

As you can see in the picture, there are two groups of four “1”s each (sharing boxes between groups is allowed). The new expression of the simplified Boolean function is derived from the Karnaugh map.

For the first group (red), the simplification gives “B” because the “1”s are located in the third and fourth columns, which correspond to B = 1.
For the second group (blue): simplifying, we get “A” because the “1”s are located in the bottom row, which corresponds to A = 1.

So the result is F = B + A or F = A + B

Example 2: A truth table like the following with its Boolean function: F = A B C + A B C + A B C + A B C

It is clearly seen that the function is a reflection of the content of the truth table when F = “1”. With this equation, the Karnaugh map is created, and the groups are selected.

3 groups of two “1”s are created. You can see that it is not possible to make groups of 3, because 3 is not a power of 2. You can see that there is a square that is shared by the three groups.