Truth Tables
Definition
A truth table is a table that lists all possible truth value combinations of one or more propositions and shows the resulting truth value of a logical expression for each combination.
If a proposition can be either True (T) or False (F), then a truth table enumerates every possible arrangement of these truth values and evaluates logical connectives such as:
Negation
- : ¬p
Conjunction
- : p ∧ q
Disjunction
- : p ∨ q
Implication
- : p → q
Biconditional
- : p ↔ q
Truth tables are used to verify logical identities, test arguments, and simplify Boolean expressions.
Main Content
1. Basic Structure of Truth Tables
- A truth table consists of columns and rows.
- Each row represents one possible combination of truth values for the propositions involved, and the final column gives the output of the logical expression.
For example, for a single proposition p, there are only two possibilities:
| p | ¬p |
|---|---|
| T | F |
| F | T |
For two propositions p and q, there are 4 combinations:
| p | q |
|---|---|
| T | T |
| T | F |
| F | T |
| F | F |
For three propositions p, q, and r, there are 8 combinations. In general, for n propositions, a truth table has 2ⁿ rows.
This is because each proposition can take two possible truth values, and all combinations must be considered.
2. Common Logical Operators and Their Truth Values
- Truth tables are used to define and understand the behavior of logical connectives.
- Each operator has a precise meaning based on how it transforms truth values.
Negation (NOT)
Negation reverses the truth value of a proposition.
| p | ¬p |
|---|---|
| T | F |
| F | T |
Conjunction (AND)
The conjunction p ∧ q is true only when both propositions are true.
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction (OR)
The disjunction p ∨ q is true when at least one proposition is true.
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Implication (IF...THEN)
The statement p → q is false only when p is true and q is false.
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
This may seem unusual at first, but it matches the logical interpretation that a promise is broken only when the condition holds and the result fails.
Biconditional (IF AND ONLY IF)
The statement p ↔ q is true when both propositions have the same truth value.
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
These operators form the building blocks of propositional logic expressions.
3. Evaluating Compound Propositions and Logical Equivalence
- Truth tables allow us to evaluate complex logical expressions step by step.
- They are also used to check whether two expressions are logically equivalent.
For example, consider the expression:
¬(p ∧ q)
Construct the truth table:
| p | q | p ∧ q | ¬(p ∧ q) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
Now compare it with:
¬p ∨ ¬q
| p | q | ¬p | ¬q | ¬p ∨ ¬q |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Since both final columns are identical, we conclude:
¬(p ∧ q) ≡ ¬p ∨ ¬q
This is an example of De Morgan’s Law.
Truth tables are also used to test whether two expressions are equivalent by comparing their final columns across all possible rows.
Working / Process
1. Identify all propositions
- Determine the atomic statements involved, such as p, q, and r.
- Assign each one a truth value of T or F.
2. List all possible combinations
- For one proposition, there are 2 rows.
- For two propositions, there are 4 rows.
- For three propositions, there are 8 rows.
- Continue until every possible case is covered.
3. Evaluate the logical expression row by row
- Compute the truth value of each smaller part of the expression first.
- Use the rules of logical operators to fill in the final column.
- Compare results if checking equivalence or validity.
Example:
Evaluate (p ∨ q) → p
| p | q | p ∨ q | (p ∨ q) → p |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | F |
| F | F | F | T |
This shows the statement is not always true, so it is not a tautology.
A simple logical layout can be visualized like this:
p ──┐
├─ AND ──> p ∧ q ──┐
q ──┘ ├─ NOT ──> ¬(p ∧ q)
This kind of stepwise evaluation is very useful in propositional logic and digital circuit design.
Advantages / Applications
Helps test logical validity
- Truth tables show whether an argument is valid by checking whether the conclusion must be true whenever the premises are true.
- They are widely used in mathematical proof and logical reasoning.
Useful in digital electronics
- Logic gates such as AND, OR, NOT, NAND, NOR, XOR, and XNOR are directly represented using truth tables.
- Engineers use truth tables to design and verify circuits before implementation.
Important in finite state machines and computing
- Truth tables help describe transition and output logic in simplified state-based systems.
- They are also used in programming, compiler design, decision-making systems, and Boolean algebra simplification.
Detects tautologies, contradictions, and contingencies
- A tautology is always true.
- A contradiction is always false.
- A contingency is sometimes true and sometimes false.
- Truth tables make these classifications immediate and accurate.
Supports logical equivalence and simplification
- By comparing truth tables, one can verify whether two Boolean expressions are equivalent.
- This helps reduce complex expressions into simpler forms.
Summary
- Truth tables list all possible truth value combinations of propositions and evaluate logical expressions systematically.
- They are essential for understanding logical connectives, checking equivalence, and analyzing arguments.
- Truth tables are widely used in propositional logic, digital circuits, and the basic logic behind finite state machines.
- Important terms to remember: proposition, truth value, conjunction, disjunction, negation, implication, biconditional, tautology, contradiction, logical equivalence