A truth table or a canonical expression can be correct and still be too large to implement, or to simplify under exam pressure. Boolean laws shrink it algebraically, a Karnaugh map shrinks it visually, and both stand or fall on one discipline: every transformation and every group must survive a truth-table check. Σm(0,2,5,7,8,10,13,15) comes down from eight four-literal minterms to B'D' + BD, and the same map read through its zeros gives (B + D')(B' + D).
1. What Boolean minimization changes
Boolean minimization finds an equivalent function with fewer terms, fewer literals, or a simpler implementation. Canonical SOP lists 1 rows as minterms; canonical POS lists 0 rows as maxterms. Neither is necessarily minimal.
A literal is a variable or its complement, such as A or A'. A minterm is an AND term containing every input variable; a maxterm is an OR term containing every input variable. An implicant covers one or more 1-cells. A prime implicant cannot be enlarged, and an essential prime implicant alone covers at least one required 1.
We use A' for NOT A, adjacency for AND, and + for OR. Thus F(A,B,C,D) = Σm(...) lists the rows where F = 1. The truth table is always the equivalence test: the expression may change, but no specified output may change.
Literal count is a useful hand measure, not a complete hardware cost. A factored expression, a two-level SOP, and a gate library can favour different implementations. The Boolean algebra and K-map minimization guide walks the six identity pairs, DeMorgan's theorems and one four-variable map traced group by group; revise it first if any law in the next section reads as new.
2. Algebraic minimization: the law behind each step
The main laws are identity (X + 0 = X, X.1 = X), complement (X + X' = 1, X.X' = 0), idempotence (X + X = X), absorption (X + XY = X), distributivity, and De Morgan's laws. Name the law beside any non-obvious step so that the reduction remains auditable.
Consider:
F(A,B,C) = A'BC + ABC + AB'C
Factor BC, then apply complement and identity:
A'BC + ABC = BC(A' + A) = BC.1 = BC
Therefore:
F = BC + AB'C
= C(B + AB')
Use distributivity to show the identity:
B + AB' = (B + A)(B + B') = (A + B).1 = A + B
So the useful factored and SOP forms are:
F = C(A + B) = AC + BC
The original is 1 exactly at m3 = 011, m5 = 101, and m7 = 111. The reduced form is also 1 at those three rows and 0 at the other five. The original has three product terms and nine literal occurrences. AC + BC has two product terms and four literals, while C(A + B) maps directly to one OR followed by one AND.
3. Karnaugh-map mechanics: Gray-code order and legal groups
For four variables, label the rows AB = 00, 01, 11, 10 and columns CD = 00, 01, 11, 10. This Gray-code order makes neighbouring cells differ in one bit. The first and last row are adjacent, as are the first and last column. Diagonal cells are not adjacent.
For SOP, cover every 1 using rectangles of 1, 2, 4, 8, ... cells. Prefer the largest legal groups. Overlap when it removes a literal, and reuse a cell if useful. A variable survives only when it remains constant throughout the group.
A prime implicant cannot be enlarged. It is essential only when it contains a required 1 that no other prime implicant covers. Identify that unique cell.
4. Worked 4-variable SOP example: Σm(0,2,5,7,8,10,13,15)
Minimise F(A,B,C,D) = Σm(0,2,5,7,8,10,13,15). Put 1 in those eight cells and 0 in the rest.
The wrap-around corner group {m0,m2,m8,m10} has changing A and C, with B = 0 and D = 0 fixed. It produces B'D'. The central group {m5,m7,m13,m15} has changing A and C, but fixed B = 1 and D = 1. It produces BD. Cell m0 makes the first implicant essential; cell m5 makes the second essential.
Therefore:
F = B'D' + BD = B XNOR D
A and C disappear because each changes inside both groups. Check four pairs: B,D = 00 gives 1, 01 gives 0, 10 gives 0, and 11 gives 1, irrespective of A and C. Eight four-literal minterms have become two two-literal products. Larger blocks reuse such functions, as in Combinational Circuits: MUX, Decoders, Adders.
5. Don't-cares and when POS is shorter
Take G(W,X,Y,Z) = Σm(1,3,7,11,15) + d(5,9,13). Treat the three don't-cares as 1 because they join all eight odd cells {1,3,5,7,9,11,13,15} into one octet. W, X, and Y vary, while Z = 1, so G = Z. All five required 1-cells remain covered. The outputs at the don't-care cells were never specified, so choosing 1 there is allowed. Don't-cares may be included, excluded, or split across groups, but never have to be covered.
For POS, return to the XNOR map and group zeros. The group with B = 0, D = 1 gives (B + D'). The group with B = 1, D = 0 gives (B' + D). Hence:
F = (B + D')(B' + D) = B'D' + BD
On the XNOR map both forms cost two terms and four literals, so switching buys nothing. POS pays off when the 0s are the smaller, more clustered set.
Take F(A,B,C,D) = Σm(0,1,2,3,4,5,10,11,14,15): ten 1s, six 0s at m6, m7, m8, m9, m12, m13. Those zeros form two groups, {m8,m9,m12,m13} with A = 1, C = 0, and {m6,m7} with A = 0, B = 1, C = 1, giving the maxterms (A' + C) and (A + B' + C'):
F = (A' + C)(A + B' + C')
The 1s need three groups, A'C' + AC + A'B': three terms and six literals as SOP, against two terms and five literals as POS. Spot check m8 = 1000, where A = 1 and C = 0 zero the factor (A' + C), so F is 0, as the minterm list requires.
6. Common minimization traps and their fixes
Wrong geometry: binary order
00, 01, 10, 11, diagonal grouping, or a six-cell group. Write Gray-code labels first, then require every group to be rectangular and a power of two, including legal wrap-around groups.Wrong literal: retaining a variable that changes, or complementing a fixed value backwards. In SOP, fixed 1 is uncomplemented and fixed 0 is complemented. POS uses the opposite maxterm convention.
Incomplete coverage: forcing every don't-care into a group, refusing overlap, or listing prime implicants without covering every required minterm. Finish with a coverage audit and a truth-table spot check.
A minimal expression is not automatically hazard-free: a glitch-free implementation is a separate design question.
7. How GATE-style questions and interviews use the topic
Typical questions test algebraic equivalence, K-map completion, minimum term or literal count, SOP versus POS, don't-cares, or recognition of the implemented gate. A frequent variant asks for a count, not an expression: the XNOR map above has exactly two prime implicants, B'D' and BD, and both are essential, so its minimal SOP is unique.
Try this 30-second check: H(P,Q,R) = Σm(1,3,5,7). All and only the odd minterms have R = 1, so H = R; P and Q disappear because both vary across the group. Verify: 000 -> 0, 001 -> 1, 110 -> 0, and 111 -> 1.
In an interview, state the representation, show the legal groups or laws, derive the expression, then verify a boundary input. That sequence demonstrates reasoning, not a memorised answer.
8. Short version and the next practice step
Use this five-step check:
Translate the function into minterms or maxterms.
Label the K-map in Gray order.
Make the largest legal groups.
Derive one term from each group.
Verify every specified row.
Algebra, SOP grouping, and POS grouping are three views of the same Boolean function. For a structured subject sequence, use GATE Guidance by Sanchit Sir. For timed application, move to the GATE Test Series. The GATE course category is the broad route chooser.
Now redraw both worked maps without looking, derive the SOP and POS for the XNOR example, and confirm them on all four B,D combinations.
