Key takeaways
- Boolean algebra writes logic with 1 for true, 0 for false, · or juxtaposition for AND, + for OR and a bar or prime for NOT.
- Its laws are the laws of logic: commutative, associative, distributive both ways, identity, complement, idempotent, absorption and De Morgan's.
- Logic gates are physical versions of the operations: AND, OR and NOT, plus XOR, NAND and NOR.
- Any truth table can be turned into a circuit by writing a sum of products, one term for each row whose output is 1, then simplifying.
- NAND alone can build NOT, AND and OR, so it can build every circuit.
Boolean algebra is propositional logic written as algebra: 1 for true, 0 for false, and familiar-looking symbols for AND, OR and NOT. Applied Discrete Structures tells the story from the switching side. Early computers relied on many switches to perform logical operations, and pioneers such as Claude Shannon realised that the circuits could be simplified by using an isomorphism between circuits and Boolean algebra. Today's circuits, the book continues, are made of large quantities of gates, which serve the same purpose as switches but can be miniaturised to a great degree.
The notation
| Logic | Boolean algebra | Gate |
|---|---|---|
| p ∧ q | xy (or x · y) | AND |
| p ∨ q | x + y | OR |
| ¬p | x̄ (or x′) | NOT (inverter) |
| p ⊕ q | x ⊕ y | XOR |
| ¬(p ∧ q) | (xy)‾ | NAND |
| ¬(p ∨ q) | (x + y)‾ | NOR |
The only values are 0 and 1, so the tables are short: 1 + 1 = 1 (true OR true is true), 1 · 0 = 0, and the complement of 1 is 0. Applied Discrete Structures uses this notation for its gates, writing XOR, NAND and NOR as x₁ ⊕ x₂, the complement of x₁ · x₂ and the complement of x₁ + x₂.
The laws
Because Boolean algebra is logic in disguise, its laws are the laws of logic:
| Law | Form |
|---|---|
| Commutative | x + y = y + x; xy = yx |
| Associative | (x + y) + z = x + (y + z); (xy)z = x(yz) |
| Distributive | x(y + z) = xy + xz; x + yz = (x + y)(x + z) |
| Identity | x + 0 = x; x · 1 = x |
| Complement | x + x̄ = 1; x · x̄ = 0 |
| Idempotent | x + x = x; xx = x |
| Domination | x + 1 = 1; x · 0 = 0 |
| Absorption | x + xy = x; x(x + y) = x |
| De Morgan's | (x + y)‾ = x̄ ȳ; (xy)‾ = x̄ + ȳ |
The bold distributive law has no counterpart in ordinary arithmetic, and the idempotent laws look wrong if you read + as addition. Read + as OR and they are obvious. De Morgan's laws are especially useful for circuits, because they convert between AND-based and OR-based designs.
In the abstract, MathWorld defines a Boolean algebra as a bounded, distributive lattice in which every element has a complement, and describes a Boolean algebra of sets: a family of subsets of a fixed set, closed under union, intersection and complement. The two-element algebra of 0 and 1 is the one used for circuits.
From truth table to expression
Any truth table can be written as a Boolean expression, by a recipe that always works.
Example: the majority function. Three inputs; the output is 1 when at least two inputs are 1.
| x | y | z | M |
|---|---|---|---|
| 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 |
Step 1: sum of products. For each row where M = 1, write a product that is 1 on that row only, negating the inputs that are 0:
M = x̄yz + xȳz + xyz̄ + xyz.
Step 2: simplify. Using idempotence to reuse xyz three times (xyz = xyz + xyz + xyz):
M = (x̄yz + xyz) + (xȳz + xyz) + (xyz̄ + xyz) = yz + xz + xy.
Each bracket simplifies with the distributive and complement laws, for example x̄yz + xyz = yz(x̄ + x) = yz. The result, M = xy + yz + xz, needs three AND gates and one three-input OR gate instead of the four three-input ANDs of step 1. Applied Discrete Structures uses the laws the same way, simplifying a three-input circuit until it can be realised by a much simpler one that does not even need the third input. The truth table guide covers building the table in the first place.
Building an adder
Adding two one-bit numbers x and y gives a sum bit S and a carry bit C:
| x | y | C | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Reading the columns: S = x ⊕ y and C = xy. One XOR gate and one AND gate form a half adder. Chaining adders, with carries passed along, adds binary numbers of any length, which ties this topic to binary representation. The majority function above is exactly the carry-out of a full adder, which adds three bits: the carry is 1 when at least two of them are 1.
NAND can do everything
The NAND gate outputs the complement of xy. With NAND alone:
- NOT: x NAND x = (xx)‾ = x̄.
- AND: take NAND, then NOT it: ((xy)‾)‾ = xy.
- OR: x̄ NAND ȳ = (x̄ ȳ)‾ = x + y, by De Morgan's law.
Since AND, OR and NOT can express any truth table (by the sum-of-products recipe), NAND gates alone can build any circuit. NOR gates have the same property. Applied Discrete Structures sets the related exercise of building XOR from AND, OR and NOT; one answer is x ⊕ y = xȳ + x̄y.
Exercises in simplifying and building gates
- Simplify x + x̄y. (x + y, using the distributive law x + x̄y = (x + x̄)(x + y).)
- Write a sum of products for a function that is 1 exactly when x = y. (x̄ȳ + xy.)
- Build NOT x using only NOR gates.
Circuits that also remember a state, rather than just combining their inputs, are modelled by finite state machines. The logic behind all of this is the first unit of Discrete Math: Study & Quiz, logic and reasoning, and the app's tools include a truth-table generator, a logical-equivalence checker and a statement simplifier for practising it. It is one of our education apps; the discrete math hub has the logic series in order.
Good to know
Frequently asked questions
What is Boolean algebra?
How is Boolean algebra different from ordinary algebra?
How do you turn a truth table into a Boolean expression?
Why is NAND a universal gate?
Sources
- A Brief Introduction to Switching Theory and Logic Design (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Boolean Algebras (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Boolean Algebra (opens in a new tab)Wolfram MathWorld — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.