[Beginner → Intermediate] — You can build any gate. Now the question is which gates to build. Boolean algebra is how you find a cheaper expression for the same function — and it routinely saves more than transistor sizing ever will.
Before you start
- You can build a CMOS gate from PDN and PUN networks and know their transistor costs — module 15.
- You know NAND is cheaper than NOR, and AND costs more than NAND — module 15.
- You can read a truth table.
After this lesson you will be able to:
- State and apply the Boolean laws, and prove any of them by exhaustive truth table.
- Use De Morgan’s laws to convert between AND-shaped and OR-shaped logic.
- Write a function in canonical sum-of-products form from its truth table.
- Simplify an expression and quantify the saving in transistors.
Study route: section 4 (De Morgan) is the practically important one. Section 6 shows why this module beats the previous one for cost saving.
1. Why this exists (real-world motivation)
Module 15 gave you a cost model: NAND2 is 4 transistors, AND2 is 6, XOR2 is 12. You can now price any circuit.
Which means you can now notice that most circuits are priced badly.
Take the function . Built literally, term by term, it needs two inverters, three AND gates and two ORs — 34 transistors.
That same function is exactly . One OR gate. Six transistors.
An 82% saving, and not one transistor was resized. Module 15 fought for 38% by choosing NAND over NOR; this fight is worth twice as much and is won before any circuit is drawn.
That is what Boolean algebra buys. It is not abstract mathematics that happens to describe circuits — it is the cost-reduction tool of digital design, and it is why synthesis software exists.
2. Terminology
| Term | Plain-English definition | Example |
|---|---|---|
| Boolean variable | Takes only 0 or 1 | |
| Complement | NOT — written or | |
| Product | AND — written or | |
| Sum | OR — written | |
| Literal | A variable or its complement | , |
| Minterm | A product containing every variable exactly once | |
| Maxterm | A sum containing every variable exactly once | |
| SOP | Sum of products — ORs of ANDs | |
| POS | Product of sums — ANDs of ORs | |
| Canonical form | The SOP or POS using only full minterms/maxterms | — |
| Duality | Swap AND↔OR and 0↔1; a valid law stays valid | — |
NOTE
The notation collides with arithmetic, and that is a deliberate historical choice. means OR, not addition — in Boolean algebra. means AND, which does coincide with multiplication on {0,1}.
Boole chose these symbols because the algebraic laws are so similar. Most of them transfer; the ones that do not are exactly the interesting ones, like .
3. The laws
Each is stated with the intuition that makes it obvious, not just the symbols. All of them are proved exhaustively in the lab.
| Law | AND form | OR form | Why |
|---|---|---|---|
| Identity | Combining with the neutral value changes nothing | ||
| Null | The dominant value wins outright | ||
| Idempotent | Repeating yourself adds nothing | ||
| Complement | Something and its opposite | ||
| Involution | (self-dual) | Two inversions cancel | |
| Commutative | Order is irrelevant | ||
| Associative | Grouping is irrelevant | ||
| Distributive | Factoring out | ||
| Absorption | The extra term is redundant | ||
| De Morgan | Inversion swaps AND and OR |
Two of these differ from ordinary arithmetic, and they are the ones that do the work:
- Idempotent (): in arithmetic that would be . Duplicate terms simply vanish.
- The second distributive law (): this has no arithmetic analogue at all — . It lets you convert SOP to POS.
Absorption is the workhorse of simplification. says that once is true the whole expression is true, so the term never decides anything. Spotting absorption is most of hand-simplification.
The duality principle
Swap every AND with OR and every 0 with 1, and a valid law remains valid. That is why the table has two columns — each row is one law and its dual, and proving one proves the other for free.
This is not a coincidence. It reflects the symmetry between the two stable states of a CMOS gate, and it is the same duality as the PDN/PUN relationship in module 15.
4. De Morgan’s laws — the practical tool
In words: breaking the bar swaps the operator. “Not (both)” is the same as “either one isn’t”. “Not (either)” is the same as “neither”.
These are the most-used laws in digital design, for a very concrete reason from module 15: CMOS gates are naturally inverting, and NAND is cheaper than NOR. De Morgan is the tool that moves inversions around until the logic lands on the cheap primitive.
A direct example. Suppose you need :
- Built literally: two inverters plus an AND gate = 10 transistors.
- Rewritten by De Morgan as : a single NOR2 = 4 transistors.
Same function, 60% fewer transistors, from applying one identity.
This is exactly what synthesis tools do at scale — pushing inversions through a whole network to land on NAND-dominated implementations. Module 18 takes this to its conclusion: if De Morgan lets you rewrite anything in terms of NAND, do you need any other gate at all?
5. From truth table to expression
Any function can be written down mechanically from its truth table.
Sum of products: write one minterm for every row where the output is 1, then OR them together. A minterm contains every variable — uncomplemented if it is 1 in that row, complemented if 0.
| Minterm | |||
|---|---|---|---|
| 0 | 0 | 0 | — |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 |
This is guaranteed correct and guaranteed inefficient. Each minterm handles exactly one row, so nothing is shared and nothing is cancelled. Canonical form is a starting point, never an answer.
Simplifying it
Apply idempotence to duplicate the term — legal, since :
Factor each pair:
By complement, each bracket is 1:
Three products and two inversions collapse to a single OR. 34 transistors become 6.
NOTE
The trick of duplicating a term to enable two factorisations is the standard move, and it is the one people find least obvious. Idempotence makes it free — you can always add another copy of a term already present.
Hand-simplification of this kind is error-prone and hard to be sure you have finished, which is exactly why module 17 introduces a visual method that makes the groupings obvious and tells you when you are done.
6. Predict before reading on
Module 15 worked hard to save 38% by choosing NAND over NOR. This module’s example saved 82% by algebra.
Does that mean transistor sizing doesn’t matter?
Check your answer
No — they compose, and they apply at different stages.
Algebraic simplification decides how many gates you build. Sizing and gate choice decide how much each gate costs. The savings multiply: simplify from 34 to 6 transistors, then implement that OR as the cheaper NAND-based form where the surrounding polarity allows, and you have taken both discounts.
But the order matters. Simplify first. There is no point carefully sizing a gate that a simplification would have deleted entirely — and this is precisely why an EDA flow runs logic optimisation before technology mapping and sizing.
It is the same principle as in software: choose a better algorithm before micro-optimising the loop. A 10× algorithmic win dwarfs a 20% constant-factor win, and doing them in the wrong order wastes the effort.
7. Worked example — runnable
Every law below is proved by exhaustive truth-table comparison, not asserted. The lab then simplifies a real expression, proves the two forms equivalent, and prices both using module 15’s transistor costs.
Save as boolean_lab.py and run python3 boolean_lab.py.
from itertools import product
# Transistor cost of each gate in static CMOS (module 15)
GATE_COST = {"NOT": 2, "AND2": 6, "OR2": 6, "NAND2": 4, "NOR2": 4, "XOR2": 12}
def verify(name, left, right, n_vars):
"""Prove an identity by exhaustive truth-table comparison."""
for values in product([0, 1], repeat=n_vars):
if left(*values) != right(*values):
return False, values
return True, None
def check_all(laws):
width = max(len(n) for n, _, _, _ in laws)
for name, left, right, n in laws:
ok, counterexample = verify(name, left, right, n)
status = "proved" if ok else f"FAILS at {counterexample}"
print(f" {name:<{width}s} {status}")
if not ok:
raise AssertionError(name)
def cost(gates):
"""Total transistors for a bag of gates, e.g. {'AND2': 3, 'NOT': 2}."""
return sum(GATE_COST[g] * n for g, n in gates.items())
if __name__ == "__main__":
print("Single-variable laws (proved over all inputs):")
check_all([
("identity A + 0 = A", lambda a: a | 0, lambda a: a, 1),
("identity A . 1 = A", lambda a: a & 1, lambda a: a, 1),
("null A + 1 = 1", lambda a: a | 1, lambda a: 1, 1),
("null A . 0 = 0", lambda a: a & 0, lambda a: 0, 1),
("idempotent A + A = A", lambda a: a | a, lambda a: a, 1),
("idempotent A . A = A", lambda a: a & a, lambda a: a, 1),
("complement A + A' = 1", lambda a: a | (1-a), lambda a: 1, 1),
("complement A . A' = 0", lambda a: a & (1-a), lambda a: 0, 1),
("involution (A')' = A", lambda a: 1-(1-a), lambda a: a, 1),
])
print()
print("Two- and three-variable laws:")
check_all([
("commutative A + B = B + A",
lambda a, b: a | b, lambda a, b: b | a, 2),
("absorption A + A.B = A",
lambda a, b: a | (a & b), lambda a, b: a, 2),
("absorption A.(A + B) = A",
lambda a, b: a & (a | b), lambda a, b: a, 2),
("De Morgan (A.B)' = A' + B'",
lambda a, b: 1-(a & b), lambda a, b: (1-a) | (1-b), 2),
("De Morgan (A+B)' = A'.B'",
lambda a, b: 1-(a | b), lambda a, b: (1-a) & (1-b), 2),
("associative (A+B)+C = A+(B+C)",
lambda a, b, c: (a | b) | c, lambda a, b, c: a | (b | c), 3),
("distributive A.(B+C) = A.B + A.C",
lambda a, b, c: a & (b | c), lambda a, b, c: (a & b) | (a & c), 3),
("distributive A+(B.C) = (A+B).(A+C)",
lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & (a | c), 3),
("consensus A.B + A'.C + B.C = A.B + A'.C",
lambda a, b, c: (a & b) | ((1-a) & c) | (b & c),
lambda a, b, c: (a & b) | ((1-a) & c), 3),
])
print()
# A real simplification, proved equivalent then costed
original = lambda a, b: (a & b) | (a & (1-b)) | ((1-a) & b)
simplified = lambda a, b: a | b
ok, _ = verify("simplification", original, simplified, 2)
print(f"F = A.B + A.B' + A'.B simplifies to F = A + B")
print(f" equivalence proved over all inputs: {ok}")
print()
print(" truth table (both):")
for a, b in product([0, 1], repeat=2):
print(f" A={a} B={b} -> {original(a,b)} {simplified(a,b)}")
print()
before = cost({"NOT": 2, "AND2": 3, "OR2": 2})
after = cost({"OR2": 1})
print(f" literal implementation: 2 NOT + 3 AND2 + 2 OR2 = {before} transistors")
print(f" simplified: 1 OR2 = {after} transistors")
print(f" saving: {before - after} transistors ({100*(before-after)/before:.0f}%)")
print()
# De Morgan in its practical role: turning NOR-shaped logic into NAND-shaped
print("De Morgan as a design tool (module 15: NAND is cheaper than NOR):")
print(f" A' . B' built directly needs 2 NOT + 1 AND2 = {cost({'NOT':2,'AND2':1})} transistors")
print(f" rewritten as (A + B)' it is one NOR2 = {cost({'NOR2':1})} transistors")
assert ok
assert before > after
print()
print("boolean_lab: passed")Expected output:
Single-variable laws (proved over all inputs):
identity A + 0 = A proved
identity A . 1 = A proved
null A + 1 = 1 proved
null A . 0 = 0 proved
idempotent A + A = A proved
idempotent A . A = A proved
complement A + A' = 1 proved
complement A . A' = 0 proved
involution (A')' = A proved
Two- and three-variable laws:
commutative A + B = B + A proved
absorption A + A.B = A proved
absorption A.(A + B) = A proved
De Morgan (A.B)' = A' + B' proved
De Morgan (A+B)' = A'.B' proved
associative (A+B)+C = A+(B+C) proved
distributive A.(B+C) = A.B + A.C proved
distributive A+(B.C) = (A+B).(A+C) proved
consensus A.B + A'.C + B.C = A.B + A'.C proved
F = A.B + A.B' + A'.B simplifies to F = A + B
equivalence proved over all inputs: True
truth table (both):
A=0 B=0 -> 0 0
A=0 B=1 -> 1 1
A=1 B=0 -> 1 1
A=1 B=1 -> 1 1
literal implementation: 2 NOT + 3 AND2 + 2 OR2 = 34 transistors
simplified: 1 OR2 = 6 transistors
saving: 28 transistors (82%)
De Morgan as a design tool (module 15: NAND is cheaper than NOR):
A' . B' built directly needs 2 NOT + 1 AND2 = 10 transistors
rewritten as (A + B)' it is one NOR2 = 4 transistors
boolean_lab: passed
Note the consensus theorem in the output: . The term is entirely redundant — whenever is true, either is true (so covers it) or is false (so covers it). It is not obvious by inspection, which is why it is worth knowing by name, and it matters practically for eliminating hazards in module 17.
8. Common pitfalls and traps
- Reading as arithmetic addition. here. Every Boolean expression is about truth, not quantity.
- Misapplying De Morgan by only swapping the operator. You must complement each term and swap the operator. is , not and not .
- Stopping at canonical form. Minterm expansion is a correct starting point and always wasteful.
- Forgetting the second distributive law. has no arithmetic analogue, so it is easy to overlook — and it is the route from SOP to POS.
- Not spotting absorption. is the most common available saving and the easiest to miss in a long expression.
- Assuming fewer literals means fewer transistors. Usually true, but the shape matters too: an expression needing a 4-input NOR may cost more than a slightly longer one built from NANDs.
9. Check your understanding
-
Simplify .
Answer
Apply De Morgan to the first term: $\overline{(\overline{A} + B)} = A \cdot \overline{B}$.
So the expression is $A\overline{B} + A\overline{B}$, which by idempotence is just $A\overline{B}$.
From roughly three gates plus two inverters down to one AND and one inverter. Always look for De Morgan opportunities on any bar covering a compound expression. -
Why is ?
Answer
Expand $A$ using complement and distribution: $A = A(B + \overline{B}) = AB + A\overline{B}$.
So $A + \overline{A}B = AB + A\overline{B} + \overline{A}B$ — which is exactly the module's worked example, equal to $A + B$.
Intuitively: if $A$ is true the whole thing is true. If $A$ is false, the expression reduces to $B$. So it is true whenever $A$ or $B$ is — the $\overline{A}$ is doing no work. -
A function is true only when exactly one of , is true. Write its canonical SOP, identify it, and price both forms.
Answer
Rows where output is 1: $(0,1)$ and $(1,0)$. So $F = \overline{A}B + A\overline{B}$ — which is XOR.
Built literally: 2 NOT + 2 AND2 + 1 OR2 = $4 + 12 + 6 = 22$ transistors. As a dedicated XOR2 cell: 12 transistors.
XOR does not simplify further — this is a case where algebra cannot help and the answer is a purpose-built cell. It is also why cell libraries include XOR despite its cost, and why adders in [[how-computers-work/05-combinational/02-adders|module 21]] are expensive. -
Why does an EDA flow simplify logic before choosing gates and sizing them?
Answer
Because simplification changes how many gates exist, while mapping and sizing change what each costs. Optimising the cost of a gate that simplification would delete is wasted work, and the ordering means the larger saving is taken first and the smaller one applies to what remains.
The two compose multiplicatively — an 82% algebraic saving followed by a 38% NAND-versus-NOR saving on the remainder is far better than either alone. Reversing the order does not just waste effort; it can also lock in a gate-level structure that hides the algebraic opportunity.
10. Practice — independent task
Task: A safety interlock outputs 1 when a machine may run. Inputs: (guard closed), (power OK), (emergency stop pressed), (maintenance mode).
The rule: run if the guard is closed and power is OK and emergency stop is not pressed. Also run in maintenance mode if power is OK and emergency stop is not pressed, regardless of the guard.
- (a) Build the full truth table for all 16 input combinations.
- (b) Write the canonical SOP expression, one minterm per 1-row.
- (c) Price the canonical form in transistors using module 15’s table. State any assumptions about multi-input gate costs.
- (d) Simplify algebraically, naming each law as you use it. Aim for a form with three literals.
- (e) Price the simplified form. What percentage did you save?
- (f) Apply De Morgan to express your answer using only NAND and NOT. Price that version too.
- (g) Extend
boolean_lab.pywith both your canonical and simplified functions and useverify()to prove they agree on all 16 inputs.
Done when: verify() confirms equivalence, and you can state the saving as a percentage and name the law that did most of the work.
Hint for (d), only if stuck
Both clauses share $P \cdot \overline{E}$. Factor it out: $F = P\overline{E}(G + M)$.That is three literals plus one OR — a dramatic reduction from the canonical form. The law doing the work is distribution applied in reverse (factoring), which is the single most productive move in hand simplification after absorption.
11. Tradeoffs and limits
- Hand simplification does not scale and has no stopping rule. Beyond three or four variables you cannot be confident you have found the minimum. Module 17 gives a visual method with a clear termination condition; beyond six variables, algorithmic methods like Quine–McCluskey and Espresso take over.
- Minimal literal count is not always minimal cost. The real objective is area, delay and power in a specific cell library — which is why synthesis tools optimise against a technology library rather than against literal count.
- Boolean algebra assumes ideal, instantaneous gates. Real gates have delay, and two algebraically identical circuits can behave differently during transitions, producing glitches. Module 17 covers hazards and how the consensus theorem fixes them.
- This is two-valued logic only. Real designs also carry high-impedance and don’t-care states, which extend the algebra.
Before moving on
- State the ten laws and prove any of them by truth table.
- Apply De Morgan correctly, complementing terms and swapping the operator.
- Write canonical SOP from a truth table and explain why it is never the final answer.
- Simplify an expression, using term duplication where it enables factoring.
- Explain why simplification comes before sizing, and why the savings compose.
Recap: Boolean algebra manipulates expressions into cheaper equivalents. Its laws mirror arithmetic except for idempotence and the second distributive law, and every law comes with a dual obtained by swapping AND with OR and 0 with 1. De Morgan’s laws move inversions across operators, which is how NOR-shaped logic becomes NAND-shaped and why they are the most used laws in practice. Canonical SOP converts any truth table into a correct, wasteful expression; simplification then removes the waste — 34 transistors to 6 in this module’s example.
Next: Module 17 — Karnaugh Maps replaces error-prone algebra with a visual method where the simplifications are literally adjacent squares, and where you can tell when you have finished.
Related
- How Computers Work — course index
- Module 15 — the transistor costs used for pricing
- Module 18 — where De Morgan leads: NAND alone suffices
- discrete-math/logic — the same algebra as propositional logic
- theory-of-computation/ — Boolean circuits as a model of computation
Software engineering
Infrastructure & security
Computer science
Hardware & engineering