SLIDE 1 / 10
CSZone.co.uk
OCR H446 · Component 1 · 1.4.3

Simplification Using
Karnaugh Maps

OCR A Level Computer Science · cszone.co.uk
H446 SpecA Level
Learning Objectives

By the end of this topic you will be able to:

Construct a 2-variable and 3-variable Karnaugh Map (K-map)
Populate a K-map from a truth table
Group 1s in K-maps to identify simplified Boolean expressions
State the rules for valid K-map groupings
What is a K-map?

Karnaugh Maps (K-maps)

A Karnaugh Map is a grid-based visual method for simplifying Boolean expressions. It arranges all possible input combinations so that adjacent cells differ by exactly one variable (Grey code ordering). Grouping adjacent 1s eliminates variables and produces a minimal expression.
2-Variable K-map Layout
B=0
B=1
A=0
¬A·¬B
¬A·B
A=1
A·¬B
A·B
Grouping Rules
Groups must be:
• Powers of 2 in size: 1, 2, 4, 8
• As large as possible
• Adjacent (including wrap-around edges)
• Contain only 1s (no 0s)
• Each 1 can be in multiple groups
• Aim for fewest groups possible
3-Variable K-map

3-Variable K-map Layout

For 3 variables (A, B, C): 8 cells arranged in a 2×4 grid. The column headers follow Grey code: 00, 01, 11, 10 — NOT binary order. Adjacent columns differ by ONE bit. Wrap-around applies (leftmost and rightmost columns are also adjacent).
     BC=00  BC=01  BC=11  BC=10
A=0   ¬A¬B¬C  ¬A¬BC  ¬ABC   ¬AB¬C
A=1   A¬B¬C   A¬BC   ABC    AB¬C
Group size 4 (in a 2×4 map): a row of 4 cells, a column of 4, or 2×2 block. Each group of size 2 eliminates 1 variable; size 4 eliminates 2 variables; size 8 eliminates all → output = 1.
K-map Example

Worked Example

Truth table (A,B,C → Q): Q=1 for: 010, 011, 110, 111
     BC=00 BC=01 BC=11 BC=10
A=0:   0     1     1     0
A=1:   0     1     1     0
Group all four 1s (2×2 block in BC=01 and BC=11 columns). A takes both values → A is eliminated. B=1 throughout. C takes both values → C is eliminated. Simplified: Q = B
Verification: Q=1 whenever B=1, regardless of A or C. Check: 010(B=1)✓, 011(B=1)✓, 110(B=1)✓, 111(B=1)✓. All correct.
Exam Practice
OCR H446 Style · 4 marks
A 2-variable truth table gives Q=1 for inputs: AB=00, AB=10, AB=11. Draw the K-map, identify the groups, and write the simplified Boolean expression.
[4 marks]
1
K-map: cells 00→1, 01→0, 11→1, 10→1. (A rows: 0,0→A=0; 1,1→A=1; B columns: 0→B=0, 1→B=1)
1
Group 1: cells 00 and 10 (column B=0) — B=0, A varies → term: ¬B
1
Group 2: cells 10 and 11 (row A=1) — A=1, B varies → term: A
1
Simplified expression: Q = ¬B + A (OR the two terms from the two groups)
Common Mistakes

Don't Lose Marks

!
Using binary order for K-map columns — K-map columns must follow Grey code: 00, 01, 11, 10. NOT 00, 01, 10, 11. The Grey code ensures adjacent cells differ by only one bit, which is what makes K-map grouping valid.
!
Making groups that are not powers of 2 in size — only groups of 1, 2, 4, 8 (powers of 2) are valid. A group of 3 or 5 is illegal and produces a wrong result. Always check your group size is a power of 2.
!
Forgetting wrap-around adjacency — in a K-map, the top row and bottom row are adjacent (wrap vertically), and the leftmost and rightmost columns are adjacent (wrap horizontally). Failing to spot wrap-around groups leads to missed simplifications.
1.4.3c Complete
Well done! ✓
Simplification Using Karnaugh Maps
Return to lesson to continue