07 · Tautology, Contradiction, Contingency, Satisfiability

Definitions

TermMeaningExample
TautologyAlways TRUE (every row T)
ContradictionAlways FALSE (every row F)
ContingencySometimes T, sometimes F
SatisfiableAt least one row Ttautologies + contingencies
UnsatisfiableNo row T= contradiction
Valid= tautology
InvalidNot a tautology (contradiction or contingency)

Summary grid

TautologyContingencyContradiction
Truth valuesalways Tsometimes T/Falways 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:

  1. Assume it’s false ⇒ = T and = F (the only F row of →).
  2. Propagate the forced values.
  3. 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 showFind
Not a tautologyone F row
Satisfiableone T row
Tautologycontradiction when assuming F (or simplify to T)
Contradictioncontradiction 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