- Practice
- About 21 min
- 5 practice questions
Tautology, contradiction, duality and logical equivalence
Classify formulas as tautologies, contradictions or contingencies, write the dual of a formula, prove logical equivalences with truth tables, and use the laws of equivalence to simplify statements.
If something looks wrong, please tell us.
By the end of this lesson you can
- Decide from a truth table whether a formula is a tautology, a contradiction or a contingency.
- Write the dual of a formula and state the principle of duality.
- Prove two formulas are logically equivalent with a truth table.
- Use the laws (idempotent, commutative, associative, distributive, identity, complement, double negation, De Morgan, absorption) to simplify without a truth table.
Some formulas are true however their parts turn out, some are always false, and many pairs of formulas that look different say exactly the same thing. Recognising these is the core of logical reasoning, and the laws of equivalence turn logic into an algebra.
Tautology, contradiction and contingency
A tautology (written 𝕋) is a statement that is always true, whatever the truth values of its components: its truth table column is all T. A contradiction (written 𝔽) is always false: its column is all F. A statement that is neither is a contingency: its column has both T and F. The negation of a tautology is a contradiction and vice versa. Two basic examples: p ∨ ¬p is a tautology and p ∧ ¬p is a contradiction, because p and ¬p always have opposite values.
Worked example 1: three classifications
| p | q | p → q | (p → q) ∧ p | [(p → q) ∧ p] → q | (p ∨ q) ∧ (¬p ∧ ¬q) | p → (p ∧ q) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | F | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | F | T |
| F | F | T | F | T | F | T |
[(p → q) ∧ p] → q has only T, so it is a tautology: it is the familiar rule "if p implies q, and p holds, then q holds". (p ∨ q) ∧ (¬p ∧ ¬q) has only F, so it is a contradiction: the first part says at least one is true, the second says neither is. p → (p ∧ q) has both T and F, so it is a contingency.
Duality
The dual of a formula is obtained by replacing ∨ by ∧, ∧ by ∨, 𝕋 by 𝔽 and 𝔽 by 𝕋 (and T by F, F by T). The symbol ¬ is not changed, the dual of the dual is the original formula, and 𝕋 and 𝔽 are duals of each other. For example, the dual of (p ∧ q) ∨ (¬r ∧ 𝕋) is (p ∨ q) ∧ (¬r ∨ 𝔽). Principle of duality: if a compound statement S₁ contains only ¬, ∧ and ∨, and S₂ is obtained from S₁ by interchanging ∧ and ∨, then S₁ is a tautology if and only if S₂ is a contradiction. That is why the laws below come in dual pairs.
Logical equivalence
Two statements A and B are logically equivalent, written A ≡ B (or A ⇔ B), if their truth table columns are identical. Then A ↔ B is a tautology. Each law below can be proved by a truth table.
| Law | Form (i) | Dual form (ii) |
|---|---|---|
| Idempotent | p ∨ p ≡ p | p ∧ p ≡ p |
| Commutative | p ∨ q ≡ q ∨ p | p ∧ q ≡ q ∧ p |
| Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Identity | p ∨ 𝔽 ≡ p, p ∨ 𝕋 ≡ 𝕋 | p ∧ 𝕋 ≡ p, p ∧ 𝔽 ≡ 𝔽 |
| Complement | p ∨ ¬p ≡ 𝕋, ¬𝕋 ≡ 𝔽 | p ∧ ¬p ≡ 𝔽, ¬𝔽 ≡ 𝕋 |
| Double negation | ¬(¬p) ≡ p | (self-dual) |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q | ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Absorption | p ∨ (p ∧ q) ≡ p | p ∧ (p ∨ q) ≡ p |
p → q ≡ ¬p ∨ q; p → q ≡ ¬q → ¬p; p ↔ q ≡ (p → q) ∧ (q → p); ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.
Worked example 2: p → q ≡ ¬p ∨ q and the contrapositive
| p | q | ¬p | ¬q | p → q | ¬p ∨ q | ¬q → ¬p | q → p |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | F | F | T |
| F | T | T | F | T | T | T | F |
| F | F | T | T | T | T | T | T |
The columns for p → q, ¬p ∨ q and ¬q → ¬p are identical (T, F, T, T), so p → q ≡ ¬p ∨ q ≡ ¬q → ¬p. The column for the converse q → p is T, T, F, T, which differs in rows 2 and 3, so a conditional is not equivalent to its converse. Using the first equivalence and De Morgan: ¬(p → q) ≡ ¬(¬p ∨ q) ≡ ¬¬p ∧ ¬q ≡ p ∧ ¬q.
Worked example 3: simplifying with the laws
(i) Show (p ∧ q) ∨ (p ∧ ¬q) ≡ p. By the distributive law, (p ∧ q) ∨ (p ∧ ¬q) ≡ p ∧ (q ∨ ¬q). By the complement law q ∨ ¬q ≡ 𝕋, and by the identity law p ∧ 𝕋 ≡ p.
(ii) Simplify p ∨ (¬p ∧ q). Distributive: ≡ (p ∨ ¬p) ∧ (p ∨ q). Complement: ≡ 𝕋 ∧ (p ∨ q). Identity: ≡ p ∨ q.
(iii) Show p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q). Start from p ↔ q ≡ (p → q) ∧ (q → p) ≡ (¬p ∨ q) ∧ (¬q ∨ p). Distribute (¬p ∨ q) over the second bracket: ≡ [(¬p ∨ q) ∧ ¬q] ∨ [(¬p ∨ q) ∧ p] ≡ (¬p ∧ ¬q) ∨ (q ∧ ¬q) ∨ (¬p ∧ p) ∨ (q ∧ p). The middle two are 𝔽 by the complement law, and dropping 𝔽 terms by the identity law leaves (p ∧ q) ∨ (¬p ∧ ¬q), after reordering by the commutative law.
Proving an equivalence by the laws
- Remove → and ↔ Use p → q ≡ ¬p ∨ q.
- Push ¬ inwards De Morgan and double negation.
- Distribute Expand or factor with the distributive laws.
- Tidy Complement, identity, absorption, idempotent.
Then back to step 1: Remove → and ↔
Key takeaways: a tautology is always T, a contradiction always F, anything mixed is a contingency. To dualise, swap ∧ with ∨ and 𝕋 with 𝔽, leaving ¬ alone. Equivalent formulas have identical truth columns; the laws let you prove equivalences by algebra. A conditional equals its contrapositive and ¬p ∨ q, but not its converse.
Check your understanding
-
1. What kind of statement is p ∨ ¬p?
- A contradiction
- A tautology
- A contingency
- Equivalent to p
Show answer
Answer: B. p and ¬p always have opposite truth values, so one of them is true and p ∨ ¬p is always T. It is a tautology.
-
2. What is the dual of p ∧ (q ∨ 𝕋)?
- p ∨ (q ∧ 𝔽)
- p ∨ (q ∧ 𝕋)
- ¬p ∨ (¬q ∧ 𝔽)
- p ∧ (q ∨ 𝔽)
Show answer
Answer: A. Replace ∧ by ∨, ∨ by ∧ and 𝕋 by 𝔽, keeping the variables (and any ¬) unchanged: p ∨ (q ∧ 𝔽).
-
3. Which formula is logically equivalent to ¬(p ∧ q)?
- ¬p ∧ ¬q
- ¬p ∨ ¬q
- p ∨ q
- ¬p ∧ q
Show answer
Answer: B. By De Morgan's law, the negation of a conjunction is the disjunction of the negations: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
-
4. Which formula is logically equivalent to ¬(p → q)?
- ¬p → ¬q
- ¬p ∧ q
- q → p
- p ∧ ¬q
Show answer
Answer: D. p → q ≡ ¬p ∨ q, so ¬(p → q) ≡ ¬(¬p ∨ q) ≡ ¬¬p ∧ ¬q ≡ p ∧ ¬q by De Morgan and double negation. A conditional is false exactly when p is true and q is false.
-
5. How is p → (p ∧ q) classified?
- A tautology
- A contradiction
- A contingency
- Equivalent to p
Show answer
Answer: C. When p is T and q is F, p ∧ q is F, so the conditional is T → F = F. In the other three rows it is T. A column with both T and F is a contingency.
Sign in to keep track of the lessons you finish.