Karnaugh Maps, Explained
After reading this you will know why a Karnaugh map lets adjacent 1s merge, how the tool turns your minterms into the smallest sum-of-products expression, and how to read the colored groups without getting fooled by the edges.
What a Karnaugh map does
A Karnaugh map is a truth table folded into a grid so that Boolean simplification becomes a game of drawing rectangles. Take a function of four variables A, B, C, D. Its truth table has 2^4 = 16 rows. On paper you would stare at 16 output bits and try to spot patterns. The map lays those 16 outputs on a 4-by-4 grid so that physically adjacent cells differ in exactly one variable.
Here is the hook. Suppose your function is 1 whenever A=1 and B=1, regardless of C and D. On the truth table that is four separate rows. On the map those four cells form one solid 2-by-2 square, and the tool reads it off as a single term AB. Four rows collapsed into two literals. That collapse is the entire point.
Why adjacency equals simplification
The Boolean identity behind everything is X\bar{Y} + XY = X. If two product terms agree on every variable except one, and that one variable appears both true and complemented, it drops out. On the map, two cells that touch differ in exactly one variable, so merging them applies that identity for free.
The map axes use Gray code order, 00 01 11 10, not binary counting order. That is what guarantees single-variable adjacency, including at the wrap-around edges. The leftmost column and the rightmost column differ in one variable, so they are neighbors even though they look far apart.
Here k is how many times the group doubles. A group of 2^0 = 1 cell eliminates nothing and keeps all variables. A group of 2^1 = 2 drops one variable. A group of 2^4 = 16 covers the whole 4-variable map and reduces to the constant 1. This is why groups must be power-of-two rectangles: only those shapes correspond to a valid string of merges.
When to reach for it, and when not to
K-maps are the right tool for 2 to 5 variables. At 4 variables the map is 4-by-4. At 5 variables it is two 4-by-4 layers, and adjacency now spans the two layers as well. Past 6 variables the map stops being something a human can scan, and adjacency in the fourth dimension defeats visual grouping.
For hand work the map wins up to 4 variables. For anything larger, an algorithm does the grouping. This tool runs the Quine-McCluskey algorithm, which finds every prime implicant mechanically, then applies Petrick's method to select a minimal cover. That scales past what you can draw, and it still shows you the answer on a map so you can check it.
If your goal is to build and watch a circuit rather than minimize an expression, the Digital Logic Gate Simulator lets you wire the simplified terms into gates and see the signals flow.
Prime implicants, essentials, and Petrick's method
Three definitions carry the algorithm. Learn them once and the output reads cleanly.
- Implicant
- Any product term that is 1 only where the function is 1 (or where you allow a don't-care). Every legal group on the map is an implicant.
- Prime implicant
- An implicant you cannot enlarge. If doubling the group in any direction would cover a 0, the group is already prime. These are the biggest legal rectangles.
- Essential prime implicant
- A prime implicant that is the only one covering some particular 1. Every minimal solution must include it, because nothing else reaches that cell.
The tool first finds all prime implicants, then marks the essential ones. Those go into the answer immediately. Whatever 1s remain uncovered are handed to Petrick's method, which searches the remaining prime implicants for the smallest set that finishes the job. Petrick guarantees a genuine minimum, not just a greedy guess.
A worked example
Reproduce the demo with the default 4-variable function. The 1s sit at minterms {0, 1, 2, 5, 6, 7, 8, 9, 10, 14}. Read each minterm as the binary value of ABCD: minterm 5 is 0101, meaning A=0, B=1, C=0, D=1.
Grouping the default map
- List the prime implicants. The tool finds four large groups that each cover four cells, so each is a 2-literal term.
- Test each for essentiality. The group \bar{B}\bar{C} is the only cover for minterm 8 (
1000), so it is essential. - Collect the remaining essentials. Working through the map yields \bar{A}\bar{C}D covering 1 and 5, and the wrap-around group C\bar{D} covering 2, 6, 10, 14.
- Hand the leftovers to Petrick. After the essentials, minterms 6 and 7 need one more term, and \bar{A}B finishes the cover.
- Write the sum-of-products: F = \bar{B}\bar{C} + C\bar{D} + \bar{A}\bar{C}D + \bar{A}B.
Count what you saved. The unsimplified form lists 10 minterms of 4 literals each, so 40 literal-appearances feeding a 10-input OR. The simplified form has 4 terms totaling 9 literals feeding a 4-input OR. That is the number the literal/gate readout reports.
How group size shapes the answer
The single most instructive parameter is group size, because each doubling removes exactly one literal. Move it and watch the term shrink.
Reading the colored output
Each chosen group gets its own colored outline on the map. Overlap between outlines is expected and correct: a single 1 can belong to several groups, and it should, because every group it joins helps eliminate a variable somewhere. The essential groups are called out separately so you can see the backbone of the solution before Petrick adds the rest.
The wrap-around groups are the ones that confuse people on paper. A group can leave the right edge and continue on the left edge, or leave the top and continue on the bottom, and a 4-corner group is a single legal 4-cell block. The tool draws these explicitly so you do not have to imagine the fold.
Switch to the product-of-sums view to minimize the 0s instead of the 1s. Sometimes the zeros group into fewer, larger rectangles than the ones. Compare the literal counts of both views and keep whichever is smaller for your circuit.
Common mistakes
The most frequent error is grouping in binary order instead of Gray code order. If you write the columns as 00 01 10 11, adjacent cells differ in two variables at the 01 to 10 step, and your merges become invalid. The order is 00 01 11 10 for a reason.
A second mistake is treating don't-cares as 1s that must be covered. They are wildcards. The tool uses a don't-care as a 1 only when it enlarges a group, and ignores it otherwise. Forcing every X into a group can produce extra terms that buy you nothing. Don't-cares usually come from input codes that never occur, such as BCD values 10 through 15 on a 4-bit input.
A third mistake is stopping at a valid cover instead of a minimal one. Two overlapping 4-cell groups may cover the same 1s that one larger 8-cell group covers with one fewer literal. Always prefer the largest legal group. Petrick's method does this for you, which is why the tool's answer can be smaller than a hand grouping.
Related tools
If Boolean minimization is part of a larger interest in how machines compute, a few neighbors here build on the same ground. The Digital Logic Gate Simulator turns a minimized expression into a working circuit. For the data-structure side of algorithms and CS, the Data Structure Visualizer steps through trees, heaps and hash tables, and the Bloom Filter Playground shows a probabilistic structure built from simple bit operations. The Regex Backtracking Visualizer makes another combinatorial explosion visible, this time in pattern matching.
Frequently asked questions
Why is the axis order 00 01 11 10 instead of 00 01 10 11?
That is Gray code. Only one bit changes between neighbors, so any two adjacent cells differ in exactly one variable. Binary counting order changes two bits at the 01 to 10 step, which would make adjacent merges illegal.
Can a minterm belong to more than one group?
Yes, and it often should. Overlap is free. A single 1 covered by three groups helps eliminate a variable in each of them. The only rule is that every 1 must be covered at least once.
Is sum-of-products always smaller than product-of-sums?
No. When the 0s of a function group into fewer or larger rectangles than the 1s, the product-of-sums form wins. Compare the literal counts of both views. In the worked example the SOP form uses 9 literals; the POS form may differ, so check both.
What happens with 5 variables?
The map becomes two stacked 4-by-4 layers, one for the fifth variable being 0 and one for it being 1. Cells in the same position on the two layers are adjacent, so groups can span both layers. The tool draws this so you do not have to picture the third dimension.
Does Petrick's method always find the true minimum?
Yes, for the number of product terms. It builds a product-of-sums over the prime implicants and expands it to find the smallest set that covers every remaining minterm. That is an exhaustive search over covers, so the result is a genuine minimum rather than a greedy approximation.
Related tools
Bloom Filter Playground
Add items, watch bits light up, measure the false positive rate.
Cache Replacement Simulator
Animate FIFO, LRU, LFU, CLOCK, ARC and Bélády's OPT on any access sequence.
Consistent Hashing Ring
See why adding a server moves 1/N of the keys, not all of them.
Data Structure Visualizer
Watch BST, AVL, red-black trees, heaps, hash tables, tries and union-find work, step by step.
Digital Logic Gate Simulator
Build circuits from gates and flip-flops, wire them up, and watch the signals flow live.
Git Branching Sandbox
Type git commands and watch the commit DAG, branches and HEAD move — with levels, remotes, undo, and merge-vs-rebase contrast.