🧠 Module 4: Formal Logic

Duration: Weeks 11-16

📚 Core Topics

Propositional Logic (Weeks 11-12)

• Syntax: Formulas, atoms, connectives (∧, ∨, →, ¬, ↔)
• Semantics: Truth tables, interpretations, models
• Classification: Tautologies, contradictions, contingencies
• Relationships: Logical equivalence (≡) and consequence (⊨)
• Proof System: Natural deduction rules

Metalogic (Week 12)

• Soundness Theorem: Provable → Valid (⊢ ⇒ ⊨)
• Completeness Theorem: Valid → Provable (⊨ ⇒ ⊢)
• Compactness Theorem: Infinite satisfiability
• Decidability: Algorithmic verification

Predicate Logic (Week 13)

• Syntax: Predicates, quantifiers (∀, ∃), terms, variables
• Scope: Bound vs free variables
• Semantics: Interpretations, domains, models
• Normal Forms: Prenex normal form
• Gödel’s Theorems (overview):
  • Completeness: Every valid formula is provable
  • Incompleteness: Arithmetic has unprovable truths

Categorical Logic (Week 14)

• Statement Types: A (All), E (No), I (Some), O (Some…not)
• Square of Opposition: Logical relationships
• Syllogisms: Three-part arguments
• Validity Analysis: Rule-based and diagrammatic
• Venn Diagrams: Visual proof method

🔑 Key Concepts

💡 Quantifier Semantics: ∀x P(x): “For all x in the domain, P(x) holds” ∃x P(x): “There exists at least one x such that P(x) holds”

💡 Applications

Real-world impact:

• 🤖 Automated theorem proving and AI reasoning
• ✅ Program verification and correctness proofs
• 🗄️ Database query languages (SQL logic)
• 🧩 Knowledge representation systems
• 🔬 Formal methods in software engineering
• 🎯 Smart contract verification

✅ Learning Outcomes

By the end of this module, you will be able to:

• ✓ Classify formulas as tautologies/contradictions/contingencies
• ✓ Construct rigorous natural deduction proofs
• ✓ Prove logical equivalence between formulas
• ✓ Translate between natural language and formal logic
• ✓ Manipulate quantifiers and work with predicate formulas
• ✓ Analyze validity of categorical syllogisms using multiple methods