A propositional formula contains 4 distinct atomic propositions (P, Q, R, S). How many rows does its complete truth table have?
A4 rows — one row per atomic proposition
B8 rows — 2 × 4
C16 rows — 2⁴
D256 rows — 4⁴
Each atomic proposition is independently assigned either T or F. With n atomic propositions, there are 2ⁿ possible combinations: 2 × 2 × ... × 2 (n times). For 4 propositions: 2⁴ = 16 rows. Option A confuses the number of rows with the number of atoms. Option D (4⁴) would apply if each atom had 4 possible values rather than 2. The exponential growth of truth table size with the number of atoms is why propositional tautology-checking becomes computationally expensive for large formulas — it is a coNP-complete problem.
Question 2 Multiple Choice
A student builds a truth table for ¬(P ∧ Q) → (¬P ∨ ¬Q) and finds the final column is all T (true in every row). What can she conclude?
AThe formula is contingent — it happens to be true for all current truth values of P and Q
BThe formula is a tautology — it is true under every possible interpretation, demonstrating De Morgan's Law as a logical truth
CThe formula is a contradiction — all-true final columns indicate unsatisfiability
DThe formula is valid only when P and Q are both true
A formula is a tautology if and only if its truth table final column contains all T. This formula — which expresses De Morgan's Law — is indeed a tautology: ¬(P ∧ Q) and ¬P ∨ ¬Q are logically equivalent, so the biconditional (and therefore the implication in both directions) holds under every interpretation. Option A misuses 'contingent': contingent means SOMETIMES true, SOMETIMES false. All-T means true regardless of what P and Q mean — it's a logical truth, not a fact about any particular domain.
Question 3 True / False
A formula that is true in 15 out of 16 rows of its truth table is a tautology.
TTrue
FFalse
Answer: False
A tautology must be true in ALL rows — every possible truth assignment yields T. A formula that is false in even a single row is not a tautology; it is contingent (sometimes true, sometimes false). There is no 'almost tautology' classification in classical logic. The single false row is enough to show that there exists an interpretation under which the formula fails, disqualifying it from tautological status. This is why truth tables are a complete decision procedure: you cannot conclude a formula is a tautology without checking every row.
Question 4 True / False
Two propositional formulas are logically equivalent if and only if they produce identical columns in their joint truth table.
TTrue
FFalse
Answer: True
Logical equivalence is defined semantically: two formulas φ and ψ are logically equivalent (φ ⟺ ψ) if they have the same truth value under every possible interpretation. The truth table directly tests this: identical columns mean they agree on all 2ⁿ possible assignments. An equivalent formal characterization: φ ↔ ψ is a tautology. Both characterizations are equivalent. This semantic notion of equivalence is what makes truth tables useful for verifying logical laws like De Morgan's, double negation, and distribution — each law is just a claim that two formula schemas have identical truth tables.
Question 5 Short Answer
What is the difference between a tautology, a contradiction, and a contingent formula? Give a simple example of each.
Think about your answer, then reveal below.
Model answer: A tautology is true under every possible truth assignment — its truth table final column is all T. Example: P ∨ ¬P (the law of excluded middle — P is either true or false, so one of P or ¬P is always true). A contradiction is false under every possible truth assignment — its truth table final column is all F. Example: P ∧ ¬P (P cannot be both true and false simultaneously). A contingent formula is sometimes true and sometimes false — its truth table final column contains both T and F. Example: P ∧ Q (true when both P and Q are true, false otherwise).
These three categories are exhaustive and mutually exclusive — every propositional formula falls into exactly one of them. The practical importance: tautologies are logical truths that hold regardless of interpretation (useful as inference rules); contradictions are always false (their negations are tautologies, a useful proof technique); contingent formulas make substantive claims that could be true or false depending on the world. Truth tables settle the classification mechanically and definitively.