Chapter 05 of 30

Rules of Inference

A detective says: "If the thief came through the window, there would be mud on the floor. There is no mud. So the thief did not come through the window." A student says: "If I study, I pass. I passed. So I must have studied." Both sound reasonable, but only the detective's reasoning is valid. The student's is a well-known fallacy, and the conclusion may be false even if both premises are true.

Rules of inference are the small, guaranteed-safe reasoning steps from which every correct argument is built. They are what a proof is made of, what a theorem prover or a Prolog engine executes, and what GATE asks you to check. In this chapter we define valid arguments, list the standard rules (and the two classic fallacies), write formal step-by-step proofs, learn the resolution rule used by automated provers, and finally extend everything to quantified statements from Predicate Logic & Quantifiers. Every argument marked valid or invalid here was checked by a truth-table program.


Arguments and Validity

An argument is a list of propositions called premises (hypotheses) p1, p2, ..., pn, followed by a proposition called the conclusion q. The argument is valid if, whenever all the premises are true, the conclusion is also true. Equivalently, the argument is valid exactly when
(p1 ∧ p2 ∧ ... ∧ pn) → q is a tautology.

We write an argument either as p1, ..., pn ⊢ q, or in the column format used in many Indian textbooks:

    p → q
    p
  -------
  ∴ q

(∴ is read "therefore".)

Valid Is Not the Same as True

Validity is about the form of the argument, not about whether the premises are actually true.

  • "If 7 is even, then 7 is divisible by 2. 7 is even. Therefore 7 is divisible by 2." This argument is valid (it is modus ponens), but its conclusion is false, because a premise is false.

  • An argument is sound if it is valid and all its premises are true. A sound argument always has a true conclusion.

Checking Validity with a Truth Table

The direct method: list all rows; find the rows where every premise is true; check that the conclusion is true in each of them. A single row with all premises T and the conclusion F (a counterexample) makes the argument invalid.

Shortcut. Instead of the whole table, try to build a counterexample: set the conclusion to F, then try to make every premise T. If this is forced into a contradiction, the argument is valid; if it succeeds, you have the counterexample.

Example. Is p → q, q → r, r ⊢ p valid? Set p = F (conclusion false). We need r = T. Then q → r is true whatever q is, and p → q is true because p is false. So p = F, q = T, r = T makes all premises true and the conclusion false. Invalid.


The Rules of Inference

Truth tables grow as 2n, and they do not explain the reasoning. Instead we use a small set of rules, each of which is a tautology checked once and for all. Then any chain of rule applications is automatically valid.

Rule

Premises ⊢ Conclusion

Tautology behind it

Modus ponens (affirming the antecedent)

p → q, p ⊢ q

((p → q) ∧ p) → q

Modus tollens (denying the consequent)

p → q, ¬q ⊢ ¬p

((p → q) ∧ ¬q) → ¬p

Hypothetical syllogism (chain rule)

p → q, q → r ⊢ p → r

((p → q) ∧ (q → r)) → (p → r)

Disjunctive syllogism

p ∨ q, ¬p ⊢ q

((p ∨ q) ∧ ¬p) → q

Addition

p ⊢ p ∨ q

p → (p ∨ q)

Simplification

p ∧ q ⊢ p

(p ∧ q) → p

Conjunction

p, q ⊢ p ∧ q

(p ∧ q) → (p ∧ q)

Resolution

p ∨ q, ¬p ∨ r ⊢ q ∨ r

((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)

Constructive dilemma

p → q, r → s, p ∨ r ⊢ q ∨ s

((p → q) ∧ (r → s) ∧ (p ∨ r)) → (q ∨ s)

Destructive dilemma

p → q, r → s, ¬q ∨ ¬s ⊢ ¬p ∨ ¬r

((p → q) ∧ (r → s) ∧ (¬q ∨ ¬s)) → (¬p ∨ ¬r)

In addition, any logical equivalence from Logical Equivalences & Normal Forms (De Morgan, double negation, p → q ≡ ¬p ∨ q, contrapositive, ...) may be used to rewrite a line, because replacing a formula by an equivalent one never changes its truth value.

Each Rule in Plain Words

  • Modus ponens: "If it rains, the ground is wet. It rains. So the ground is wet."

  • Modus tollens: "If it rained, the ground would be wet. The ground is dry. So it did not rain." (This is the detective's argument.)

  • Hypothetical syllogism: "If I wake up late, I miss the bus. If I miss the bus, I am late for class. So if I wake up late, I am late for class."

  • Disjunctive syllogism: "The bug is in the frontend or the backend. It is not in the frontend. So it is in the backend."

  • Addition: "Ravi is in Pune. So Ravi is in Pune or in Chennai." (Weakening a true statement keeps it true.)

  • Simplification: "The test passed and the build is green. So the test passed."

  • Resolution: "Either the cache is stale or the API is slow. Either the cache is not stale or the network is down. So the API is slow or the network is down." (If the cache is stale, the second premise gives the network; if not, the first gives the API.)


Two Classic Fallacies

A fallacy is an argument form that looks like a rule but is not valid.

Fallacy

Form

Counterexample row

Example

Affirming the consequent

p → q, q ⊢ p

p = F, q = T

"If I study, I pass. I passed. So I studied." (Maybe the paper was easy.)

Denying the antecedent

p → q, ¬p ⊢ ¬q

p = F, q = T

"If you buy the premium plan, you get ad-free videos. You did not buy it. So you get ads." (Maybe there is a free trial.)

Affirming the consequent treats p → q as if it were its converse q → p; denying the antecedent treats it as its inverse ¬p → ¬q. As we saw in Propositional Logic, neither is equivalent to the original. The valid neighbours are modus ponens and modus tollens.


Writing a Formal Proof

A formal proof is a numbered list of lines. Each line is either a premise or follows from earlier lines by a named rule. The last line is the conclusion.

Example 1: The Server Outage

Premises:

  1. If the server is down, the website is unreachable.

  2. If the website is unreachable, customers complain.

  3. Customers did not complain.

  4. The server is down or the cache expired.

Conclusion: the cache expired.

Step 1, symbolise. d: server down, u: website unreachable, c: customers complain, e: cache expired. Premises: d → u, u → c, ¬c, d ∨ e. Conclusion: e.

Step 2, plan. We need e. Premise 4 gives e if we can show ¬d (disjunctive syllogism). To get ¬d from d → u we need ¬u (modus tollens), and ¬u comes from u → c and ¬c (modus tollens again).

Step 3, write the proof.

Step  Statement      Reason
1.    u → c          Premise
2.    ¬c             Premise
3.    ¬u             Modus tollens (1, 2)
4.    d → u          Premise
5.    ¬d             Modus tollens (4, 3)
6.    d ∨ e          Premise
7.    e              Disjunctive syllogism (6, 5)

Example 2: Using an Equivalence

Show (p ∧ q) → r, ¬r, q ⊢ ¬p.

Step  Statement      Reason
1.    (p ∧ q) → r    Premise
2.    ¬r             Premise
3.    ¬(p ∧ q)       Modus tollens (1, 2)
4.    ¬p ∨ ¬q        De Morgan (3)
5.    q              Premise
6.    ¬¬q            Double negation (5)
7.    ¬p             Disjunctive syllogism (4, 6)

In words: if p were true, then with q we would have p ∧ q and hence r, but r is false. Line 7 uses disjunctive syllogism in the form "a ∨ b, ¬b ⊢ a" (with a = ¬p, b = ¬q), which is the same rule after commutativity.

Example 3: Conditional Proof

When the conclusion is an implication p → r, it is often easier to add p as an extra premise and derive r. This is justified by exportation: (A ∧ p) → r ≡ A → (p → r). Show p → (q → r), p → q ⊢ p → r:

Step  Statement      Reason
1.    p → (q → r)    Premise
2.    p → q          Premise
3.    p              Assumption (for conditional proof)
4.    q → r          Modus ponens (1, 3)
5.    q              Modus ponens (2, 3)
6.    r              Modus ponens (4, 5)
7.    p → r          Conditional proof (3 to 6)

This is the formal version of the "assume p, show q" direct proof that you will use constantly in Proof Techniques.

Inconsistent Premises Prove Anything

If the premises can never all be true at once (they are inconsistent), every argument from them is vacuously valid. For example, p, ¬p ⊢ q for any q: from p, addition gives p ∨ q; then disjunctive syllogism with ¬p gives q. This is why one contradiction in a set of requirements or axioms makes the whole set useless: it "proves" everything.


Resolution

Automated theorem provers and SAT solvers rely mainly on one rule, resolution, applied to formulas in CNF (see Logical Equivalences & Normal Forms):

From two clauses that contain a complementary pair of literals, p in one and ¬p in the other, derive the clause made of all the remaining literals: (p ∨ A), (¬p ∨ B) ⊢ (A ∨ B). The result is called the resolvent. Resolving p with ¬p gives the empty clause □, which is a contradiction.

Special cases: with B empty, (p ∨ A), ¬p ⊢ A is disjunctive syllogism; and since p → q is ¬p ∨ q, modus ponens is resolution of (¬p ∨ q) with p.

Proof by Resolution Refutation

To show premises ⊢ q: convert the premises and ¬q to clauses, then keep resolving. If the empty clause appears, the premises together with ¬q are contradictory, so q must follow.

Example. Show p ∨ q, p → r, q → r ⊢ r (proof by cases: either way, r).

Clauses:   C1: p ∨ q     C2: ¬p ∨ r     C3: ¬q ∨ r     C4: ¬r   (negated conclusion)

C5: ¬p      resolve C2, C4 on r
C6: ¬q      resolve C3, C4 on r
C7: q       resolve C1, C5 on p
C8: □       resolve C7, C6 on q     empty clause: contradiction, so r follows

Resolution is refutation complete for propositional logic: whenever a set of clauses is unsatisfiable, repeated resolution will eventually produce the empty clause.


Checking Arguments with a Program

The truth-table definition of validity translates directly into code: search for a row with all premises true and the conclusion false.

from itertools import product

def implies(a, b):
    return (not a) or b

def check(name, variables, premises, conclusion):
    """An argument is valid if no row makes all premises true and the conclusion false."""
    bad = []
    for values in product([True, False], repeat=len(variables)):
        env = dict(zip(variables, values))
        if all(p(env) for p in premises) and not conclusion(env):
            bad.append(''.join('T' if env[v] else 'F' for v in variables))
    print(f"{name:22} {'VALID' if not bad else 'INVALID, counterexample ' + str(bad)}")

check("Modus ponens", "pq", [lambda e: implies(e['p'], e['q']), lambda e: e['p']],
      lambda e: e['q'])
check("Affirming consequent", "pq", [lambda e: implies(e['p'], e['q']), lambda e: e['q']],
      lambda e: e['p'])
check("Denying antecedent", "pq", [lambda e: implies(e['p'], e['q']), lambda e: not e['p']],
      lambda e: not e['q'])
# Server argument: d -> u, u -> c, not c, d or e  therefore e
check("Server argument", "duce",
      [lambda e: implies(e['d'], e['u']), lambda e: implies(e['u'], e['c']),
       lambda e: not e['c'], lambda e: e['d'] or e['e']],
      lambda e: e['e'])

Output:

Modus ponens           VALID
Affirming consequent   INVALID, counterexample ['FT']
Denying antecedent     INVALID, counterexample ['FT']
Server argument        VALID

Both fallacies fail on the same row p = F, q = T, exactly as in the table above. A program like this confirms validity, but in an exam you must still show the step-by-step proof.


Rules of Inference for Quantified Statements

Now we can handle the argument from the start of Predicate Logic & Quantifiers. Four rules let us remove and introduce quantifiers. In the table, c denotes an element of the domain.

Rule

Form

Condition

Universal instantiation (UI)

∀x P(x) ⊢ P(c)

c can be any element, including one already used

Universal generalisation (UG)

P(c) ⊢ ∀x P(x)

c must be an arbitrary element: nothing special was assumed about it (in particular it must not come from EI)

Existential instantiation (EI)

∃x P(x) ⊢ P(c)

c must be a new name not used earlier in the proof; we only know some element works

Existential generalisation (EG)

P(c) ⊢ ∃x P(x)

None: one example is enough

UI and modus ponens are used together so often that the combination has its own name, universal modus ponens: ∀x (P(x) → Q(x)), P(a) ⊢ Q(a). Similarly, universal modus tollens: ∀x (P(x) → Q(x)), ¬Q(a) ⊢ ¬P(a).

Example 4: Asha Studies Discrete Mathematics

C(x): x is a CSE student; D(x): x studies discrete mathematics. Premises ∀x (C(x) → D(x)) and C(Asha). Conclusion D(Asha).

Step  Statement            Reason
1.    ∀x (C(x) → D(x))     Premise
2.    C(Asha) → D(Asha)    Universal instantiation (1)
3.    C(Asha)              Premise
4.    D(Asha)              Modus ponens (2, 3)

Example 5: Using All Four Kinds of Step

"Every student in this class has written a C program. Some student in this class has never used Linux. Therefore someone who has written a C program has never used Linux."

S(x): x is a student in this class; W(x): x has written a C program; L(x): x has used Linux. Premises: ∀x (S(x) → W(x)), ∃x (S(x) ∧ ¬L(x)). Conclusion: ∃x (W(x) ∧ ¬L(x)).

Step  Statement            Reason
1.    ∃x (S(x) ∧ ¬L(x))    Premise
2.    S(a) ∧ ¬L(a)         Existential instantiation (1), a is a new name
3.    S(a)                 Simplification (2)
4.    ∀x (S(x) → W(x))     Premise
5.    S(a) → W(a)          Universal instantiation (4)
6.    W(a)                 Modus ponens (5, 3)
7.    ¬L(a)                Simplification (2)
8.    W(a) ∧ ¬L(a)         Conjunction (6, 7)
9.    ∃x (W(x) ∧ ¬L(x))    Existential generalisation (8)

Order tip: do existential instantiation before universal instantiation. EI needs a fresh name, while UI can use any name, including the one EI just introduced. Doing it the other way round would force EI to pick a name that is already in use, which is not allowed.

A Wrong Proof to Learn From

Claim: ∃x P(x), ∃x Q(x) ⊢ ∃x (P(x) ∧ Q(x)). "Proof": from ∃x P(x) get P(c); from ∃x Q(x) get Q(c); conjunction gives P(c) ∧ Q(c); EG gives the conclusion. The error is the second EI: c was already used, so it must be a new name d, and P(c) ∧ Q(d) does not give the conclusion. The claim is in fact false: some number is even and some number is odd, but no number is both.


Common Mistakes

  • Affirming the consequent / denying the antecedent. From p → q, the valid moves are "p, so q" and "¬q, so ¬p" only.

  • Confusing valid with true. A valid argument with a false premise may have a false conclusion; only a sound argument guarantees truth.

  • Using simplification on a disjunction. p ∧ q ⊢ p is valid, but p ∨ q ⊢ p is not.

  • Reusing a name in existential instantiation. Each EI needs a brand-new constant.

  • Generalising from a specific element. UG is allowed only for an arbitrary element, never for a constant obtained by EI or one with special assumptions.

  • Resolving on two pairs at once. From (p ∨ q) and (¬p ∨ ¬q) you may resolve on p (giving q ∨ ¬q) or on q, but not on both at once to get the empty clause; these two clauses are satisfiable together (p = T, q = F).

  • Not naming the rule and the line numbers. In exams, a step without its justification usually gets no marks.


Interview and GATE-Style Questions

Which rule is used? "If it is a weekday, I go to college. I did not go to college today. So today is not a weekday."

Modus tollens: w → c, ¬c ⊢ ¬w.

Is the argument p → q, q → r, r ⊢ p valid?

No. p = F, q = T, r = T (or p = F, q = F, r = T) makes all premises true and the conclusion false.

What can you conclude from ¬p ∨ q and p ∨ r?

By resolution on p: q ∨ r.

Prove p → (q ∨ r), ¬q, ¬r ⊢ ¬p.

1. ¬q (premise). 2. ¬r (premise). 3. ¬q ∧ ¬r (conjunction 1, 2). 4. ¬(q ∨ r) (De Morgan 3). 5. p → (q ∨ r) (premise). 6. ¬p (modus tollens 5, 4).

What is the difference between a valid argument and a sound argument?

Valid: the conclusion is true in every case where all premises are true (a property of the form). Sound: valid and all premises are actually true, so the conclusion is guaranteed true.

"All birds can fly. Penguins are birds. So penguins can fly." Valid? Sound?

Valid (universal modus ponens), but not sound, because the premise "all birds can fly" is false. That is why the conclusion is false.

Find the error: from ∃x P(x) we get P(c), and then by UG ∀x P(x).

UG requires c to be an arbitrary element. A constant introduced by existential instantiation is a specific (unknown) element, so universal generalisation from it is not allowed. Indeed, "some integer is negative" does not imply "every integer is negative".

Use resolution refutation to show p, p → q, q → r ⊢ r.

Clauses: p, ¬p ∨ q, ¬q ∨ r, and the negated conclusion ¬r. Resolve p with ¬p ∨ q to get q; q with ¬q ∨ r to get r; r with ¬r to get the empty clause. So r follows.


Summary

  • An argument is valid if (premises) → conclusion is a tautology; sound means valid with true premises.

  • To show invalidity, give one row with all premises T and the conclusion F.

  • Core rules: modus ponens, modus tollens, hypothetical and disjunctive syllogism, addition, simplification, conjunction, resolution, and the constructive and destructive dilemmas. Equivalences may also be used to rewrite lines.

  • Fallacies: affirming the consequent (p → q, q ⊢ p) and denying the antecedent (p → q, ¬p ⊢ ¬q).

  • Resolution on CNF clauses, with refutation (add ¬conclusion and derive □), is the engine of automated provers.

  • Quantifier rules: UI (any element), UG (only an arbitrary element), EI (a new name), EG (any witness). Do EI before UI.

  • Next, Proof Techniques turns these rules into the everyday proof methods of mathematics: direct proof, contrapositive, contradiction and proof by cases.