Karnaugh Maps

A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions, devised by the physicist Maurice Karnaugh in 1953. It takes the same job the previous lesson did by algebra — reducing an expression to its cheapest equivalent — and turns it into a visual pattern-matching exercise on a grid. Where algebraic simplification relies on cleverness and offers no promise of reaching the minimum, a K-map drawn and grouped correctly guarantees the minimal sum-of-products form for up to four or five variables. That guarantee, and the speed with which a trained eye reads a completed map, is exactly why the OCR H446 specification names the K-map as a required technique alongside the algebraic laws.

The core insight is geometric. A truth table lists input combinations in plain binary order, so two rows that differ in only one variable can be far apart on the page. A K-map re-lays the same information on a grid arranged so that physically adjacent cells differ in exactly one variable. Adjacency on the grid therefore means "these two minterms are identical except for one variable" — and that is precisely the condition under which the complement law $X + \overline{X} = 1$X+X=1 lets you delete a variable. Grouping adjacent 1s is thus the same complement-pair elimination you did by hand last lesson, performed by eye. Everything in this lesson follows from that single correspondence between grid adjacency and one-variable difference.

This lesson is deliberately worked-example heavy, with fully worked 2-, 3- and 4-variable simplifications and a treatment of don't-care conditions, because reading K-maps is a skill drilled by repetition, not a fact recalled. Every map is rendered as a markdown table so the grid is unambiguous.

---

Spec Mapping

This lesson covers the Karnaugh-map strand of OCR H446 section 1.4.3 (Boolean algebra):

• Constructing a 2-, 3- or 4-variable Karnaugh map from a truth table or list of minterms, using Gray-code row and column ordering.
• Grouping adjacent 1s into the largest legal groups (powers of two), exploiting wrap-around adjacency, and reading off the minimal sum-of-products expression.
• Using don't-care conditions to enlarge groups and simplify further.
• Relating the K-map result to the algebraic simplification of the previous lesson and to the gate cost of the resulting circuit.

It builds directly on truth tables and on algebraic simplification, and feeds the circuit-design lesson, where a K-map is the standard first step in minimising a design before it is drawn as gates.

---

Why Use Karnaugh Maps?

Method	Strengths	Limitations
Algebraic simplification	Works for any number of variables; transparent reasoning	Easy to err; no guaranteed route to the minimum; needs pattern-spotting flair
Karnaugh map	Visual; systematic; guarantees the minimal SoP form	Practical only to about 4 variables (5–6 possible but unwieldy); a manual technique

The two methods are complementary rather than rival. Algebra scales to any size and shows your reasoning step by step; the K-map is faster and certain but runs out of steam past four variables because a human cannot see adjacency in five or six dimensions. For the 2-, 3- and 4-variable problems that dominate exams, the K-map is usually the better tool — and beyond six variables, neither is used in practice: computer algorithms such as Quine–McCluskey take over.

---

The Key Idea: Gray Code Ordering

A K-map labels its rows and columns in Gray code — the ordering $00, 01, 11, 10$00,01,11,10 rather than the natural binary $00, 01, 10, 11$00,01,10,11. The defining property of Gray code is that consecutive codes differ in exactly one bit: from $01$01 to $11$11 only the left bit flips; from $11$11 to $10$10 only the right bit flips. Laying the map out this way means a single horizontal or vertical step always changes exactly one variable, so neighbouring cells are guaranteed to be one-variable-apart minterms.

This is the whole engine of the method. When a block of adjacent 1s is grouped, the variable(s) that change across the block can be eliminated, because for every value of those variables the output is the same — exactly the situation $X + \overline{X} = 1$X+X=1 describes. The variable(s) that stay constant across the block survive into the product term. Crucially, the natural binary order would break this: $01$01 to $10$10 flips both bits, so adjacent cells would no longer be one variable apart and grouping would be meaningless. Gray code is not a cosmetic choice; it is what makes geometric adjacency equal logical adjacency.

Key Term: Gray code is a binary ordering in which successive values differ in exactly one bit. On a K-map it ensures that moving one step up, down, left or right changes exactly one variable.

---

2-Variable Karnaugh Map

For two variables A and B the map is a $2 \times 2$2×2 grid. Each cell holds the output for one input combination:

	B=0	B=1
A=0	minterm 00	minterm 01
A=1	minterm 10	minterm 11

Worked example. Simplify $Q = \overline{A} \cdot B + A \cdot B$Q=A⋅B+A⋅B. The two product terms are minterms 01 and 11, so place a 1 in each:

	B=0	B=1
A=0	0	1
A=1	0	1

The two 1s sit one above the other in the B=1 column, forming a legal group of two. Reading the group: B is constant at 1 throughout, while A changes from 0 to 1. The changing variable A is eliminated; the constant B survives. Therefore:

$Q = B$Q=B

Check against algebra: $\overline{A}\cdot B + A\cdot B = (\overline{A} + A)\cdot B = 1 \cdot B = B$A⋅B+A⋅B=(A+A)⋅B=1⋅B=B — the complement law and identity, exactly the elimination the grouping performed by eye.

---

3-Variable Karnaugh Map

For three variables the map is a $2 \times 4$2×4 grid. One variable (A) labels the two rows; the other two (B, C) label the four columns in Gray-code order $00, 01, 11, 10$00,01,11,10:

	BC=00	BC=01	BC=11	BC=10
A=0	m0	m1	m3	m2
A=1	m4	m5	m7	m6

The minterm numbers (m0–m7) show where each row of a truth table lands. Note the column order is $00, 01, 11, 10$00,01,11,10 — not $00, 01, 10, 11$00,01,10,11 — so that adjacent columns differ in one bit. Because of this, the BC=00 and BC=10 columns are also adjacent (they differ only in B), which is the wrap-around adjacency discussed below.

Worked example. Simplify the function given by this truth table:

A	B	C	Q
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Transcribe each 1 onto the grid (the output is 1 whenever C=1):

	BC=00	BC=01	BC=11	BC=10
A=0	0	1	1	0
A=1	0	1	1	0

The four 1s form a $2 \times 2$2×2 block spanning the BC=01 and BC=11 columns across both rows. Read the block: A changes (rows 0 and 1 both included), B changes (column groups 01 and 11 differ in B), but C is constant at 1 throughout. Two variables eliminated, one survives:

$Q = C$Q=C

A four-cell group eliminates two variables, leaving a single literal — the largest legal group always gives the simplest term, which is why the rules insist you group as big as you can.

---

4-Variable Karnaugh Map

For four variables the map is a $4 \times 4$4×4 grid. Variables A and B label the rows in Gray code, C and D label the columns in Gray code:

	CD=00	CD=01	CD=11	CD=10
AB=00	m0	m1	m3	m2
AB=01	m4	m5	m7	m6
AB=11	m12	m13	m15	m14
AB=10	m8	m9	m11	m10

Both rows and columns are Gray-coded, so wrap-around applies in both directions: the top row (AB=00) is adjacent to the bottom row (AB=10), and the left column (CD=00) is adjacent to the right column (CD=10). It helps to picture the grid wrapped onto a torus (a doughnut), where the top edge meets the bottom and the left edge meets the right. Memorising the minterm-number layout above makes transcribing a list of minterms onto the map fast and reliable.

---

Rules for Grouping

1. Group only the 1s (for sum-of-products simplification — grouping 0s instead yields product-of-sums).
2. Groups must be rectangular (squares count) and contain a power-of-two number of cells: 1, 2, 4, 8 or 16.
3. Make every group as large as legally possible — a bigger group eliminates more variables and gives a shorter term.
4. Every 1 must be covered by at least one group.
5. Groups may overlap — a single 1 can belong to several groups if that lets each group grow larger.
6. The map wraps around: leftmost and rightmost columns are adjacent, and top and bottom rows are adjacent.
7. Use the fewest groups that cover all the 1s — each group becomes one product term, so fewer groups means a shorter expression.

Rules 3 and 7 work together and capture the goal precisely: cover every 1 using the smallest number of the largest possible groups. A group of size $2^k$2k eliminates $k$k variables.

---

What Each Group Gives You

Group size	Variables eliminated	Variables remaining (4-var map)
1 cell	0	4 (a full minterm)
2 cells	1	3
4 cells	2	2
8 cells	3	1
16 cells	4	0 (output always 1)

The pattern is exact: a group of $2^k$2k cells eliminates $k$k variables. This is why doubling a group's size always shortens its term by one literal, and why grouping as large as possible is the route to the minimum.

---

Worked Example: 4-Variable K-Map

Simplify the function that is 1 for minterms 0, 1, 2, 3, 5, 7 over variables A (MSB), B, C, D.

Locate each minterm using the layout grid above, then place the 1s:

• m0 = 0000 → AB=00, CD=00
• m1 = 0001 → AB=00, CD=01
• m2 = 0010 → AB=00, CD=10
• m3 = 0011 → AB=00, CD=11
• m5 = 0101 → AB=01, CD=01
• m7 = 0111 → AB=01, CD=11

	CD=00	CD=01	CD=11	CD=10
AB=00	1	1	1	1
AB=01	0	1	1	0
AB=11	0	0	0	0
AB=10	0	0	0	0

Group 1 — the whole top row (4 cells: m0, m1, m3, m2). Across this row, A=0 and B=0 are constant, while C and D both change. Two variables eliminated:

$\text{Group 1} = \overline{A} \cdot \overline{B}$Group 1=A⋅B

Group 2 — the four cells in columns CD=01 and CD=11, rows AB=00 and AB=01 (m1, m3, m5, m7). Across this block, A=0 is constant and D=1 is constant (both these columns have D=1), while B changes (rows 00 and 01) and C changes (columns 01 and 11). Two variables eliminated:

$\text{Group 2} = \overline{A} \cdot D$Group 2=A⋅D

Every 1 is now covered (m1 and m3 are shared between the two groups — overlap is allowed and here lets both groups stay at size four). OR the two terms:

$Q = \overline{A}\cdot\overline{B} + \overline{A}\cdot D$Q=A⋅B+A⋅D

Tidy by algebra — factor $\overline{A}$A:

$Q = \overline{A}\cdot(\overline{B} + D)$Q=A⋅(B+D)

The original function had six minterms (a six-term SoP); the map reduces it to two small products, and factoring gives a two-gate-deep circuit. K-map and algebra agree, and the map guaranteed this was minimal — algebra alone could not have promised it.

---

Worked Example: Overlapping Groups (3-Variable)

Overlap is not just permitted — it is often necessary to keep every group as large as possible. Simplify the three-variable function that is 1 for minterms 0, 1, 2, 5, 7:

	BC=00	BC=01	BC=11	BC=10
A=0	1	1	0	1
A=1	0	1	1	0

Three legal groups of two cover everything, and the central 1s are shared:

• Group 1 — m0, m1 (A=0, columns BC=00 and BC=01): A=0 and B=0 are constant; C changes. Term: $\overline{A}\cdot\overline{B}$A⋅B.
• Group 2 — m0, m2 (A=0, columns BC=00 and BC=10, using wrap-around): A=0 and C=0 are constant; B changes. Term: $\overline{A}\cdot\overline{C}$A⋅C.
• Group 3 — m5, m7 (A=1, columns BC=01 and BC=11): A=1 and C=1 are constant; B changes. Term: $A\cdot C$A⋅C.

Notice m0 belongs to two groups and m1 is reused — without overlap, m0 and m2 could not have paired, and the answer would carry an extra isolated minterm. The minimal SoP is:

$Q = \overline{A}\cdot\overline{B} + \overline{A}\cdot\overline{C} + A\cdot C$Q=A⋅B+A⋅C+A⋅C

The lesson: when a 1 sits at the junction of two possible groups, let it join both. A cell costs nothing extra by being reused, but a group left small costs a literal.

---

Why Adjacency Equals the Complement Law

It is worth pausing on why grouping works, because it makes the rules feel inevitable rather than arbitrary. Take Group 1 above, $\overline{A}\cdot\overline{B}$A⋅B. The two cells it covers are the full minterms $\overline{A}\cdot\overline{B}\cdot\overline{C}$A⋅B⋅C (m0) and $\overline{A}\cdot\overline{B}\cdot C$A⋅B⋅C (m1). Their sum is:

$\overline{A}\cdot\overline{B}\cdot\overline{C} + \overline{A}\cdot\overline{B}\cdot C = \overline{A}\cdot\overline{B}\cdot(\overline{C} + C) = \overline{A}\cdot\overline{B}\cdot 1 = \overline{A}\cdot\overline{B}$A⋅B⋅C+A⋅B⋅C=A⋅B⋅(C+C)=A⋅B⋅1=A⋅B