Digital Logic & Microprocessor — Digital Logic, NEC licence examination syllabus (Nepal Engineering Council).
Karnaugh Maps: simplification by looking, not algebra
Boolean algebra needs you to spot the trick. A K-map makes the answer visible.
Start here: why a grid instead of algebra
Boolean algebra can simplify an expression, but you have to spot which law applies, and it is easy to miss a step and stop early.
A Karnaugh map turns the same job into something visual: draw the 1s in a grid, circle the groups, read off the answer. No law-spotting, and you can see when you are finished.
The trick that makes it work
The map is a truth table folded into a grid — but the rows and columns are deliberately arranged so that neighbouring squares differ by only one bit.
That is the whole idea. If two neighbouring squares both hold a 1, then that one differing variable does not matter — the output is 1 whether it is 0 or 1 — so it drops out of the expression. Circling a pair is how you delete a variable.
💡 This is why the column headings run 00, 01, 11, 10 and not 00, 01, 10, 11. The counting order would put 01 next to 10, which differ by two bits, and the neighbour trick would break. The odd-looking order is the entire mechanism.
The rules for circling
⭕ How to group
Powers of two onlyGroups of 1, 2, 4, 8 — never 3, never 6.
Bigger is betterEach doubling removes one more variable, so always take the largest group you can.
Overlapping is fineA 1 may be in several groups. Reusing it costs nothing.
Edges wrap aroundThe left column touches the right, and the top row touches the bottom, as if the map were rolled into a tube.
Cover every 1And when they are all covered, stop.
💡 Reading a group: look at which variables stay the same across every square in it. Those go into the term. Any variable that changes has been eliminated — that is the simplification you came for.
Algebraic simplification works, but it depends on noticing that you can duplicate a term, or that consensus applies. Miss it and you carry redundant gates. Maurice Karnaugh's 1953 insight was to lay the truth table out in a grid where adjacent cells differ by exactly one variable — so any pair you can circle simplifies automatically, and the eye finds pairs faster than algebra does.
The Gray-code ordering is the whole trick
Columns and rows are labelled in GRAY CODE — 00, 01, 11, 10
— NOT in binary counting order 00, 01, 10, 11.
Why: in Gray code, neighbours differ in exactly ONE bit.
So two adjacent cells always share all variables but one,
and that one variable cancels:
A'BC + A'BC' = A'B(C + C') = A'B
Circle two adjacent 1s → one variable disappears.
Circle four → two variables disappear.
Circle eight → three variables disappear.
Group of 2ⁿ cells eliminates n variables.
The grouping rules
1. Groups must contain 2ⁿ cells: 1, 2, 4, 8, 16 — never 3,
5, 6 or 7.
2. Groups must be rectangular (no L-shapes or diagonals).
3. Make groups AS LARGE AS POSSIBLE — bigger groups mean
fewer variables in the term.
4. Groups MAY OVERLAP. Reusing a 1 costs nothing.
5. The map WRAPS AROUND: leftmost column is adjacent to
rightmost; top row is adjacent to bottom. All four
corners are mutually adjacent.
6. Every 1 must be covered by at least one group.
7. Use the FEWEST groups that cover all the 1s.
Reading a group: keep only the variables that stay CONSTANT
across the whole group. Constant 1 → plain; constant 0 →
barred; changes → drop it.
Rule 5 is what students forget and examiners exploit. A 4-variable map is topologically a torus, not a flat sheet: the four corner cells (m₀, m₂, m₈, m₁₀) form a valid group of four. If a question's map has 1s in all four corners, that single group is the intended answer — spotting it separates full marks from half.
Worked numerical 1 — three-variable K-map
Simplify F = Σm(0,2,4,5,6) using a K-map.
3-variable map, columns in Gray code BC = 00,01,11,10:
BC=00 01 11 10
A=0 | 1 0 0 1 (m0, m1, m3, m2)
A=1 | 1 1 0 1 (m4, m5, m7, m6)
Place 1s at m0,m2,m4,m5,m6 as shown.
GROUPS:
Group 1 — the whole BC=00 column (m0, m4): A changes,
B=0, C=0 constant → B'C'
Group 2 — the whole BC=10 column (m2, m6): A changes,
B=1, C=0 constant → BC'
Group 3 — the A=1 row, cells m4,m5 : A=1, B=0 constant,
C changes → AB'
Wait — can we do better? Groups 1 and 2 both have C'=0.
Combine them: m0, m2, m4, m6 all have C = 0.
That is a group of FOUR → C'
Revised:
Group A — m0, m2, m4, m6 (C=0 everywhere) → C'
Group B — m4, m5 (A=1, B=0) → AB'
F = C' + AB'
Cost: 1 inverter + 1 AND + 1 OR = 3 gates.
Compare canonical SOP: 5 three-input ANDs + 1 OR = 6 gates.
Verify m5 (A=1,B=0,C=1): C'=0, AB'=1 → F=1 ✔
Verify m7 (A=1,B=1,C=1): C'=0, AB'=0 → F=0 ✔ (m7 not listed)
Verify m1 (A=0,B=0,C=1): C'=0, AB'=0 → F=0 ✔
Worked numerical 2 — four-variable with corner wrap
Simplify F = Σm(0,2,8,10,5,7,13,15).
4-variable map (rows AB, columns CD, both Gray-coded):
AB\CD 00 01 11 10
00 | 1 0 0 1 (m0 m1 m3 m2)
01 | 0 1 1 0 (m4 m5 m7 m6)
11 | 0 1 1 0 (m12 m13 m15 m14)
10 | 1 0 0 1 (m8 m9 m11 m10)
GROUP 1 — the FOUR CORNERS: m0, m2, m8, m10
In all four: B=0 and D=0 (A and C both change)
→ B'D'
This uses the wrap-around in both directions.
GROUP 2 — the middle block: m5, m7, m13, m15
In all four: B=1 and D=1 (A and C both change)
→ BD
F = B'D' + BD
Notice this is XNOR: F = (B ⊕ D)' — output is 1 when B and
D are equal. The K-map made that structure visible.
Cost: 2 two-input ANDs + 1 OR + 2 inverters = 5 gates,
or a single XNOR gate.
Compare canonical SOP: 8 four-input ANDs + 1 eight-input OR
= 9 gates plus inverters. The K-map found an 8:1 reduction.
Worked numerical 3 — don't-care conditions
A BCD-to-something decoder has inputs 0–9 valid; 10–15 never occur. Simplify F = Σm(1,3,5,7,9) with don't-cares d(10,11,12,13,14,15).
Mark don't-cares as X — you may treat each as 0 OR 1,
whichever gives bigger groups.
AB\CD 00 01 11 10
00 | 0 1 1 0 (m0 m1 m3 m2)
01 | 0 1 1 0 (m4 m5 m7 m6)
11 | X X X X (m12 m13 m15 m14)
10 | 0 1 X X (m8 m9 m11 m10)
WITHOUT using don't-cares:
m1,m3,m5,m7 group as A'D (A=0, D=1)
m9 alone needs AB'C'D
F = A'D + AB'C'D → messy
WITH don't-cares — treat m11, m13, m15 as 1:
Now the entire CD=01 and CD=11 columns are 1 or X:
m1,m3,m5,m7,m9,m11,m13,m15 → all have D = 1
One group of EIGHT!
F = D
The circuit is a single wire. Don't-cares turned a
two-term expression into nothing at all.
This is why BCD circuits are so much simpler than they look:
six of sixteen input combinations never happen, giving huge
freedom in grouping.
Worked numerical 4 — POS from a K-map
For F = Σm(0,1,2,5,8,9,10), find the minimal POS by grouping the ZEROS.
AB\CD 00 01 11 10
00 | 1 1 0 1 (m0 m1 m3 m2)
01 | 0 1 0 0 (m4 m5 m7 m6)
11 | 0 0 0 0 (m12 m13 m15 m14)
10 | 1 1 0 1 (m8 m9 m11 m10)
Group the ZEROS to get F', then complement.
Zeros at: m3, m4, m6, m7, m12, m13, m14, m15
GROUP 1 — m3, m7, m11, m15? No, m11 and m15 are 0 too...
check: CD=11 column is m3,m7,m15,m11 → all 0 ✔
In all four: C=1, D=1 → contributes CD to F'
GROUP 2 — m4, m6, m12, m14 : B=1, D=0 → BD'
GROUP 3 — m12, m13, m14, m15 : A=1, B=1 → AB
F' = CD + BD' + AB
Complement using De Morgan:
F = (CD + BD' + AB)'
= (CD)'·(BD')'·(AB)'
= (C' + D')(B' + D)(A' + B)
POS form: F = (C'+D')(B'+D)(A'+B)
Cost: 3 two-input ORs + 1 three-input AND = 4 gates
(plus inverters)
Verify m0 (0000): (1+1)(1+0)(1+0) = 1·1·1 = 1 ✔
Verify m3 (0011): (0+0)(1+1)(1+0) = 0·1·1 = 0 ✔
💡 Exam angle: K-maps are the single highest-value topic in this section — expect 8–10 marks. Draw the grid with Gray-code labels and mark the minterm number in each cell; that alone earns marks. Always check for the corner group and edge wrap-around. Treat don't-cares as whatever makes groups bigger. And state the gate-count saving versus canonical form — it shows you understand why you did the work.
Syllabus points
Truth table → K-map
2/3/4-variable simplification (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.