What a Karnaugh map does
A Karnaugh map is a truth table redrawn so that adjacency means something. The rows and columns are labelled in Gray code - each label differs from its neighbour in exactly one bit - so any two cells that touch differ in exactly one variable. Two adjacent 1s can therefore be merged, and the variable that changes between them drops out of the expression entirely.
That is the whole method. Circle groups of 1s whose size is a power of two, read each group as a product term containing only the variables that stay constant across it, and OR the terms together. A group of 2 removes one variable, a group of 4 removes two, a group of 8 removes three.
The map also wraps around: the leftmost column is adjacent to the rightmost, and the top row to the bottom, because their Gray code labels also differ in one bit. The four corners of a four-variable map form a legitimate group of four, which is the fact beginners miss most often.
This calculator does not guess at circles. It runs the Quine-McCluskey algorithm, which finds every prime implicant systematically and then selects a minimum-cost cover exactly, so the answer it gives is a genuine minimum rather than a good-looking grouping. The map is still drawn, because seeing the groups is how the method is taught and checked.
Implicants, prime implicants and the cover
Three terms carry the whole theory.
An implicant is any product term that is 1 only where the function is 1 (or don't-care). On the map it is any legal group. A prime implicant is an implicant that cannot be enlarged - no bigger legal group contains it. Only prime implicants can appear in a minimal expression, because a non-prime group could always be replaced by a larger one with fewer literals.
An essential prime implicant is one that is the sole cover of some minterm. If a cell is covered by exactly one prime implicant, that implicant has to be in every minimal solution - there is no alternative. Finding the essential ones first, then covering whatever is left as cheaply as possible, is the standard procedure and the one this page follows.
The last step is where hand methods and algorithms diverge. Selecting the cheapest subset of the remaining prime implicants that covers the remaining minterms is a set-cover problem, and the textbook technique for it is Petrick's method - writing the cover condition as a product of sums, multiplying it out, and reading off the cheapest product. This calculator instead searches the choices directly with branch and bound, which finds the same minimum without the algebraic expansion.
Cost is judged first by the number of terms and then by the number of literals, which is the conventional criterion: fewer terms means fewer gates feeding the output, and fewer literals means fewer gate inputs. Two different expressions can tie on both counts, in which case several equally minimal answers exist and the calculator reports one of them.
Don't-care conditions - input combinations that cannot occur, or whose output nobody cares about - are the cheapest simplification available. Each one may be treated as a 1 when that enlarges a group and as a 0 when it does not, and a single well-placed don't-care often removes a whole term. They are written X on the map and entered separately here.
Worked example: F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)
Write out what those indices mean in binary, with A as the most significant bit:
0 = 0000, 2 = 0010, 5 = 0101, 7 = 0111, 8 = 1000, 10 = 1010, 13 = 1101, 15 = 1111
- Look for a pattern. In every one of those, the B bit and the D bit are equal: 0000 has B = 0 and D = 0; 0101 has B = 1 and D = 1; 1010 has B = 0 and D = 0; 1111 has both 1. The function is the XNOR of B and D.
- Group the cells where B = 0 and D = 0. Those are minterms 0, 2, 8 and 10 - a group of four in which A and C both vary and both drop out. The term is
B′D′. - Group the cells where B = 1 and D = 1. Those are 5, 7, 13 and 15 - another group of four giving
BD. - Combine. Every minterm is covered, so F = B′D′ + BD: two terms, four literals.
On the map these two groups look scattered rather than rectangular, which is the point of the wrap-around rule - minterms 0, 2, 8 and 10 sit at the four corners of the four-variable map, and they are adjacent through both edges. A student circling only visually contiguous blocks would find four groups of two and produce an expression with four terms and eight literals, twice the gate cost for the same function.
Both groups here are essential: minterm 0 is covered only by B′D′ and minterm 5 only by BD, so no choice arises and the minimum is unique. Building it takes two AND gates, one OR gate and two inverters - or, if you recognise the pattern, a single XNOR gate.
Reading the output
The prime implicant table is where the reasoning is visible. Rows marked essential are forced - they are the only cover for at least one minterm, and they appear in every minimal answer. Rows marked chosen were selected to finish the cover, and a different but equally cheap choice may have been available. Rows marked not needed are perfectly valid groups that the minimal solution happens not to use.
The pattern column uses a dash for each eliminated variable, so -0-0 in a four-variable problem means B = 0 and D = 0 with A and C free - a group of four, since two free variables give 2² cells. Count the dashes and you know the group size without looking at the map.
Literal count is the better guide to cost than term count alone. Two terms of four literals each need more gate inputs than three terms of two, even though the term count is smaller. The gate estimate on this page counts one AND gate per multi-literal product, one OR gate to combine them, and one inverter per distinct complemented variable - assuming gates with unlimited fan-in and no complemented inputs available. Real technology mappings differ, and a NAND-only implementation converts a sum of products directly by De Morgan at no extra cost.
If you asked for a product of sums, the prime implicant table describes the complement of your function. That is how POS minimisation works: minimise where the function is 0, then apply De Morgan to the result, which turns each product into a sum and complements every literal. Compare the SOP and POS forms of the same function and take whichever is cheaper - there is no rule that says one always wins.
How much a group removes
| Cells in the group | Variables eliminated | Literals in the term (4 variables) | Literals (5 variables) | Example term |
|---|---|---|---|---|
| 1 | 0 | 4 | 5 | A′BC′D |
| 2 | 1 | 3 | 4 | A′BC′ |
| 4 | 2 | 2 | 3 | B′D′ |
| 8 | 3 | 1 | 2 | B |
| 16 | 4 | 0 (constant 1) | 1 | 1 |
| 32 | 5 | n/a | 0 (constant 1) | 1 |
Every legal group has a size that is a power of two, and doubling the group removes exactly one more variable. A group of six is not legal, however neatly it fits on the page.
Mistakes that cost gates
- Forgetting that the map wraps. The four corners of a four-variable map form a group of four, and the leftmost and rightmost columns are adjacent. Missing this is the single most common source of a non-minimal answer.
- Making groups that are not powers of two. A block of six cells is not a legal group. Cover it as a four and a two, which may overlap.
- Refusing to overlap groups. Overlapping is not only allowed but usually required - a minterm may be covered any number of times, and larger overlapping groups beat smaller disjoint ones.
- Using a non-maximal group. If a group can be doubled, double it. Only prime implicants belong in a minimal expression, and a group of two inside a legal group of four carries one unnecessary literal.
- Labelling the map in binary counting order. The columns run 00, 01, 11, 10 - Gray code - not 00, 01, 10, 11. Getting this wrong destroys the adjacency property the whole method rests on.
- Wasting don't-cares. They are free simplification, but only where they enlarge a group. A don't-care that sits alone should be left as a 0; covering it adds a term for nothing.
Where this fits in digital design
Maurice Karnaugh published the map in 1953, refining a chart Edward Veitch had introduced the year before; the Gray code labelling is what makes the Karnaugh version work visually, and it is why the map survived while the Veitch diagram did not. Quine and McCluskey gave the tabular algorithm later in the 1950s, and it is that algorithm - not the drawing - that scales.
The practical limit of the drawing is about six variables. Beyond four the map splits into multiple planes and adjacency stops being visible; beyond six, nobody can see the groups at all. Real synthesis tools use heuristic minimisers in the Espresso family, which give up the guarantee of an exact minimum in exchange for handling functions with dozens of inputs and many outputs at once.
Minimisation still matters even when a tool does it for you, because it fixes gate count, propagation delay and power. It also has a subtlety the map does not show: a minimal cover can contain a static hazard, a momentary wrong output when two input variables change so that coverage passes from one group to another. The fix is to add a redundant prime implicant bridging the two groups - deliberately non-minimal logic, added for timing rather than area.
For the algebraic route to the same answer, the Boolean algebra simplifier works from an expression rather than from minterm indices, and the truth table calculator converts between the two - the minterm list is exactly the set of rows where the output is 1. The underlying algebra is the same structure as set operations, with AND for intersection, OR for union and complement for complement, so De Morgan's laws read identically in both notations.