Definition
A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions by grouping adjacent cells containing 1s.
Key Point
K-Map Rules:
• Group 1s in powers of 2 (1, 2, 4, 8)
• Groups must be rectangular
• Make groups as large as possible
• Groups can wrap around edges
• Each 1 must be in at least one group
• Larger groups = simpler expression
• Group 1s in powers of 2 (1, 2, 4, 8)
• Groups must be rectangular
• Make groups as large as possible
• Groups can wrap around edges
• Each 1 must be in at least one group
• Larger groups = simpler expression
Worked Example
Worked Example: 2-Variable K-Map (clear grouping)
Step 1: Start from the truth table.
Step 2: Fill the K-map (rows = A, columns = B).
Step 3: Form largest valid groups (powers of 2).
Notes:
• Overlap is allowed (cell A=0,B=1 is used in both groups).
• Grouping larger pairs reduces expression size.
Final simplified expression:
Q = ¬A ∨ B
Step 1: Start from the truth table.
| A | B | Q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| A\B | 0 | 1 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| Group | Cells used | Constant term |
|---|---|---|
| G1 (top row pair) | (A=0,B=0) and (A=0,B=1) | ¬A |
| G2 (right column pair) | (A=0,B=1) and (A=1,B=1) | B |
• Overlap is allowed (cell A=0,B=1 is used in both groups).
• Grouping larger pairs reduces expression size.
Final simplified expression:
Q = ¬A ∨ B
Four-Variable Karnaugh Maps
Exam questions usually use a map with four inputs: AB across the top and CD down the side, giving 16 cells.
Key Point
Reading a four-variable map:
• The columns and rows are labelled 00, 01, 11, 10. This is not counting order: only one bit changes between neighbouring labels
• Groups contain 1, 2, 4, 8 or 16 cells. A group of 3 or 6 is never allowed
• The map wraps round: the left and right columns are neighbours, so are the top and bottom rows, and the four corners form a group of four
• Each group gives one term. Keep the inputs that stay the same in every cell of the group: write the input if it stays at 1, and NOT the input if it stays at 0. Leave out the inputs that change
• Join the terms from all the groups with OR
• The columns and rows are labelled 00, 01, 11, 10. This is not counting order: only one bit changes between neighbouring labels
• Groups contain 1, 2, 4, 8 or 16 cells. A group of 3 or 6 is never allowed
• The map wraps round: the left and right columns are neighbours, so are the top and bottom rows, and the four corners form a group of four
• Each group gives one term. Keep the inputs that stay the same in every cell of the group: write the input if it stays at 1, and NOT the input if it stays at 0. Leave out the inputs that change
• Join the terms from all the groups with OR
Worked Example
Worked Example: Simplifying with a Four-Variable Map
Two groups of four cover every 1:
The cell where AB is 10 and CD is 10 is in both groups, which is allowed.
Answer: Q = (¬B ∧ ¬D) ∨ (A ∧ C)
| CD \ AB | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 1 | 1 |
| 10 | 1 | 0 | 1 | 1 |
| Group | Cells | What stays the same | Term |
|---|---|---|---|
| The four corners | AB is 00 or 10, CD is 00 or 10 | B is 0 and D is 0 | ¬B ∧ ¬D |
| The block at the bottom right | AB is 11 or 10, CD is 11 or 10 | A is 1 and C is 1 | A ∧ C |
Answer: Q = (¬B ∧ ¬D) ∨ (A ∧ C)
Exam Tip
Completing a map from an expression:
• Take one term at a time and put a 1 in every cell that fits it. A term with two inputs, such as A ∧ ¬B, fills four cells of a four-variable map
• Draw the largest groups you can, then check that every 1 is inside at least one group
• Fewer, larger groups give a shorter expression
• Take one term at a time and put a 1 in every cell that fits it. A term with two inputs, such as A ∧ ¬B, fills four cells of a four-variable map
• Draw the largest groups you can, then check that every 1 is inside at least one group
• Fewer, larger groups give a shorter expression