Enter a logic function of 2 to 4 variables by clicking cells in the truth table or the Karnaugh map, and get the minimal sum of products (SOP) and product of sums (POS) right away. The SOP groups are drawn on the map in color, along with the prime implicants, the essential ones and the number of gate inputs. You can also load examples such as a 3-input majority function, a 7-segment display decoder and odd parity.
Favorites and recently used calculators are stored only in this browser (localStorage).
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
What a Karnaugh map is, and why Gray code order
A Karnaugh map puts each row of a truth table into one cell: 4 cells for two variables, 8 for three and 16 for four. Here, four variables use AB for the rows and CD for the columns, three use A for the rows and BC for the columns, and two use A and B, with the labels in the Gray code order 00, 01, 11, 10. In binary order (00, 01, 10, 11), two bits change between 01 and 10, but in Gray code order neighboring cells differ in exactly one variable. Two minterms that differ in only one variable merge into a single product term with that variable removed, as in A̅BC + ABC = BC. A Karnaugh map simply lets you spot these mergeable pairs by eye as neighboring cells.
Grouping rules: power-of-two rectangles and wrap-around edges
Group the 1s in rectangles whose size is a power of two: 1, 2, 4, 8 or 16 cells. A group of 2ᵏ cells eliminates k variables, so make each group as large as possible and use as few groups as possible to cover every 1; groups may overlap. Because 10 and 00 also differ in a single bit, the left and right edges are adjacent, as are the top and bottom, so the map behaves like a surface that wraps around in both directions. In the “Four corners” example, Σm(0, 2, 8, 10), the four corner cells form one group in which A and C change while B and D stay 0, so the result is the single term B̅D̅. By contrast, in “3-input odd parity” (A⊕B⊕C) the 1s and 0s form a checkerboard with no two 1s adjacent, so all four minterms remain and the SOP cannot be simplified at all.
Using don't cares (X): the 7-segment example
A don't care, shown as X here, is a cell whose input combination never occurs or whose output does not matter. An X can be treated as 1 when that makes a group larger and as 0 otherwise, which gives you more freedom in grouping. The “7-segment ‘a’ (BCD)” example decides whether to light the top bar, segment a, for digits 0 to 9 given as 4-bit BCD (ABCD, A most significant); with the common digit shapes in which 6 also has a top bar, a is lit for 0, 2, 3, 5, 6, 7, 8 and 9 and off for 1 and 4. Inputs 10 to 15 never occur, so marking them X gives the minimal SOP A + C + BD + B̅D̅, with four terms and six literals, all four of them essential prime implicants. Leaving 10 to 15 at 0 instead needs four terms and 11 literals, such as A̅BD + A̅C + AB̅C̅ + A̅B̅D̅, and there is another solution of the same size. The same X can even be used as 1 in the SOP and as 0 in the POS: in this example, 12 (ABCD = 1100) lies in the SOP group A but in the POS group (B̅ + C + D).
Prime implicants, essential prime implicants and Quine-McCluskey
A group that cannot be made any larger, meaning a product term not contained in any other group, is called a prime implicant. A prime implicant that is the only one covering some 1 is called essential, and every minimal expression must include it. When the essential prime implicants do not cover every 1, you must choose among the remaining ones, and some functions, such as Σm(0, 1, 2, 5, 6, 7), have no essential prime implicants at all and two minimal solutions. Instead of looking at the map, this tool uses the Quine-McCluskey method: it systematically merges terms that differ in one variable to find every prime implicant, then searches for the combination with the fewest terms and, among those, the fewest literals, so the result is always a true minimum. People can reliably see adjacency on a Karnaugh map only up to about four or five variables; larger functions are simplified with tabular methods like this or with the heuristic algorithms in logic synthesis tools.
SOP vs POS, NAND/NOR implementation and hazards
A sum of products (SOP) ORs together AND terms and is found by grouping 1s. A product of sums (POS) ANDs together OR terms and is found by grouping 0s, writing each variable that stays 0 in a group as itself and each that stays 1 as its complement, then ORing them. By De Morgan's theorem, a two-level AND-OR circuit maps directly to NAND-NAND and a two-level OR-AND circuit to NOR-NOR, so either form can be built purely from NAND or NOR gates, which are easy to make in CMOS. Which form is smaller depends on the function: for segment a, the SOP has four terms while the POS, (A + B + C + D̅)(B̅ + C + D), has just two. A minimal expression is not necessarily hazard-free, either: with the minimal SOP A̅C + AB for Σm(1, 3, 6, 7), if A changes while B = C = 1, the output can drop briefly to 0 at the moment one term hands over to the other, a static-1 hazard. Adding the consensus term BC, which spans both groups and appears here as a non-essential prime implicant, gives A̅C + AB + BC and prevents the glitch, so if your circuit must be hazard-free, add such terms to the minimal expression shown.
A Karnaugh map arranges a truth table so that adjacent cells differ in only one input bit (Gray-code order). Grouping adjacent 1s in rectangles of 1, 2, 4 or 8 cells eliminates the variables that change within each group, simplifying the expression; note that the edges wrap around and count as adjacent. Manual use tops out at about four or five variables; beyond that, the Quine-McCluskey method or synthesis-tool algorithms are used.
Answer: B. When two or more of the three inputs are 1
A majority circuit outputs 1 when more than half its inputs are 1—for three inputs, when two or more are 1. Its expression AB + BC + CA is the same as a full adder's carry output. Triple modular redundancy (TMR), which votes among three copies of a circuit, keeps the output correct even if one copy fails or suffers a radiation-induced bit flip, and is used in aerospace equipment and high-reliability servers.
A + A·B = A·(1 + B) = A·1 = A (the absorption law). If A is 1 the whole is 1; if A is 0 then A·B is also 0, so the result equals A regardless of B. The dual form A·(A + B) = A also holds. Removing redundant gates through such simplification saves area, delay and power, though some designs deliberately keep redundant terms to avoid hazards.
FAQ
How many variables does it support?
This tool handles 2 to 4 variables. Up to four variables (16 cells), a single 4 × 4 grid lets you check adjacency by eye, including the wrap-around edges, but five variables need two 4 × 4 maps side by side with cells in the same position on both maps also counted as adjacent, which is much harder to read. The truth table also doubles in length with each extra variable, so the tool stops at four, where the map and table are easy to compare. Larger functions are simplified with software such as logic synthesis tools.
Why does it say other solutions of the same size exist?
Some functions have more than one combination with both the fewest terms and the fewest literals. For example, Σm(0, 1, 2, 5, 6, 7) can be written as either A̅B̅ + BC̅ + AC or A̅C̅ + B̅C + AB, each with three terms and six literals, and it has no essential prime implicants. The tool shows one of them. They all describe the same logic function, so every one of them is a correct answer.
What does X (don't care) mean?
It marks an input combination that never occurs, or one whose output does not matter. Typical examples are the codes 10 to 15 in BCD and unused states in a state machine. During simplification, an X takes whichever value makes the expression smaller. In the real circuit an X cell still outputs a 0 or 1 set by the resulting expression, so use don't cares only when you are sure those inputs really cannot occur.
How do I find the POS by hand?
Group the 0s using the same rules as for 1s. In each group, write each variable that stays 0 as itself (A) and each that stays 1 as its complement (A̅), OR them together, then AND all these terms to get the POS. This is the same as grouping the 0s to get the SOP of the complement F̅ and then complementing the whole thing with De Morgan's theorem. For a 3-input majority function, for example, you get (A + B)(A + C)(B + C), which expands to the same function as the SOP AB + AC + BC.
Can I check the result as a circuit?
Yes. In the site's “Logic circuit simulator,” wire AND, OR and NOT gates exactly as the expression says; it builds the truth table automatically, so you can confirm that it matches the one in this tool. Cells marked X will show whichever 0 or 1 the expression produces. You can also rebuild the circuit as two levels of NAND gates and check that the table stays the same. Note that the simulator does not model gate delays, so glitches caused by hazards will not appear.