Karnaugh Maps

A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions. It is an alternative to algebraic simplification that is often faster and less error-prone, especially for expressions with 3 or 4 variables. The OCR H446 specification requires you to understand and use K-maps.

---

Why Use Karnaugh Maps?

Method	Advantages	Disadvantages
Algebraic simplification	Works for any number of variables	Easy to make mistakes; no guaranteed path to simplest form
Karnaugh maps	Visual; systematic; guaranteed minimal SoP form	Practical only for up to 4 variables (5-6 possible but complex)

---

The Key Idea: Gray Code Ordering

K-maps arrange truth table rows so that adjacent cells differ by exactly one variable. This is called Gray code ordering. Because adjacent cells differ by one bit, groups of adjacent 1s correspond to terms where that variable can be eliminated.

---

2-Variable Karnaugh Map

For variables A and B, the K-map is a 2x2 grid:

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

Each cell holds the output value (0 or 1) for that combination of inputs.

Example: Simplify Q = (NOT A AND B) OR (A AND B)

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

The two 1s are in the B=1 column. They form a group of 2. Within this group, A changes (from 0 to 1) but B stays at 1. So A is eliminated, and the simplified expression is Q = B.

---

3-Variable Karnaugh Map

For variables A, B, C, the K-map is a 2x4 grid. The columns use Gray code ordering:

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

Note the column order: 00, 01, 11, 10 (NOT 00, 01, 10, 11). This ensures adjacent columns differ by only one bit.

Example: Simplify Q with the following 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

K-map:

	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 2x2 block in columns BC=01 and BC=11. Within this block, A changes, B changes, but C is always 1. The simplified expression is Q = C.

---

4-Variable Karnaugh Map

For variables A, B, C, D, the K-map is a 4x4 grid:

	CD=00	CD=01	CD=11	CD=10
AB=00
AB=01
AB=11
AB=10

Both rows and columns use Gray code ordering.

Key Term: Gray code ensures that moving one step in any direction (up, down, left, right) on the K-map changes exactly one variable.

---

Rules for Grouping