In Canonical Forms: SOP & POS we learned to write any function as a list of minterms. That list is correct but expensive: the majority function needs 12 literals in canonical form and only 6 when simplified. Simplifying with Boolean algebra works, but you have to spot the right steps, and it is easy to miss one. In 1953 Maurice Karnaugh, an engineer at Bell Labs, published a picture-based method that turns simplification into a visual puzzle. It is called the Karnaugh map, or K-map, and it is the standard hand method for functions of up to 4 (sometimes 5 or 6) variables.
The whole method rests on one algebraic fact, the combining law:
XY + XY′ = X(Y + Y′) = X
Two minterms that differ in exactly one variable merge into one shorter term, and that variable disappears. A K-map arranges the minterms so that every such pair sits side by side, so you can see the merges instead of hunting for them.
A Karnaugh map is a grid with one cell per minterm, whose rows and columns are labelled in Gray code order so that any two physically adjacent cells (including cells that wrap around opposite edges) differ in exactly one variable.
Every map, grouping and final answer in this chapter was checked against the original minterm list by enumerating all input rows in Python.
Building the Map
Why Gray Code Order?
If columns were labelled 00, 01, 10, 11 (normal binary), the neighbours 01 and 10 would differ in two bits, so they could not be merged. Gray code order 00, 01, 11, 10 changes one bit at each step, and the last label (10) also differs from the first (00) in one bit. So the map behaves as if its edges are glued together: left touches right and top touches bottom.
Two-Variable Map
B=0 B=1
A=0 | m0 | m1 |
A=1 | m2 | m3 |
Example 1. F(A, B) = Σm(1, 2, 3).
B=0 B=1
A=0 | 0 | 1 |
A=1 | 1 | 1 |
Group the bottom row (m2, m3): A = 1, B varies → A
Group the right column (m1, m3): B = 1, A varies → B
F = A + B
That is just the OR truth table, as expected. Notice that m3 was used in both groups. Overlap is allowed, because X + X = X.
Three-Variable Map
BC=00 BC=01 BC=11 BC=10
A=0 | m0 | m1 | m3 | m2 |
A=1 | m4 | m5 | m7 | m6 |
Notice the column order 00, 01, 11, 10: m3 comes before m2. The leftmost and rightmost columns are adjacent (m0 with m2, m4 with m6).
Example 2. F(A, B, C) = Σm(0, 2, 4, 5, 6).
BC=00 BC=01 BC=11 BC=10
A=0 | 1 | 0 | 0 | 1 |
A=1 | 1 | 1 | 0 | 1 |
Group 1 (size 4): columns 00 and 10, both rows → m0, m2, m4, m6
A varies, B varies, C = 0 throughout → C′
Group 2 (size 2): m4, m5
A = 1, B = 0, C varies → AB′
F = C′ + AB′
The group of four wraps around the left and right edges. Students who forget wrap-around would write C′ as two separate groups and get a longer answer.
Four-Variable Map
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 in Gray order, so rows 11 and 10 are swapped too. Memorise this numbering; you will fill hundreds of these maps. A handy check: the third column is always the odd numbers 3, 7, 15, 11, and the third row is 12, 13, 15, 14.
Grouping Rules
For SOP, group only 1s. (For POS, group only 0s; see below.)
Every group must contain 1, 2, 4, 8 or 16 cells, a power of 2.
Every group must be a rectangle (a square is fine). Wrap-around is allowed: left-right edges, top-bottom edges, and the four corners of a 4-variable map together.
Make each group as large as possible.
Use as few groups as possible to cover every 1. Groups may overlap.
Reading a Group
For each variable, look at its value across the whole group. If it is always 1, write the variable; if always 0, write its complement; if it changes, drop it. A group of 2k cells in an n-variable map gives a term with n − k literals.
Group size (4-variable map) | Variables eliminated | Literals in term | Example |
|---|---|---|---|
1 | 0 | 4 | A′BCD′ |
2 | 1 | 3 | A′BD′ |
4 | 2 | 2 | BD′ |
8 | 3 | 1 | C′ |
16 | 4 | 0 | F = 1 |
Example 3. F(A, B, C, D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14).
CD=00 CD=01 CD=11 CD=10
AB=00 | 1 | 1 | 0 | 1 |
AB=01 | 1 | 1 | 0 | 1 |
AB=11 | 1 | 1 | 0 | 1 |
AB=10 | 1 | 1 | 0 | 0 |
Group 1 (8 cells): the two left columns (CD = 00, 01) → C = 0 → C′
Group 2 (4 cells): rows 00, 01 × columns 00, 10 (wrap)
m0, m2, m4, m6: A = 0, D = 0 → A′D′
Group 3 (4 cells): rows 01, 11 × columns 00, 10 (wrap)
m4, m6, m12, m14: B = 1, D = 0 → BD′
F = C′ + A′D′ + BD′
Eleven minterms (44 literals) became 5 literals. Notice how groups 2 and 3 reuse cells from group 1; overlapping is what lets them grow to size 4.
Example 4: Corners and Centre. F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
CD=00 CD=01 CD=11 CD=10
AB=00 | 1 | 0 | 0 | 1 |
AB=01 | 0 | 1 | 1 | 0 |
AB=11 | 0 | 1 | 1 | 0 |
AB=10 | 1 | 0 | 0 | 1 |
Four corners (m0, m2, m8, m10): B = 0, D = 0 → B′D′
Centre square (m5, m7, m13, m15): B = 1, D = 1 → BD
F = B′D′ + BD ( = (B ⊕ D)′ )
The four corners are one group because the map wraps in both directions. This is the group students miss most often.
Implicants, Prime Implicants and Essential Prime Implicants
To make the "fewest, largest groups" rule precise, we need three definitions. They are asked directly in GATE.
An implicant is any product term that is 1 only where F is 1, i.e. any valid group of 1s. A prime implicant (PI) is an implicant that cannot be enlarged: no bigger valid group contains it. An essential prime implicant (EPI) is a prime implicant that covers at least one 1 that no other prime implicant covers.
A minimal SOP always consists of prime implicants only (a non-prime group could be enlarged, removing a literal). It must contain every essential PI. The only real decision is which non-essential PIs to add.
The Systematic Procedure
Mark all prime implicants (the largest possible groups around each 1).
Find the 1s that are covered by exactly one PI. Those PIs are essential: select them.
For the 1s still uncovered, choose the fewest (and largest) remaining PIs that cover them.
Example 5: Product of Sums
Before the procedure example, let us see how to get a POS answer. Group the 0s to find a minimal SOP for F′, then apply De Morgan.
F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10).
CD=00 CD=01 CD=11 CD=10
AB=00 | 1 | 1 | 0 | 1 |
AB=01 | 0 | 1 | 0 | 0 |
AB=11 | 0 | 0 | 0 | 0 |
AB=10 | 1 | 1 | 0 | 1 |
SOP (group the 1s):
corners m0, m2, m8, m10 → B′D′
m0, m1, m8, m9 → B′C′
m1, m5 → A′C′D
F = B′D′ + B′C′ + A′C′D (3 terms, 7 literals)
POS (group the 0s):
row AB = 11 (m12..m15) → AB
column CD = 11 (m3, m7, m15, m11) → CD
m4, m6, m12, m14 → BD′
F′ = AB + CD + BD′
F = (AB + CD + BD′)′ = (A′ + B′)(C′ + D′)(B′ + D) (3 terms, 6 literals)
Here the POS is cheaper by one literal. In general, try both and keep the smaller. A shortcut for reading POS groups directly: for a group of 0s, write each constant variable complemented if it is 1 and plain if it is 0, and OR them. The row AB = 11 gives (A′ + B′) directly.
Example 6: The Redundant Group Trap
F(A, B, C, D) = Σm(1, 5, 6, 7, 11, 12, 13, 15).
CD=00 CD=01 CD=11 CD=10
AB=00 | 0 | 1 | 0 | 0 |
AB=01 | 0 | 1 | 1 | 1 |
AB=11 | 1 | 1 | 1 | 0 |
AB=10 | 0 | 0 | 1 | 0 |
Prime implicants (5 in total):
BD = m5, m7, m13, m15 (the centre square, size 4)
A′C′D = m1, m5
A′BC = m6, m7
ABC′ = m12, m13
ACD = m11, m15
Which 1s have only one PI?
m1 → only A′C′D ⇒ A′C′D is essential
m6 → only A′BC ⇒ A′BC is essential
m12 → only ABC′ ⇒ ABC′ is essential
m11 → only ACD ⇒ ACD is essential
The four EPIs already cover m5, m7, m13, m15. BD adds nothing.
F = A′C′D + A′BC + ABC′ + ACD
The tempting mistake is to circle the big centre square first ("largest group first") and then add the four pairs, giving five terms. The centre square is a prime implicant, but it is not needed. Always pick essential PIs first, and only then look at the rest.
Example 7: A Cyclic Function (No Essential PIs)
F(A, B, C) = Σm(0, 1, 2, 5, 6, 7).
BC=00 BC=01 BC=11 BC=10
A=0 | 1 | 1 | 0 | 1 |
A=1 | 0 | 1 | 1 | 1 |
Prime implicants (6, all pairs):
A′B′ (m0,m1) A′C′ (m0,m2) B′C (m1,m5)
BC′ (m2,m6) AC (m5,m7) AB (m6,m7)
Every 1 is covered by exactly two PIs, so there is no essential PI.
The PIs form a ring: each overlaps the next. Pick any one, and the rest of the choice is forced. There are two equally good minimal answers:
F = A′B′ + BC′ + AC or F = A′C′ + B′C + AB
Both have 3 terms and 6 literals. This is why a minimal SOP is not always unique. Such functions are called cyclic; the Quine-McCluskey Method chapter shows a systematic way (Petrick's method) to find all minimal covers.
When a K-map Cannot Help: XOR
The 4-input parity function A ⊕ B ⊕ C ⊕ D is 1 on the 8 minterms with an odd number of 1s. On the map these form a checkerboard: no two 1s are adjacent, because neighbours differ in exactly one bit, which always changes the parity. Every PI is a single minterm, so the minimal SOP is the canonical one with 8 terms of 4 literals. That is why parity circuits are built from XOR gates instead (see Parity Generators & Checkers).
Five-Variable Maps
For five variables A, B, C, D, E, draw two 4-variable maps: one for A = 0 and one for A = 1. Within each map, normal adjacency applies. In addition, a cell in one map is adjacent to the cell in the same position in the other map (imagine the maps stacked on top of each other). Minterm number = 16A + 8B + 4C + 2D + E.
Example 8. F(A, B, C, D, E) = Σm(0, 2, 4, 6, 9, 13, 21, 23, 25, 29, 31).
A = 0 A = 1
DE=00 DE=01 DE=11 DE=10 DE=00 DE=01 DE=11 DE=10
BC=00 | 1 | 0 | 0 | 1 | (0-3) BC=00 | 0 | 0 | 0 | 0 | (16-19)
BC=01 | 1 | 0 | 0 | 1 | (4-7) BC=01 | 0 | 1 | 1 | 0 | (20-23)
BC=11 | 0 | 1 | 0 | 0 | (12-15) BC=11 | 0 | 1 | 1 | 0 | (28-31)
BC=10 | 0 | 1 | 0 | 0 | (8-11) BC=10 | 0 | 1 | 0 | 0 | (24-27)
Group 1: m0, m2, m4, m6 in the A = 0 map (columns DE=00 and DE=10, wrapping, top two rows)
A = 0, B = 0, E = 0 → A′B′E′
Group 2: m9, m13 (A = 0) and m25, m29 (A = 1), same positions
B = 1, D = 0, E = 1 → BD′E
Group 3: m21, m23, m29, m31 in the A = 1 map
A = 1, C = 1, E = 1 → ACE
F = A′B′E′ + BD′E + ACE
All three are essential. Beyond five or six variables, maps become impossible to read reliably, and we switch to the tabular Quine-McCluskey Method or to software.
Checking Your Answer in Code
A K-map answer is easy to check: evaluate it on every row and compare with the minterm list. This short program verifies Examples 2, 3 and 5, and shows what happens with a typical mistake (forgetting the corner group in Example 5):
from itertools import product
def check(name, f, minterms, n):
"""Compare a simplified expression with its minterm list on every row."""
for i, bits in enumerate(product([0, 1], repeat=n)):
if bool(f(*bits)) != (i in minterms):
print(f"{name}: WRONG at row {i}")
return
print(f"{name}: matches all {2**n} rows")
# Example 2: F = sum m(0,2,4,5,6) -> C' + AB'
check("C' + AB'", lambda a, b, c: (not c) or (a and not b),
{0, 2, 4, 5, 6}, 3)
# Example 3: F = sum m(0,1,2,4,5,6,8,9,12,13,14) -> C' + A'D' + BD'
check("C' + A'D' + BD'",
lambda a, b, c, d: (not c) or (not a and not d) or (b and not d),
{0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14}, 4)
# Example 5: POS (A' + B')(C' + D')(B' + D)
check("(A'+B')(C'+D')(B'+D)",
lambda a, b, c, d: (not a or not b) and (not c or not d) and (not b or d),
{0, 1, 2, 5, 8, 9, 10}, 4)
# A common wrong answer for Example 5: forgetting the corner group
check("B'C' + A'C'D (missing B'D')",
lambda a, b, c, d: (not b and not c) or (not a and not c and d),
{0, 1, 2, 5, 8, 9, 10}, 4)
Output:
C' + AB': matches all 8 rows
C' + A'D' + BD': matches all 16 rows
(A'+B')(C'+D')(B'+D): matches all 16 rows
B'C' + A'C'D (missing B'D'): WRONG at row 2
Row 2 (0010) is m2, which only the corner group B′D′ covers. The checker finds the exact cell you missed.
K-map Method at a Glance
Aspect | SOP from K-map | POS from K-map |
|---|---|---|
Cells grouped | 1s | 0s |
Variable constant at 1 in a group | Written plain (A) | Written complemented (A′) |
Variable constant at 0 in a group | Written complemented (A′) | Written plain (A) |
Terms combined with | OR | AND |
Circuit | AND-OR or NAND-NAND | OR-AND or NOR-NOR |
Common Mistakes
Labelling in binary order (00, 01, 10, 11) instead of Gray order (00, 01, 11, 10). The map then puts non-adjacent minterms side by side.
Groups of 3, 5 or 6. Only powers of two are valid. Three 1s in a row are covered by two overlapping pairs.
Diagonal groups. Diagonal cells differ in two variables and cannot be merged.
Forgetting wrap-around and corners. Left-right, top-bottom and all four corners are adjacent.
Choosing the biggest group first. Pick essential PIs first; a big group can still be redundant (Example 6).
Groups that are not as large as possible. A pair inside a possible quad leaves an extra literal in the answer.
Reading POS groups with SOP rules. For a group of 0s, a variable that is constantly 1 appears complemented.
Interview and GATE-Style Questions
Q1. Why are K-map rows and columns labelled in Gray code?
So that every pair of adjacent cells, including wrap-around neighbours, differs in exactly one variable. Then any adjacent pair can be merged by XY + XY′ = X.
Q2. In a 4-variable K-map, a group of 4 cells gives a term with how many literals?
A group of 2k cells eliminates k variables, so 4 = 22 leaves 4 − 2 = 2 literals.
Q3. For F(A, B, C, D) = Σm(1, 5, 6, 7, 11, 12, 13, 15), how many prime implicants and how many essential prime implicants are there?
5 prime implicants (BD, A′C′D, A′BC, ABC′, ACD) and 4 essential ones (all except BD). Minimal SOP: A′C′D + A′BC + ABC′ + ACD.
Q4. Minimise F(A, B, C) = Σm(3, 4, 6, 7).
Groups: m3, m7 → BC; m4, m6 (wrap) → AC′. F = BC + AC′. (AB covering m6, m7 is also a prime implicant, but it is redundant: it is the consensus of BC and AC′.)
Q5. Which cells are adjacent to m0 in a 4-variable K-map?
m1, m2, m4 and m8: each differs from 0000 in exactly one bit. On the map, m2 is reached by wrapping left-right and m8 by wrapping top-bottom.
Q6. Can a minimal SOP be non-unique? Give an example.
Yes. F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) has two minimal forms, A′B′ + BC′ + AC and A′C′ + B′C + AB, each with 3 terms and 6 literals.
Q7. Why does the K-map give no simplification for A ⊕ B ⊕ C?
Its 1s are m1, m2, m4, m7 (odd parity). Every pair of adjacent cells differs in one bit and therefore in parity, so no two 1s are adjacent. Each minterm is its own prime implicant.
Summary
A K-map places minterms in Gray code order so that adjacent cells differ in one variable; the map wraps around its edges.
Group 1s (SOP) or 0s (POS) in rectangles of 1, 2, 4, 8 or 16 cells, as large and as few as possible. A group of 2k cells removes k variables.
Prime implicant: a group that cannot be enlarged. Essential PI: the only PI covering some 1. The minimal SOP contains every EPI plus the fewest extra PIs needed.
Select essential PIs first; a large group can be redundant. Cyclic functions have no EPIs and several minimal answers.
Five-variable maps use two stacked 4-variable maps. For more variables, use the Quine-McCluskey Method.
Real problems often have input combinations that never occur. The next chapter, K-Maps with Don't-Care Conditions, shows how to use them for even simpler circuits.