Base CS from zero
Boolean logic
You already know that a bit is either 0 or 1. Now consider this: those two values can
mean more than just numbers. They can mean true and false. A 1 stored in a
variable called isLoggedIn means “yes, this user is logged in.” A 0 stored in
fileExists means “no, that file is not there.”
Once a bit carries a truth value, you need operations that work on truth values — ways
to ask “are both conditions true?” or “is at least one true?” or “flip this from true to
false.” These are the operations of boolean logic, and they are the foundation of
every decision a computer ever makes — from a simple if statement to the billion
transistors deciding in parallel which memory address to fetch next.
After this lesson you can explain what a boolean value is, read and construct truth tables for AND, OR, and NOT, evaluate any combination of these operations on given inputs, and explain at a conceptual level why AND, OR, and NOT together are enough to express every possible true/false rule.
True and false as a bit. A boolean value is a value that can only be true or
false — nothing in between. In hardware and in most programming languages, true is
stored as 1 and false as 0. (Some languages use the word boolean or bool for the
type; others just use an integer and treat 0 as false and any non-zero value as true.)
The name comes from George Boole (1815–1864), a mathematician who formalised a system of algebra that works with truth values instead of numbers. His algebra uses 1 for true and 0 for false, and defines operations that map truth values to truth values. This is exactly what a computer needs: the state of a transistor is either high (1, true) or low (0, false), and logic circuits combine those states to make decisions.
The crucial insight: a bit is already a boolean. When you read a bit, you can choose to interpret it as the number 0 or 1, or you can interpret it as the truth value false or true. The hardware stores the same thing; the meaning depends on how your software interprets it.
Truth tables: the complete definition of an operation. A truth table lists every possible combination of inputs and the output the operation produces for each. For operations on truth values, an input is either 0 (false) or 1 (true), so two inputs give 2 × 2 = 4 rows. One input gives 2 rows.
A truth table is not just a helpful summary — it is the definition. Two operations are the same operation if and only if their truth tables are identical. This makes truth tables the primary tool for reasoning about boolean logic: if you want to prove that two expressions are equivalent, show that they produce the same output for every row.
NOT: the simplest operation. NOT takes one input and flips it. If the input is true (1), the output is false (0). If the input is false (0), the output is true (1). That is all it does — invert.
| Input A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
In code you write this as !a (most languages) or not a (Python). In digital circuits
it is called an inverter. The symbol in diagrams is a small circle on the output.
AND: true only when both inputs are true. AND takes two inputs and produces 1 if and only if both inputs are 1. If either input (or both) is 0, the output is 0.
| Input A | Input B | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In code: a && b or a and b. Natural language equivalent: “A is true and B is
true.” Only one row in the four-row table produces 1 — the bottom row where both
inputs are 1. This matches the everyday meaning of “and”: the sentence “it is raining
and I have an umbrella” is true only when both halves are true.
A concrete example: isLoggedIn AND hasPermission is 1 only when the user is both
logged in and has the required permission. Either condition failing is enough to deny
access.
OR: true when at least one input is true. OR takes two inputs and produces 1 if at least one input is 1. It produces 0 only when both inputs are 0.
| Input A | Input B | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
In code: a || b or a or b. Three rows out of four produce 1; only the top row
(both false) produces 0. This is inclusive or — “A or B or both.”
A concrete example: isCacheHit OR isPreloaded is 1 if the data is available by either
means. The requestor does not care which path delivered the data — either suffices.
Edge cases
Boolean OR in computing is inclusive or (true if one or both). Natural language “or” is often exclusive or (XOR) — “soup or salad” usually means one, not both. The XOR operation is true only when inputs differ (A=0 B=1 gives 1; A=1 B=0 gives 1; A=0 B=0 gives 0; A=1 B=1 gives 0). XOR is a useful and common operation, but it is not one of the three primitives — it can be built from AND, OR, and NOT.
Combining operations. Real programs combine AND, OR, and NOT into larger expressions. Evaluation follows operator precedence: NOT first, then AND, then OR (just like multiplication before addition in arithmetic). Parentheses override precedence.
Consider: NOT A OR (B AND C). With A=1, B=1, C=0:
- NOT A = NOT 1 = 0
- B AND C = 1 AND 0 = 0
- 0 OR 0 = 0
With A=0, B=1, C=1:
- NOT A = NOT 0 = 1
- B AND C = 1 AND 1 = 1
- 1 OR 1 = 1 (OR of two 1s is still 1)
Compound expressions like this appear constantly in code: access control checks, cache invalidation rules, retry logic, input validation — all reduce to boolean expressions evaluated on bit-wide truth values.
Why this works
Why are AND, OR, and NOT enough? The claim is that every possible rule for computing a true/false result from any number of true/false inputs — no matter how exotic — can be expressed using only AND, OR, and NOT. Why?
Any truth table with N inputs has 2^N rows. For each row where the output is 1, you can write one AND expression that is true exactly for that row (using NOT to negate any input that is 0 in that row). Then you OR all those per-row expressions together. The result is true for exactly the rows where the output is 1 and false everywhere else — which matches the original truth table perfectly.
This construction is called disjunctive normal form (DNF). It proves that AND, OR, and NOT can express every truth table that can be written down, which means every boolean function that exists. The set (AND, OR, NOT) is functionally complete.
You can go even further: (AND, NOT) alone is complete (OR can be built from them:
A OR B = NOT(NOT A AND NOT B)), and so is (OR, NOT). Most strikingly, NAND alone is
complete — the entire computer can be built from a single type of gate — which is the
premise of the nand2tetris course.
Evaluate (A AND NOT B) OR (NOT A AND B) for all four input combinations.
This expression is called XOR (exclusive or): it is true when exactly one input is true.
| A | B | !B | !A | A && !B | !A && B | XOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
The output is 1 exactly when A and B differ. This is how XOR is built from AND, OR, and NOT — demonstrating that those three operations are genuinely enough to construct new ones.
1 AND 0 = ?
1 OR 0 = ?
NOT 0 = ?
0 OR 0 = ?
NOT 1 AND 1 = ? (Evaluate NOT first, then AND.)
How many rows does the truth table for a two-input operation have?
You want to express XOR (true when exactly one input is true) using only AND, OR, and NOT. Is this possible?
A boolean value is true (1) or false (0) — a single bit interpreted as a truth value. NOT inverts: NOT 1 = 0, NOT 0 = 1. AND is 1 only when both inputs are 1; all other cases give 0. OR is 0 only when both inputs are 0; all other cases give
- A truth table lists every input combination and the corresponding output — it is the complete, unambiguous definition of an operation. AND, OR, and NOT together are functionally complete: every possible boolean function, no matter how complex, can be built from these three operations. The technique is disjunctive normal form: write one AND expression per output-1 row, then OR those expressions together. This completeness is why these three operations (or even just NAND alone) are enough to construct an entire computer.