07 · Tautology, Contradiction, Contingency, Satisfiability
Definitions
| Term | Meaning | Example |
|---|---|---|
| Tautology | Always TRUE (every row T) | |
| Contradiction | Always FALSE (every row F) | |
| Contingency | Sometimes T, sometimes F | |
| Satisfiable | At least one row T | tautologies + contingencies |
| Unsatisfiable | No row T | = contradiction |
| Valid | = tautology | |
| Invalid | Not a tautology (contradiction or contingency) |
Summary grid
| Tautology | Contingency | Contradiction | |
|---|---|---|---|
| Truth values | always T | sometimes T/F | always F |
| Satisfiable? | ✅ | ✅ | ❌ |
| Valid? | ✅ | ❌ | ❌ |
Take-aways
- Every tautology is satisfiable; not every satisfiable formula is a tautology.
- Invalid ≠ always false. A contingency is invalid too. (“Satisfiable but not valid” = contingency.)
- is a tautology ⟺ is a contradiction (unsatisfiable).
- is satisfiable ⟺ is not a tautology.
⚡ The “assume FALSE” trick (fastest GATE technique)
To test whether is a tautology:
- Assume it’s false ⇒ = T and = F (the only F row of →).
- Propagate the forced values.
- Contradiction reached ⇒ it can never be false ⇒ tautology. Consistent assignment found ⇒ that row falsifies it ⇒ not a tautology.
Is a tautology?
Assume false ⇒ = F ⇒ a = T, c = F. Antecedent must be T ⇒ = T ⇒ b = T; then = T → F = F ❌. Contradiction ⇒ tautology ✅ (this is hypothetical syllogism).
Is a tautology?
Assume false ⇒ consequent F ⇒ ¬b = T and = F. Antecedent T ⇒ a = c ⇒ a = c = F. Check: = T ✓, b = F, = F ✓. Consistent ⇒ NOT a tautology (falsified by a = b = c = F). ← GATE 2014.
Which test to use
Want to show Find Not a tautology one F row Satisfiable one T row Tautology contradiction when assuming F (or simplify to T) Contradiction contradiction when assuming T (or simplify to F)
Logical implication (⇒) vs implication (→)
- (“P logically implies Q”) means is a tautology.
- / means is a tautology.
- ”→” is an operator inside a formula; ”⇒” and ”≡” are statements about formulas. → GATE 2016 in 11 GATE PYQs.
Prev ← 06 Logic Puzzles · Next → 08 Logical Equivalences