Boolean simplification

Also called: simplification, simplify, algebraic simplification, logic simplification, logic minimization, simplification strategy

Rewriting a Boolean expression into an equivalent one with fewer terms and literals, so the circuit needs fewer, smaller gates.

Simplifying an expression means finding an equivalent expression that is cheaper to build. Cheaper usually means fewer terms (fewer gates) and fewer literals (fewer gate inputs). See literal count and gate input count.

A reliable strategy with the laws of boolean algebra:

Remove long bars with de morgans laws.
Multiply out into a sum of products.
Delete the easy stuff: terms with X and together (they are 0), duplicates and constants.
Combine terms that differ in exactly one letter: = X. See combining terms.
Absorb: delete any term that contains another, and drop barred letters with = .
Look for consensus terms to delete.
Check a row or two against the original.

After each change, go back to step 3, because one simplification often opens up another.

Algebra works on any expression but gives no guarantee you have the smallest answer. For that, the systematic tools are prime implicants and Karnaugh maps.

Worked examples

Example

Following the strategy

Simplify .

1.
No long bars. Multiply out: .
2.
Easy stuff: appears twice and = B, giving .
3.
Absorb: B absorbs and , giving .
4.
Nothing combines and nothing else is absorbed. Result: .
5.
Check A = 1, B = 0, C = 1: original 0 + 1 + 0 = 1, result 0 + 1 = 1.

Example

De Morgan first

Simplify .

1.
De Morgan: = , so the expression is .
2.
Multiply out: .
3.
Combine = C, giving .
4.
Absorb: C absorbs . Result: C.

Common mistakes

Stopping after one pass. A single change often makes a new simplification possible.
Using a rule from ordinary algebra, such as cancelling.
Skipping the final check. One row against the original catches most slips.

Practice Boolean simplification

Interactive questions with instant feedback and a worked solution for every wrong answer.

Boolean Algebra lesson

And 11 more in the Boolean Algebra lesson.