Karnaugh maps

Building the map

Each cell is one row of the truth table. Rows and columns are labelled in Gray code order, 00, 01, 11, 10, so that neighbouring cells differ in exactly one variable. Put a 1 in each cell where the output is 1.

For 2 variables use a 2 x 2 grid; for 3 variables, 2 x 4 (A down the side, BC across); for 4 variables, 4 x 4 (AB down, CD across).

Grouping rules

• Group only 1s, in rectangles of 1, 2, 4, 8 or 16 cells (powers of 2).
• Make groups as large as possible and use as few groups as possible.
• Groups may overlap, and every 1 must be in at least one group.
• The map wraps around: the left and right edges are adjacent, and so are the top and bottom (so the four corners can form a group).
• For each group, keep only the variables that do not change across it: 0 gives ¬X, 1 gives X. A group of 2 removes one variable, 4 removes two, 8 removes three.
• OR the group terms together: a sum of products.

Worked 4-variable map

Minterms [4, 5, 6, 7, 13, 15] (A is the most significant bit).

Group 1: row AB = 01 (four cells) gives ¬A.B. Group 2: the square AB = 01, 11 with CD = 01, 11 gives B.D. Result: ¬A.B + B.D

Why use K-maps

Simpler expressions mean fewer logic gates: cheaper, smaller, faster, lower-power circuits, and simpler conditions in code. Always check that each grouped term really covers only 1s; a quick truth-table check catches mistakes.

Worked example

Simplify F = ¬A.¬B.C + ¬A.B.C + A.¬B.C + A.B.C with a 3-variable K-map.

1. The 1s are in every cell where C = 1: a group of four.
2. Across the group, A and B both change; only C stays at 1.

Answer: F = C

Check yourself

1. In what order are the column headings of a 4-variable K-map written?
   • 00, 01, 10, 11
   • 00, 10, 01, 11
   • 11, 10, 01, 00
   • 00, 01, 11, 10
   Show answer

   00, 01, 11, 10. Gray code: neighbours differ by one bit.

2. Which group size is NOT allowed in a K-map?
   • 2 cells
   • 6 cells
   • 4 cells
   • 8 cells
   Show answer

   6 cells. Groups must be powers of 2.

3. A 4-variable K-map has 1s only in its four corner cells (minterms 0, 2, 8, 10). What is the simplified expression?
   • B.D
   • ¬A.¬C
   • A.C
   • ¬B.¬D
   Show answer

   ¬B.¬D. Corners are adjacent by wrap-around; B = 0 and D = 0 throughout.

4. What is the simplest sum of products for minterms [4, 5, 6, 7, 13, 15] in a 4-variable K-map?
   • ¬A.B + B.D
   • B
   • ¬A.B.D + A.B.D
   • B.C + B.D
   Show answer

   ¬A.B + B.D. Group the AB = 01 row (¬A.B) and the B.D square.

5. How many product terms does the simplest sum of products for minterms [4, 5, 6, 7, 13, 15] have?
   Show answer

   2. Two groups: ¬A.B and B.D.

6. A 3-variable K-map has 1s for minterms 6 and 7 only (A = 1, B = 1). What is the simplified expression?
   • A.B
   • A.B.C
   • B.C
   • A
   Show answer

   A.B. C changes across the pair, leaving A.B.

7. A group of 4 cells in a 4-variable K-map gives a product term with how many variables?
   Show answer

   2. Each doubling removes one variable: 4 cells remove two of the four.

8. Why can 1s in the leftmost and rightmost columns of a K-map be grouped together?
   • Edges are always ignored
   • The outer columns are always 0
   • The map is read diagonally
   • The columns 00 and 10 differ by only one bit, so the map wraps around
   Show answer

   The columns 00 and 10 differ by only one bit, so the map wraps around. Gray code makes opposite edges adjacent.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.