Algebraic Minimization

Algebraic minimization rewrites a Boolean expression using identities until literal count, term count, or gate count drops, without changing the truth table. It is the syllabus's first minimization technique: no map drawing, no tabular covering. For two or three variables it is often enough; for four or more, Karnaugh Maps and Quine-McCluskey scale better, but algebraic steps still justify every grouping those methods find.

Common objectives (state which one a question wants):

Algebraic minimization is not guaranteed to reach a global minimum without a systematic method; it is guided search using identities.

Cost conventions. For $f = ab + a'c$ (complemented literals available for free):

If complemented inputs are not available, add one inverter per complemented variable (here one, for $a'$). A single-literal term needs no AND gate, so it adds a literal and an OR input but no gate.

Combining is the algebraic form of circling two adjacent 1s on a K-map: the changing variable drops out.

Dual steps: combine sums that differ in one literal, absorb, distribute carefully, apply dual consensus.

Two-level minimal SOP is not always the cheapest in gates once shared factors are allowed. Example: $f = ab + ac + ad = a(b+c+d)$ saves gates. Multi-level minimization is largely heuristic in this setting; mention factoring when a common literal is obvious.

Sometimes the shortest route first adds a redundant consensus term, uses it to combine or absorb, and only then deletes. For $f = xy + yz' + x'z$:

Six literals became three. Deleting whole terms cannot reach this form; it needs the literal $x$ dropped from $xy$, which is legal only because the other two terms already cover $x'y$. Finding that cover is exactly what the consensus step does.

To minimize as a product of sums, minimize $f'$ as a sum of products, then apply De Morgan once. For $f = x' + yz$: $f' = x(yz)' = xy' + xz'$, so $f = (x' + y)(x' + z)$. Here the SOP (3 literals) is cheaper than the POS (4 literals); for other functions the POS wins, so compare both when a question asks for the cheaper two-level form.

Worked discipline. An identity in $n$ variables is proved by its $2^n$-row truth table. For $n \le 3$ that is quick enough to do by hand in an exam, and it is the safest final check of an algebraic answer.

There is no short complete algorithm short of Quine-McCluskey. A practical greedy sketch (terms are products of literals):

Always finish with an equivalence check against the original truth table for worked examples.

The loop is greedy: it never adds terms, so it can miss reductions such as the consensus-addition example above, and it can stop at a form that is irredundant (no term or literal can be deleted) but not minimum. Its cost per pass is $O(k^2 n)$ for $k$ terms over $n$ variables.

Prime implicants (preview). A product term $P$ is an implicant of $f$ if $P=1$ implies $f=1$. It is prime if deleting any literal destroys that property. A minimal SOP is always a sum of prime implicants (possibly not all of them). Algebraic combining finds prime implicants; essential ones must appear in every minimal SOP. Full covering is the Quine-McCluskey chart step.

Why minimal SOPs use only primes. If a minimal SOP contained a non-prime implicant $P$, some literal could be deleted from $P$ leaving an implicant $P^{*}$ that covers everything $P$ covered and more, still inside $f$. Replacing $P$ by $P^{*}$ lowers the literal count without changing $f$, a contradiction.

Minimal forms need not be unique. $f = x'y + y'z + xz'$ equals $\sum m(1, 2, 3, 4, 5, 6)$, and so does $xy' + yz' + x'z$. Both have three terms and six literals, and no two-term SOP exists. Such cyclic functions have no essential prime implicant; see Quine-McCluskey Method.

Irredundant is weaker than minimum. An SOP is irredundant when no term and no literal can be removed. For $f = \sum m(1,2,3,4,5,6)$ above, the four-term SOP $x'y + xy' + x'z + xz'$ covers $\{2,3\}, \{4,5\}, \{1,3\}, \{4,6\}$, and removing $x'z$ leaves $m_1$ uncovered, removing $xz'$ leaves $m_6$ uncovered, removing $x'y$ leaves $m_2$ uncovered, removing $xy'$ leaves $m_5$ uncovered, and every term is already prime. It is irredundant, yet it has four terms where three suffice.

$f = xyz + xyz' + x'y$. Combine first two: $xy(z+z')=xy$. Then $xy + x'y = y(x+x')=y$. So $f=y$. Check: whenever $y=1$, original has a 1 from $x'y$ or from $xy(\cdot)$; whenever $y=0$, every term is 0.

$f = ac + a'b + bc$. Consensus of $ac$ and $a'b$ is $bc$, so $f = ac + a'b$.

$f = a + a'b + cd = a + b + cd$ after $a+a'b=a+b$, then nothing absorbs $cd$.

$f = (x+y)(x+y')(x'+z)$. Combine first two: $(x+y)(x+y')=x+yy'=x$. Then $x(x'+z)=xx'+xz=xz$. So $f=xz$.

Start with

Factor by pairs:

The factored circuit shares $(c+d)$ and may exploit an XOR primitive. This is not a reduction in strict two-level AND-OR product terms: expanding the XOR and the factor restores the four original products, all essential under that model. Compare costs only after specifying the available gates and number of levels.

$g = (x+y+z)(x+y+z')(x'+y)$. The first two factors combine on $z$ (dual combining rule $(A + z)(A + z') = A$): $(x+y+z)(x+y+z') = x+y$. Then $(x+y)(x'+y) = y + xx' = y$ by the distributive law of OR over AND. So $g=y$.

Expression $h = xy + xy'z + x'yz$ (8 literals).

Final $h = xy + xz + yz$, the majority function: 6 literals, down from 8. Its minterms are $\{3, 5, 6, 7\}$.

$(ab + c'd)' = (ab)'(c'd)' = (a' + b')(c + d')$. Multiplying out gives $a'c + a'd' + b'c + b'd'$, the SOP of the complement, with no further reduction (four prime implicants, all needed).

Common misconceptions.