Karnaugh Maps

We can write the boolean expression for any truth table using minterms. However, simplifying the expression using boolean algebra can be difficult.

Karnaugh maps are an easy way to simplify expressions of up to 4 variables. They are a diagramming technique for writing the truth tables in such as way that simplifications are easy to see.

Karnaugh Maps Format

The first step is to rewrite the truth table as a Karnaugh map. The 2-variable truth table:

truth table 2 variables

is drawn as:

kmap 2 variables

The 3-variable truth table:

truth table 3variables

is drawn as:

kmap  3 variables

It is important to pair the B and C variables and to write the values in the order shown if simplification is to be accomplished. (Note that only one value in the values changes with each column).

The 4-variable truth table:

truth table 4 variables

is drawn as:

kmap 4 variables

It is important to pair the variables and to write the values in the order shown if simplification is to be accomplished. (Note that only one value in the values changes with each column).

Looping

The truth table has its 1's and 0's written into the Karnaugh map in the corresponding locations, then each location in the Karnaugh map represents one minterm. Then two, four or eight adjacent squares that contain 1's are looped to create a simplified boolean expression (note the number of adjacent squares in a power of 2). The expression for the loop will eliminate the variable(s) that appear in both normal and complemented form.

Example1:

Write the expression for the truth table shown:

results in the Karnaugh map with the single loop:

The A variable appears complemented and the variable B is both complemented and uncomplemented, so B does not appear in the final expression of:

 

Example2:

Write the expression for the truth table shown:

results in the Karnaugh map with the single loop:

The variable B appears uncomplemented and the variable A is both complemented and uncomplemented, so A does not appear in the final expression of:

 

Example3:

Write the expression for the truth table shown:

results in the Karnaugh map with the two loops:

The variable B is complemented in the first loop, with A being both complemented and uncomplemented, so the variable A does not appear in the first loop expression. The variable A is uncomplemented in the secondloop, with B being both complemented and uncomplemented, so the variable B does not appear in the second loop expression. The two expressions are ORed together (as minterms are) to arrive at the final expression of:

 

Example 4:

Write the expression for the truth table shown:

results in the Karnaugh map with the two loops:

The variable C is complemented and uncomplemented in the smaller loop, with A being uncomplemented and B being complemented, so the variable C does not appear in the smaller loop expression.The variables A and B are both complemented and uncomplemented in the larger loop, with C being uncomplemented, so the variables A and B do not appear in the larger loop expression. Since the variable B is both complemented and uncomplemented, it does not appear in the final expression of:

 

Example 5:

Write the expression for the truth table shown:

results in the Karnaugh map with the two loops:

In this example, the two corner squares are looped and there is a loop with just a single square in it. This results in the final expression:

 

Assignments

  1. The following are unsimplified minterm expressions. Draw the 2x4 Karnaugh map and find a simpler expression.

     

  2. Given the following truth tables, find the Karnaugh map and the boolean expression