Solve 2, 3, and 4 variable Karnaugh maps instantly. Supports Sum of Products (SOP), Product of Sums (POS), and don't-care conditions with Gray code adjacency, step-by-step prime implicant derivation, and formal truth-table equivalence verification.
Variables:
Form:
⚠️Invalid input detected.
💡 Click any cell to cycle: 0 → 1 → X (Don't-Care) → 0
Minimized SOP Expression
f = 0
Original Canonical Literals: 0 → Minimized: 0(0% reduction)
✓ Verified Truth Table Match
Selected Prime Implicants / Groups:
📝 Step-by-Step Mathematical Derivation
Digital Logic & VLSI Engineering • Clean Advertisement Area
What is a Karnaugh Map (K-Map)?
A Karnaugh Map (K-Map) is a specialized visual diagram used in digital logic design to simplify Boolean algebraic expressions into minimal two-level Sum of Products (SOP) or Product of Sums (POS) forms. Developed by telecommunications engineer Maurice Karnaugh at Bell Laboratories in 1953 as a refinement of Edward Veitch's earlier diagrams, the K-map translates multi-dimensional truth tables into a planar grid.
In algebraic simplification, finding common terms requires applying Boolean theorems such as $X \cdot Y + X \cdot Y' = X(Y + Y') = X$. When expressions have multiple variables, spotting these adjacencies by hand becomes tedious and prone to human error. A K-map solves this by arranging cells such that any two adjacent grid cells differ by exactly one variable.
Why Gray Code Ordering is Essential
Standard binary counting (00 → 01 → 10 → 11) is unsuitable for K-map axes because moving from 01 to 10 changes two variables simultaneously ($A$ changes from 0 to 1, and $B$ changes from 1 to 0). This would destroy the single-variable adjacency property.
Instead, K-maps arrange row and column indices in Gray Code sequence:
00 → 01 → 11 → 10
Notice that between each adjacent pair:
From 00 to 01: only the second bit changes.
From 01 to 11: only the first bit changes.
From 11 to 10: only the second bit changes.
From 10 back to 00 (wraparound): only the first bit changes.
Because each step represents a Hamming distance of 1, grouping two adjacent cells algebraically eliminates the single variable whose value differs between them.
Rules for K-Map Grouping (Prime Implicants)
To achieve a mathematically minimal Boolean equation, follow these six universal engineering rules:
Group Sizes Must Be Powers of Two: Valid groups can contain only $1, 2, 4, 8,$ or $16$ cells ($2^k$). Groups of 3, 5, 6, or 7 cells are invalid because their variables cannot be cleanly factored out.
Groups Must Be Rectangular or Square: Groups must be $1 imes 1, 1 imes 2, 2 imes 1, 2 imes 2, 1 imes 4, 4 imes 1, 2 imes 4, 4 imes 2,$ or $4 imes 4$. L-shaped, diagonal, or T-shaped groups are not permitted.
Always Select the Largest Possible Groups: A larger group eliminates more variables:
A group of 1 cell eliminates 0 variables (retains all $n$ literals).
A group of 2 cells eliminates 1 variable ($n - 1$ literals).
A group of 4 cells eliminates 2 variables ($n - 2$ literals).
A group of 8 cells eliminates 3 variables ($n - 3$ literals).
A group of 16 cells eliminates 4 variables (simplifies to $1$).
Groups May Wrap Around Opposite Edges: The top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column (toroidal topology).
Groups May Overlap: Minterms already covered by one group can be included in another group if doing so creates a larger group that reduces overall literal count.
Every Required Minterm (1) Must Be Covered: Continue selecting groups until no unassigned 1s remain.
Wraparound Adjacency & The Four Corners Group
One of the most frequently tested concepts in university exams and VLSI technical interviews is edge and corner wraparound.
In a 4-variable K-map ($4 imes 4$ grid):
Cell $m_0$ (0000) is adjacent to cell $m_2$ (0010) across the horizontal boundary ($D$ is eliminated).
Cell $m_0$ (0000) is adjacent to cell $m_8$ (1000) across the vertical boundary ($A$ is eliminated).
The Four Outer Corners—$m_0$ (0000), $m_2$ (0010), $m_8$ (1000), and $m_{10}$ (1010)—form a single, contiguous group of 4:
m(0, 2, 8, 10) → B'D'
Here, $A$ varies ($0$ in row 00, $1$ in row 10) and $C$ varies ($0$ in col 00, $1$ in col 10), leaving only $B = 0$ ($B'$) and $D = 0$ ($D'$).
SOP (Sum of Products) vs. POS (Product of Sums)
Any Boolean logic function can be expressed in either of two canonical forms:
Characteristic
Sum of Products (SOP)
Product of Sums (POS)
Focus Cells
Groups minterms (cells with output 1).
Groups maxterms (cells with output 0).
Mathematical Form
OR of AND terms: $f = AB + CD'$
AND of OR terms: $f = (A + B')(C' + D)$
Literal Interpretation
Variable = 1 → $A$ Variable = 0 → $A'$
Variable = 0 → $A$ Variable = 1 → $A'$
Hardware Gate Equivalent
Two-level NAND-NAND gate network.
Two-level NOR-NOR gate network.
When to Prefer
When truth table has fewer 1s than 0s.
When truth table has fewer 0s than 1s.
Understanding Don't-Care Conditions (X)
In many practical digital circuits, certain input combinations are physically impossible or their resulting output has no impact on system behavior. These are designated as Don't-Care conditions (denoted by $X$ or $d$).
Classic Example: BCD to 7-Segment Decoder: Binary Coded Decimal (BCD) uses 4 bits to encode decimal digits 0 through 9 ($0000_2$ to $1001_2$). The remaining six binary combinations—10 ($1010_2$) through 15 ($1111_2$)—never occur in valid BCD streams.
By marking minterms $m_{10}, m_{11}, m_{12}, m_{13}, m_{14}, m_{15}$ as don't-cares ($d$), the K-map solver treats them as wildcards:
If setting an $X$ to 1 allows an adjacent group of 1s to expand from size 2 to size 4, it is included, eliminating an extra literal.
If an $X$ does not assist in expanding any group of 1s, it is simply treated as 0 and ignored.
A group made entirely of don't-cares is never formed, because it does not cover any actual required minterms.
Common K-Map Mistakes to Avoid
Creating Groups That Aren't Powers of Two: Grouping 3 or 6 cells is a frequent beginner error. Group counts must strictly be 1, 2, 4, 8, or 16.
Overlooking Wraparound Edges & Corners: Forgetting that column 00 wraps to column 10, or missing the 4-corner group $m(0, 2, 8, 10)$, results in redundant product terms.
Selecting Redundant Prime Implicants: Including a group whose minterms are already completely covered by other essential groups adds unnecessary hardware gates.
Writing Complements Backwards in POS: In SOP, 0 corresponds to $A'$; in POS, 0 corresponds to $A$ and 1 corresponds to $A'$.
Misinterpreting Gray Code Axis Labels: Filling cells using standard binary row order ($00 o 01 o 10 o 11$) instead of Gray code ($00 o 01 o 11 o 10$) invalidates all neighbor adjacencies.
Practical Solved K-Map Examples
Step through these 7 verified examples covering 2, 3, and 4 variables in both SOP and POS forms:
2-Variable • SOP
Example 1: OR Gate Function
F(A,B) = Σm(1, 2, 3)
Group 1: m(1, 3) → B
Group 2: m(2, 3) → A f = A + B
2-Variable • POS
Example 2: NOR Gate in POS
F(A,B) = ΠM(1, 2, 3)
Maxterm m(0) is 1.
Maxterms 1, 2, 3 are 0. f = (A' + B')(A' + B)(A + B') → (A')(B')
3-Variable • SOP with Don't Care
Example 3: Column Absorption
F(A,B,C) = Σm(1, 3, 5, 7) + d(0, 2)
Group m(1, 3, 5, 7) forms a group of 4.
Both rows A=0,1 covered; BC cols 01, 11 covered. f = C
3-Variable • POS
Example 4: 3-Variable POS Form
F(A,B,C) = ΠM(0, 2, 4, 6)
0s located at columns with C=0.
All 4 cells form a group of 4 in POS. f = (C)
4-Variable • 4 Corners
Example 5: Four Corner Wraparound
F(A,B,C,D) = Σm(0, 2, 8, 10)
Corners wrap vertically & horizontally.
A and C vary; B=0 and D=0. f = B'D'
4-Variable • BCD Segment 'a'
Example 6: BCD 7-Segment Decoder
F = Σm(0,2,3,5,6,7,8,9) + d(10..15)
Don't-cares allow four large groups of 4 and 8. f = A + C + BD + B'D'
4-Variable • POS
Example 7: Odd Minterms in POS
F(A,B,C,D) = ΠM(1,3,5,7,9,11,13,15)
Maxterms 0 across all odd addresses where D=1.
Forms an 8-cell POS group. f = (D')
Frequently Asked Questions (FAQ)
Q1. What is a Karnaugh map (K-map)?
A Karnaugh map (K-map) is a graphical method invented by Maurice Karnaugh in 1953 to simplify Boolean algebra expressions without algebraic manipulation. It organizes truth table outputs into a two-dimensional grid arranged in Gray code order, where physically adjacent cells differ by exactly one binary variable.
Q2. Why is Gray code used in Karnaugh maps?
Gray code ensures that between any two horizontally or vertically adjacent cells, exactly one variable changes state (Hamming distance = 1). This topological adjacency directly embodies the Boolean theorem A·B + A·B' = A(B + B') = A, allowing adjacent minterms to combine and eliminate the changing variable.
Q3. What is the difference between SOP and POS minimization in K-maps?
Sum of Products (SOP) groups cells with value 1 (minterms) to produce product AND-terms OR-ed together, matching a two-level NAND-NAND circuit. Product of Sums (POS) groups cells with value 0 (maxterms) to produce sum OR-terms AND-ed together, matching a NOR-NOR circuit.
Q4. How do don't-care conditions (X) help in K-map simplification?
Don't-care conditions (marked X) represent input combinations that can never physically occur or whose output is irrelevant. In K-map simplification, don't-cares can be optionally included in groups of 1s (or 0s) to create larger rectangles (powers of 2), which eliminates more variables and produces smaller Boolean expressions. However, groups composed entirely of don't-cares are omitted.
Q5. What are the rules for forming valid K-map groups?
1. Group sizes must be exact powers of two (1, 2, 4, 8, 16 cells). 2. Groups must be rectangular or square. 3. Groups may wrap around opposite edges and the four outer corners. 4. Groups may overlap to achieve maximal coverage. 5. Every required minterm (or maxterm) must be covered by at least one group. 6. Always choose the largest possible groups to eliminate the maximum number of literals.
Q6. How does wraparound adjacency work in 4-variable K-maps?
Because Gray code sequences are circular (00 is adjacent to 10), the top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column. Crucially, the four outer corner cells (m0, m2, m8, m10) are all mutually adjacent and form a single valid group of 4, simplifying to B'D'.
Q7. What is an essential prime implicant (EPI)?
A prime implicant is a maximal valid group that cannot be combined into any larger group. An essential prime implicant is a prime implicant that uniquely covers at least one minterm that is not covered by any other prime implicant. Essential prime implicants must be included in every minimal solution.
Q8. Can multiple minimal expressions exist for the same K-map?
Yes. When uncovered minterms can be covered by different combinations of non-essential prime implicants of equal size, multiple equally minimal Boolean expressions exist. Both solutions have identical literal counts and produce identical truth table outputs.
Explore Related VLSI & Digital Engineering Tools
Advance your digital logic design, transistor simulation, and hardware verification skills: