Karnaugh Maps

Computer Science· Unit 3: Hardware, Topic 3: Karnaugh Maps· 25 min read

1. Introduction to Karnaugh Maps★★☆☆☆⏱ 5 min

A Karnaugh map is a graphical reorganisation of a truth table, where each cell corresponds to one combination of input variables. Adjacent cells differ by exactly one input variable, which allows groups of 1s to be combined to eliminate redundant variables.

📘 Definition

Karnaugh Map

$2^{n}$ cells for $n$ input variables

A grid-based graphical tool for simplifying Boolean expressions that leverages adjacency of cells differing by one variable to eliminate redundant terms

Example:

A 2-variable K-map has 4 cells arranged in a 2×2 grid

📐 Worked Example

Draw a 2-variable K-map for $F (A, B) = A^{'} B + A B^{'} + A B$

1
List all input combinations and mark where $F = 1$ :
2
$F = 1 \text{ for } A'B, AB', AB \text{, } F = 0 \text{ for } A'B'$
3
Arrange cells in a 2×2 grid with Gray code ordering (0, 1) for rows (A) and columns (B)
4
The completed K-map has 1s in cells (0,1), (1,0), (1,1) and 0 at (0,0)

2. Grouping Rules and Minimal SOP★★★☆☆⏱ 10 min

The core of K-map simplification is grouping adjacent 1s into rectangles with side lengths that are powers of 2 (1, 2, 4, etc.). Larger groups produce simpler final expressions, as they eliminate more variables.

📘 Definition

Essential Prime Implicant

A prime implicant (maximal valid group) that covers at least one 1 not covered by any other prime implicant, so it must be included in the final expression

📐 Worked Example

Simplify the 2-variable K-map for $F (A, B) = A^{'} B + A B^{'} + A B$

1
Identify the largest possible groups: the two 1s in column $B = 1$ ( $A^{'} B + A B$ ) can be grouped to eliminate $A$ , leaving $B$
2
The two 1s in row $A = 1$ ( $A B^{'} + A B$ ) can be grouped to eliminate $B$ , leaving $A$
3
All 1s are covered by these two groups, so the minimal sum-of-products expression is:
4
$F = A + B$

✓ Quick check

Check your understanding of grouping rules

Which of the following groups is valid in a K-map?
- 3 adjacent 1s in a row
- 4 adjacent 1s arranged in a 2×2 square
- 2 adjacent 1s diagonal to each other
Reveal answer
1 —
Groups must have sizes that are powers of 2, and adjacency is only horizontal/vertical (diagonals are not valid).

3. 3 and 4 Variable K-maps★★★☆☆⏱ 7 min

For 3 variables, K-maps are 2×4 grids, and for 4 variables they are 4×4 grids. A key rule that is often missed: the top/bottom and left/right edges of the K-map wrap around, so the first and last rows/columns are adjacent.

📐 Worked Example

Simplify $F (A, B, C) = Σ m (0, 1, 2, 3, 4, 6)$

1
Draw a 2×4 K-map, mark 1s for all listed minterms
2
The largest possible group is all 4 1s in row $A = 0$ , which eliminates $A$ and $B$ , leaving $C^{'}$
3
The remaining 1s ( $m 4, m 6$ ) are adjacent, grouped to eliminate $B$ , leaving $A C^{'}$
4
Simplify the result to get the minimal expression:
5
$F = A' + C'$

4. Don't Care Conditions★★★★☆⏱ 3 min

Don't care conditions are input combinations that will never occur in practice, so their output can be set to 0 or 1 to help produce a simpler final expression. They are marked as $X$ in K-maps.

📐 Worked Example

Simplify $F (A, B, C, D) = Σ m (1, 3, 5, 7, 9) + d (10, 11, 12, 13, 14, 15)$

1
Mark all minterms as 1 and don't cares as $X$ on the 4×4 K-map
2
All 1s are in the $D = 1$ column. Use the 6 don't cares to form an 8-cell group covering all $D = 1$ cells, eliminating $A, B, C$
3
All 1s are covered by this single group, so the minimal expression is:
4
$F = D$

5. Common Pitfalls

Wrong move:

Forming groups of 3 or 5 cells, or grouping diagonal 1s

Why:

Groups must have sizes that are powers of 2, and only horizontal/vertical adjacency is valid

Correct move:

Only form groups of 1, 2, 4, 8, etc. adjacent horizontally or vertically

Wrong move:

Forgetting that K-map edges wrap around

Why:

You will miss larger valid groups that cross the edge of the map, leading to a non-minimal expression

Correct move:

Always check if groups can wrap around the top/bottom or left/right edges

Wrong move:

Using binary ordering (00, 01, 10, 11) instead of Gray code

Why:

Adjacent cells will differ by two variables, so grouping will produce incorrect terms

Correct move:

Use standard Gray code order 00, 01, 11, 10 for all 4-value K-map axes

Wrong move:

Treating don't care Xs as 1s that must be covered

Why:

This adds unnecessary terms to the final expression, making it non-minimal

Correct move:

Only use Xs to extend groups of 1s, you do not need to cover Xs

6. Quick Reference Cheatsheet

Rule	Summary
Group size	Must be powers of 2 (1, 2, 4, 8...)
Adjacency	Horizontal/vertical only, edges wrap around, no diagonals
Gray code order	4-value sequence: 00 → 01 → 11 → 10
Essential prime implicants	Must be included in final expression
Don't care Xs	Use for grouping, no need to cover
Minimal SOP	Sum of essentials + extra terms to cover all 1s

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 12
Simplify 4-variable Boolean expression
2023 · 11
Use K-map with don't care terms
2021 · 13
Derive minimal SOP from K-map

Going deeper

syllabusCIE 9618 A-Level Computer Science Syllabus

What's Next

Karnaugh maps are the primary method for hand-simplification of Boolean expressions up to 4 variables, which is a very common exam question for CIE A-Level Computer Science. For more than 4 variables, automated methods like Quine-McCluskey are used, but K-maps are sufficient for all exam-level questions and build core intuition for logic design of combinational circuits. Mastery of K-map simplification is essential for advanced topics like sequential logic design, where simplified next-state and output expressions are required to build efficient, low-cost digital logic circuits.