# Karnaugh Maps

> Computer Science · CIE A-Level
> Source: https://www.owlsprep.com/study/cie-9618-u3-karnaugh-maps/

Karnaugh maps (K-maps) are a graphical method for simplifying Boolean expressions, used to design minimal combinational logic circuits. This guide covers 2-4 variable K-maps, prime implicants and handling don't care conditions.

**Prerequisites:** [Boolean Algebra and Logic Gates](https://www.owlsprep.com/study/cie-9618-u3-boolean-algebra/); [Sum-of-Products (SOP) Forms](https://www.owlsprep.com/study/cie-9618-u3-sop-pos-forms/)

## Learning objectives

- Construct 2-, 3- and 4-variable Karnaugh maps from truth tables or Boolean expressions
- Identify prime implicants and essential prime implicants for minimal simplification
- Simplify sum-of-products Boolean expressions using K-maps
- Handle don't care conditions to produce simpler expressions

## Introduction to Karnaugh Maps

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.

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

*Notation:* $2^n$ cells for $n$ input variables

*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 + AB' + AB$

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)

## Grouping Rules and Minimal SOP

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.

**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

> **tip**
>
> Always find the largest possible groups first, and start with essential prime implicants to avoid unnecessary terms in your final expression.

**Worked example:** Simplify the 2-variable K-map for $F(A,B) = A'B + AB' + AB$

1. Identify the largest possible groups: the two 1s in column $B=1$ ($A'B + AB$) can be grouped to eliminate $A$, leaving $B$
2. The two 1s in row $A=1$ ($AB' + AB$) 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$$

**Check your understanding**

Check your understanding of grouping rules

1. 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

   *Answer:* 4 adjacent 1s arranged in a 2×2 square

   *Why:* Groups must have sizes that are powers of 2, and adjacency is only horizontal/vertical (diagonals are not valid).

## 3 and 4 Variable K-maps

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.

> **info**
>
> Gray code ordering for 4 values is always 00, 01, 11, 10. This ensures adjacent cells differ by exactly one variable.

**Worked example:** Simplify $F(A,B,C) = \Sigma 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 ($m4, m6$) are adjacent, grouped to eliminate $B$, leaving $AC'$
4. Simplify the result to get the minimal expression:
5. $$F = A' + C'$$

## Don't Care Conditions

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.

> **tip**
>
> Use $X$s to extend your groups as much as possible, but you do not need to cover all $X$s in your final groups. Only 1s need to be covered.

**Worked example:** Simplify $F(A,B,C,D) = \Sigma 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$$

## Common pitfalls

- **Wrong:** Forming groups of 3 or 5 cells, or grouping diagonal 1s
  - Why it fails: Groups must have sizes that are powers of 2, and only horizontal/vertical adjacency is valid
  - Correct: Only form groups of 1, 2, 4, 8, etc. adjacent horizontally or vertically
- **Wrong:** Forgetting that K-map edges wrap around
  - Why it fails: You will miss larger valid groups that cross the edge of the map, leading to a non-minimal expression
  - Correct: Always check if groups can wrap around the top/bottom or left/right edges
- **Wrong:** Using binary ordering (00, 01, 10, 11) instead of Gray code
  - Why it fails: Adjacent cells will differ by two variables, so grouping will produce incorrect terms
  - Correct: Use standard Gray code order 00, 01, 11, 10 for all 4-value K-map axes
- **Wrong:** Treating don't care Xs as 1s that must be covered
  - Why it fails: This adds unnecessary terms to the final expression, making it non-minimal
  - Correct: Only use Xs to extend groups of 1s, you do not need to cover Xs

## 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 |

## 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.

- [Boolean Algebra](https://www.owlsprep.com/study/cie-9618-u3-boolean-algebra/)
- [Computer Architecture](https://www.owlsprep.com/study/cie-9618-u3-computer-architecture/)
- [Input and Output Devices](https://www.owlsprep.com/study/cie-9618-u3-input-and-output-devices/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u3-karnaugh-maps/