K-Map Solver

About this tool

K-Map Solver simplifies boolean logic equations using 2-variable, 3-variable, and 4-variable Karnaugh maps. By organizing minterms in adjacency Gray-code grids ($00, 01, 11, 10$), the solver groups contiguous powers of two ($1, 2, 4, 8, 16$) to eliminate redundant literals. It computes both Minimal Sum of Products (SOP) and Minimal Product of Sums (POS), supports Don’t Care conditions ($X$), and provides full prime implicant grouping breakdowns for digital circuit optimization.

When to use it

• Minimize combinational digital logic circuits to reduce physical gate count and propagation delay
• Check homework and exam problems for Computer Architecture and Digital Systems coursework
• Solve boolean minimization problems with Don’t Care states ($d$)
• Compare canonical Sum of Products (SOP) and Product of Sums (POS) implementations
• Verify logic simplification proofs derived via boolean algebra theorems or De Morgan’s laws

How to use it

To solve a Karnaugh map

1. Select the Number of variables:
   • 2 variables ($A, B$): 4 cells ($2 \times 2$ grid).
   • 3 variables ($A, B, C$): 8 cells ($2 \times 4$ grid).
   • 4 variables ($A, B, C, D$): 16 cells ($4 \times 4$ grid).
2. Enter values into the map using either of two methods:
   • Interactive grid: Click any cell to cycle through values: 0 $\rightarrow$ 1 $\rightarrow$ X (Don’t care) $\rightarrow$ 0.
   • Text input: Type comma-separated minterm numbers ($\Sigma m$) and optional don’t cares ($d$), then click Fill K-map from text.
3. The solver computes the minimal boolean expressions in real time:
   • Minimal Sum of Products (SOP): Grouping of 1s and available Xs.
   • Minimal Product of Sums (POS): Grouping of 0s and available Xs.
4. Review the Prime Implicant Groupings table below the expressions to see the binary cover and covered decimal minterms for each rectangular loop.
5. Click Copy SOP or Copy POS to copy the simplified expression to your clipboard.

Questions

Why does a Karnaugh map use Gray code ordering?

Standard binary counting sequences ($00, 01, 10, 11$) change two bits between $01$ and $10$. Karnaugh maps use Gray code sequences:

$00 \rightarrow 01 \rightarrow 11 \rightarrow 10$

In Gray code, adjacent cells differ by exactly one bit (Hamming distance of 1). This ensures that any adjacent rectangular group of $2^k$ cells shares $n - k$ identical literal states, allowing the differing variable to be factored out via the boolean identity:

$XY + XY' = X(Y + Y') = X(1) = X$

How are Don’t Care conditions ($X$) utilized?

Don’t care conditions represent input combinations that can never occur in normal operation or whose output value does not affect system correctness (such as invalid BCD digits $10$ through $15$).

• When grouping for Sum of Products (SOP), an $X$ is included in a loop of 1s if it helps form a larger rectangular power-of-two group (reducing literal count). Otherwise, it is ignored.
• When grouping for Product of Sums (POS), an $X$ is similarly included if it expands a group of 0s.

What are Essential Prime Implicants?

• A Prime Implicant is a maximal rectangular grouping of 1s (of size $1, 2, 4, 8, \dots$) that cannot be merged into any larger power-of-two group.
• An Essential Prime Implicant is a prime implicant that covers at least one minterm $m_k$ that is not covered by any other prime implicant. Essential prime implicants must be included in every minimal SOP solution.