▤

Karnaugh Map (K-Map) Solver

Minimal SOP · Minimal POS · Prime Implicants · Don't-Care Conditions

Click K-map cells to toggle 0 / 1 / X, then solve to get the minimal Sum of Products and Product of Sums expressions with color-coded group highlighting.

Number of Variables

Input Method

Quick Examples

K-Map Grid

Click cells to cycle: 0 → 1 → X → 0

0 = False 1 = True X = Don't Care

Full Truth Table

Rows with f=1 highlighted green · f=X highlighted yellow · f=0 white. Click K-Map cells to update.

What Is a Karnaugh Map?

A Karnaugh map (K-map) is a visual graphical method for simplifying Boolean algebra expressions, introduced by Maurice Karnaugh in 1953. It arranges all possible input combinations as cells in a grid, where adjacent cells differ in exactly one variable — a property called Gray code ordering. By identifying groups of adjacent 1-cells, engineers can directly read off a simplified Boolean expression without tedious algebraic manipulation.

K-maps are widely taught in digital electronics and computer engineering curricula as the primary hand-calculation method for minimizing Boolean functions of up to 4–5 variables. The visual grouping of cells makes the simplification process intuitive and easy to verify.

Why Gray Code Ordering Matters

The key insight of the K-map is the use of Gray code (reflected binary code) to label rows and columns. In standard binary counting, adjacent numbers can differ in multiple bits (e.g., 3 = 011 and 4 = 100 differ in 3 bits). In Gray code, consecutive values always differ in exactly one bit.

This means physically adjacent K-map cells represent logically adjacent minterms — minterms that differ in only one variable. When two such cells are both 1, the corresponding Boolean term simplifies by eliminating that variable. For example, cells AB=00 and AB=01 represent A'B' and A'B, which combine to give A' (the B variable is eliminated).

How to Read K-Map Groups

Groups in a K-map must be:

Rectangular (including wrap-around shapes)
Sized as a power of 2 (1, 2, 4, 8, or 16 cells for a 4-variable map)
As large as possible (to eliminate as many variables as possible)
Composed only of 1-cells and X (don't-care) cells

A group of 2 cells eliminates 1 variable; a group of 4 eliminates 2 variables; a group of 8 eliminates 3 variables; a group of 16 (all cells) gives f = 1. The remaining variables — those that don't change within the group — form the product term for that group.

Prime Implicants and Essential Prime Implicants

A prime implicant is a maximal group of 1s (and optionally don't-cares) that cannot be combined with any adjacent group to form a larger valid group. Finding all prime implicants is the first step in K-map minimization.

An essential prime implicant is a prime implicant that is the sole cover for at least one minterm — no other prime implicant covers that particular 1-cell. Essential prime implicants must always be included in the final minimal expression. After including all essential prime implicants, any remaining uncovered minterms are covered by selecting additional prime implicants using a greedy approach.

Don't-Care Conditions

Don't-care conditions (marked X) arise when certain input combinations either cannot physically occur (e.g., invalid BCD codes above 9) or when the output value is truly irrelevant to the application. During K-map minimization, X cells can be treated as 1s to form larger groups, but they cannot be counted as minterms that must be covered.

Properly utilizing don't-cares can dramatically simplify the final expression. For example, a 4-variable function requiring 4 terms without don't-cares might reduce to 2 terms when don't-cares are exploited.

SOP vs POS: Two Dual Forms

Every Boolean function has two standard minimal forms. The Sum of Products (SOP) form is derived by grouping 1-cells: each group contributes an AND term, and all terms are OR-ed together. The Product of Sums (POS) form is derived by grouping 0-cells: each group contributes an OR term, and all terms are AND-ed together.

Both forms implement the same logical function. In practice, SOP is implemented with an AND-OR two-level network, while POS uses OR-AND. The simpler of the two is chosen based on the number of gates required.

K-Maps vs. Quine-McCluskey Algorithm

K-maps are limited to 4–5 variables — beyond that, the visual grid becomes impractical. The Quine-McCluskey algorithm is a systematic tabular method that produces the same results as K-maps but scales to any number of variables. It is suitable for computer implementation and forms the basis of many logic synthesis tools. For 6+ variables, computer-aided tools like Espresso use heuristic algorithms to handle hundreds of variables efficiently.

Applications in Digital Circuit Design

Boolean minimization has direct real-world impact:

ASIC / FPGA design: Fewer logic terms mean fewer LUTs (Look-Up Tables) or standard cells, reducing chip area and cost
Power consumption: Fewer switching gates reduce dynamic power dissipation
Propagation delay: Simpler logic reduces the critical path delay, enabling higher clock frequencies
Hazard elimination: K-map analysis helps identify and eliminate static and dynamic hazards in combinational logic
Controller design: FSM (Finite State Machine) output logic and next-state logic are routinely minimized with K-maps

Frequently Asked Questions

What is a Karnaugh map?

A Karnaugh map (K-map) is a visual method for simplifying Boolean algebra expressions. Invented by Maurice Karnaugh in 1953, it arranges truth table values in a grid where adjacent cells differ in exactly one variable (Gray code ordering). By grouping adjacent 1s into rectangles of size 2^k, you can directly read off a minimal Sum of Products expression without algebraic manipulation.

What is the difference between SOP and POS forms?

SOP (Sum of Products) is a Boolean expression formed by OR-ing together AND terms (minterms). For example: AB' + BC + A'C. POS (Product of Sums) is formed by AND-ing together OR terms (maxterms). For example: (A+B')(B+C)(A'+C). SOP is derived by grouping 1-cells in the K-map; POS is derived by grouping 0-cells. Both forms represent the same Boolean function.

What are don't-care conditions in K-maps?

Don't-care conditions (marked X) are input combinations that either cannot occur in practice or whose output value doesn't matter. In K-map minimization, X cells can be treated as either 0 or 1 — whichever allows larger groupings. Using don't-cares can significantly reduce the complexity of the minimal expression, but they cannot be used as the sole reason a group is needed (only 1-cells must be covered).

What is a prime implicant?

A prime implicant is a group of 1s (and optionally don't-cares) in a K-map that is as large as possible — it cannot be combined with another adjacent group to form a larger valid group. An essential prime implicant is one that is the only prime implicant covering at least one minterm. Essential prime implicants must always be included in the minimal cover.

How do wrap-around groups work in K-maps?

K-maps use Gray code ordering so that the top and bottom rows are logically adjacent, as are the left and right columns. This means cells at opposite edges can form valid groups. For example, in a 4-variable K-map, the four corner cells (minterms 0, 2, 8, 10) form a valid group of 4. These wrap-around groups are just as valid as any other grouping and often yield important prime implicants.

When should I use Quine-McCluskey instead of K-maps?

K-maps are practical and visual for up to 4–5 variables. For 6 or more variables, the map becomes too large for human inspection. The Quine-McCluskey algorithm (tabular method) is algorithmic and works for any number of variables, making it suitable for computer-aided design tools. For 5+ variables, use Quine-McCluskey or modern SAT-based logic synthesis tools like Espresso.

What is Boolean algebra minimization used for?

Boolean algebra minimization reduces the complexity of digital logic circuits. A simpler Boolean expression means fewer logic gates, which translates to lower chip area, reduced power consumption, fewer propagation delays, and lower manufacturing cost. It is fundamental in digital circuit design, FPGA programming, CPU design, and any application involving combinational logic synthesis.