What is a Karnaugh Map?

A Karnaugh map (K-map) is a visual method for simplifying Boolean expressions. It arranges all possible input combinations in a grid where adjacent cells differ by exactly one variable (Gray code ordering). By grouping 1s together, you can read off a simplified Sum of Products (SOP) expression directly — without applying algebraic laws.

K-maps are faster and less error-prone than algebraic simplification for expressions with 2–4 variables.

2-Variable K-Map

A 2-variable K-map (inputs A and B) has 4 cells:

Each cell corresponds to a minterm. Enter 0 or 1 from your truth table, then group the 1s.

3-Variable K-Map

A 3-variable K-map (inputs A, B, C) has 8 cells. The column order uses Gray code (00, 01, 11, 10) so adjacent cells differ by one bit:

4-Variable K-Map

A 4-variable K-map (A, B, C, D) has 16 cells. Both rows and columns use Gray code:

Grouping Rules

• Groups must contain only 1s (no 0s).
• Group sizes must be a power of 2: 1, 2, 4, 8, 16.
• Groups must be rectangular (including wrap-around: the map is a torus — top wraps to bottom, left wraps to right).
• Make groups as large as possible — larger groups → more variables cancel → simpler expression.
• Every 1 must be covered by at least one group.
• Groups may overlap — use the same 1 in multiple groups if it makes groups larger.
• Use the minimum number of groups needed to cover all 1s.

Reading a Group

For each group, identify which variables are the same across ALL cells in the group. Variables that change within the group are eliminated. The product term uses only the constant variables.

• Variable is 0 in all cells of group → use it complemented (¬A)
• Variable is 1 in all cells of group → use it uncomplemented (A)
• Variable changes → eliminate it from the term

The final simplified expression is the OR of all group terms (Sum of Products).

Worked Example

Simplify the expression with truth table: A=0,B=0,C=0 → 0; A=0,B=0,C=1 → 1; A=0,B=1,C=0 → 1; A=0,B=1,C=1 → 1; A=1,B=0,C=0 → 0; A=1,B=0,C=1 → 0; A=1,B=1,C=0 → 1; A=1,B=1,C=1 → 1

Fill the 3-variable K-map:

Group 1: Top row BC=01, BC=11, BC=10 (3 cells with 1 — not a power of 2). Try: {(A=0,BC=01),(A=0,BC=11),(A=0,BC=10)} → ¬A · (B+C)... Let's use power-of-2 groups:

Group 1 (size 4): The four cells where B=1 (all BC=01,11 in A=0 and BC=11,10 in A=1): B=1 in all → keep B. A varies (0 and 1) → eliminate A. C varies → eliminate C. Result: B

Group 2 (size 2): Cells (A=0,BC=01) and (A=0,BC=11): A=0 in all → ¬A. B varies → eliminate. C=1 in all → C. Result: ¬A·C

Check: Group 1 covers all B=1 cells. Group 2 covers (A=0,B=0,C=1) which wasn't in Group 1. All 1s covered.

Simplified expression: F = B + ¬A·C

Don't-Care Conditions

Sometimes certain input combinations are impossible (e.g. BCD digits only go 0–9, states 10–15 never occur). These are marked X (don't-care) in the K-map. You may treat an X as 1 (include in a group to make it larger) or 0 (ignore it) — whichever gives the simplest expression.