Boolean algebra
The math of true and false
Boolean algebra is the mathematics of true and false: variables take only the values 0 or 1, combined with AND, OR, and NOT. Its identities and De Morgan's laws let you rewrite a logic expression into the simpler circuit that computes the same function.
Builds onBinary numbers
From binary a value is
0 or 1. Boolean algebra is the math you do with those two values, the way ordinary algebra is the math you do with numbers. It has three operations, AND, OR, and NOT, and a handful of laws that let you rewrite an expression into an equal but differently-shaped one. That rewriting is not abstract: a logic expression and a circuit are the same thing, so simplifying the algebra simplifies the hardware. The boolean algebra simplifier reduces any expression to its minimal form for you, and applied to every bit of two numbers at once, AND, OR, and XOR become the bitwise operators a CPU runs.The three operations
Read
1 as true and 0 as false. The operations match the everyday words:- AND (written
A AND B, orA·B) is1only when both inputs are1. Like "this and that must both hold." - OR (written
A OR B, orA+B) is1when at least one input is1. Like "this or that (or both)." - NOT (written
NOT A, orA') flips its single input:NOT 0 = 1,NOT 1 = 0.
The
+ and · notation is deliberate: AND behaves like multiplication and OR like addition, so A·1 = A and A + 0 = A read naturally. Just remember it is logic, not arithmetic: 1 + 1 = 1 in boolean OR (true-or-true is true), not 2.Identities: the rules you can always apply
A few laws hold for any inputs. They look obvious one at a time, and together they are enough to simplify almost any expression by hand:
A·0 = 0 A·1 = A A+0 = A A+1 = 1
A·A = A A+A = A A·A' = 0 A+A' = 1
The last two are the most useful.
A·A' = 0 says a thing AND its opposite is never both true. A+A' = 1 says a thing OR its opposite is always true. Double negation also cancels: NOT (NOT A) = A, which is exactly why AND is built as NAND then NOT, and OR as NOR then NOT: the two inversions undo each other.De Morgan's laws: swapping AND and OR
The two De Morgan's laws are the workhorses. They tell you how a NOT moves across an AND or an OR, and the operation flips when it crosses:
¬(A ∧ B) = (¬A) ∨ (¬B)
¬(A ∨ B) = (¬A) ∧ (¬B)
In words: "not (both)" is the same as "(not this) or (not that)", and "not (either)" is the same as "(not this) and (not that)". To apply a De Morgan law: push the NOT inward onto each input, and flip AND to OR (or OR to AND) as it passes through. You can check either law exhaustively by filling its truth table, which is the next lesson.
De Morgan's laws are why NAND and NOR are universal.
NOT(A AND B) (a NAND) equals (NOT A) OR (NOT B): an OR built from inverted inputs. So an OR is just a NAND fed inverted inputs, an AND is a NOR fed inverted inputs, and since NOT is a NAND with its inputs tied together, NAND alone can make everything. Every gate you build later is De Morgan's laws made physical.Try it
Use a De Morgan law to rewrite
NOT (A OR B OR C) without the outer NOT wrapping the whole group.Answer
Push the NOT onto each input and flip OR to AND:
NOT (A OR B OR C) = (NOT A) AND (NOT B) AND (NOT C). The result is 1 only when A, B, and C are all 0, which is exactly when the original A OR B OR C is 0.Duality: every law has a mirror twin
Look back at the identities you just met and you will notice they travel in pairs. That is the duality principle: take any true boolean identity, swap every
· (AND) with + (OR) and every 0 with 1, leave the variables and their NOTs untouched, and the identity you get is also true. One proof buys two laws. Here are pairs already on this page:A·0 = 0has the dualA+1 = 1: swap the·for+and the0for1.A·1 = Ahas the dualA+0 = A.A·A' = 0has the dualA+A' = 1.- Even De Morgan is a dual pair:
NOT (A·B) = A'+B'becomesNOT (A+B) = A'·B'.
Duality is not De Morgan, and confusing the two is the classic slip. Duality only swaps
· with + and 0 with 1; it never touches a variable, and the dual is a *different* identity, not an equal expression. De Morgan goes further: it also complements every variable, and it gives a real equality you can substitute into a formula. Use duality to double your stock of laws, use De Morgan to push a NOT through a gate.Seeing one law in a real gate
The NAND gate computes the left side of the first law,
NOT (A AND B). By De Morgan that is identical to (NOT A) OR (NOT B). So the NAND below is *also* an OR of the inverted inputs, the same function wearing two names. Toggle the inputs and you will see its output is 0 only when both inputs are 1 (the "not both" reading) and 1 whenever either input is 0 (the "not-A or not-B" reading).NOT (A AND B), which De Morgan's law says equals (NOT A) OR (NOT B). Open it in the lab and confirm both readings against the same four input rows: output low only when both inputs are high.Boolean algebra is the toolkit for *manipulating* logic. The companion tool for *defining* and *verifying* it is the truth table: list every input combination and the output you want, and you have an unambiguous specification you can both check an expression against and build a gate from.
Carving a function down: three judges
Here is that companion tool earning its keep. Three boxing judges each hold a button, call them
A, B, and C, and the win lamp Y should light when at least two of them press. Start with the truth table: one row for every combination of the three inputs.| A | B | C | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Y is 1 in exactly the four rows where two or more inputs are 1.To turn the table into an expression, write one AND term for each row where
Y is 1 (the term that is true for exactly that row, using A' wherever the input is 0) and OR the terms together. The four winning rows give a first, honest expression:Y = A'·B·C + A·B'·C + A·B·C' + A·B·C
Correct, but wasteful: four 3-input ANDs feeding a 4-input OR. Now simplify with the identities. The lever is idempotence,
A+A = A: OR-ing the term A·B·C into the sum extra times changes nothing, so keep two spare copies and pair one with each of the other terms.- Add two more copies of
A·B·C(idempotence):Y = (A'·B·C + A·B·C) + (A·B'·C + A·B·C) + (A·B·C' + A·B·C). - Factor the first pair, which shares
B·C:A'·B·C + A·B·C = B·C·(A' + A) = B·C·1 = B·C. - The second pair shares
A·C:A·B'·C + A·B·C = A·C·(B' + B) = A·C. The third sharesA·B:A·B·C' + A·B·C = A·B. - Collect the results:
Y = A·B + B·C + A·C.
Read the answer back in words: the lamp is on when
A and B both press, or B and C, or A and C, that is, whenever any two judges agree. Four large gates have collapsed to three 2-input ANDs and one OR computing the identical function, so the circuit is smaller, cheaper, and faster. That one-AND-term-per-true-row starting form is the sum of products, covered in canonical forms.This is the whole payoff of boolean algebra: the truth table is the honest specification, and the identities are the tools that carve it into the smallest circuit that still matches every row. A Karnaugh map later automates the same hunt for the minimal form, but the laws are what it is built on.
Try it
The majority function is self-dual: take the dual of
Y = A·B + B·C + A·C (swap every · for + and every + for ·) and simplify. What do you get, and why does that make sense?Answer
The dual is
(A + B)·(B + C)·(A + C). Multiply it out (using absorption like B + B·C = B) and it collapses right back to A·B + B·C + A·C. Landing on the same function is exactly what self-dual means, and it fits the rule: "at least two of three pressed" mirrors "at most one stayed up," so swapping AND with OR leaves the majority unchanged.Reading logic off a circuit
Everything above ran one way, from an expression to a circuit. The reverse skill matters just as much: someone hands you a finished circuit and you have to say what it computes. The method is mechanical. Start at the inputs, write the expression at the output of each gate, and walk toward the final output one level at a time.
Take a small two-level circuit: an AND gate fed by
A and B, a second AND gate fed by B and C, and an OR gate combining the two AND outputs into Y.- Level one, the gates touching the inputs. The top AND outputs
A·B; the bottom AND outputsB·C. - Level two, the gate fed by those results. The OR gives
Y = A·B + B·C. - Simplify.
Bis common to both terms, so factor it out with the distributive law:Y = A·B + B·C = B·(A + C). That is one OR feeding one AND, down from two ANDs and an OR.
The same walk works on an all-NAND circuit, you just carry the inversions. Suppose two NANDs feed a third:
G1 = NOT (A·B), G2 = NOT (B·C), and the output NAND gives Y = NOT (G1·G2).- Substitute the inner gates:
Y = NOT ( NOT (A·B) · NOT (B·C) ). - Apply De Morgan to the outer NOT: it splits the AND into an OR and flips each half,
Y = NOT (NOT (A·B)) + NOT (NOT (B·C)). - Double negations cancel:
Y = A·B + B·C, the very same function as the AND-OR circuit above, which factors again toB·(A + C).
That cancellation is why a two-layer NAND-NAND network is the workhorse of real chips: it computes any sum of products directly, and reading it back is nothing more than De Morgan erasing the double NOTs. Every AND-OR circuit has an equal NAND-only twin, which is NAND universality seen from the other direction.
Frequently asked
What is boolean algebra?
Boolean algebra is the mathematics of true and false, where every variable is
0 (false) or 1 (true). It has three operations, AND, OR, and NOT, plus a set of laws that let you rewrite a logic expression into an equal but differently-shaped one. Because an expression and a circuit are the same thing, simplifying the algebra simplifies the hardware.What is De Morgan's law?
De Morgan's two laws say a NOT flips the operation when it crosses an AND or OR:
NOT (A AND B) = (NOT A) OR (NOT B), and NOT (A OR B) = (NOT A) AND (NOT B). In words, "not (both)" equals "(not this) or (not that)". To apply one, push the NOT onto each input and swap AND for OR (or OR for AND).What is the difference between AND and OR in boolean algebra?
AND (written
A·B) is 1 only when both inputs are 1 and behaves like multiplication (A·1 = A, A·0 = 0). OR (written A+B) is 1 when at least one input is 1 and behaves like addition (A+0 = A, A+1 = 1). Just remember 1 + 1 = 1 in OR (true-or-true is true), not 2.Why are NAND and NOR called universal gates?
Because De Morgan's laws let either one build every operation.
NOT (A AND B) (a NAND) equals (NOT A) OR (NOT B), so an OR is a NAND fed inverted inputs and an AND is a NOR fed inverted inputs. Since a NOT is just a NAND with its inputs tied together, NAND alone can make any logic function.What is the duality principle in boolean algebra?
The duality principle says that if you take any true boolean identity and swap every AND (
·) with OR (+) and every 0 with 1, leaving the variables alone, the result is also a true identity. For example A·0 = 0 has the dual A+1 = 1. It is not the same as De Morgan's law: duality never complements a variable and produces a *different* identity, while De Morgan complements the variables and gives an equal expression you can substitute.How do you find the boolean expression of a logic circuit?
Work from the inputs toward the output one gate level at a time: write each gate's output as the AND, OR, or NOT of its inputs, substitute those results into the next gate, and repeat until you reach the final output. For a NAND-only circuit, apply De Morgan's law at each stage so the double NOTs cancel, which reveals the sum of products the network computes. Then simplify with the identities to get the smallest equivalent expression.
Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →