ece

K-Maps & Boolean Minimization

Simplifying Boolean functions using Karnaugh maps — SOP/POS, don't-cares, prime implicants and the traps interviewers probe.

QualcommTexas InstrumentsIntelISRO

Key formulas

(A·B)' = A' + B' and (A + B)' = A'·B'
De Morgan's laws: The single most-used identity in gate-level simplification and NAND/NOR conversion.
f = Σm(1,3,5) → group adjacent minterms → f = A'C + AC'… (fewer literals)
Canonical ↔ simplified: Interviewers often start from a minterm list and ask you to minimise it on the spot.

▸Groups must be powers of 2 (1, 2, 4, 8…) and can wrap around map edges — the map is cyclic.
▸Larger groups give simpler terms: a group of 8 drops 3 literals, a group of 4 drops 2.
▸SOP groups the 1s (minterms); POS groups the 0s (maxterms) — both realise the same function.
▸Don't-care (X) cells may be used inside a group to enlarge it, but never group X alone.
▸A redundant (non-prime) implicant adds cost without coverage — drop it.
▸XOR cannot be minimised by K-map adjacency: A⊕B has no adjacent groupings.

Aspect	SOP (Sum of Products)	POS (Product of Sums)
Group on map	1s (minterms)	0s (maxterms)
Basic gate	AND into OR	OR into AND
NAND / NOR friendly	Two-level NAND	Two-level NOR
Typical use	Faster, fewer inversions in datapaths	Common in control / active-low logic

  AB\C   0   1
   00    1   1
   01    0   1
   11    0   1
   10    1   0     → group four 1s (C=1 column) + corners (00,10 row)

1. In a 4-variable K-map, the cells m0 and m2 are…

2. A group of 8 cells in a 4-variable map eliminates how many literals?

3. Which is true about don't-care conditions?

4. f(A,B,C) = Σm(1,3,5,7) simplifies to…