Rules of Inference

What are Rules of Inference?

Rules of inference are logical rules that allow us to deduce new valid conclusions from given premises (statements that are assumed to be true). They form the foundation of mathematical proofs and logical reasoning.

Why Do We Need Rules of Inference?

Instead of using truth tables (which can be huge for many variables), we use rules of inference to:

  • Construct valid arguments step by step
  • Prove mathematical theorems
  • Verify program correctness
  • Make logical deductions

Valid Arguments

An argument consists of:

  1. Premises: Starting statements (p₁, p₂, …, pₙ)
  2. Conclusion: Statement we want to prove (q)

An argument is valid if: whenever all premises are true, the conclusion must also be true.

Notation: (p₁ ∧ p₂ ∧ … ∧ pₙ) → q is a tautology

Basic Rules of Inference for Propositional Logic

1. Modus Ponens (Law of Detachment)

Rule:

p
p → q
∴ q

Meaning: If p is true, and p implies q, then q is true.

Example 1:

  • Premise 1: “It is raining” (p)
  • Premise 2: “If it is raining, then the ground is wet” (p → q)
  • Conclusion: “The ground is wet” (q)

Example 2:

  • Premise 1: “I studied hard” (p)
  • Premise 2: “If I study hard, then I will pass” (p → q)
  • Conclusion: “I will pass” (q)

Why it works:

pqp → qp ∧ (p → q)q
TTTTT
TFFFF
FTTFT
FFTFF

When p ∧ (p → q) is true, q is also true.

2. Modus Tollens (Method of Denying)

Rule:

p → q
¬q
∴ ¬p

Meaning: If p implies q, and q is false, then p must be false.

Example 1:

  • Premise 1: “If it is raining, then the ground is wet” (p → q)
  • Premise 2: “The ground is not wet” (¬q)
  • Conclusion: “It is not raining” (¬p)

Example 2:

  • Premise 1: “If the program has errors, it won’t compile” (p → q)
  • Premise 2: “The program compiled” (¬q)
  • Conclusion: “The program has no errors” (¬p)

Why it works: This is based on the contrapositive: p → q ≡ ¬q → ¬p

3. Hypothetical Syllogism (Chain Rule)

Rule:

p → q
q → r
∴ p → r

Meaning: If p implies q, and q implies r, then p implies r.

Example 1:

  • Premise 1: “If it rains, the ground is wet” (p → q)
  • Premise 2: “If the ground is wet, it’s slippery” (q → r)
  • Conclusion: “If it rains, it’s slippery” (p → r)

Example 2:

  • Premise 1: “If you study, you understand” (p → q)
  • Premise 2: “If you understand, you pass” (q → r)
  • Conclusion: “If you study, you pass” (p → r)

4. Disjunctive Syllogism

Rule:

p ∨ q
¬p
∴ q

Meaning: If p or q is true, and p is false, then q must be true.

Example 1:

  • Premise 1: “Either it’s raining or it’s snowing” (p ∨ q)
  • Premise 2: “It’s not raining” (¬p)
  • Conclusion: “It’s snowing” (q)

Example 2:

  • Premise 1: “I will go by bus or by train” (p ∨ q)
  • Premise 2: “I’m not going by bus” (¬p)
  • Conclusion: “I will go by train” (q)

5. Addition

Rule:

p
∴ p ∨ q

Meaning: If p is true, then (p or q) is true.

Example 1:

  • Premise: “It is raining” (p)
  • Conclusion: “It is raining or it is snowing” (p ∨ q)

Example 2:

  • Premise: “I passed the exam” (p)
  • Conclusion: “I passed the exam or I failed” (p ∨ q)

Note: This seems trivial but is useful in constructing proofs.

6. Simplification

Rule:

p ∧ q
∴ p

Meaning: If (p and q) is true, then p is true.

Example 1:

  • Premise: “It is raining and it is cold” (p ∧ q)
  • Conclusion: “It is raining” (p)

Example 2:

  • Premise: “I have a laptop and a phone” (p ∧ q)
  • Conclusion: “I have a laptop” (p)

7. Conjunction

Rule:

p
q
∴ p ∧ q

Meaning: If p is true and q is true, then (p and q) is true.

Example:

  • Premise 1: “It is raining” (p)
  • Premise 2: “It is cold” (q)
  • Conclusion: “It is raining and it is cold” (p ∧ q)

8. Resolution

Rule:

p ∨ q
¬p ∨ r
∴ q ∨ r

Meaning: From (p or q) and (not p or r), we can conclude (q or r).

Example:

  • Premise 1: “I go by bus or I go by train” (p ∨ q)
  • Premise 2: “I don’t go by bus or I arrive late” (¬p ∨ r)
  • Conclusion: “I go by train or I arrive late” (q ∨ r)

Rules of Inference for Quantified Statements

9. Universal Instantiation (UI)

Rule:

∀x P(x)
∴ P(c) for any element c in the domain

Meaning: If P(x) is true for all x, then it’s true for any specific element c.

Example 1:

  • Premise: “All humans are mortal” (∀x (Human(x) → Mortal(x)))
  • Conclusion: “Socrates is mortal” (Human(Socrates) → Mortal(Socrates))

Example 2:

  • Premise: “All students in this class passed” (∀x Passed(x))
  • Conclusion: “Ram passed” (Passed(Ram))

10. Universal Generalization (UG)

Rule:

P(c) for an arbitrary element c
∴ ∀x P(x)

Meaning: If P(c) is true for an arbitrary element c, then P(x) is true for all x.

Important: c must be arbitrary (not a specific example)!

Example:

  • If we prove x² ≥ 0 for any arbitrary number x
  • Then we conclude ∀x (x² ≥ 0)

Warning: Cannot use a specific example!

  • If 2² = 4 is even
  • We CANNOT conclude ∀x (x² is even) ✗

11. Existential Instantiation (EI)

Rule:

∃x P(x)
∴ P(c) for some element c

Meaning: If there exists an x such that P(x) is true, we can give it a name c.

Example:

  • Premise: “Someone in this class scored 100” (∃x Scored100(x))
  • Conclusion: “Let’s call that person c, then c scored 100” (Scored100(c))

Important: c is a specific (but unknown) element, not arbitrary!

12. Existential Generalization (EG)

Rule:

P(c) for some specific element c
∴ ∃x P(x)

Meaning: If P(c) is true for a specific c, then there exists an x such that P(x).

Example:

  • Premise: “Ram scored 100” (Scored100(Ram))
  • Conclusion: “Someone scored 100” (∃x Scored100(x))

Using Rules of Inference in Proofs

Example 1: Simple Argument

Given:

  1. p → q (If it rains, the ground is wet)
  2. q → r (If the ground is wet, it’s slippery)
  3. p (It is raining)

Prove: r (It’s slippery)

Proof:

  1. p (Given premise 3)
  2. p → q (Given premise 1)
  3. q (Modus Ponens on 1, 2)
  4. q → r (Given premise 2)
  5. r (Modus Ponens on 3, 4) ✓

Example 2: Using Modus Tollens

Given:

  1. p → q (If the program has bugs, it crashes)
  2. ¬q (The program doesn’t crash)

Prove: ¬p (The program has no bugs)

Proof:

  1. p → q (Given)
  2. ¬q (Given)
  3. ¬p (Modus Tollens on 1, 2) ✓

Example 3: Complex Argument

Given:

  1. p ∨ q (I’ll study math or physics)
  2. p → r (If I study math, I’ll need a calculator)
  3. ¬r (I don’t have a calculator)

Prove: q (I’ll study physics)

Proof:

  1. p → r (Given premise 2)
  2. ¬r (Given premise 3)
  3. ¬p (Modus Tollens on 1, 2)
  4. p ∨ q (Given premise 1)
  5. q (Disjunctive Syllogism on 4, 3) ✓

Example 4: Quantified Argument

Given:

  1. ∀x (Student(x) → Studies(x)) (All students study)
  2. Student(Ram) (Ram is a student)

Prove: Studies(Ram) (Ram studies)

Proof:

  1. ∀x (Student(x) → Studies(x)) (Given)
  2. Student(Ram) → Studies(Ram) (Universal Instantiation on 1)
  3. Student(Ram) (Given)
  4. Studies(Ram) (Modus Ponens on 2, 3) ✓

Example 5: Existence Proof

Given:

  1. ∀x (Bird(x) → HasWings(x)) (All birds have wings)
  2. Bird(Sparrow) (Sparrow is a bird)

Prove: ∃x HasWings(x) (Something has wings)

Proof:

  1. ∀x (Bird(x) → HasWings(x)) (Given)
  2. Bird(Sparrow) → HasWings(Sparrow) (Universal Instantiation on 1)
  3. Bird(Sparrow) (Given)
  4. HasWings(Sparrow) (Modus Ponens on 2, 3)
  5. ∃x HasWings(x) (Existential Generalization on 4) ✓

Fallacies (Invalid Arguments)

These are INCORRECT ways of reasoning:

1. Affirming the Conclusion (Fallacy)

Invalid Rule:

p → q
q
∴ p  ✗ WRONG!

Example:

  • If it rains, the ground is wet (p → q)
  • The ground is wet (q)
  • Therefore, it is raining (p) ✗

Why wrong? Ground could be wet from a sprinkler!

2. Denying the Hypothesis (Fallacy)

Invalid Rule:

p → q
¬p
∴ ¬q  ✗ WRONG!

Example:

  • If it rains, the ground is wet (p → q)
  • It’s not raining (¬p)
  • Therefore, the ground is not wet (¬q) ✗

Why wrong? Again, sprinkler!

Summary Table of Rules

Rule NameFormExample
Modus Ponensp, p→q ∴ qRain, Rain→Wet ∴ Wet
Modus Tollensp→q, ¬q ∴ ¬pRain→Wet, ¬Wet ∴ ¬Rain
Hypothetical Syllogismp→q, q→r ∴ p→rA→B, B→C ∴ A→C
Disjunctive Syllogismp∨q, ¬p ∴ qA or B, ¬A ∴ B
Additionp ∴ p∨qRain ∴ Rain or Snow
Simplificationp∧q ∴ pRain and Cold ∴ Rain
Conjunctionp, q ∴ p∧qRain, Cold ∴ Rain and Cold

Key Points for Exams

  1. Modus Ponens and Modus Tollens are most commonly used
  2. Know the difference between valid rules and fallacies
  3. Each step in a proof must cite a rule
  4. For quantifiers: UI and EI remove quantifiers, UG and EG add them
  5. Universal Generalization requires arbitrary element, not specific
  6. Draw truth tables if you’re unsure about validity
  7. Practice constructing multi-step proofs
  8. Hypothetical Syllogism chains implications

Practice Problems

  1. Prove: Given p→q, q→r, p, prove r

  2. What’s wrong with: p→q, q, therefore p?

  3. Given: ∀x (Student(x) → Smart(x)), Student(Mary), prove Smart(Mary)

  4. Prove: p∨q, ¬p∨r, ¬q, prove r

  5. Is this valid? p→q, ¬p, therefore ¬q

  6. Given: p→r, ¬r, p∨q, prove q

  7. Explain why this is a fallacy: “If it’s a cat, it’s a mammal. It’s a mammal. Therefore, it’s a cat.”

  8. Given: ∃x P(x), ∀x (P(x) → Q(x)), prove ∃x Q(x)