1
A tautology carries no information
p ∨ ¬p is true whatever p says, so learning it tells you nothing about the world. That is exactly why tautologies are useful as reasoning steps.
Lesson · Logic and Proof · Propositional logic
Tautology, Contradiction, Satisfiability
Classify a formula by its final column: all true, all false, or mixed. Then meet satisfiability — the question of whether any assignment works — and why it is the problem computer science measures hardness against.
tautology true under EVERY assignment p ∨ ¬p
contradiction true under NO assignment p ∧ ¬p
contingent true under some, false under others p ∧ q
satisfiable true under at least one assignment
Three classes, one question
Core ideas
What this lesson establishes
One column, three verdicts — and a fourth question that turns out to be the hard one.
2
Contradiction and negation are linked
A is a contradiction exactly when ¬A is a tautology. Every question about one is a question about the other.
3
Satisfiable is weaker than valid
Satisfiable asks whether SOME row is true; tautology asks whether EVERY row is. Most useful formulas are satisfiable and not tautologies.
The material
Classifying formulas
The three classes, then the question that made this lesson famous.
Definition · Tautology, contradiction, contingency
A formula is a tautology if it is true under every assignment, a contradiction if it is true under none, and contingent otherwise.
Definition · Satisfiability
A formula is satisfiable if at least one assignment makes it true. Tautologies and contingent formulas are satisfiable; contradictions are not.
The relationships are worth stating as a single sentence: A is a tautology exactly when ¬A is unsatisfiable, and A is satisfiable exactly when ¬A is not a tautology. Every one of these questions reduces to any other, which is why an algorithm for one is an algorithm for all.
Theorem · Equivalence as a tautology
A ≡ B if and only if A ↔ B is a tautology. “Logical Equivalence”'s whole subject is therefore a special case of this lesson's.
Deciding satisfiability by truth table takes 2ⁿ rows. For a formula with 300 variables — small by the standards of real applications — that is 2³⁰⁰ rows, more than there are atoms in the observable universe, and no faster general method is known.
Theorem · SAT is NP-complete (Cook, 1971)
The problem of deciding whether a propositional formula is satisfiable was the first problem shown NP-complete. Algorithms and Complexity defines the term; what matters here is that this lesson's innocent question is the reference point against which computational hardness is measured.
The practical situation is stranger than the theory suggests. Modern SAT solvers routinely handle formulas with millions of variables, because real instances have structure that the worst case does not. Hardness in the worst case and difficulty in practice are different claims.
Example · Classifying three formulas
(p → q) ∨ (q → p) is a tautology — check all four rows. (p ↔ q) ∧ (p ⊕ q) is a contradiction, since the two conjuncts are negations of each other. p → (q ∧ r) is contingent.
Interactive
Truth table
Every assignment, evaluated
Method
Classifying a formula
Look for a shortcut before writing 2ⁿ rows.
1
Try to make it false
To test for a tautology, assume the whole formula is false and work backwards. If that forces a contradiction, it is a tautology.
2
Try to make it true
To test satisfiability, look for one assignment. Finding it ends the question; a table is only needed when you fail.
3
Use the structure
A disjunction is satisfiable if either side is; a conjunction is a contradiction if either side is. Half the work is often unnecessary.
4
Fall back on the table
When the shortcuts do not settle it, 2ⁿ rows always will. Correctness beats elegance when the answer matters.
Classification
Score 0 / 0Choose the answer you can justify.
Is ((p → q) ∧ ¬q) → ¬p a tautology?
Assume it is false and see whether that is possible.
Suppose the whole conditional is FALSE.
then (p → q) ∧ ¬q is T and ¬p is F
¬p = F ⟹ p = T
(p → q) ∧ ¬q = T ⟹ p → q = T and ¬q = T
¬q = T ⟹ q = F
p = T, q = F ⟹ p → q = F CONTRADICTION
No assignment makes it false, so it is a TAUTOLOGY.
This tautology has a name: modus tollens, the inference rule of “Rules of Inference”. Every valid rule of inference is a tautology in exactly this shape — premises conjoined, implying the conclusion.
Common mistakes
1
Confusing satisfiable with trueA satisfiable formula is one that could be true. Whether it is true depends on the assignment, which the formula alone does not fix.
2
Assuming a tautology says somethingTautologies are exactly the formulas that carry no information about the world. Their usefulness lies in being safe to assert, not in being informative.
3
Reading NP-complete as "impossible"It is a statement about worst-case scaling. SAT solvers handle industrial instances with millions of variables every day.
Check your understanding
✓
Finish when you can settle a tautology claim by assuming it false.
Take (p ∨ q) → (p ∧ q) and decide its class without a full table, by trying to construct a falsifying assignment. You should find one in two lines — and be able to say which row it is.
Note: The lab reports the count of satisfying rows, not only the verdict. That count is the number of models of the formula, and counting models is a strictly harder problem than deciding whether one exists.