101
0/276
Loading content...
How do you precisely define what AND, OR, and NOT mean? Not through vague English descriptions, but with mathematical rigor that leaves no ambiguity?
The answer is the truth table—a systematic enumeration of every possible input combination and its corresponding output. Truth tables are the formal specification of boolean operations, used identically by logicians, mathematicians, computer scientists, and electrical engineers.
When you truly understand truth tables, you possess the complete knowledge of boolean logic. There are no hidden cases, no edge conditions, no surprises—the truth table shows everything.
By the end of this page, you will understand truth tables as the formal definition of boolean operations, master the fundamental operations (AND, OR, NOT, XOR, NAND, NOR), see how complex expressions decompose into truth tables, and recognize why these concepts matter for both programming and hardware.
A truth table is a tabular representation that exhaustively lists every possible combination of inputs to a boolean expression along with the resulting output.
The structure of a truth table:
For n inputs, there are 2ⁿ rows:
| Inputs | Possible Combinations |
|---|---|
| 1 variable (A) | 2 rows: T, F |
| 2 variables (A, B) | 4 rows: TT, TF, FT, FF |
| 3 variables (A, B, C) | 8 rows |
| 4 variables | 16 rows |
| n variables | 2ⁿ rows |
Why truth tables are complete:
A boolean variable has exactly 2 states. With n independent variables, the total possibility space is 2 × 2 × ... × 2 = 2ⁿ. The truth table covers every point in this space—no combination is missed, no ambiguity remains.
Truth table as contract:
Think of a truth table as a contract that completely specifies the behavior of a boolean operation. If you follow the inputs down to the corresponding row, you will find the exact output—guaranteed, always, universally true.
Truth tables use various notations: T/F, True/False, 1/0, High/Low. We'll use T (true) and F (false) for clarity. In digital circuits, 1 and 0 are more common. The concepts are identical regardless of notation.
The simplest boolean operation is NOT, also called negation or inversion. It takes a single input and produces its opposite.
Symbols:
The truth table for NOT:
| A | NOT A |
|---|---|
| T | F |
| F | T |
Understanding NOT:
NOT simply flips the value:
Key properties of NOT:
Programming examples:
isLoggedIn = true
if (!isLoggedIn) { // NOT isLoggedIn → false
redirectToLogin()
}
doorLocked = false
if (!doorLocked) { // NOT false → true
allowEntry()
}
Common patterns:
!isEmpty → "has content"!isValid → "is invalid"!found → "still searching"NOT interacts with AND and OR in profound ways captured by De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B), and NOT(A OR B) = (NOT A) AND (NOT B). We'll see these in the complex expressions section.
AND, also called conjunction, outputs true only when all inputs are true. It represents the logical concept of "both conditions must hold."
Symbols:
The truth table for AND:
| A | B | A AND B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Understanding AND:
Key properties of AND:
Programming examples:
// Both conditions must be true
if (hasPermission && isAuthenticated) {
grantAccess()
}
// Guard pattern using AND
if (array != null && array.length > 0) {
processFirstElement(array[0])
}
Real-world analogy:
AND is like a series circuit with two switches. Current flows (output = true) only if both switches are closed (both inputs = true). Open either switch, and the circuit breaks.
AND extends naturally to more inputs: A AND B AND C AND D is true only if ALL inputs are true. With n inputs, there's exactly 1 true output (all inputs true) and 2ⁿ-1 false outputs.
OR, also called disjunction, outputs true when at least one input is true. It represents the logical concept of "either condition may hold" (inclusive or).
Symbols:
The truth table for OR:
| A | B | A OR B |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Understanding OR:
Key properties of OR:
Programming examples:
// Either condition suffices
if (isAdmin || isOwner) {
showEditButton()
}
// Default value pattern
name = providedName || "Anonymous"
Real-world analogy:
OR is like a parallel circuit with two switches. Current flows (output = true) if either switch is closed (either input = true). Both must be open for the circuit to break.
Inclusive vs. Exclusive:
This OR is inclusive—true when both inputs are true. English "or" is sometimes exclusive ("soup or salad" implies one, not both). Programming uses inclusive OR; exclusive OR (XOR) is a separate operation.
Read 'A OR B' as 'at least one of A, B is true.' This includes the case where both are true. For exactly-one semantics, use XOR (covered next).
XOR (Exclusive OR) outputs true when exactly one input is true—when the inputs differ. It captures the "one or the other, but not both" meaning of "or."
Symbols:
The truth table for XOR:
| A | B | A XOR B |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Understanding XOR:
Key properties of XOR:
XOR's special powers:
// Swap without temporary variable
a = a ^ b // a now holds a XOR b
b = a ^ b // b now holds original a
a = a ^ b // a now holds original b
// Toggle a boolean
value = value ^ true // Flips value
// Check if two values differ
if (old ^ new) {
handleChange()
}
Real-world applications:
XOR is equivalent to addition modulo 2: 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0. This connection links boolean algebra to finite field arithmetic, important in cryptography and coding theory.
NAND (NOT AND) and NOR (NOT OR) are each functionally complete—any boolean function can be built using only NAND gates, or only NOR gates. This profound property makes them the building blocks of digital hardware.
NAND truth table:
| A | B | A NAND B |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
NOR truth table:
| A | B | A NOR B |
|---|---|---|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
Why NAND is universal:
Every other operation can be built from NAND:
NOT A = A NAND A
A AND B = (A NAND B) NAND (A NAND B)
A OR B = (A NAND A) NAND (B NAND B)
This means you can construct any boolean circuit—no matter how complex—using only NAND gates.
Why this matters for hardware:
Historical note:
The Apollo Guidance Computer (1966) that landed humans on the Moon was built almost entirely from NOR gates—about 5,600 of them implementing 3-input NOR logic. This uniformity simplified design, testing, and manufacturing for a mission-critical system.
NAND outputs false only when both inputs are true (the opposite of AND). Think of it as 'not both'—it fails only in the single case where both conditions are met.
Complex boolean expressions combine multiple operations. Truth tables expand to handle any expression by evaluating step-by-step.
Example: (A AND B) OR (NOT C)
We need 3 variables → 2³ = 8 rows:
| A | B | C | A AND B | NOT C | Result |
|---|---|---|---|---|---|
| T | T | T | T | F | T |
| T | T | F | T | T | T |
| T | F | T | F | F | F |
| T | F | F | F | T | T |
| F | T | T | F | F | F |
| F | T | F | F | T | T |
| F | F | T | F | F | F |
| F | F | F | F | T | T |
Reading the table:
The expression is true in 5 out of 8 cases:
De Morgan's Laws:
These fundamental equivalences simplify boolean expressions:
NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)
De Morgan's laws allow you to:
Example application:
// Original
if (!(isNull || isEmpty)) { process(); }
// Apply De Morgan's: NOT(A OR B) = NOT A AND NOT B
if (!isNull && !isEmpty) { process(); }
Both forms are logically equivalent; the second is often more readable.
Simplification through truth tables:
If two expressions have identical truth tables, they're logically equivalent. This provides a mechanical way to verify simplifications or find simpler forms of complex expressions.
Standard precedence: NOT binds tightest, then AND, then OR. So 'A OR B AND C' means 'A OR (B AND C)', not '(A OR B) AND C'. When in doubt, use parentheses for clarity.
Understanding truth tables pays dividends across computing—from debugging conditionals to designing digital circuits.
Debugging complex conditions:
When a boolean expression behaves unexpectedly:
Design verification:
Before implementing a complex condition:
Applications beyond programming:
The limits of truth tables:
Truth tables grow exponentially: n variables → 2ⁿ rows. For 20 variables, you'd need over 1 million rows. This is why:
Despite this scaling limit, truth tables remain invaluable for understanding and debugging the boolean expressions we encounter daily in programming.
Next time you write a complex if-condition, try sketching its truth table. Even for 2-3 variables (4-8 rows), this exercise builds intuition and often reveals edge cases you'd otherwise miss.
We've explored truth tables as the formal foundation of boolean logic. Let's consolidate what we've learned:
Module Complete:
You've now mastered the boolean data type from multiple perspectives:
This foundation prepares you for every algorithm that involves decision-making—which is to say, every algorithm. Booleans may be the simplest primitive, but they enable the full complexity of computation.
You've completed the Boolean Data Type module! From George Boole's 19th-century insights to modern CPU branch predictors, booleans connect logic, hardware, and software. This humble two-valued type is the foundation upon which all computational decision-making rests. Next, explore how primitive operations connect to algorithmic complexity in Module 7.