Karnaugh Maps – ACSL Topics

Overview

Logic design is about analysing, building and minimising Boolean functions. A circuit built from a shorter expression uses fewer gates, so finding the smallest equivalent expression matters. Simplifying by algebra alone works but takes experience and a certain amount of luck, and it gets harder quickly as the number of variables grows. Some simplifications are obvious: AB + AB clearly depends only on B. Others are not: it is far from obvious that AB + BC + AC is the same function as AB + AC.

The Karnaugh map (Maurice Karnaugh, 1953) is a tool that turns this into pattern recognition. It lays the truth table out as a grid arranged so that any two neighbouring cells differ in exactly one variable. Groups of adjacent 1's then correspond directly to simplified product terms.

Key Concepts:

A map for n variables has 2ⁿ cells, one for each row of the truth table.
Row and column headings are written in Gray code order (00, 01, 11, 10) so that neighbours differ by a single bit. The map also wraps around: the first and last rows are neighbours, as are the first and last columns.
Circle rectangular groups of 1's whose size is a power of two. Each group becomes one product term containing only the variables that are constant across the group.
The minimal expression is the OR of the group terms.

Key Concepts

Laying Out the Map

Write 1 for an uncomplemented variable and 0 for a complemented one, so the term ABC corresponds to the binary cell 101. Each cell is filled with the function's value for that input combination.

Two variables

A \ B	0	1
0	00	01
1	10	11

Cell labels show the values of AB.

Three variables

C \ AB	00	01	11	10
0	000	010	110	100
1	001	011	111	101

Cell labels show ABC. Note the column order 00, 01, 11, 10.

Four variables

CD \ AB	00	01	11	10
00	0000	0100	1100	1000
01	0001	0101	1101	1001
11	0011	0111	1111	1011
10	0010	0110	1110	1010

Cell labels show ABCD. Both the rows and the columns use Gray code order.

Grouping Rules

Groups contain only 1's; no zeros are allowed.
Groups are rectangles (no diagonals) of 1, 2, 4, 8 or 16 cells.
Make each group as large as possible.
Every 1 must be in at least one group.
Groups may overlap.
Groups may wrap around the edges of the map.
Use the fewest groups possible.

Reading a Group as a Term

Within a group, look at each variable. If it has the same value in every cell of the group, keep it (uncomplemented for 1, complemented for 0). If it changes, drop it. In a four-variable map a group of two cells eliminates one variable, a group of four eliminates two, and a group of eight eliminates three.

Examples

Example 1: Two variables

Minimise f(A, B) = AB + AB.

A \ B	0	1
0	1	0
1	1	0

The two 1's form a vertical pair in the B = 0 column. A changes within the group (0 then 1), so it is dropped; B is 0 throughout, so the term is B.

f = B

Example 2: Three variables

Minimise f(A, B, C) = AB + BC + AC.

First find which cells are 1. AB covers 100 and 101; BC covers 001 and 101; AC covers 001 and 011.

C \ AB	00	01	11	10
0	0	0	0	1
1	1	1	0	1

The two 1's in the AB = 10 column (cells 100 and 101) form a group. C changes; A = 1 and B = 0 are constant. Term: AB.
The two 1's in the C = 1 row under AB = 00 and 01 (cells 001 and 011) form a group. B changes; A = 0 and C = 1 are constant. Term: AC.
Every 1 is now covered, so the BC term from the original expression was redundant.

f = AB + AC

Example 3: Wrapping around

Minimise f(A, B, C) = ABC + ABC + AB + AC.

Cells that are 1: 000 (from the first and fourth terms), 110, 100 and 101 (from AB), and 010 (from AC).

C \ AB	00	01	11	10
0	1	1	1	1
1	0	0	0	1

The whole C = 0 row is 1's: a group of four. Only C is constant. Term: C.
The remaining 1 at 101 pairs with 100 directly above it. Term: AB.

f = C + AB

Practice Problems

Type complements with an apostrophe (A' for A), write AND as juxtaposition (AB) and OR as +. Terms may be given in any order.

Problem 1 Junior

Use a Karnaugh map to minimise the function whose truth table gives f(A, B) = 1 for (A, B) = (0, 0), (0, 1) and (1, 1), and f = 0 for (1, 0).

Solution

A \ B	0	1
0	1	1
1	0	1

The top row (A = 0) is all 1's. B changes, A is constant at 0. Term: A.
The right column (B = 1) is all 1's. A changes, B is constant at 1. Term: B.
The two groups overlap at cell 01, which is allowed, and together they cover all three 1's.

f = A + B (typed as A'+B)

Problem 2 Junior

Use a Karnaugh map to minimise f = ABC + ABC + ABC + ABC.

Solution

The four terms are the cells 000, 001, 100 and 101.

C \ AB	00	01	11	10
0	1	0	0	1
1	1	0	0	1

The 1's sit in the first and last columns. Because the map wraps around, those two columns are adjacent, so all four 1's form a single group of four.
Within the group A changes (0 and 1) and C changes (0 and 1), but B is 0 in every cell.

f = B (typed as B')

Problem 3 Intermediate

Use a Karnaugh map to minimise f = ABC + ABC + ABC + ABC + ABC.

Solution

The terms are the cells 001, 011, 111, 101 and 110.

C \ AB	00	01	11	10
0	0	0	1	0
1	1	1	1	1

The entire C = 1 row is 1's: a group of four in which only C is constant. Term: C.
The remaining 1 at 110 pairs with 111 directly below it. A = 1 and B = 1 are constant, C changes. Term: AB.

f = C + AB

Problem 4 Intermediate

The Karnaugh map below shows a three-variable function. Write its minimal sum-of-products expression.

C \ AB	00	01	11	10
0	1	0	0	1
1	1	1	0	0

Problem 5 Senior

Use a four-variable Karnaugh map to minimise f = ABD + ABCD + ABC + BCD + ABCD.

Solution

First expand each term into the ABCD cells it covers:

ABD: 1000, 1010
ABCD: 1100
ABC: 1110, 1111
BCD: 0101, 1101
ABCD: 0111

CD \ AB	01	11	10
00	0	1	1
01	1	1	0
11	1	1	0
10	0	1	1

The 2 × 2 block in the middle (columns 01 and 11, rows 01 and 11) is cells 0101, 0111, 1101, 1111. B = 1 and D = 1 throughout; A and C change. Term: BD.
The four corner-ish cells 1100, 1000, 1110, 1010 (columns 11 and 10, rows 00 and 10) form a group of four that wraps from the top row to the bottom row. A = 1 and D = 0 throughout; B and C change. Term: AD.
All eight 1's are covered by these two groups.

f = BD + AD (typed as BD+AD')