Simplifying with Boolean identities works, but it is slow and error-prone: you have to see which terms to combine and which law to apply next. In 1953 Maurice Karnaugh, a telecommunications engineer at Bell Labs working on telephone switching circuits, invented a graphical method that makes the combinations visible. The Karnaugh map (K-map) lays out a truth table so that terms which can be merged sit next to each other, and simplification becomes “draw the biggest rectangles you can” (Null & Lobur, Ch. 3 Special Section).
Minterms
A minterm is a product term that contains every one of the function’s variables exactly once, either complemented or not. Each minterm is 1 in exactly one row of the truth table.
For two variables x,y the minterms are x′y′, x′y, xy′, xy. For three variables:
row
x
y
z
minterm
0
0
0
0
x′y′z′
1
0
0
1
x′y′z
2
0
1
0
x′yz′
3
0
1
1
x′yz
4
1
0
0
xy′z′
5
1
0
1
xy′z
6
1
1
0
xyz′
7
1
1
1
xyz
Rule: a 0 in the row becomes a complemented variable, a 1 becomes an uncomplemented variable. Any function equals the OR of the minterms of the rows where it is 1 (its canonical sum-of-products).
Mini-example
F(x,y)=xy+xy′ has minterms xy′ (row 10) and xy (row 11), so F=Σm(2,3).
The Idea Behind the Map
Two minterms that differ in exactly one variable combine into one shorter term:
xy′z+xyz=xz(y′+y)=xz
The variable that changes (y) disappears. A K-map is arranged so that any two physically adjacent cells differ in exactly one variable. Then every pair of neighbouring 1s is a simplification waiting to happen, and a block of 2k neighbouring 1s eliminates k variables.
Two-Variable K-map
A K-map has one cell per minterm, i.e. one cell per truth-table row. For F(x,y): rows are x, columns are y.
x\y
0
1
0
x′y′
x′y
1
xy′
xy
Fill in each cell with the function’s output for that minterm.
Mini-example (lecture)
F(x,y)=xy is 1 only in row 11:
x\y
0
1
0
0
0
1
0
1
The Rules of K-map Simplification
Groups may contain only 1s, never 0s.
Groups are formed only at right angles (rows/columns); diagonal groups are not allowed.
The number of 1s in a group must be a power of 2 (1, 2, 4, 8, …), even if the group is a single 1.
Groups must be made as large as possible.
Groups may overlap, and may wrap around the sides of the map (the left edge is adjacent to the right edge, the top to the bottom).
Also: every 1 must be covered by at least one group, and use as few groups as possible.
Reading a group: look at which variables keep the same value over the whole group. Those variables form the product term (uncomplemented if constant 1, complemented if constant 0); variables that change inside the group are irrelevant and drop out. The simplified function is the OR of all the group terms.
Group size
Variables eliminated (3-var map)
Term has
1 cell
0
3 literals
2 cells
1
2 literals
4 cells
2
1 literal
8 cells (whole map)
3
F=1
Three-Variable K-map and Gray-Code Ordering
For F(x,y,z) the rows are x=0,1 and the columns are the four values of yz, written in the order
yz=00,01,11,10
This is not normal binary order (00,01,10,11). It is a Gray code: each step changes exactly one bit, including the wrap from 10 back to 00. That is what makes neighbouring columns combinable and what allows wrap-around.
x\yz
00
01
11
10
0
x′y′z′ (m0)
x′y′z (m1)
x′yz (m3)
x′yz′ (m2)
1
xy′z′ (m4)
xy′z (m5)
xyz (m7)
xyz′ (m6)
The first row holds all minterms with x=0; the second row those with x=1.
The first column holds the minterms with y=0 and z=0.
Columns 00 and 10 are adjacent through the wrap-around (they differ only in y).
The most common K-map mistake is labelling the columns 00,01,10,11. Then cells 01 and 10 sit side by side although they differ in two bits, and groups give wrong answers. Always use 00,01,11,10, and note that the cell order by minterm number is 0,1,3,2 / 4,5,7,6.
Mini-example
F=Σm(6,7): cells xyz′ and xyz are adjacent in the bottom row (columns 11 and 10). Over this pair x=1, y=1, and z changes. So F=xy.
Four-Variable K-map
For F(w,x,y,z) both rows (wx) and columns (yz) use the Gray order 00,01,11,10:
wx\yz
00
01
11
10
00
m0
m1
m3
m2
01
m4
m5
m7
m6
11
m12
m13
m15
m14
10
m8
m9
m11
m10
Wrap-around now works in both directions: the top row is adjacent to the bottom row, the left column to the right column, and therefore the four corners (m0, m2, m8, m10) form one group of 4.
Group size (4-var map)
Literals in the term
1
4
2
3
4
2
8
1
16
F=1
Mini-example
F=Σm(0,2,8,10): the four corners. Over these cells x=0 and z=0 while w and y both change, so F=x′z′.
Don’t-Care Conditions
Sometimes certain input combinations can never occur (e.g. the codes 1010 to 1111 in a BCD digit), or we do not care what the output is for them. These cells are marked d (or X). When grouping you may treat each d as a 1 if it helps make a bigger group, and as a 0 otherwise. Don’t-cares never need to be covered.
Mini-example
F(x,y,z)=Σm(1,3)+d(5,7). Treating d5 and d7 as 1s, column 01 and column 11 together are all 1/d, a group of 4 in which only z is constant (z=1). So F=z instead of x′z.
Procedure Summary
Draw the map with Gray-code labels (2, 3 or 4 variables).
Put a 1 in each cell whose minterm is in the function (and d for don’t-cares).
Find the largest power-of-2 rectangles of 1s, including wrap-around groups; start with 1s that can only be covered one way.
Keep adding groups until every 1 is covered, using as few groups as possible (overlap is fine).
Write one product term per group (constant variables only) and OR them.
Worked Examples
Exercise 1
(Lecture example) Use a K-map to simplify F(x,y)=x′y+xy′+xy (the canonical form of x+y).
Show solution ↓Hide solution ↑
Solution
Map (1s at m1 =x′y, m2 =xy′, m3 =xy):
m2, m3→x
m1, m3→y
F = x + y
Groups (both of size 2, overlapping at xy):
Group A (bottom row: xy′, xy): x=1 constant, y changes → term x.
Group B (right column: x′y, xy): y=1 constant, x changes → term y.
F=x+y
Check: x+y is 0 only at x=y=0, which is the only 0 in the map ✓. Note the overlap: cell xy is used by both groups, which is allowed and is exactly what lets both groups be as large as possible.
Exercise 2
(Lecture example) Simplify F(x,y,z)=x′y′z+x′yz+xy′z+xyz with a K-map.
Show solution ↓Hide solution ↑
Solution
The minterms are m1 (x′y′z), m3 (x′yz), m5 (xy′z), m7 (xyz).
m1, m3, m5, m7→z
F = z
Largest group: the four 1s in columns 01 and 11 form a 2×2 square (size 4=22).
Group A (m1, m3, m5, m7): over these cells x takes both values, y takes both values, but z=1 in every cell. So x and y are irrelevant and the term is z.
F(x,y,z)=z
Check with identities: x′z(y′+y)+xz(y′+y)=x′z+xz=z ✓. Four minterms (eight AND inputs, one 4-input OR) reduce to a wire.
Group A (top row, size 4): m0, m1, m3, m2. Here x=0 throughout; y and z both vary → term x′.
Group B (wrap-around, size 4): columns 00 and 10, both rows: m0, m2, m4, m6. Columns 00 and 10 are adjacent because the map wraps from the right edge to the left. Over this group x varies, y varies (0 in column 00, 1 in column 10), and z=0 throughout → term z′.
Every 1 is covered (m0 and m2 are in both groups).
F(x,y,z)=x′+z′
Six minterms reduce to two literals.
Check: x′+z′ is 0 only when x=1 and z=1, i.e. m5 and m7, which are exactly the two 0 cells ✓.
Exercise 4
Simplify F(x,y,z)=Σm(0,2,4,5,6) with a K-map, and compare with the algebraic simplification.
Show solution ↓Hide solution ↑
Solution
Place 1s using the cell order m0 m1 m3 m2 / m4 m5 m7 m6:
m0, m2, m4, m6→z'
m4, m5→xy'
F = z' + xy'
Group A (wrap-around, size 4): m0, m2, m4, m6 (outer columns 00 and 10). Constant: z=0 → z′.
Group B (size 2): m4, m5 (bottom row, columns 00 and 01). Constant: x=1, y=0; z varies → xy′.
m5 can only be grouped with m4 (its other neighbours m1 and m7 are 0), so group B cannot be larger.
F=z′+xy′
This matches the algebraic result z′+xy′ from the identities section, but here it needed no idempotent trick: the overlap of m4 in both groups is the graphical version of writing xy′z′=xy′z′+xy′z′.
Simplify the four-variable function F(w,x,y,z)=Σm(0,1,2,5,8,9,10).
Show solution ↓Hide solution ↑
Solution
Map (rows wx, columns yz, both in Gray order):
m0, m1, m8, m9→x'y'
m0, m2, m8, m10→x'z'
m1, m5→w'y'z
F = x'y' + x'z' + w'y'z
Group A (size 4, top/bottom wrap): m0, m1, m8, m9 (rows 00 and 10, columns 00 and 01). Constant: x=0, y=0 (w and z vary) → x′y′.
Group B (size 4, the four corners): m0, m2, m8, m10. Constant: x=0, z=0 → x′z′.
Group C (size 2): m1, m5 (column 01, rows 00 and 01). Constant: w=0, y=0, z=1; x varies → w′y′z. (m5’s neighbours m4, m7, m13 are 0, so this pair is the largest group containing m5.)
F=x′y′+x′z′+w′y′z
Check (each term’s cells): x′y′ → 0, 1, 8, 9; x′z′ → 0, 2, 8, 10; w′y′z → 1, 5. Union ={0,1,2,5,8,9,10} ✓, and no 0 cell is covered.
Exercise 6
Simplify F(w,x,y,z)=Σm(0,2,5,7,8,10,13,15).
Show solution ↓Hide solution ↑
Solution
m0, m2, m8, m10→x'z'
m5, m7, m13, m15→xz
F = x'z' + xz
Group A (the four corners): m0, m2, m8, m10. Constant x=0, z=0 → x′z′.
Group B (centre square): m5, m7, m13, m15 (rows 01 and 11, columns 01 and 11). Constant x=1, z=1 → xz.
F=x′z′+xz
F is 1 exactly when x and z are equal: this is XNOR, F=(x⊕z)′. Eight minterms of four variables reduce to a function of two variables; w and y are irrelevant.