The Karnaugh Map
A K-map is a truth table redrawn as a grid whose cells are arranged in Gray-code order, so that physically adjacent cells differ in exactly one variable. Adjacent 1s can therefore be combined, and each combination removes one variable.
The whole method in one line:
group the 1s in the largest possible power-of-two blocks, then
write the literals that stay CONSTANT inside each block.1. Map Layouts
2-variable map
B' B
+------+------+
A' | m0 | m1 |
+------+------+
A | m2 | m3 |
+------+------+3-variable map — note the column order 00, 01, 11, 10
BC
00 01 11 10
+------+------+------+------+
A=0 | m0 | m1 | m3 | m2 |
+------+------+------+------+
A=1 | m4 | m5 | m7 | m6 |
+------+------+------+------+4-variable map
CD
00 01 11 10
+------+------+------+------+
AB 00 | m0 | m1 | m3 | m2 |
+------+------+------+------+
01 | m4 | m5 | m7 | m6 |
+------+------+------+------+
11 | m12 | m13 | m15 | m14 |
+------+------+------+------+
10 | m8 | m9 | m11 | m10 |
+------+------+------+------+Why 00, 01, 11, 10 and not 00, 01, 10, 11? Because Gray code guarantees single-bit change between neighbours. m3 (011) and m2 (010) differ only in C — so they can be combined.
2. Adjacency Rules
| Rule | Effect |
|---|---|
| Groups must contain 2^k cells (1, 2, 4, 8, 16) | Nothing else combines cleanly |
| Groups must be rectangular — horizontal/vertical only, never diagonal | Diagonals differ in 2 variables |
| Groups wrap around left↔right and top↔bottom edges | The map is a torus |
| The four corners of a 4-variable map form one valid group | m0, m2, m8, m10 |
| Groups may overlap | Overlap is free; it often makes groups larger |
| Make each group as large as possible, and use as few groups as possible | Largest group = fewest literals |
| Every 1 must be covered by at least one group | Otherwise the function is wrong |
Group size -> literals eliminated -> literals remaining (n = 4)
1 cell 0 4
2 cells 1 3
4 cells 2 2
8 cells 3 1
16 cells 4 0 (F = 1)3. Worked Example — 3 Variables
F(A, B, C) = Σm(0, 1, 2, 4, 6)
BC
00 01 11 10
+------+------+------+------+
A=0 | 1 | 1 | 0 | 1 |
| (m0) | (m1) | (m3) | (m2) |
+------+------+------+------+
A=1 | 1 | 0 | 0 | 1 |
| (m4) | (m5) | (m7) | (m6) |
+------+------+------+------+Grouping:
Group 1 (4 cells): m0, m2, m4, m6 -> column 00 and column 10, both rows
A changes, B changes, C stays 0 -> C'
Group 2 (2 cells): m0, m1 -> row A=0, columns 00 and 01
A = 0 constant, B = 0 constant, C changes -> A'B'
F = C' + A'B'Verification: C' covers m0, m2, m4, m6 ✓; A'B' covers m0, m1 ✓. All five 1s covered, no 0 covered. ✓
4. Worked Example — 4 Variables
F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10)
CD
00 01 11 10
+------+------+------+------+
AB 00 | 1 | 1 | 0 | 1 |
| (0) | (1) | (3) | (2) |
+------+------+------+------+
01 | 0 | 1 | 0 | 0 |
| (4) | (5) | (7) | (6) |
+------+------+------+------+
11 | 0 | 0 | 0 | 0 |
| (12) | (13) | (15) | (14) |
+------+------+------+------+
10 | 1 | 1 | 0 | 1 |
| (8) | (9) | (11) | (10) |
+------+------+------+------+Grouping:
Group 1 (4 cells): m0, m2, m8, m10 -> the FOUR CORNERS
A changes, B = 0, C changes, D = 0 -> B'D'
Group 2 (4 cells): m0, m1, m8, m9 -> columns 00, 01 in rows AB=00 and AB=10
A changes, B = 0, C = 0, D changes -> B'C'
Group 3 (2 cells): m1, m5 -> rows AB=00 and AB=01, column CD=01
A = 0, B changes, C = 0, D = 1 -> A'C'D
F = B'D' + B'C' + A'C'DCheck every 1 is covered: m0 (G1,G2), m1 (G2,G3), m2 (G1), m5 (G3), m8 (G1,G2), m9 (G2), m10 (G1). ✓
5. Prime Implicants and Essential Prime Implicants
| Term | Definition |
|---|---|
| Implicant | Any valid group (any product term that implies F) |
| Prime implicant (PI) | A group that cannot be made larger — not contained in any bigger group |
| Essential prime implicant (EPI) | A prime implicant that covers at least one 1 that no other PI covers |
| Redundant PI | A PI whose every 1 is covered by other selected PIs |
Selection procedure:
1. Circle ALL prime implicants.
2. Select every ESSENTIAL prime implicant (each has a uniquely covered 1).
3. Cover any remaining 1s with the fewest additional PIs.Example. F = Σm(0, 1, 2, 5, 8, 9, 10) above:
m2 and m10 are covered ONLY by B'D' -> B'D' is ESSENTIAL
m5 is covered ONLY by A'C'D -> A'C'D is ESSENTIAL
m9 is covered by B'C' and by B'D'... m9 = 1001: B'D'? D=1 so no.
-> B'C' is the only cover of m9 -> B'C' is ESSENTIAL
All three are essential; the answer is unique.6. Worked Example with a Non-Unique Answer
F(A, B, C, D) = Σm(0, 1, 5, 7, 8, 10, 14, 15)
CD
00 01 11 10
+------+------+------+------+
AB 00 | 1 | 1 | 0 | 0 |
01 | 0 | 1 | 1 | 0 |
11 | 0 | 0 | 1 | 1 |
10 | 1 | 0 | 0 | 1 |
+------+------+------+------+
Groups:
m0, m1 -> A'B'C'
m1, m5 -> A'C'D
m5, m7 -> A'BD
m7, m15 -> BCD
m14, m15 -> ABC
m10, m14 -> ACD'
m0, m8 -> B'C'D'
m8, m10 -> AB'D'
A minimum cover: F = A'B'C' + A'BD + BCD + ACD' + AB'D'
(5 terms x 3 literals)When several minimum covers of the same cost exist, any of them is a correct answer — say so explicitly in the exam.
7. 5-Variable K-Map (bonus)
Drawn as two 4-variable maps side by side, one for A = 0 and one for A = 1. Cells in the same position on the two maps are adjacent.
A = 0 A = 1
CDE CDE
00 01 11 10 00 01 11 10
BC 00 m0 m1 m3 m2 BC 00 m16 m17 m19 m18
01 m4 m5 m7 m6 01 m20 m21 m23 m22
11 m12 m13 m15 m14 11 m28 m29 m31 m30
10 m8 m9 m11 m10 10 m24 m25 m27 m26
A group spanning BOTH maps eliminates the variable A.8. Common K-Map Mistakes
| Mistake | Consequence |
|---|---|
| Forgetting the wrap-around / corner adjacency | Answer is correct but not minimal |
| Using a group of 3 or 6 cells | Invalid — groups must be powers of 2 |
| Grouping diagonally | Two variables change — invalid |
| Reading the column order as 00, 01, 10, 11 | Wrong adjacency, wrong answer |
| Writing the changing variable instead of the constant one | Inverted result |
| Stopping before covering every 1 | Incomplete function |
Reading rule to memorise: inside a group, a variable that is 0 in every cell is written complemented; 1 in every cell is written plain; changing is dropped.
The next lesson applies exactly the same map to the 0s to obtain the minimum POS form.