Logic II: Truth-Functions, Truth Tables, the Shorter Truth-Table Method and Proofs of Validity

This chapter takes the syllabus items "Truth-Functions and Propositional Logic", "Symbolic Logic: Use of symbols", "Decision Procedures: Truth Table, Using Truth-Tables for testing the validity of arguments" and "Proving Validity, Argument and Argument-form". It follows the notation of Irving Copi's Introduction to Logic and Symbolic Logic, which Indian university courses use: ~ for negation, · for conjunction, ∨ for inclusive disjunction, ⊃ for material implication and ≡ for material equivalence. Every truth table and every proof below is worked in full so that it can be checked line by line, and the quiz asks for computations, not definitions.

1. Symbols and truth-functions

A compound statement is truth-functional when its truth-value is fixed entirely by the truth-values of its components. The five connectives of propositional logic are defined by their truth tables. Note especially the conditional: p ⊃ q is false in exactly one case, when p is true and q is false, and is therefore true whenever p is false. This "material" conditional is weaker than the everyday "if... then", which is why a false antecedent makes a conditional true.

Truth tables of the five connectives
pq~pp · qp ∨ qp ⊃ qp ≡ q
TTFTTTT
TFFFTFF
FTTFTTF
FFTFFTT
  • Translation: "p unless q" is p ∨ q; "p only if q" is p ⊃ q; "p if q" is q ⊃ p; "p if and only if q" is p ≡ q; "neither p nor q" is ~p · ~q, equivalently ~(p ∨ q); "not both p and q" is ~(p · q).
  • Main connective: the connective with the widest scope, which determines the form of the whole. In ~(p · q) ⊃ r the main connective is ⊃; in ~[(p · q) ⊃ r] it is ~.
  • Tautology, contradiction, contingency: a statement form is tautologous if true in every row, self-contradictory if false in every row, and contingent otherwise. Two forms are logically equivalent when their biconditional is a tautology, that is, when they agree in every row.

2. Truth tables as a decision procedure

A truth table for a form with n distinct variables has 2ⁿ rows, since each variable can be true or false independently: 2 variables give 4 rows, 3 give 8, 4 give 16, 5 give 32. By convention the first variable alternates in blocks of half the rows, the next in blocks of a quarter, and so on, down to the last, which alternates every row. Because a finite table settles every case, truth tables are a decision procedure for propositional logic: they decide, mechanically and in a finite number of steps, whether any form is tautologous or any argument form valid.

Worked: p ⊃ q is equivalent to ~p ∨ q and to ~q ⊃ ~p
pqp ⊃ q~p ∨ q~q ⊃ ~pq ⊃ p
TTTTTT
TFFFFT
FTTTTF
FFTTTT

The columns for p ⊃ q, ~p ∨ q and ~q ⊃ ~p agree in all four rows, so they are logically equivalent (the replacement rules material implication and transposition). The converse q ⊃ p differs in rows 2 and 3, so a conditional is not equivalent to its converse, which is the source of the fallacy of affirming the consequent.

Worked validity test: modus ponens against affirming the consequent
pqp ⊃ q (premise)Modus ponens: premise p, conclusion qAffirming the consequent: premise q, conclusion p
TTTpremises T, T; conclusion Tpremises T, T; conclusion T
TFFa premise is Fa premise is F
FTTa premise is Fpremises T, T; conclusion F: counterexample
FFTa premise is Fa premise is F
ℹ️ The test in one sentence
An argument form is valid if and only if there is no row of its truth table in which all the premises are true and the conclusion false. Modus ponens has no such row. Affirming the consequent has one, row 3 (p false, q true), so it is invalid.

3. The shorter truth-table method

A full table for five variables has 32 rows. The shorter (indirect) method instead tries to construct a counterexample directly: assign the conclusion the value false and every premise the value true, then work out what the variables must be. If a consistent assignment results, it is a counterexample and the argument is invalid. If every attempt forces some variable to be both true and false, no counterexample exists and the argument is valid. When the conclusion can be false in more than one way, each way must be tried.

Three worked tests
Argument formWorkingVerdict
p ⊃ q, q ⊃ r ∴ p ⊃ r (hypothetical syllogism)Conclusion false forces p = T, r = F. Premise p ⊃ q true with p = T forces q = T. Premise q ⊃ r true with r = F forces q = F. q cannot be both T and FValid
p ∨ q, p ∴ ~qConclusion false forces q = T. Premise p true forces p = T. Then p ∨ q = T ∨ T = T, so every premise is true and the conclusion false with p = T, q = TInvalid (counterexample p = T, q = T)
(p ⊃ q) · (r ⊃ s), p ∨ r ∴ q ∨ s (constructive dilemma)Conclusion false forces q = F, s = F. The first premise true makes p ⊃ q and r ⊃ s true, forcing p = F and r = F. Then p ∨ r = F, so the second premise is falseValid
⚠️ Inclusive "or"
The second example is invalid because ∨ is inclusive: "p or q" is true when both are true, so learning that p is true tells us nothing about q. The valid pattern is disjunctive syllogism, which goes the other way: from p ∨ q and ~p, infer q. Inferring ~q from p ∨ q and p is sometimes called affirming a disjunct.

4. Proving validity: rules of inference and replacement

Truth tables become unwieldy for many variables, so validity is also shown by a formal proof: a sequence of statements, each either a premise or derived from earlier lines by a rule, ending in the conclusion. An argument is a set of statements; an argument form is its skeleton with statement variables, and a given argument is a substitution instance of every form it fits. Copi's system has nine rules of inference, which apply only to whole lines, and ten rules of replacement, which license replacing a part of a line by a logically equivalent expression.

The nine rules of inference
RuleForm
Modus ponens (MP)p ⊃ q, p ∴ q
Modus tollens (MT)p ⊃ q, ~q ∴ ~p
Hypothetical syllogism (HS)p ⊃ q, q ⊃ r ∴ p ⊃ r
Disjunctive syllogism (DS)p ∨ q, ~p ∴ q
Constructive dilemma (CD)(p ⊃ q) · (r ⊃ s), p ∨ r ∴ q ∨ s
Absorption (Abs)p ⊃ q ∴ p ⊃ (p · q)
Simplification (Simp)p · q ∴ p
Conjunction (Conj)p, q ∴ p · q
Addition (Add)p ∴ p ∨ q
The ten rules of replacement (each states a logical equivalence)
RuleEquivalence
De Morgan's theorems (De M)~(p · q) ≡ (~p ∨ ~q); ~(p ∨ q) ≡ (~p · ~q)
Commutation (Com)(p ∨ q) ≡ (q ∨ p); (p · q) ≡ (q · p)
Association (Assoc)[p ∨ (q ∨ r)] ≡ [(p ∨ q) ∨ r], and the same for ·
Distribution (Dist)[p · (q ∨ r)] ≡ [(p · q) ∨ (p · r)]; [p ∨ (q · r)] ≡ [(p ∨ q) · (p ∨ r)]
Double negation (DN)p ≡ ~~p
Transposition (Trans)(p ⊃ q) ≡ (~q ⊃ ~p)
Material implication (Impl)(p ⊃ q) ≡ (~p ∨ q)
Material equivalence (Equiv)(p ≡ q) ≡ [(p ⊃ q) · (q ⊃ p)]; (p ≡ q) ≡ [(p · q) ∨ (~p · ~q)]
Exportation (Exp)[(p · q) ⊃ r] ≡ [p ⊃ (q ⊃ r)]
Tautology (Taut)p ≡ (p ∨ p); p ≡ (p · p)
Worked proof: (P ∨ Q) ⊃ R, S ⊃ ~R, S ∴ ~P
LineStatementJustification
1(P ∨ Q) ⊃ RPremise
2S ⊃ ~RPremise
3SPremise
4~R2, 3 MP
5~(P ∨ Q)1, 4 MT
6~P · ~Q5 De M
7~P6 Simp
🎯 Why simplification cannot be used on part of a line
Rules of inference are valid argument forms, so they apply only to entire lines: from (p · q) ⊃ r one may not infer p ⊃ r by "simplifying" the antecedent, and indeed that inference is invalid (let p be true, q false, r false). Rules of replacement are equivalences, so they may be applied to any part of a line. Conditional proof (assume the antecedent, derive the consequent, discharge the assumption) and indirect proof (assume the negation of the conclusion and derive a contradiction) extend the system, and the formal fallacies of affirming the consequent and denying the antecedent are exactly the invalid look-alikes of MP and MT.

Key takeaways

  • Five connectives: ~, ·, ∨ (inclusive), ⊃ (false only when T ⊃ F), ≡; "p only if q" is p ⊃ q, "p unless q" is p ∨ q, "neither p nor q" is ~p · ~q.
  • A truth table for n variables has 2ⁿ rows (16 for four, 32 for five); tautology, contradiction and contingency; equivalence as agreement in every row; p ⊃ q equals ~p ∨ q and ~q ⊃ ~p, but not q ⊃ p.
  • An argument form is valid iff no row makes all premises true and the conclusion false; affirming the consequent fails in the row p = F, q = T.
  • Shorter truth-table method: make the conclusion false and premises true; a consistent assignment is a counterexample (invalid), a forced contradiction shows validity (HS and CD valid; p ∨ q, p ∴ ~q invalid).
  • Nine rules of inference (MP, MT, HS, DS, CD, Abs, Simp, Conj, Add) apply to whole lines; ten rules of replacement (De M, Com, Assoc, Dist, DN, Trans, Impl, Equiv, Exp, Taut) apply to parts; conditional and indirect proof extend the system.

Practice questions (10)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. How many rows does a complete truth table need for a statement form containing four distinct variables? Type the number.

    Numerical answer — type the value.

    Show answer

    Answer: 16

    Each variable can be true or false independently, so n variables give 2ⁿ rows: 2⁴ = 16. Three variables would need 8 and five would need 32.

  2. A material conditional p ⊃ q is false when:

    1. p and q are both false
    2. p is false and q is true
    3. p is true and q is false
    4. p and q are both true
    Show answer

    Answer: C — p is true and q is false

    The conditional is false in exactly one row, true antecedent with false consequent. With a false antecedent it is true whatever q is, and with both true it is true.

  3. From "p ⊃ q" and "~q", the inference to "~p" is justified by:

    1. Disjunctive syllogism
    2. Modus tollens
    3. Denying the antecedent
    4. Modus ponens
    Show answer

    Answer: B — Modus tollens

    Modus tollens denies the consequent to deny the antecedent. Modus ponens affirms the antecedent; denying the antecedent (from p ⊃ q and ~p to ~q) is the invalid look-alike.

  4. By De Morgan's theorem, ~(p · q) is logically equivalent to:

    1. ~p ∨ ~q
    2. ~p · ~q
    3. p ∨ q
    4. ~p ⊃ q
    Show answer

    Answer: A — ~p ∨ ~q

    "Not both p and q" is true unless both are true, which is exactly when at least one is false: ~p ∨ ~q. The form ~p · ~q ("neither") is equivalent to ~(p ∨ q), the other De Morgan theorem.

  5. Using the shorter truth-table method, which of the following argument forms is INVALID?

    1. p ∨ q, ~p ∴ q
    2. p ⊃ q, q ⊃ r ∴ p ⊃ r
    3. p ⊃ q, ~p ∴ ~q
    4. p ⊃ q, ~q ∴ ~p
    Show answer

    Answer: C — p ⊃ q, ~p ∴ ~q

    For p ⊃ q, ~p ∴ ~q, make the conclusion false (q = T) and the premise ~p true (p = F); then p ⊃ q is F ⊃ T = T. All premises are true and the conclusion false, so it is invalid (denying the antecedent). The other three are MT, DS and HS; in each, trying to build a counterexample forces a contradiction.

  6. Assertion (A): The argument form "p ⊃ q, q ∴ p" is invalid. Reason (R): Every argument with a true conclusion is valid. Choose the correct option.

    1. Both A and R are true, and R is the correct explanation of A
    2. Both A and R are true, but R is not the correct explanation of A
    3. A is true, but R is false
    4. A is false, but R is true
    Show answer

    Answer: C — A is true, but R is false

    A is true: the row p = F, q = T makes both premises true and the conclusion false (affirming the consequent). R is false: validity is a matter of form, and an invalid form can have instances with true conclusions; what cannot happen in a valid argument is true premises with a false conclusion.

  7. Assertion (A): (p · q) ⊃ p is a tautology. Reason (R): A truth table for n variables has 2ⁿ rows. Choose the correct option.

    1. Both A and R are true, and R is the correct explanation of A
    2. Both A and R are true, but R is not the correct explanation of A
    3. A is true, but R is false
    4. A is false, but R is true
    Show answer

    Answer: B — Both A and R are true, but R is not the correct explanation of A

    Both are true, but R does not explain A. (p · q) ⊃ p is tautologous because the antecedent is true only when p is true, so the conditional can never be T ⊃ F; this holds in all four rows. The row count is a general fact about truth tables and gives no reason why this particular form is true in every row.

  8. Which of the following statement forms are tautologies? Select all that apply.

    1. (p · ~p) ⊃ q
    2. p ⊃ (q ⊃ p)
    3. p ⊃ (p · q)
    4. (p ⊃ q) ⊃ p
    Show answer

    Answer: A — (p · ~p) ⊃ q; B — p ⊃ (q ⊃ p)

    p ⊃ (q ⊃ p) is false only if p is true and q ⊃ p false, but q ⊃ p is false only if p is false: impossible, so it is a tautology. (p · ~p) ⊃ q has an antecedent that is false in every row, so it is always true. (p ⊃ q) ⊃ p is false when p = F (then p ⊃ q is T and the whole is T ⊃ F). p ⊃ (p · q) is false when p = T, q = F.

  9. Which of the following are rules of replacement (not rules of inference) in Copi's system? Select all that apply.

    1. Transposition
    2. Absorption
    3. Disjunctive syllogism
    4. Exportation
    Show answer

    Answer: A — Transposition; D — Exportation

    Transposition, (p ⊃ q) ≡ (~q ⊃ ~p), and exportation, [(p · q) ⊃ r] ≡ [p ⊃ (q ⊃ r)], are equivalences and may be applied to parts of lines. Absorption and disjunctive syllogism are among the nine rules of inference and apply only to whole lines.

  10. In how many rows of the complete truth table for "(p ∨ q) ⊃ r" is the statement false? Type the number.

    Numerical answer — type the value.

    Show answer

    Answer: 3

    The table has 2³ = 8 rows. A conditional is false only when its antecedent is true and its consequent false, so r must be F (4 rows) and p ∨ q must be T. Among those 4 rows, p ∨ q is false only when p = F and q = F, so it is true in 3 of them. The statement is false in exactly 3 rows.