Truth tables and equivalence
Prerequisite: review 1.1 Propositional logic first, because the truth-table language uses the same connectives.
What a truth table does
Definition
Truth table
A truth table lists the truth value of a formula for every possible assignment of its variables.
It is the safest way to check whether two formulas always match.
A first example
Worked example
Checking implication by rows
Consider the formula P → Q.
| P | Q | P → Q |
| --- | --- | --- |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The formula is false only in the row where P is true and Q is false.
Solution
Why `P → Q` matches `¬P ∨ Q`
Logical equivalence
Definition
Logical equivalence
Two formulas are logically equivalent when they have the same truth value in every row of their truth tables.
That means a rewrite is allowed only if the whole table matches, not just one example row.
Common mistake
One matching row is not a proof
If two formulas agree on a single assignment, that does not prove equivalence.
You must compare every row, or use a known equivalence law such as
P → Q ≡ ¬P ∨ Q.
Tautologies and contradictions
Definition
Two special kinds of formulas
- A tautology is always true.
- A contradiction is always false.
Examples:
P ∨ ¬Pis a tautology.P ∧ ¬Pis a contradiction.
Quick check
Quick check
Are `P ∧ Q` and `Q ∧ P` logically equivalent?
Try it live
Try it here
Truth-table builder
The live builder lets you switch formulas and inspect how each row changes the final truth value.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |