1. What a Karnaugh map is
A Karnaugh map is a truth table redrawn as a grid. Maurice Karnaugh introduced it at Bell Labs in 1953 as a way of simplifying switching circuits by eye, and it is still the quickest way to minimise a small Boolean function by hand: no algebra, no laws to recall, just rectangles.
Every cell of the map holds one row of the truth table. What makes the map more than a rearrangement is the order those rows are placed in: cells that sit next to each other differ in exactly one variable.
That single property does all the work. If two neighbouring cells are both true, the variable that changes between them cannot be what makes the expression true, so it drops out and one term covers both cells. Simplifying becomes a matter of drawing the largest rectangles you can.
2. Why the columns look out of order
The columns of a Karnaugh map do not count 00, 01, 10, 11. They run 00, 01, 11, 10 - reflected Gray code, an ordering in which each value differs from the next in a single bit. Counting in binary would put 01 next to 10, which differ in two bits, and neighbouring cells would tell you nothing.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
The edges are neighbours too. The leftmost and rightmost columns differ in one variable, and so do the top and bottom rows, so a group may run off one edge and continue on the other - which is why the four corners of a four-variable map form a single group. A Karnaugh map is really drawn on a torus; the flat sheet is a convenience.
3. Grouping the ones
To read a minimal sum of products off the map, cover every cell holding a 1 with rectangular groups, following four rules:
- A group is a rectangle of 1, 2, 4, 8 … cells - a power of two along each side.
- A group may wrap around the edges of the map, horizontally, vertically, or both.
- Groups may overlap. A cell covered twice costs nothing; a cell left uncovered changes the function.
- Make every group as large as it will go, then use as few groups as will cover all the ones.
Each group becomes one term. Read it by asking which variables stay the same across the whole group: those appear in the term - plain where they are 1, negated where they are 0 - and every variable that changes drops out. A group of two cells loses one variable, a group of four loses two, a group of eight loses three. The minimal expression is the disjunction of the terms.
4. A worked example
Take (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Its map has four variables: A and B down the rows, C and D across the columns.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Two groups cover every 1. One is the block of four cells in the two rows where A = 0 and the two columns where C = 1: B and D both change inside it, so they drop out and the term is ¬A ∧ C. The other is the whole row where A and B are 1, spanning all four columns: C and D change across it, leaving A ∧ B.
So the minimal form is (¬A ∧ C) ∨ (A ∧ B). The third term of the original, B ∧ C ∧ D, has vanished: every cell it covered was already covered by one of the two groups. That is what absorption looks like when you can see it.
5. Prime and essential implicants
A group that cannot be made any larger is called a prime implicant. Listing the prime implicants is the easy half of the problem; choosing which of them to keep is the half that goes wrong.
If some cell is covered by only one prime implicant, that implicant is essential: no minimal form can leave it out, because nothing else covers that cell. Take the essential implicants first, then cover whatever is left over with as few of the remaining groups as possible.
Being greedy - repeatedly taking the largest group still available - is tempting, and it does not always work. On a cyclic chart, where no implicant is essential and every cell is covered twice over, the greedy choice can finish one term longer than the best answer. The map on this site searches the remaining choices exhaustively instead, which at four variables costs nothing.
6. Grouping the zeros instead
Everything above works just as well on the zeros. Cover them with the same rectangles, read each group with its literals negated - a variable that is 1 across the group appears negated, one that is 0 appears plain - and join the groups with ∧ instead of ∨.
The result is a product of sums: a conjunction of disjunctions that is false in exactly the cells the expression is false in, and therefore true everywhere else. Which form is shorter depends on the function - a formula with few ones has a short sum of products, one with few zeros a short product of sums - so it is worth reading both off the map before choosing.
7. Bigger maps, and don't-cares
Five and six variables can be drawn as two or four four-variable maps stacked on top of one another, with cells in the same position on neighbouring layers counted as adjacent. It works, but the adjacency that made the method visual is now something to remember rather than see. Past that, the Quine-McCluskey algorithm does the same job as a table: it is the mechanical form of exactly this grouping, and it is what runs behind the maps here.
Hardware design adds one more idea. Some input combinations never occur - a binary-coded decimal digit is never 1010 - so the designer does not care what the circuit does with them. Those cells are marked X and may be read as either value, whichever makes the groups larger. The maps in this calculator are built from a formula, which gives every assignment a value, so no cell is ever a don't-care.
8. Try it yourself
Type an expression of two to four variables into the calculator and its map is drawn below the truth table, with every group ringed in its own colour and the minimal form spelled out underneath. Switch it to product of sums to see the zeros grouped instead.