Questions: Tautologies, Contradictions, and Satisfiability

Question 1

Which statement correctly describes the relationship between tautologies and satisfiability?

• A. Every tautology is satisfiable, but not every satisfiable formula is a tautology
• B. A tautology and a satisfiable formula are the same thing
• C. A tautology is not satisfiable because its truth value doesn't depend on any specific assignment
• D. Every satisfiable formula must be a tautology, since satisfiability requires truth in all cases

Answer: (A)

A tautology is true under every truth assignment — which means it is certainly true under at least one, so it qualifies as satisfiable. But satisfiable only requires truth under at least one assignment. Contingencies (like p → q) are satisfiable but not tautologies, since they are false under some assignments. The relationship is: tautologies ⊂ satisfiable formulas. Contradictions are the only formulas that are unsatisfiable.

Question 2

A student claims: 'The formula (p → q) → p is a tautology because it seems obviously reasonable — if p implies q, then p is true.' This claim is:

• A. Correct — the formula holds under every truth assignment
• B. Incorrect — this is a contingency; when p is false, (p → q) is vacuously true, making (p → q) → p false
• C. Incorrect — this formula is actually a contradiction
• D. Correct only when p and q are propositional constants rather than variables

Answer: (B)

This is the classic trap of reasoning from intuition rather than checking all truth assignments. When p = false: (false → q) is true (vacuous implication), so (p → q) → p becomes true → false, which is false. The formula fails on this assignment, making it a contingency, not a tautology. This is why tautology-checking requires systematic verification of all 2ⁿ assignments, not just the plausible-seeming ones.

Question 3

If a formula φ is a tautology, then its negation ¬φ must be unsatisfiable.

• T. True
• F. False

Answer: True

This equivalence is fundamental: φ is a tautology (true under every assignment) if and only if ¬φ is false under every assignment (a contradiction), which is exactly what unsatisfiable means. This transformation is practically powerful for proof systems and automated reasoning: checking whether φ is a tautology can be converted into checking whether ¬φ is satisfiable, and vice versa. SAT solvers exploit this duality extensively.

Question 4

A satisfiable formula is one that is true under most possible truth assignments.

• T. True
• F. False

Answer: False

False. 'Satisfiable' means true under at least one truth assignment — not all of them. A formula that is true under all assignments is a tautology, which is a strictly stronger condition. Satisfiable formulas include tautologies (all assignments work), contingencies (some work, some don't), but not contradictions (no assignment works). Confusing 'satisfiable' with 'always true' is a common error that conflates two very different concepts.

Question 5

What is the practical value of being able to convert the question 'Is φ a tautology?' into 'Is ¬φ satisfiable?' Why might this conversion matter for automated reasoning?

Model answer: Tautology-checking and satisfiability-checking are in principle equivalent problems (one converts to the other by negation), but automated systems — especially SAT solvers — are specialized for satisfiability. By converting a tautology check into an unsatisfiability check on the negation, you can apply highly optimized SAT-solving algorithms to what was originally a validity question. This matters for proof systems, circuit verification, and formal methods, where the question 'is this formula always true?' is central but satisfiability tools are more computationally mature.

The tautology-contradiction-satisfiability triangle is not just a classification system — it is an operational toolkit. Every proof system targets exactly the tautologies. Every SAT solver operates on the satisfiability question. The equivalence between them means progress in one domain directly benefits the other. This is why the relationship is taught not as mere definitional housekeeping but as a conceptually powerful transformation.