Simplify logic by eye: draw the truth table so neighbours differ by one variable, then circle the groups.
The idea
In the last chapter, A'BC' + ABC' simplified to BC'. That worked because the two terms differ in exactly one variable, and x + x' = 1 removes it. Simplifying is mostly about finding such pairs, but in a truth table they can sit far apart.
A Karnaugh map (K-map) is a truth table redrawn so that terms differing in one variable are always next to each other. Then you can see the simplifications. It relies on the Gray code from Chapter 4: rows and columns count 00, 01, 11, 10, not 00, 01, 10, 11.
Grouping
F = b
The smallest K-map. Each small number in a corner is the row of the truth table. The two 1s touch, and within that group a changes while b stays 1, so a drops out and F = b.
Who counts as a neighbour
Two cells are neighbours if they differ in one variable, and that includes cells at opposite edges. The map wraps around, as if it were rolled into a tube, both left to right and top to bottom.
> Loading the animation…
NoteEach cell in an n-variable map has exactly n neighbours, one for each variable you could flip. On a 4-variable map, the four corners touch through the wrap-around, so they can form a single group.
The rules for grouping
Circle only 1s (for SOP).
A group is a rectangle, and it may wrap around the edges.
Its size must be a power of 2: 1, 2, 4, 8 or 16.
Make each group as large as possible, because a bigger group means a simpler term.
Use as few groups as possible, because each group is one more term.
Groups may overlap, and every 1 must be in at least one group.
To read a group, look at which variables stay the same across all its cells. Those stay in the term, inverted if they stay 0. Any variable that changes drops out. A group of 2ᵏ cells removes k variables.
Click a cell to change it (0, 1, then don't-care). The groups and the answer update.
Grouping
F = a'c' + ac
A 3-variable map you can edit. Press Play to see the groups form. Notice that a'c' wraps around the left and right edges.
TipTry making the whole map 1s, or a checkerboard. A checkerboard is XOR: no two 1s touch, so nothing simplifies at all.
Four variables
With four variables, the map is a 4 × 4 grid and groups of 8 become possible. This function has eleven 1s, yet the answer has only three terms.
Grouping
F = c' + a'd' + bd'
Press Play. The group of eight gives c' on its own, because only c stays constant across it.
Grouping
F = b'd' + bd
The four corners form one group, b'd'. The middle four form bd. Together, F is 1 exactly when b and d are equal: it's an XNOR of b and d, and a and c don't matter.Worked example: Reading a group
A group covers minterms 0, 2, 8 and 10 of a 4-variable map. What term is it?
Write them in binary: 0000, 0010, 1000, 1010.
a changes, so it drops out.
b is always 0, so b' stays.
c changes, so it drops out.
d is always 0, so d' stays.
Answer:b'd'
Practice
How many literals does a group of 4 cells on a 4-variable map leave in its term?
Don't-cares
Sometimes certain inputs can't happen, or their output doesn't matter. In BCD, the patterns 10 to 15 never occur. Mark these cells X, for don't-care. You can include an X in a group if it makes the group bigger, and ignore it if it doesn't.
Here's a circuit that takes a BCD digit and outputs 1 if it's 5 or more. Compare the answers with and without don't-cares.
Grouping
F = bd + bc + a
Using don't-cares: three short terms.
Grouping
F = a'bd + a'bc + ab'c'
The same function if patterns 10 to 15 must output 0: nine literals rather than five.
Watch outDon't-cares must really be impossible. If a stray 1101 does reach this circuit, its output is whatever the chosen groups happen to make it.
Grouping the zeros: POS
To get a product of sums, group the 0s instead. Each group gives a sum term, with the variables read inverted: a variable that stays 1 appears as x', and one that stays 0 appears as x.
Grouping
F = (c' + d')(a' + b + c')
The same function as the first 4-variable map above, as a product of sums. Here the groups circle the 0s. Which form is cheaper varies from function to function, so try both.
Prime and essential
Two terms make precise what "as large as possible" means, and you'll need them for exams and for the next chapter.
A prime implicant is a group that can't be made any bigger.
An essential prime implicant is a prime that's the only one covering some 1. It must appear in every minimal answer.
So the method is: find all the primes, take the essential ones, then pick as few of the others as you need to cover what's left.
Grouping
F = b'd' + a'c'd' + bd
This map has 4 primes: b'd', bd, a'c'd' and a'bc'. The first two are essential. They leave only cell 4 uncovered, and either of the other two can take it, so a minimal answer isn't always unique. Press Play and read why each group is chosen.
Grouping
F = a'b' + bc' + ac
A cyclic map: 6 primes and none are essential. Every 1 can be covered in two ways, so this one has two different minimal answers of three terms each.
Five variables, and exam countingGATE: fine to skip at first
A 5-variable map is drawn as two 4-variable maps, one for a = 0 and one for a = 1. Imagine one stacked on the other: a cell is also a neighbour of the same cell on the other sheet. A group that appears in the same place on both sheets loses a.
a=0
a=1
Grouping
F = c'e' + b'ce
Both groups repeat on the two sheets, so a drops out of both terms.
Practice · GATE-style
For F(a, b, c, d) = Σm(0, 2, 4, 5, 7, 8, 10, 13, 15), how many essential prime implicants are there?
Practice · GATE-style
What is the minimal SOP of F(a, b, c, d) = Σm(1, 3, 7, 11, 15)?
Practice · GATE-style
How many cells are in the largest possible group that isn't the whole map, on a 5-variable map?