Boolean Axioms and Theorems
In the previous article we met the three Boolean operations and the truth table. In this one we go through the rules that let you rearrange and simplify Boolean expressions. I think of them as legal moves, in the way a chess player thinks of the rules of chess: not restrictions, but the set of things you are allowed to do. The better you know them, the faster you spot a simplification, and every simplification is a gate you do not have to build.
Every theorem here has a physical meaning in hardware, and I point it out each time. That is what makes them worth understanding rather than memorising.
Huntington’s postulates
An axiom is something accepted without proof, the base on which everything else is built. Edward Huntington wrote down a minimal set of postulates for Boolean algebra in 1904. Grouped in the way that is useful for us:
P1, Closure. The result of any Boolean operation on Boolean values is a Boolean value: $A + B$ and $A \cdot B$ are each 0 or 1.
P2, Identity elements. $$A + 0 = A \qquad A \cdot 1 = A$$ Zero is the identity for OR and one is the identity for AND.
P3, Commutativity. $$A + B = B + A \qquad A \cdot B = B \cdot A$$ Order does not matter. Swapping the input wires of a gate changes nothing.
P4, Distributivity. $$A \cdot (B + C) = A \cdot B + A \cdot C$$ $$A + (B \cdot C) = (A + B) \cdot (A + C)$$ The second one has no counterpart in ordinary algebra. Check it with a truth table; it takes a moment to believe.
P5, Complement. $$A + A’ = 1 \qquad A \cdot A’ = 0$$ Every variable has a complement. OR with the complement always gives 1; AND with it always gives 0.
Notice that the postulates come in pairs. Every statement about OR has a twin about AND with 0 and 1 swapped. This is the duality principle, and it means every theorem you learn comes with a second theorem for free. We use this constantly.
Theorems, with proofs
Theorems have to be proved from the postulates. In Boolean algebra the standard method is perfect induction: since each variable can only be 0 or 1, you check every combination. It is not elegant, but it is complete.
Idempotency
$$A + A = A \qquad A \cdot A = A$$
| $A$ | $A + A$ |
|---|---|
| 0 | $0 + 0 = 0$ |
| 1 | $1 + 1 = 1$ |
In hardware: if the same signal feeds both inputs of an OR or AND gate, the gate does nothing. Remove it and keep the wire.
Null elements
$$A + 1 = 1 \qquad A \cdot 0 = 0$$
| $A$ | $A + 1$ |
|---|---|
| 0 | 1 |
| 1 | 1 |
In hardware: a gate with one input tied to a constant that dominates it is doing nothing. Replace the gate with the constant. You see this when a feature is disabled by tying an enable pin to a fixed level; synthesis removes the whole cone of logic behind it.
Involution
$$(A’)’ = A$$
| $A$ | $A'$ | $(A’)'$ |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
In hardware: two inverters in series cancel. In schematics you find this where someone added an inversion defensively and then had to invert again to fix the polarity. Two bubbles in a row are a wire.
Absorption
$$A + AB = A \qquad A(A + B) = A$$
Proof of the OR form by expansion:
$$A + AB = A \cdot 1 + AB = A(1 + B) = A \cdot 1 = A$$
And by truth table:
| $A$ | $B$ | $AB$ | $A + AB$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
The last column equals the $A$ column.
In hardware: if $A$ already feeds an OR gate directly, an AND gate computing $AB$ into the same OR is redundant. The whole AND gate and its wiring can go.
There is a useful variant that is not quite absorption and is worth knowing separately:
$$A + A’B = A + B$$
Proof: $A + A’B = (A + A’)(A + B) = 1 \cdot (A + B) = A + B$ by the second distributive law. A very common error is to simplify $A + A’B$ to $B$. It is not $B$; when $A = 1$ the expression is 1 whatever $B$ is.
Consensus
$$AB + A’C + BC = AB + A’C$$
The $BC$ term is redundant, which is not obvious by inspection. Proof:
$$BC = BC(A + A’) = ABC + A’BC$$
so
$$AB + A’C + BC = AB + A’C + ABC + A’BC = AB(1 + C) + A’C(1 + B) = AB + A’C$$
In hardware: an entire gate disappears. This one is hard to see by eye, which is one of the reasons we use Karnaugh maps in section 1.4.
Synthesis tools apply all of these, and many more, automatically. The reason to know them anyway is that a designer who understands them writes cleaner RTL to begin with, and can read what the tool did afterwards.
Three worked simplifications
I write these as two columns, the expression and the rule that justifies each step.
Example 1: $F = A’B + A’B’ + AB$
| Expression | Rule |
|---|---|
| $A’B + A’B’ + AB$ | start |
| $A’(B + B’) + AB$ | distributivity |
| $A’ \cdot 1 + AB$ | complement |
| $A’ + AB$ | identity |
| $(A’ + A)(A’ + B)$ | second distributive law |
| $1 \cdot (A’ + B)$ | complement |
| $A’ + B$ | identity |
So $F = A’ + B$. We started with three product terms and five literals and finished with one OR gate and one inverter.
Example 2: $F = AB’C + AB’C’ + ABC$
| Expression | Rule |
|---|---|
| $AB’C + AB’C’ + ABC$ | start |
| $AB’(C + C’) + ABC$ | distributivity |
| $AB’ + ABC$ | complement, identity |
| $A(B’ + BC)$ | distributivity |
| $A(B’ + C)$ | the variant $X + X’Y = X + Y$ with $X = B'$ |
So $F = A(B’ + C) = AB’ + AC$. Nine literals became four.
Example 3: $F = ABC + ABD + A’B’C + A’B’D$
| Expression | Rule |
|---|---|
| $ABC + ABD + A’B’C + A’B’D$ | start |
| $AB(C + D) + A’B’(C + D)$ | distributivity |
| $(AB + A’B’)(C + D)$ | distributivity |
$AB + A’B’$ is XNOR and does not reduce further, so $F = (AB + A’B’)(C + D)$. This is a factored form: fewer gates than the two-level version, at the cost of one more level of logic.
Summary of the theorems
| Theorem | OR form | AND form |
|---|---|---|
| Identity | $A + 0 = A$ | $A \cdot 1 = A$ |
| Null | $A + 1 = 1$ | $A \cdot 0 = 0$ |
| Idempotency | $A + A = A$ | $A \cdot A = A$ |
| Complement | $A + A’ = 1$ | $A \cdot A’ = 0$ |
| Involution | $(A’)’ = A$ | |
| Commutativity | $A + B = B + A$ | $AB = BA$ |
| Associativity | $A + (B + C) = (A + B) + C$ | $A(BC) = (AB)C$ |
| Distributivity | $A + BC = (A + B)(A + C)$ | $A(B + C) = AB + AC$ |
| Absorption | $A + AB = A$ | $A(A + B) = A$ |
| Absorption variant | $A + A’B = A + B$ | $A(A’ + B) = AB$ |
| Consensus | $AB + A’C + BC = AB + A’C$ | $(A+B)(A’+C)(B+C) = (A+B)(A’+C)$ |
Practice Exercise
Problem 1. Simplify $F = AB + AB’ + A’B$.
Solution
| Expression | Rule |
|---|---|
| $AB + AB’ + A’B$ | start |
| $A(B + B’) + A’B$ | distributivity |
| $A + A’B$ | complement, identity |
| $A + B$ | absorption variant |
$F = A + B$.
Problem 2. Simplify $F = (A + B)(A + B’)$.
Solution
| Expression | Rule |
|---|---|
| $(A + B)(A + B’)$ | start |
| $A + BB'$ | second distributive law, in reverse |
| $A + 0$ | complement |
| $A$ | identity |
$F = A$. Whatever $B$ is, one of the two factors is $A + 1$ and the other is $A + 0$.
Problem 3. Simplify $F = A’BC + AB’C + ABC’ + ABC$.
Solution
The term $ABC$ can be used more than once by idempotency ($ABC = ABC + ABC + ABC$). Pair it with each of the other three:
| Expression | Rule |
|---|---|
| $A’BC + AB’C + ABC’ + ABC$ | start |
| $A’BC + AB’C + ABC’ + ABC + ABC + ABC$ | idempotency |
| $BC(A’ + A) + AC(B’ + B) + AB(C’ + C)$ | distributivity |
| $BC + AC + AB$ | complement, identity |
$F = AB + AC + BC$. This is the 3-input majority function from the last article. It does not reduce further: consensus does not apply, because no variable appears in both complemented and uncomplemented form. If you are tempted to drop a term, try $A = 0, B = 1, C = 1$: $F = 1$, and only the $BC$ term makes it so.
In the next article we look at the two identities you will use more than any other, De Morgan’s laws, which are the key to reading real schematics and to understanding why CMOS is built from NAND and NOR.