Noesis
3.1.11 · D5Boolean Algebra & Logic Gates

Question bank — Karnaugh map simplification (2,3,4 variables)

1,701 words8 min read↑ Back to topic

Before we start, one reminder of the single law that everything below tests:

The three worked traps below each ship with a coloured map so you can see which cells are circled and which variable survives.

True or false — justify

A group of 4 cells always eliminates exactly 2 variables in any size map.
True. Group size eliminates variables regardless of ; so variables vary and vanish, leaving literals.
A K-map with all cells = 1 simplifies to the constant .
True. The whole map is one legal group of cells, , so literals survive — every variable varies and drops, leaving just .
Two cells that sit side by side on paper are always K-map adjacent.
False. Adjacency means differing in exactly one bit, which only holds because of Gray-code labelling; columns 01 and 10 are printed adjacent but differ in two bits, so they are not groupable.
The four corner cells of a 4-variable map can form a single legal group.
True. Under wrap-around the map is a torus, so all four corners are mutually adjacent and form a group of 4, eliminating 2 variables.
A larger group can never produce a longer product term than a smaller one.
True. Literals , so more cells (bigger ) means strictly fewer literals. This is exactly why we always grab the largest legal group first.
Overlapping groups double-count some 1s, which is an error.
False. Overlap is legal and encouraged — a 1 may belong to many groups. Overlap only adds terms already implied by the algebra; it never breaks correctness, and it often lets a group grow larger. See Logic Gate Minimisation.
You can safely leave a lone isolated 1 uncovered if it is inconvenient.
False. Every 1 in the SOP must be covered at least once, or the expression fails to output 1 for that minterm — it would contradict the truth table.
Grouping the 0s instead of the 1s gives a wrong answer.
False. Grouping 0s gives the minimal Product-of-Sums form, which is equally valid — it just describes when . See Sum of Products and Product of Sums.
A don't-care must always be included in some group.
False. A don't-care is used only if it enlarges a group; otherwise it is ignored (treated as 0). It never forces an extra term. See Don't-care Conditions.

Spot the error

"I grouped three adjacent 1s into one term to save a group." — what's wrong?
3 is not a power of two, so the combining theorem cannot collapse it to one product term. Split into a pair plus an overlapping pair, each of size 2. (See the size-2 vs size-3 sketch in the figure above.)
"Columns are labelled 00, 01, 10, 11 so my neighbours are correct." — error?
That is binary order, not Gray code. 01→10 changes two bits, breaking adjacency. Use 00, 01, 11, 10 so every neighbour differs by one bit.
"My group is an L-shape covering 4 cells, so it eliminates 2 variables." — error?
Groups must be rectangles/squares. An L-shape does not correspond to holding some variables constant while others sweep all combinations, so the algebra does not collapse cleanly.
"The map has hard edges, so the top row and bottom row can't be grouped." — error?
The map wraps around like a donut (torus); top and bottom edges are adjacent. Ignoring wrap misses the largest groups and gives a bulkier expression.
"I read across my group but actually flips inside it, so I'll still write ." — error?
If a variable varies inside the group it must be dropped, not written. Only variables that stay constant across every cell survive as literals.
" on a 3-variable map (rows , columns ) gave me ; I circled two pairs." — error?
All four 1s form one block spanning columns 01 and 11, where and both vary and only stays — so the minimal term is the single literal . Two smaller pairs is legal but not minimal; always take the largest group first. (Blue block, top map in the figure.)
"I used a size-8 group of 1s but wrote a 2-literal term." — error?
A size-8 group has , so it must yield literals. In a 4-variable map that is exactly 1 literal, not 2 — recount which variables stay constant.

Why questions

Why must rows/columns be Gray-coded rather than binary-ordered?
So physically adjacent cells differ in exactly one variable, which is the precondition for the combining theorem to apply to neighbours.
Why does a bigger group give a simpler circuit?
Literals ; more cells means larger , hence fewer literals, hence fewer gate inputs and cheaper hardware.
Why are only powers of two allowed as group sizes?
The combining theorem cancels variables one at a time by pairing; each cancellation halves the term count, so only collapse to a single product term.
Why can overlapping actually help minimisation?
Reusing a 1 in a second group can let that group reach size 4 or 8 instead of 2, eliminating more variables for the whole expression.
Why do we group 1s for SOP but 0s for POS?
1s mark where is true, giving OR-of-ANDs (SOP); 0s mark where is false, and grouping them yields the complement, producing AND-of-ORs (POS).
Why is Quine–McCluskey preferred once variables exceed 4 or 5?
Visual adjacency becomes impossible to see in higher dimensions; the Quine-McCluskey Method does the same combining algebraically in a table that a computer can follow.

Edge cases

A 2-variable map has a single 1 in one cell — how many literals?
A lone cell is a group of , so and literals ; both variables survive, e.g. .
Every cell in a 3-variable map is a don't-care and no 1s exist — what is ?
is unconstrained; you may output anything, commonly (simplest circuit) since no minterm requires a 1.
A 4-variable map has 1s only in the four corners — minimal form?
Under our labels (rows , columns ) the four corners are cells 00 00, 00 10, 10 00, 10 10. Across all four, and stay constant while and vary, so the wrap-around group of 4 gives the 2-literal term . (Green corners, bottom map in the figure.)
A single 1 sits alone with no adjacent 1 or don't-care — can it be simplified?
No. It stays a full -literal minterm; there is nothing adjacent to combine with, so no variable can be dropped.
A whole map of 0s except one 0-free row — does wrap change the answer?
If the 1s occupy top and bottom edge rows, wrap merges them into one group of 8; without recognising wrap you would wrongly write two separate 4-cell terms.

Active Recall

Recall What single fact makes a "true/false" K-map claim resolvable?

Whether the cells involved differ by exactly one bit (Gray adjacency) and whether the group size is a power of two — those two tests decide almost every trap.

Recall One-line rule that kills the "group of 3" mistake.

Groups are only; overlap into a nearby 1 to reach the next power of two.

Recall In the four-corners case, which variables survive and why?

and survive (as ) because they are constant at 0 across all four corners; and vary and drop.

Connections