Introduction
An inference rule is a logical rule that allows us to derive new conclusions from existing premises. These rules form the foundation of formal reasoning and automated theorem proving.
Understanding inference rules is essential for:
- Constructing Proofs: Building valid arguments step by step
- Automated Reasoning: Implementing reasoning in computer systems
- Formal Verification: Proving software and hardware correctness
- Artificial Intelligence: Knowledge representation and reasoning
- Philosophy: Analyzing logical arguments rigorously
This comprehensive guide explores the fundamental inference rules, with emphasis on modus ponens and other essential rules for formal reasoning.
What is an Inference Rule?
Definition
An inference rule is a logical rule that permits us to derive a conclusion from one or more premises.
General Form:
Premise 1
Premise 2
...
Premise n
─────────────
Conclusion
The horizontal line indicates “therefore” or “so.”
Validity of Inference Rules
An inference rule is valid if whenever all premises are true, the conclusion must also be true.
Formal Definition:
An inference rule is valid if and only if:
(Premise₁ ∧ Premise₂ ∧ ... ∧ Premiseₙ) → Conclusion
is a tautology (always true).
Why Inference Rules Matter
Correctness: Valid inference rules guarantee that true premises lead to true conclusions.
Efficiency: Inference rules allow us to derive conclusions without constructing full truth tables.
Automation: Inference rules can be implemented in computer systems for automated reasoning.
Proof Construction: Inference rules are the building blocks of formal proofs.
Fundamental Inference Rules
1. Modus Ponens (Affirming the Antecedent)
Name: Latin for “mode that affirms”
Form:
Premise 1: p → q (If p, then q)
Premise 2: p (p is true)
─────────────────
Conclusion: q (Therefore, q is true)
Validity: Valid (tautology)
Truth Table Verification:
| p | q | p → q | p | q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | F | F |
When both premises are true (p → q is true AND p is true), the conclusion q is true.
Examples:
Example 1:
Premise 1: If it rains, then the ground gets wet.
Premise 2: It is raining.
─────────────────────────────────────────────
Conclusion: Therefore, the ground is wet.
Example 2:
Premise 1: If x > 5, then x > 3.
Premise 2: x > 5.
─────────────────────────────────
Conclusion: Therefore, x > 3.
Example 3:
Premise 1: If the program has a bug, then it will crash.
Premise 2: The program has a bug.
──────────────────────────────────────────────────────
Conclusion: Therefore, the program will crash.
Why It’s Valid:
If we know that p implies q, and we know that p is true, then q must be true. There’s no way for both premises to be true and the conclusion to be false.
Common Mistake: Confusing modus ponens with affirming the consequent (invalid).
INVALID: If p then q. q is true. Therefore, p is true.
2. Modus Tollens (Denying the Consequent)
Name: Latin for “mode that denies”
Form:
Premise 1: p → q (If p, then q)
Premise 2: ¬q (q is false)
─────────────────
Conclusion: ¬p (Therefore, p is false)
Validity: Valid (tautology)
Intuition: If p implies q, and q is false, then p must be false (otherwise q would be true).
Examples:
Example 1:
Premise 1: If it rains, then the ground gets wet.
Premise 2: The ground is not wet.
──────────────────────────────────────────────
Conclusion: Therefore, it is not raining.
Example 2:
Premise 1: If x > 5, then x > 3.
Premise 2: x ≤ 3.
──────────────────────────────
Conclusion: Therefore, x ≤ 5.
Example 3:
Premise 1: If the program has a bug, then it will crash.
Premise 2: The program did not crash.
──────────────────────────────────────────────────────
Conclusion: Therefore, the program does not have a bug.
Why It’s Valid:
If p implies q, and q is false, then p cannot be true (because if p were true, q would have to be true). So p must be false.
Relationship to Contrapositive:
Modus tollens is essentially applying the contrapositive:
p → q ≡ ¬q → ¬p (Contrapositive equivalence)
3. Hypothetical Syllogism (Chain Rule)
Name: Also called “chain rule” or “transitivity of implication”
Form:
Premise 1: p → q (If p, then q)
Premise 2: q → r (If q, then r)
─────────────────
Conclusion: p → r (Therefore, if p, then r)
Validity: Valid (tautology)
Intuition: If p leads to q and q leads to r, then p leads to r.
Examples:
Example 1:
Premise 1: If I study, I will pass the exam.
Premise 2: If I pass the exam, I will graduate.
──────────────────────────────────────────────
Conclusion: Therefore, if I study, I will graduate.
Example 2:
Premise 1: If x > 5, then x > 3.
Premise 2: If x > 3, then x > 0.
──────────────────────────────────
Conclusion: Therefore, if x > 5, then x > 0.
Example 3:
Premise 1: If the temperature rises, the ice melts.
Premise 2: If the ice melts, the water level rises.
──────────────────────────────────────────────────
Conclusion: Therefore, if the temperature rises, the water level rises.
Why It’s Valid:
If p is true, then q must be true (from premise 1). If q is true, then r must be true (from premise 2). Therefore, if p is true, r must be true.
4. Disjunctive Syllogism
Name: Also called “elimination” or “proof by cases”
Form:
Premise 1: p ∨ q (Either p or q, or both)
Premise 2: ¬p (p is false)
─────────────────
Conclusion: q (Therefore, q is true)
Validity: Valid (tautology)
Intuition: If at least one of p or q is true, and p is false, then q must be true.
Examples:
Example 1:
Premise 1: Either it's raining or it's sunny.
Premise 2: It's not raining.
──────────────────────────────────────────
Conclusion: Therefore, it's sunny.
Example 2:
Premise 1: The suspect was either at home or at the office.
Premise 2: The suspect was not at home.
──────────────────────────────────────────────────────────
Conclusion: Therefore, the suspect was at the office.
Example 3:
Premise 1: Either the program has a bug or the input is invalid.
Premise 2: The input is valid.
──────────────────────────────────────────────────────────────
Conclusion: Therefore, the program has a bug.
Why It’s Valid:
If p ∨ q is true and p is false, then q must be true (because at least one of them must be true).
5. Addition
Name: Also called “weakening” or “disjunction introduction”
Form:
Premise 1: p (p is true)
─────────────────
Conclusion: p ∨ q (Therefore, p or q is true)
Validity: Valid (tautology)
Intuition: If p is true, then “p or anything” is true.
Examples:
Example 1:
Premise 1: It is raining.
──────────────────────────────────────────
Conclusion: Therefore, it is raining or it is sunny.
Example 2:
Premise 1: x > 5.
──────────────────────────────────────────
Conclusion: Therefore, x > 5 or x < 0.
Why It’s Valid:
If p is true, then p ∨ q is true regardless of q’s truth value.
6. Simplification
Name: Also called “conjunction elimination”
Form:
Premise 1: p ∧ q (Both p and q are true)
─────────────────
Conclusion: p (Therefore, p is true)
Validity: Valid (tautology)
Intuition: If both p and q are true, then p is true.
Examples:
Example 1:
Premise 1: It is raining and it is cold.
──────────────────────────────────────
Conclusion: Therefore, it is raining.
Example 2:
Premise 1: x > 5 and y < 3.
──────────────────────────────
Conclusion: Therefore, x > 5.
Why It’s Valid:
If p ∧ q is true, then both p and q are true, so p is certainly true.
7. Conjunction
Name: Also called “conjunction introduction”
Form:
Premise 1: p (p is true)
Premise 2: q (q is true)
─────────────────
Conclusion: p ∧ q (Therefore, both p and q are true)
Validity: Valid (tautology)
Intuition: If p is true and q is true, then “p and q” is true.
Examples:
Example 1:
Premise 1: It is raining.
Premise 2: It is cold.
──────────────────────────────────────────
Conclusion: Therefore, it is raining and it is cold.
Example 2:
Premise 1: x > 5.
Premise 2: y < 3.
──────────────────────────────────────────
Conclusion: Therefore, x > 5 and y < 3.
Why It’s Valid:
If both p and q are true, then p ∧ q is true.
8. Resolution
Name: Also called “cut” or “consensus”
Form:
Premise 1: p ∨ q (Either p or q)
Premise 2: ¬p ∨ r (Either not p or r)
─────────────────
Conclusion: q ∨ r (Therefore, either q or r)
Validity: Valid (tautology)
Intuition: If p ∨ q is true and ¬p ∨ r is true, then q ∨ r must be true.
Proof:
- Case 1: If p is true, then from ¬p ∨ r, r must be true. So q ∨ r is true.
- Case 2: If p is false, then from p ∨ q, q must be true. So q ∨ r is true.
Examples:
Example 1:
Premise 1: Either the suspect was at home or at the office.
Premise 2: Either the suspect was not at home or they were alone.
──────────────────────────────────────────────────────────────
Conclusion: Therefore, either the suspect was at the office or they were alone.
Example 2:
Premise 1: Either x > 5 or y < 3.
Premise 2: Either x ≤ 5 or z = 0.
──────────────────────────────────────────
Conclusion: Therefore, either y < 3 or z = 0.
Why It’s Valid:
If p ∨ q is true and ¬p ∨ r is true, then:
- If p is true, then r must be true (from ¬p ∨ r), so q ∨ r is true.
- If p is false, then q must be true (from p ∨ q), so q ∨ r is true.
Importance: Resolution is the basis for many automated reasoning systems and SAT solvers.
Constructing Formal Proofs
What is a Formal Proof?
A formal proof is a sequence of statements where each statement is either:
- A premise (given as true)
- Derived from previous statements using an inference rule
Example Proof 1: Simple Modus Ponens Chain
Goal: Prove q from the premises:
- p → q
- p
Proof:
1. p → q [Premise]
2. p [Premise]
3. q [Modus Ponens from 1, 2]
Example Proof 2: Hypothetical Syllogism
Goal: Prove p → r from the premises:
- p → q
- q → r
Proof:
1. p → q [Premise]
2. q → r [Premise]
3. p → r [Hypothetical Syllogism from 1, 2]
Example Proof 3: Complex Proof
Goal: Prove s from the premises:
- p → q
- q → r
- r → s
- p
Proof:
1. p → q [Premise]
2. q → r [Premise]
3. r → s [Premise]
4. p [Premise]
5. q [Modus Ponens from 1, 4]
6. r [Modus Ponens from 2, 5]
7. s [Modus Ponens from 3, 6]
Example Proof 4: Using Disjunctive Syllogism
Goal: Prove r from the premises:
- p ∨ q
- p → r
- q → r
Proof:
1. p ∨ q [Premise]
2. p → r [Premise]
3. q → r [Premise]
4. ¬p ∨ r [Implication from 2]
5. r ∨ r [Resolution from 1, 4]
6. r [Idempotent from 5]
Alternative proof:
1. p ∨ q [Premise]
2. p → r [Premise]
3. q → r [Premise]
4. Assume p [Case 1]
5. r [Modus Ponens from 2, 4]
6. Assume q [Case 2]
7. r [Modus Ponens from 3, 6]
8. r [Proof by cases from 1, 5, 7]
Invalid Inference Patterns
Affirming the Consequent (Invalid!)
Form:
Premise 1: p → q (If p, then q)
Premise 2: q (q is true)
─────────────────
Conclusion: p (Therefore, p is true) [INVALID]
Why It’s Invalid: q could be true for reasons other than p.
Example:
Premise 1: If it rains, the ground gets wet.
Premise 2: The ground is wet.
──────────────────────────────────────────
Conclusion: Therefore, it rained. [INVALID]
Counterexample: The ground could be wet from sprinklers, not rain.
Denying the Antecedent (Invalid!)
Form:
Premise 1: p → q (If p, then q)
Premise 2: ¬p (p is false)
─────────────────
Conclusion: ¬q (Therefore, q is false) [INVALID]
Why It’s Invalid: q could be true even if p is false.
Example:
Premise 1: If it rains, the ground gets wet.
Premise 2: It is not raining.
──────────────────────────────────────────
Conclusion: Therefore, the ground is not wet. [INVALID]
Counterexample: The ground could be wet from sprinklers even though it’s not raining.
Applications of Inference Rules
In Automated Reasoning
Automated reasoning systems use inference rules to derive conclusions automatically.
Example: SAT solvers use resolution to determine if a formula is satisfiable.
In Artificial Intelligence
AI systems use inference rules for knowledge representation and reasoning.
Example: Expert systems use modus ponens to derive conclusions from rules and facts.
In Formal Verification
Formal verification uses inference rules to prove software and hardware correctness.
Example: Theorem provers use inference rules to construct proofs of program properties.
In Logic Programming
Logic programming languages like Prolog use inference rules to query knowledge bases.
Example: Prolog uses modus ponens and resolution to answer queries.
Practice Problems
Problem 1: Apply Modus Ponens
Given:
- If the temperature is above 100°F, then the system will overheat.
- The temperature is 105°F.
Conclude:
Solution:
Premise 1: Temperature > 100°F → System overheats
Premise 2: Temperature = 105°F (which is > 100°F)
─────────────────────────────────────────────────
Conclusion: Therefore, the system will overheat.
Problem 2: Apply Modus Tollens
Given:
- If the program has a syntax error, it will not compile.
- The program compiled successfully.
Conclude:
Solution:
Premise 1: Syntax error → Program won't compile
Premise 2: Program compiled (¬(Program won't compile))
──────────────────────────────────────────────────
Conclusion: Therefore, the program does not have a syntax error.
Problem 3: Apply Hypothetical Syllogism
Given:
- If I study hard, I will pass the exam.
- If I pass the exam, I will get a good grade.
- If I get a good grade, I will be happy.
Conclude:
Solution:
Premise 1: Study hard → Pass exam
Premise 2: Pass exam → Good grade
Premise 3: Good grade → Happy
──────────────────────────────────────────────────
Conclusion: Therefore, if I study hard, I will be happy.
Problem 4: Construct a Formal Proof
Goal: Prove t from the premises:
- p → q
- q → r
- r → s
- s → t
- p
Solution:
1. p → q [Premise]
2. q → r [Premise]
3. r → s [Premise]
4. s → t [Premise]
5. p [Premise]
6. q [Modus Ponens from 1, 5]
7. r [Modus Ponens from 2, 6]
8. s [Modus Ponens from 3, 7]
9. t [Modus Ponens from 4, 8]
Related Resources and Tools
Online Learning Platforms
- Stanford Encyclopedia of Philosophy - Inference Rules - Academic treatment
- Khan Academy - Deductive Reasoning - Video tutorials
- Coursera - Mathematical Logic - University course
- MIT OpenCourseWare - Mathematics for Computer Science - Free materials
Interactive Tools
- Proof Checker - Fitch Proof Checker - Verify formal proofs
- Logic Simulator - LogicSim - Visual logic design
- Argument Mapper - Rationale - Map arguments visually
- Truth Table Generator - Stanford Tool - Create truth tables
Recommended Books
- “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
- “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
- “Logic: The Laws of Truth” by Nicholas J.J. Smith - Modern treatment
- “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
Academic Journals
- Journal of Symbolic Logic - Leading journal on mathematical logic
- Studia Logica - International journal on logic and philosophy
- Logic and Logical Philosophy - Open access journal
Software Tools
- Prolog - Logic programming language
- Coq - Interactive theorem prover
- Isabelle - Generic proof assistant
- Z3 - SMT solver
Glossary of Key Terms
- Addition: Rule allowing p to conclude p ∨ q
- Conjunction: Rule allowing p and q to conclude p ∧ q
- Disjunctive Syllogism: Rule for eliminating disjuncts
- Formal Proof: Sequence of statements derived using inference rules
- Hypothetical Syllogism: Rule for chaining implications
- Inference Rule: Rule for deriving conclusions from premises
- Modus Ponens: Rule for affirming the antecedent
- Modus Tollens: Rule for denying the consequent
- Resolution: Rule for combining disjunctions
- Simplification: Rule for extracting conjuncts
- Validity: Property of inference rules that preserve truth
Conclusion
Inference rules are the foundation of formal reasoning. By mastering:
- Modus ponens and modus tollens
- Hypothetical syllogism and disjunctive syllogism
- Addition, simplification, and conjunction
- Resolution and other advanced rules
You develop the ability to:
- Construct valid formal proofs
- Reason about complex logical systems
- Implement automated reasoning systems
- Verify software and hardware correctness
- Understand the foundations of artificial intelligence
The next article in this series will explore Proof Techniques, covering direct proof, proof by contradiction, proof by induction, and other fundamental proof strategies.
Which inference rule do you find most useful? Have you used formal proofs in your work? Share your examples in the comments below!
Comments