The idea: fold the truth table so neighbours differ in one input

Any truth table can be written as a sum of minterms: one AND term for each row where F = 1, all ORed together. It is always correct but long. The majority function F(A, B, C), which is 1 when at least two inputs are 1, has four minterms: A'BC + AB'C + ABC' + ABC, 12 literals. The shortest form is AB + AC + BC, 6 literals. A Karnaugh map (K-map) finds it by eye. It puts the rows of the truth table in a grid where cells that touch differ in exactly one input. Two touching 1s then mean "this input does not matter", and the pair becomes one shorter term.

Left: the 8-row truth table of the majority function with F = 1 in rows m3, m5, m6 and m7. Right: the same 8 values placed in a 2 by 4 Karnaugh map, rows A = 0 and 1, columns BC in the order 00, 01, 11, 10, with each cell labelled by its minterm number
Each row of the table is one cell of the map; the columns go 00, 01, 11, 10, so m2 sits to the right of m3.

On the canvas the truth table is on the left, the map in the middle and the result on the right. Press Fill Map to copy the rows into the map, Group 1s to find the groups and the minimal formula, and Algebra to reach the same formula by Boolean algebra.

Gray code and wrap-around

Counting in binary, 01 → 10 changes two bits at once. The map orders its rows and columns in Gray code instead: 00, 01, 11, 10. Each step changes one bit, and so does the step from the last back to the first (10 → 00). So the map wraps around: the left column touches the right column, the top row touches the bottom row, and with 4 inputs the four corners are all neighbours. Picture the map drawn on a doughnut.

inputsmapcells
2 (A, B)2 × 2: rows A, columns B4
3 (A, B, C)2 × 4: rows A, columns BC8
4 (A, B, C, D)4 × 4: rows AB, columns CD16

The page numbers cells by minterm, with A as the most significant bit: m5 = 0101 means A = 0, B = 1, C = 0, D = 1, so it sits in row AB = 01 and column CD = 01.

Grouping rules

  • A group is a rectangle of 1, 2, 4, 8 or 16 cells: a power of two. A group of 3 or 6 is not allowed.
  • It may contain only 1s (and don't cares), never a 0.
  • Make each group as big as possible: bigger groups give shorter terms.
  • Use as few groups as possible to cover every 1. Groups may overlap.
  • Groups may wrap around the edges.
Three 4 by 4 maps. First: a legal pair, a legal quad in one row and a legal 2 by 2 square, marked with a tick. Second: a legal group of the four corner cells and a legal pair wrapping from the left edge to the right edge, marked with a tick. Third: an illegal group of three cells and an illegal L shape, marked with a cross
Rectangles of 1, 2, 4 or 8 cells, also across the edges, are legal; 3 cells or an L shape are not.

A group that cannot grow any bigger is a prime implicant. If it is the only group that covers some 1, it is essential and must be in the answer. The page finds all prime implicants and picks the smallest set that covers every 1 (Demo: four corners).

Reading a term from a group

A group of 2k cells has k inputs that change inside it. Those inputs drop out. The inputs that stay the same form the term: an input that stays 1 is written plain, one that stays 0 gets a prime ('). In the four corners group of a 4-input map, A changes (rows 00 and 10) and C changes (columns 00 and 10), while B = 0 and D = 0 everywhere, so the group reads B'D'. An octet of 8 cells keeps only one input (Demo: an octet).

group size (4 inputs)inputs droppedliterals in the term
104
213
422
831
164F = 1

OR the terms of all groups and you have the minimal sum of products (SOP). It maps straight onto an AND–OR circuit with the fewest gates and gate inputs.

The map versus Boolean algebra

Every group is the algebra rule XY + XY' = X (from X(Y + Y') = X · 1), applied once per input that drops out. Two neighbouring cells differ in one input Y, so their minterms are exactly XY and XY'. The map does nothing algebra cannot; it just shows which terms to pair.

Left: the majority map with three overlapping pairs, BC, AC and AB, all sharing cell m7. Right: the algebra: A'BC + AB'C + ABC' + ABC; copy ABC twice; pair A'BC + ABC = BC, AB'C + ABC = AC, ABC' + ABC = AB; F = AB + AC + BC
Three groups share m7 = ABC; algebra needs ABC copied twice (X = X + X), the map shows the overlap for free.

The hard part in algebra is knowing what to do. In the majority function every pair uses ABC, so you must first write ABC + ABC + ABC (the rule X = X + X) before you can pair it three times. On the map the three pairs simply overlap on m7 (Demo: majority vote, map vs algebra). This is the same function as the carry-out of a full adder, see Combinational Logic.

Don't cares

Sometimes an input combination never happens. A BCD digit uses 4 bits for 0–9, so codes 10–15 never occur. Their output is a don't care, written X. In the map an X may be treated as 1 when that makes a group bigger, and as 0 otherwise. For "digit ≥ 5" (minterms 5–9), the Xs let 8 and 9 join the octet A, and the result is A + BC + BD instead of the longer form without them (Demo: don't cares).

Redundant groups and the consensus theorem

Not every prime implicant is needed. For Σm(0, 1, 3, 7), A'B', A'C and BC are all legal pairs, but A'B' and BC already cover every 1, so A'C is dropped. In algebra this is the consensus theorem XY + X'Z + YZ = XY + X'Z: the term YZ (here A'C) is implied by the other two (Demo: redundant group). Greedy grouping ("take every group you see") gives a correct but not minimal answer.

Beyond four inputs

A 5- or 6-input map needs two or four 4 × 4 maps stacked, and spotting groups gets hard. Programs use the Quine–McCluskey method instead: list all prime implicants by combining terms that differ in one bit (the same XY + XY' = X), then pick a minimum cover. Picking the cover is NP-hard in general, so tools for large circuits, such as Espresso, use heuristics. With at most 4 inputs the page simply tries every combination.

See also Truth Tables and Sets for truth tables and De Morgan's law, and Sequential Logic for circuits whose next-state logic is simplified the same way.

What the page leaves out

Product of sums (grouping the 0s to get F in POS form), maps with 5 or 6 inputs, multi-output minimization (sharing terms between several outputs), hazards and the extra consensus terms that remove glitches, the Quine–McCluskey tables step by step, and the cost of a real circuit (NAND/NOR gates, fan-in limits, wiring).