by Albert Major

Introduction to Logic

Introduction to Natural Deduction

What is Natural Deduction? Natural Deduction is a step-by-step method of showing how we can logically get from our starting premises to a conclusion.

Why Natural Deduction?

• Limitations of Truth Tables:
  • While effective, truth tables only show IF an argument is valid
  • Don't show HOW or WHY premises lead to conclusions
  • Can become impractical with complex arguments
  • Limited to truth-functional logic (TFL)
• Advantages of Natural Deduction:
  • Shows step-by-step reasoning process
  • Provides insight into logical connections
  • Works for both TFL and First-Order Logic (FOL)
  • More practical for complex arguments
  • Doesn't require dealing with truth values directly
  • Pure syntactic manipulation

Basic Structure of Natural Deduction Proofs

Components:

1. Assumptions/Premises:
   • Listed at the top
   • Numbered sequentially
   • Separated by horizontal "assumption line"
2. Proof Lines:
   • Vertical lines showing reasoning flow
   • Start from first assumption
   • End at conclusion
   • Show dependencies and structure
3. Citations:
   • Must cite which rule was used
   • Reference previous line numbers
   • Use commas for specific lines (e.g., "1, 2")
   • Use dashes for sub-proofs (e.g., "3-5")
4. Sub-proofs:
   • Indented one level
   • Start with additional assumption
   • Can be nested
   • Used for certain rules (like conditional introduction)
   • Lines within closed sub-proofs can't be referenced directly

Natural Deduction Rules

Basic Rules

1. Conjunction (∧) Rules:

• Conjunction Introduction (∧I):
  • If you have A and B separately
  • Can combine as A∧B
  • Cite both source lines
• Conjunction Elimination (∧E):
  • From A∧B
  • Can extract either A or B
  • Must use rule twice to get both conjuncts
  • Only works on main operator

2. Conditional (→) Rules: