Karnaugh Map (K-Map) Solver

The Karnaugh Map (K-Map) Solver minimizes any Boolean logic function of 2 to 5 variables and visualizes the simplification as a classic K-map with color-coded groupings. Enter your minterms, maxterms, or use the interactive truth table — the solver runs the Quine-McCluskey algorithm under the hood, finds every prime implicant, marks the essential ones, and produces the minimal Sum-of-Products (SOP) or Product-of-Sums (POS) expression with a step-by-step explanation. Click any prime implicant chip to pulse-glow the cells it covers and see how the grouping simplifies logic.

What is a Karnaugh Map?

A Karnaugh map (invented by Maurice Karnaugh in 1953) is a graphical representation of a truth table, laid out so that cells which differ by only one input variable are physically adjacent. The key trick is Gray-code ordering of rows and columns: consecutive labels like 00, 01, 11, 10 differ by exactly one bit. This adjacency lets you visually spot groups of 1s (or 0s) that can be combined into a single simplified term.

For n input variables, the K-map has 2^n cells. A 4-variable K-map is a 4×4 grid of 16 cells; a 5-variable map is drawn as two adjacent 4×4 grids.

SOP vs POS: Which Form to Choose

Sum of Products (SOP)

SOP groups the 1-cells. Each group becomes a product (AND) of literals, and all groups are OR'd together. Example: AB'C + BD. SOP is usually the default because it maps directly to AND–OR gate networks.

Product of Sums (POS)

POS groups the 0-cells. Each group becomes a sum (OR) of the complemented literals, and all sums are AND'd together. Example: (A + B')(C + D'). POS is often smaller when the function has more 1s than 0s.

The tool computes both forms independently — toggle the output mode to compare literal counts and pick whichever is simpler for your implementation.

Grouping Rules for Karnaugh Maps

• Power-of-two groups only: groups must contain 1, 2, 4, 8, or 16 cells. A group of 3 or 5 is not allowed.
• Rectangular shape: cells in a group form a rectangle (horizontally, vertically, or wrapping around edges).
• Wrap-around adjacency: the top row is adjacent to the bottom row; the leftmost column is adjacent to the rightmost. This is why gray-code ordering matters.
• Largest groups first: bigger groups eliminate more variables, producing shorter product terms. An 8-cell group drops 3 variables; a 4-cell group drops 2; a 2-cell group drops 1.
• Every 1 must be covered: at least one group must cover each 1-cell (for SOP) or 0-cell (for POS).
• Overlapping is allowed: the same 1 can be covered by multiple groups if that leads to larger groups.
• Don't-cares are flexible: they may be grouped if doing so produces larger groups, but they don't have to be covered.

Prime Implicants and Essential Prime Implicants

A prime implicant is a group that cannot be expanded further — enlarging it would include a 0-cell (for SOP). The solver lists every prime implicant it finds. Then it picks a minimal cover: the smallest set of prime implicants that covers every required minterm.

An essential prime implicant is marked ESSENTIAL when it is the only prime implicant covering at least one specific minterm. Every minimal expression must include all essential prime implicants. After selecting them, the remaining uncovered minterms are covered by the cheapest additional prime implicants.

Don't-Care Conditions

A don't-care (shown as X on the K-map) is an input combination whose output is irrelevant — either it never occurs in the real circuit or its value does not matter. The algorithm is free to treat each X as either 0 or 1, choosing whichever yields a simpler expression. In practice, don't-cares often reduce literal count by 30–60%. A common real-world source: decimal digit decoders that only use 10 of the 16 four-bit input combinations, leaving combinations 10–15 as don't-cares.

The Quine-McCluskey Algorithm

The K-map is a visual method, but for more than 4–5 variables it becomes impractical. The Quine-McCluskey (QM) algorithm is the tabular equivalent — mathematically rigorous and scalable. This solver uses QM internally:

1. List minterms in binary, group them by number of 1-bits.
2. Combine pairs from adjacent groups (differing in one bit), replacing the differing bit with a dash. Example: 0011 + 0111 → 0-11.
3. Repeat until no further combinations are possible. Terms that cannot be combined are prime implicants.
4. Build a prime implicant chart — rows are primes, columns are required minterms. Identify essential primes (columns with a single check mark).
5. Petrick's method / exhaustive search: for the remaining uncovered minterms, find the smallest set of additional primes that covers them.

How to Use This Calculator

1. Select the number of variables: 2, 3, 4, or 5. The K-map grid adapts automatically.
2. Choose an input method:
   • Minterms: enter indices where F = 1 (e.g. 1, 3, 5, 7) and any don't-cares.
   • Maxterms: enter indices where F = 0. The solver computes the rest as 1s automatically.
   • Truth Table: click each row to cycle output between 0, 1, and X. Perfect for hand-designed logic.
3. Pick SOP or POS output. Compare both forms by toggling — one is often shorter than the other.
4. Click Solve. The K-map appears with every prime implicant in a distinct color. Click any chip to pulse-glow the cells it covers.
5. Inspect the steps: the Quine-McCluskey breakdown shows how every prime implicant was derived and which are essential.

Worked Example: 4-Variable Function with Don't-Cares

Consider F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Without don't-cares, the minimal SOP would need several terms. Treating {0, 2} as 1s lets the solver build the 4-cell group A'B' (covering 0, 1, 2, 3). Treating 5 as a 1 lets it extend CD coverage. The resulting simplification is:

Just 4 literals — down from 10+ without the don't-care trick. You can load this exact example with the "4-var with Don't-Cares" quick example above.

Why Minimize Boolean Functions?

• Fewer gates = lower hardware cost, smaller chip area, lower power consumption.
• Faster circuits: fewer gate delays on the critical path.
• Cleaner documentation: a concise expression is easier to verify and maintain.
• Foundation of digital design: every FPGA synthesis tool runs a descendant of Quine-McCluskey (Espresso-II, and later).

Limitations and When to Use Other Tools

• 5+ variables: K-maps become visually cluttered. This tool supports up to 5 by splitting into two 4×4 maps. Beyond that, rely on the Quine-McCluskey steps or use synthesis tools like ABC / Espresso.
• Hazards and glitches: a minimal cover may contain static hazards. For hazard-free design, include redundant prime implicants — this tool marks them but does not auto-add hazard covers.
• Multi-output minimization: if several functions share variables, joint minimization (sharing gates) yields smaller hardware. This tool minimizes one function at a time.

Frequently Asked Questions

What is a Karnaugh map?

A Karnaugh map (K-map) is a visual method for minimizing Boolean expressions. Cells are arranged so that adjacent cells differ by only one variable (Gray code ordering). Grouping 1s into rectangles of size 1, 2, 4, 8, or 16 reveals the minimal Sum-of-Products expression.

What is the difference between SOP and POS?

SOP (Sum of Products) groups the 1-cells and ORs their product terms together, e.g. A'B + CD. POS (Product of Sums) groups the 0-cells and ANDs their sum terms together, e.g. (A + B')(C' + D). Both describe the same function but one form is usually more compact.

What are don't-cares and why use them?

Don't-care terms (marked X) are input combinations whose output value is irrelevant — they never occur or their value does not matter. The solver may treat them as either 0 or 1, whichever yields a simpler expression. Don't-cares often dramatically reduce the literal count.

What is a prime implicant?

A prime implicant is the largest possible group of adjacent 1-cells (power-of-two size) that cannot be expanded further. An essential prime implicant is one that uniquely covers at least one minterm and must be included in every minimal expression.

How does the Quine-McCluskey algorithm work?

Quine-McCluskey is the tabular equivalent of a K-map, suitable for many variables. It lists all minterms in binary, groups them by the number of 1s, and iteratively combines pairs that differ in exactly one bit. Terms that cannot be combined further are prime implicants. A prime implicant chart then selects the minimum cover.

How many variables does this K-map solver support?

This tool supports 2 to 5 variables. A 5-variable K-map is displayed as two adjacent 4×4 maps (one for A=0, one for A=1). Beyond 5 variables K-maps become impractical; use the Quine-McCluskey steps for larger functions.

Further Reading

• Karnaugh Map — Wikipedia
• Quine-McCluskey Algorithm — Wikipedia
• Petrick's Method — Wikipedia