Karnaugh maps for 2, 3 and 4 variables: adjacency and grouping

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What is AB + AB'? from Lesson 3.1.2
• Canonical SOP of F(A, B, C) = A + B'C? from Lesson 3.2.1
• In Gray code, how many bits change between neighbours? from Lesson 1.2.1

1 · The Hook

🎣

Simplifying with Boolean laws needs luck: you must spot which law to apply. Maurice Karnaugh found a picture that does the spotting for you. Lay the truth table out as a grid where neighbouring cells differ in exactly one variable; then every pair, square or strip of 1s you can circle is a simplification you can read off directly. GATE asks a K-map question in almost every paper.

2 · Predict First

🤔

Two neighbouring cells hold the minterms A'BC and A'BC'. What single term covers both?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A'BC + A'BC' = A'B(C + C') = A'B. The variable that changes (C) disappears.

🗣️

In plain words

A Karnaugh map (K-map) is a truth table drawn as a grid. Rows and columns are labelled in Gray-code order (00, 01, 11, 10), so any two cells side by side differ in one variable. Circle groups of 1s whose size is a power of two (1, 2, 4, 8, …) in a rectangle. Inside a group, any variable that changes drops out; the variables that stay fixed form the group's product term.

1. Layouts

• 2 variables: 2 × 2 (A rows, B columns).
• 3 variables: 2 × 4 (A rows; BC columns 00, 01, 11, 10).
• 4 variables: 4 × 4 (AB rows 00, 01, 11, 10; CD columns 00, 01, 11, 10).

4-variable cell numbers (row AB, column CD):

Note the order 3 before 2, and rows 12–15 before 8–11 (Gray code).

2. Adjacency

Two cells are adjacent if they differ in one variable. That includes wrap-around: the left and right edges are neighbours, the top and bottom edges are neighbours, and the four corners form one group of 4.

3. Grouping rules

• A group is a rectangle of 1, 2, 4, 8 or 16 cells (a power of 2), possibly wrapping around the edges.
• It contains only 1s.
• A group of 2ᵏ cells removes k variables: write only the variables that are constant across the group (plain if 1, primed if 0).
• To minimise: make every group as large as possible, use as few groups as possible, cover every 1 at least once. Groups may overlap.

4. Worked example

F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).

• The four corners 0, 2, 8, 10: B = 0 and D = 0 throughout → B'D'.
• The centre square 5, 7, 13, 15: B = 1 and D = 1 → BD.
• F = BD + B'D' (which is B ⊙ D).

4 · Visual

F = Σm(0, 2, 5, 7, 8, 10, 13, 15). The four corners are one group (wrap-around both ways): F = BD + B'D'.

F = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) = C' + A'D' + BD'. The 8-cell group removes three variables.

5 · Worked Examples

Example 1 Easy

In a 4-variable map, a group covers cells 8, 9, 10, 11 (the bottom row). What term is it?

Solution

Row AB = 10 throughout, C and D change → AB'.

Example 2 Medium

Minimise F(A, B, C) = Σm(1, 3, 4, 5, 6, 7).

Solution

Column pairs with C = 1 (1, 3, 5, 7) → C; the whole A = 1 row (4, 5, 6, 7) → A. F = A + C.

Example 3 GATE

Minimise F(A, B, C, D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). How many literals are in the minimal SOP?

Solution

C' + A'D' + BD' → 1 + 2 + 2 = 5 literals.

6 · GATE Traps

⚠️

• Columns go 00, 01, 11, 10: cell 3 sits before cell 2.
• Corners and opposite edges are adjacent; don't miss wrap-around groups.
• Group sizes must be powers of 2 and rectangular (no L-shapes, no groups of 3 or 6).
• Bigger groups are always better: a group of 4 is cheaper than two groups of 2 covering the same cells.

7 · Memory Hook

🧠

"Gray-code the edges, wrap the borders, circle powers of two, keep what doesn't change."

8 · Connect the Dots

Grouping by eye works, but which groups are really needed? The next lesson names them: prime implicants and essential prime implicants, and shows how to get the minimal SOP (and POS) without guessing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markReading a group

In a 4-variable K-map (AB rows, CD columns), a group covers cells 1, 3, 9, 11. Its term is:

• (A) A'D
• (B) B'C
• (C) CD
• (D) B'D

Q2NAT1 markLiterals removed

A group of 8 cells in a 4-variable K-map leaves how many literals in its term?

Numerical answer: ________

Q3MCQ2 marksMinimise

F(A, B, C, D) = Σm(0, 2, 8, 10). The minimal SOP is:

• (A) B'D'
• (B) B'C'D'
• (C) BD
• (D) A'B'D'

Q4NAT2 marksMinimise

F(A, B, C, D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). How many product terms are in the minimal SOP?

Numerical answer: ________

Q5MCQ1 markLayout

In a 3-variable K-map with A as rows and BC as columns, which minterm is in row A = 1, column BC = 10?

• (A) m₄
• (B) m₆
• (C) m₅
• (D) m₇

10 · Rule Card

• K-map rows and columns in Gray order (00, 01, 11, 10); adjacent cells differ in one variable; edges and corners wrap.
• Groups: rectangles of 2ᵏ cells containing only 1s; a 2ᵏ group drops k variables.
• Term of a group: the variables that stay constant (1 → plain, 0 → primed).
• Minimise: largest possible groups, fewest groups, every 1 covered; overlaps allowed.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Karnaugh map2-, 3- and 4-variable layoutsGray-code labellingadjacency and wrap-aroundcorner groupsgroup sizes as powers of tworeading a group's termminimisation by grouping

12 · Answer Vault