← 🧮 Boolean Algebra, Canonical Forms & K-Maps
Subtopic 3 of 5

2.3K-map minimisation with don't cares

The idea

A Karnaugh map is a truth table drawn so that neighbouring cells differ in one variable. Grouping neighbouring 1s in powers of two removes variables and gives the minimal sum of products.

Think of it like this: A map where friends live next door: grouping neighbours shows what they have in common.

Why it exists

K-map minimisation with don't-cares is the single most reliable Digital Logic question in GATE.

How it works

  1. Fill the map in Gray order (00, 01, 11, 10) so that edges wrap around.
  2. Circle the largest rectangles of 1s of size 1, 2, 4, 8 or 16, using X cells when they help.
  3. Each group of 2ᵏ cells drops k variables; read the remaining literals.
  4. Every 1 must be covered; essential prime implicants are always in the answer.

Worked example: Σm(1,3,7,11,15) with d(0,2,5)

Group 3, 7, 11, 15 with column CD = 11: CD. Group 1, 3 and the don't cares 0, 2, 5 with A′ and D = 1: A′D. F = CD + A′D.

Now play with it

  • →Press the first preset and check the minimal SOP matches.
  • →Try the corner wrap-around preset: the four corners form one group B′D′.

Click a cell to cycle 0 → 1 → X (don't care). Rows and columns are in Gray order, so neighbours (including the wrap-around edges) differ in one bit.

AB\CD00011110
000X11312X
01405X7160
11120130151140
108090111100
Minimal SOPCD + A'D
Minimal POS(D)(A' + C)
Prime implicants3
Essential1
CD covers 3, 7, 11, 15 (essential)
A'D covers 1, 3, 5, 7

No static-1 hazard in this SOP cover: every pair of adjacent 1s shares a group.

Check yourself

F = Σm(0,2,8,10) of four variables has the minimal SOP

Remember: Group 1s (or 0s for POS) in powers of two; edges wrap; X cells are optional helpers.
Exam notes (the dense version)

A K-map lists the truth table in Gray-code order so physical neighbours differ in one variable (edges wrap around). Group 1s (for SOP) in rectangles of size 1, 2, 4, 8, 16 (powers of two), as large as possible; a group of 2ᵏ cells eliminates k variables. Don't-care cells may be used to enlarge groups but need not be covered. Prime implicant: a group that cannot be enlarged. Essential: covers a 1 that no other prime implicant covers. For POS, group the 0s and complement the result of each group. The Quine–McCluskey method does the same by tabulation.

Previous year questions: Boolean Algebra, Canonical Forms & K-Maps (27)

PYQs are grouped by topic, so this is the full set for Boolean Algebra, Canonical Forms & K-Maps; try the ones that match this subtopic. Open all 27 on the topic page.