Karnaugh Maps

Computer Science: OCR A Level, topic 4.3.6

Karnaugh Maps

Karnaugh maps are diagrams used to simplify boolean expressions.

Drawing Karnaugh maps

Drawing Karnaugh maps

Solving a two-variable problem using a Karnaugh map involves creating a grid as shown:
The ‘0’ and ‘1’ down the left of the grid refer to ‘not A’ and 'A'.
The the ‘0’ and ‘1’ along the top of the grid refer to ‘not B' and 'B'.

Example

Example

Simplify the expression:
$A.\overline{B}+\overline{A}.B+A.B$
We start by splitting it into three sets of brackets using the associative rule:
$(A.\overline{B})+(\overline{A}.B)+(A.B)$

Fill in the table

Fill in the table

The first of these brackets refers to ‘A AND NOT B’.
That means we put a ‘1’ in the box with the coordinates (A1, B0) as shown.
The second bracket refers to ‘NOT A AND B’ .
That means we put a '1' in the box with coordinates (A0, B1).
The third bracket means ‘A AND B’, so we put a one in the box with coordinates (A1, B1).

Group

Group

The final stage involves grouping the '1's into sets of either 2, 4 or 8.
In this example, there are only three '1's in total, but they can be grouped into two pairs as shown.
The green pair both have the same value for A (1) and the blue pair have the same value for B (1).
So our original expression simplifies to $A + B$ .

Karnaugh Maps

We can also construct Karnaugh maps to simplify expressions with 3 or 4 variables.

Three variables

Three variables

With a three-variable problem, the grid is expanded by adding variable C to the top.
This means each column represents a combination of the variables B and C.
In the second column of the map shown, labelled 01.
The 0 refers to B and the 1 refers to C.
The order of these combinations follows the rules of Gray code.
This means that each combination is only a single bit different from the combinations either side of it.

Three variables

Three variables

Four variables

Four variables

For four variable Karnaugh maps, we do the same as for three variable but the rows now come to represent another combination of variables.
Each row is labelled using the Gray code as before.

Simplification

Simplification

In this example, the ‘1’s have been grouped into a pair (green) and a set of four (blue).
This is interpreted as (A AND B AND NOT C) OR (C AND NOT D) with the expression:
$(A.B.\overline{C})+(C.\overline{D})$

Test yourself on Karnaugh Maps

Which expression is represented by the Karnaugh map shown?
Which expression is represented by the Karnaugh map shown?
Which expression is represented by the Karnaugh map shown?
Which expression is represented by the Karnaugh map shown?

Practise this topic for free