Boolean Algebra Laws and Theorems

Identity

a · 1 = a

Dual: a + 0 = a

Axiom — assumed, not proved

Also called: identity element, unit law.

This is not proved. It is one of Huntington’s postulates — 0 and 1 are the identity elements of + and · — and every other law on this page is built on it.

❌ Wrong: a + 1 = a ✅ Right: a + 1 = 1 — that is the Null law, not Identity

Null (annihilation, domination)

a · 0 = 0

Dual: a + 1 = 1

Theorem — proved from the axioms

Also called: annihilation, domination, zero law.

❌ Wrong: 1 + b = b ✅ Right: 1 + b = 1 — Boolean addition does not carry

Idempotent

a · a = a

Dual: a + a = a

Theorem — proved from the axioms

Also called: tautology law, Boole’s index law.

❌ Wrong: a + a = 2a ✅ Right: a + a = a — there is no 2 in this algebra

Complement

a · a′ = 0

Dual: a + a′ = 1

Axiom — assumed, not proved

Also called: inverse law, law of the excluded middle.

A Huntington postulate: every element has a complement. The constant forms follow — 0′ = 1 and 1′ = 0 — and so does the fact the De Morgan and Involution proofs turn on: **the complement is unique**. If a + x = 1 and a · x = 0 then x is a′.

❌ Wrong: a · a′ = a ✅ Right: a · a′ = 0 — nothing is both

Involution (double negation)

(a′)′ = a

Dual: self-dual

Theorem — proved from the axioms

Also called: double negation, double complement.

❌ Wrong: (a′)′ = a′ ✅ Right: (a′)′ = a — two inverters in series cancel

Commutative

a · b = b · a

Dual: a + b = b + a

Axiom — assumed, not proved

Also called: order law.

This toolkit never prints a “commutative” step. Commutativity and associativity are handled by canonicalising each product term as a sorted set of literals, which is why the simplifier does not emit six pointless reorderings.

❌ Wrong: a → b = b → a ✅ Right: implication is not commutative; AND and OR are

Associative

(a·b)·c = a·(b·c)

Dual: (a+b)+c = a+(b+c)

Theorem — proved from the axioms

Also called: grouping law.

Derivable from Huntington’s fourth postulate set; most digital-logic textbooks nevertheless present it as an axiom. Both statements are true, and the table below proves the identity either way. Because AND and OR are associative, A·B·C draws as one three-input gate rather than a cascade.

❌ Wrong: (a ↑ b) ↑ c = a ↑ (b ↑ c) ✅ Right: NAND and NOR are **not** associative — check the table

Distributive

a·(b + c) = a·b + a·c

Dual: a + b·c = (a + b)·(a + c)

Axiom — assumed, not proved

Also called: factoring (right to left), multiplying out.

The second form is the one students refuse to believe, because it is false in ordinary arithmetic. It works here for one reason: a·a = a, so multiplying out gives a + a·c + a·b + b·c and absorption removes the two middle terms. Read right to left the first form is **factoring**, which increases literal count and is therefore budgeted as a size-increasing move by the simplifier.

❌ Wrong: a + b·c = (a + b)·c ✅ Right: a + b·c = (a + b)·(a + c) — the second form has no arithmetic analogue

Absorption

a + a·b = a

Dual: a · (a + b) = a

Theorem — proved from the axioms

Also called: covering law.

Step 3 is the one people skip: 1 + b = 1, not b.

On a Karnaugh map. The group for a·b sits entirely inside the group for a, so it circles nothing new. Draw it.

❌ Wrong: A + A·B = A·B ✅ Right: A + A·B = A

Redundancy (second absorption)

a + a′·b = a + b

Dual: a · (a′ + b) = a · b

Theorem — proved from the axioms

Also called: second absorption law, simplification theorem, wrongly: absorption.

Absorption **deletes** the second term; redundancy **keeps** it and strips one literal. If the extra literal is the complement of the term you are absorbing into, you cannot absorb — you can only strip that literal.

On a Karnaugh map. The a′·b group sticks out of the a group by exactly the cells where b is 1, so together they are the group for a plus the group for b. Draw it.

❌ Wrong: “absorbing” A′·B into A to get A ✅ Right: A + A′·B = A + B

Consensus

a·b + a′·c + b·c = a·b + a′·c

Dual: (a+b)·(a′+c)·(b+c) = (a+b)·(a′+c)

Theorem — proved from the axioms

Also called: consensus theorem, redundancy theorem.

How to spot the consensus term: find two terms containing a complementary pair (a and a′); the consensus is the product of everything else.

On a Karnaugh map. The consensus group straddles the other two and covers no cell they do not already cover — which is exactly the picture of “redundant”. Draw it.

❌ Wrong: looking for a consensus term where no complementary pair exists ✅ Right: A·B + A·C has none; A·B + A′·C′ has one, and its consensus is B·C′

De Morgan

(a · b)′ = a′ + b′

Dual: (a + b)′ = a′ · b′

Theorem — proved from the axioms

Also called: De Morgan’s theorem, break the bar, change the sign.

Proved by uniqueness of the complement rather than by table, because that proof generalises to n operands and a table does not: (a₁·a₂·…·aₙ)′ = a₁′ + a₂′ + … + aₙ′.

On a Karnaugh map. Grouping the 0s instead of the 1s is De Morgan on a map. Draw it.

❌ Wrong: (A + B)′ = A′ + B′ ✅ Right: (A + B)′ = A′ · B′

Adjacency (K-map combining)

a·b + a·b′ = a

Dual: (a + b)·(a + b′) = a

Theorem — proved from the axioms

Also called: combining, the K-map grouping law, uniting theorem.

This three-step chain is exactly the engine’s ADJACENCY_CHAIN — factoring, complement, identity — and the simplifier prints it as one collapsed step called Adjacency unless bookkeeping steps are switched on.

On a Karnaugh map. Every group of two is one application; a group of four is two; a group of eight is three. Each doubling removes exactly one more literal. Draw it.

❌ Wrong: A·B + A′·B′ merges to something shorter ✅ Right: those two differ in **two** literals and do not merge — that pair is XNOR

Shannon expansion

f = a · f|ₐ₌₁ + a′ · f|ₐ₌₀

Dual: f = (a + f|ₐ₌₀)·(a′ + f|ₐ₌₁)

Theorem — proved from the axioms

Also called: Boole’s expansion theorem, cofactor expansion.

Worked instance: for f = A·B + A′·C, f|A=1 = B and f|A=0 = C, so f = A·B + A′·C reconstructs itself. The dual expansion gives (A + C)·(A′ + B) — which is this function’s minimal POS, computed independently by the minimiser and matching exactly. Expanding on every variable in turn produces the canonical SOP one minterm at a time, and the expansion is what a multiplexer computes.

On a Karnaugh map. Splitting the map into the half where a = 1 and the half where a = 0 is one expansion. Draw it.

❌ Wrong: f = a·f + a′·f ✅ Right: the two branches are the **cofactors** f|ₐ₌₁ and f|ₐ₌₀, not f itself

Definition of XOR / XNOR

a ⊕ b = a·b′ + a′·b

Dual: a ⊙ b = a·b + a′·b′

Definition — a convention, with nothing to prove

Also called: exclusive or, parity, equivalence (for XNOR).

A definition, not a theorem: there is nothing to prove, only a convention to state. A chain of ⊕ is the sum of its odd-parity minterms.

On a Karnaugh map. Two diagonal cells that never merge, which is why odd parity has no short SOP. Draw it.

❌ Wrong: a ⊕ b = a + b ✅ Right: they differ in the row where both are 1

Definition of implication / biconditional

a → b = a′ + b

Dual: a ↔ b = a·b + a′·b′

Definition — a convention, with nothing to prove

Also called: material conditional, biconditional, iff.

A definition, not a theorem. The biconditional is the same function hardware calls XNOR.

❌ Wrong: 0 → 1 = 0 ✅ Right: 0 → 1 = 1 — a false antecedent makes the conditional vacuously true