Tabla de contenido
Here you’ll learn how to determine if a logical expression is always true or always false depending on the circumstances, and we’ll do this with the help of a visual tool called a truth table, a fundamental tool in propositional logic.
In this guide, you’ll learn what they are, how to build them step by step, and how to use them to classify logical expressions.
What is a Truth Table?
A truth table is a tabular representation that shows all possible truth values of a logical expression, based on all possible combinations of its component propositions.
Formal Definition
A truth table systematically lists the truth value of a compound proposition for each possible combination of truth values of its simple propositions.
Who Developed Them?
Truth tables were developed by Charles Sanders Peirce in the 1880s and popularized by Ludwig Wittgenstein in his work Tractatus Logico-Philosophicus (1921). Today they are essential tools in logic, mathematics, computing, and digital electronics.
Atomic vs. Molecular Propositions
Before building truth tables, it’s important to understand the difference between these two types of propositions.
Atomic Propositions
An atomic proposition (or simple proposition) is a statement that cannot be broken down into simpler parts. It’s represented with lowercase letters: p, q, r, s…
| Example | Representation |
|---|---|
| “Today is Monday” | p |
| “It’s raining” | q |
| “2 + 2 = 4” | r |
Molecular Propositions (Molecular Schemas)
A molecular proposition (or compound proposition) is one formed by atomic propositions joined by logical connectives.
| Example | Representation |
|---|---|
| “Today is Monday AND it’s raining” | p ∧ q |
| “If it rains, then I get wet” | p → q |
| “It’s not true that 2+2=5” | ¬p |
What Does “Molecular” Mean?
It’s simply an analogy from chemistry:
- Atoms → Simple propositions (cannot be divided)
- Molecules → Compound propositions (atoms joined by “bonds” = connectives)
Molecular Schemas
A molecular schema is a propositional formula that combines variables (p, q, r…) and logical connectives (¬, ∧, ∨, →, ↔), organized using parentheses to establish the hierarchy of operations.
Examples of Molecular Schemas
| Schema | Reading |
|---|---|
| p ∧ q | “p and q” |
| p ∨ ¬q | “p or not q” |
| (p → q) ∧ r | “(if p then q) and r” |
| ¬(p ∨ q) → r | “if not (p or q), then r” |
Name of the Molecular Schema
The name of a molecular schema is determined by its main connective (the one with highest hierarchy, the last to be evaluated):
| Schema | Main Connective | Name |
|---|---|---|
| p ∧ q | ∧ | Conjunction |
| p ∨ q | ∨ | Disjunction |
| p → q | → | Conditional |
| p ↔ q | ↔ | Biconditional |
| ¬p | ¬ | Negation |
| (p ∧ q) → r | → | Conditional |
| p ∨ (q ∧ r) | ∨ | Disjunction |
What Are Truth Tables Used For?
Truth tables have multiple applications:
1. Determining truth values
They allow you to know the value of a compound expression for any combination of values of its components.
2. Classifying propositions
They help identify whether a proposition is a tautology, contradiction, or contingency.
3. Verifying logical equivalences
They allow you to prove that two expressions are logically equivalent (have the same truth values).
4. Validating arguments
They are used to verify if an argument is valid or invalid.
5. Digital circuit design
In electronics, truth tables describe the behavior of logic gates (AND, OR, NOT, etc.).
6. Programming
Boolean operators in programming languages follow the same rules.
Components of a Truth Table
A truth table has three main parts:
1. Variable Columns (Input)
The first columns contain the atomic propositions (p, q, r…) with all their value combinations.
2. Auxiliary Columns (Intermediate)
Columns for subexpressions that help calculate the final result step by step.
3. Main Column (Output)
The last column shows the truth value of the complete expression.
Visual Example
For the expression (p → q) ∧ p:
| p | q | p → q | (p → q) ∧ p |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | F |
| F | F | T | F |
- Input columns: p, q
- Auxiliary column: p → q
- Main column: (p → q) ∧ p
Number of Rows in a Truth Table
The number of rows is calculated with the formula:
Formula
\[\text{Number of rows} = 2^n\]
Where n is the number of distinct atomic propositions in the expression.
Why Is the Value 2ⁿ Used?
Each proposition can have 2 values (T or F). With n propositions, the possible combinations are:
| Propositions | Formula | Rows |
|---|---|---|
| 1 (just p) | 2¹ | 2 |
| 2 (p, q) | 2² | 4 |
| 3 (p, q, r) | 2³ | 8 |
| 4 (p, q, r, s) | 2⁴ | 16 |
| 5 | 2⁵ | 32 |
| 10 | 2¹⁰ | 1,024 |
Note: With 10 propositions, we’d already have more than a thousand rows. That’s why, for very complex expressions, other simplification methods are used.
The Correct Way to Fill in Variable Columns
There is a systematic method for assigning T and F values to atomic propositions, ensuring all combinations are covered.
Standard Method
For n propositions, each column follows an alternation pattern:
| Column | Alternation Pattern |
|---|---|
| 1st (leftmost) | Upper half T, lower half F |
| 2nd | Alternates in blocks of n/2 |
| 3rd | Alternates in blocks of n/4 |
| … | … |
| Last (rightmost) | Alternates T, F, T, F… one by one |
Example with 3 Variables (p, q, r)
| Row | p | q | r |
|---|---|---|---|
| 1 | T | T | T |
| 2 | T | T | F |
| 3 | T | F | T |
| 4 | T | F | F |
| 5 | F | T | T |
| 6 | F | T | F |
| 7 | F | F | T |
| 8 | F | F | F |
Observe the pattern starting from column 1:
- p: 4 T’s followed by 4 F’s
- q: 2 T, 2 F, 2 T, 2 F
- r: T, F, T, F, T, F, T, F (alternates one by one)
General Rule
For column i (counting from the right, starting with the first column):
- Alternate in blocks of 2^(i-1) values
Operator Hierarchy (Order of Evaluation)
When evaluating an expression, connectives are applied in this order of priority (from highest to lowest):
| Priority | Operator | Name |
|---|---|---|
| 1 (highest) | ¬ | Negation |
| 2 | ∧ | Conjunction |
| 3 | ∨ | Disjunction |
| 4 | → | Conditional |
| 5 (lowest) | ↔ | Biconditional |
Important Rules
- Parentheses always have maximum priority – What’s inside parentheses is evaluated first.
- For operators of equal priority – Evaluate from left to right.
Example
In the expression: ¬p ∨ q ∧ r → s
The order of evaluation would be:
- ¬p (negation first)
- q ∧ r (conjunction before disjunction)
- (¬p) ∨ (q ∧ r) (disjunction)
- Everything → s (conditional at the end)
Equivalent to: ((¬p) ∨ (q ∧ r)) → s
Truth Tables of Basic Connectives
Before building complex tables, let’s review the fundamental tables for each connective.
Negation (¬)
| p | ¬p |
|---|---|
| T | F |
| F | T |
Conjunction (∧)
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Only true when both are true.
Disjunction (∨)
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Only false when both are false.
Conditional (→)
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Only false when the antecedent is T and the consequent is F.
Biconditional (↔)
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
True when both have the same value.
Exclusive Disjunction (⊻ or XOR)
| p | q | p ⊻ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
True when they have different values.
Step-by-Step Construction: Examples
Example 1: Simple Expression
Let’s build the truth table for: p → (q ∧ p)
Step 1: Identify variables → p, q (n = 2, rows = 4)
Step 2: Create columns for variables and subexpressions (for the example: q ∧ p)
Step 3: Fill in the combinations of p and q
Step 4: Calculate q ∧ p
Step 5: Calculate p → (q ∧ p)
| p | q | q ∧ p | p → (q ∧ p) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | F | T |
| F | F | F | T |
Example 2: With Negation
Truth table for: ¬(p ∧ q) ∨ p
Step 1: Variables: p, q (n = 2, rows = 4)
Step 2: Subexpressions: p ∧ q, ¬(p ∧ q), final result
| p | q | p ∧ q | ¬(p ∧ q) | ¬(p ∧ q) ∨ p |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | T | T |
Observation: All results are T! This expression is a tautology.
Example 3: Complex Expression
Truth table for: (p → q) ∧ (q → r) → (p → r)
Step 1: Variables: p, q, r (n = 3, rows = 8)
| p | q | r | p→q | q→r | (p→q)∧(q→r) | p→r | Final |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
Observation: Again, all values are T. This is the law of the Hypothetical Syllogism, a fundamental tautology.
Classification of Propositions
According to the results of their truth table, propositions are classified as:
1. Tautology
A proposition is a tautology when it is always true, regardless of the truth values of its components.
| Main Column | Classification |
|---|---|
| T, T, T, T, … (only T) | Tautology |
Examples of tautologies:
- p ∨ ¬p (Law of Excluded Middle)
- p → p (Reflexivity)
- (p → q) ↔ (¬q → ¬p) (Contraposition)
2. Contradiction
A proposition is a contradiction when it is always false, regardless of the truth values of its components.
| Main Column | Classification |
|---|---|
| F, F, F, F, … (only F) | Contradiction |
Examples of contradictions:
- p ∧ ¬p
- (p → q) ∧ (p ∧ ¬q)
3. Contingency
A proposition is a contingency when its truth value depends on the values of its components (has a mix of T and F).
| Main Column | Classification |
|---|---|
| T, F, T, F, … (mixed) | Contingency |
Examples of contingencies:
- p ∧ q
- p → q
- p ∨ q
Visual Summary
| Type | All T | All F | Mixed |
|---|---|---|---|
| Tautology | ✅ | ||
| Contradiction | ✅ | ||
| Contingency | ✅ |
Using Tables to Verify Equivalences
Two expressions are logically equivalent if they have the same main columns in their truth tables.
Example: Verify that p → q ≡ ¬p ∨ q
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The columns for p → q and ¬p ∨ q are identical: T, F, T, T
Therefore: p → q ≡ ¬p ∨ q ✓
Practice Exercises
Exercise 1: Build Tables
Build the truth table for each expression:
- p ∧ (q ∨ r)
- ¬p → (q ∧ p)
- (p ↔ q) → (p ∧ q)
- ¬(p → q) ∨ q
Exercise 2: Classify
Determine if each expression is a tautology, contradiction, or contingency:
- p → (q → p)
- (p ∧ q) ∧ ¬(p ∧ q)
- p ∧ ¬q
- (p → q) ∨ (q → p)
Exercise 3: Verify Equivalences
Use truth tables to verify if they are equivalent:
- ¬(p ∧ q) and ¬p ∨ ¬q
- p → q and ¬q → ¬p
- p ∧ (p ∨ q) and p
Answers
Answers to Exercise 1
📝 I’ll leave building the truth tables for this exercise as practice. These are 8-row tables (3 variables), so it’s excellent practice for mastering the step-by-step method.
Answers to Exercise 2
- p → (q → p) = Tautology
| p | q | q → p | p → (q → p) |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | F | T |
| F | F | T | T |
- (p ∧ q) ∧ ¬(p ∧ q) = ContradictionIt’s of the form A ∧ ¬A, always false.
- p ∧ ¬q = ContingencyDepends on the values of p and q.
- (p → q) ∨ (q → p) = Tautology
| p | q | p → q | q → p | (p→q) ∨ (q→p) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Answers to Exercise 3
- ¬(p ∧ q) ≡ ¬p ∨ ¬q → Equivalent (De Morgan’s Law)
- p → q ≡ ¬q → ¬p → Equivalent (Contraposition)
- p ∧ (p ∨ q) ≡ p → Equivalent (Absorption Law)
Applications in Programming
Truth tables are fundamental in programming. Boolean operators work exactly the same way:
JavaScript / Python
// AND (&&) - Conjunction
true && true // true
true && false // false
// OR (||) - Disjunction
false || false // false
true || false // true
// NOT (!) - Negation
!true // false
!false // true
As you can see, the && (AND), || (OR), and ! (NOT) operators in programming behave exactly like their logical counterparts in truth tables.
Conditional Example in Code
# The expression: if (age >= 18 and has_license):
# Is a conjunction that is only True if BOTH conditions are met
age = 20
has_license = True
can_drive = age >= 18 and has_license # True
Upcoming Chapters
In the next chapter, we’ll explore Laws of Logical Equivalence, where you’ll learn to simplify expressions without needing to build complete truth tables.
Did you find this post useful? Leave me a comment with your questions or suggestions! And don’t forget to check out the next installment of this series on mathematical logic.