Module 4: Formal Logic

Duration: Weeks 11-16

Core Topics

Propositional Logic (Weeks 11-12)

Syntax: formulas, atoms, connectives
Semantics: truth tables, models
Tautologies, contradictions, satisfiability
Logical equivalence and consequence
Natural deduction proof system

Metalogic (Week 12)

Soundness theorem
Completeness theorem
Compactness theorem
Decidability

Predicate Logic (Week 13)

Syntax: predicates, quantifiers (∀, ∃), terms
Bound and free variables
Interpretations and models
Prenex normal form
Gödel’s completeness theorem (overview)
Gödel’s incompleteness theorems (overview)

Categorical Logic (Week 14)

A, E, I, O statements
Traditional square of opposition
Categorical syllogisms
Validity analysis
Venn diagram methods

Key Concepts

Tautology: Formula true in all interpretations (e.g., P ∨ ¬P)

Logical Consequence: Γ ⊨ φ means φ is true in all models where all formulas in Γ are true

Soundness: If provable, then valid (⊢ implies ⊨)

Completeness: If valid, then provable (⊨ implies ⊢)

Quantifiers:

∀x P(x): “For all x, P(x) holds”
∃x P(x): “There exists x such that P(x) holds”

Applications

Automated theorem proving
Program verification
Database query languages
Knowledge representation
Formal methods in software engineering

What You’ll Be Able To Do

Determine if formulas are tautologies/contradictions
Construct natural deduction proofs
Show logical equivalence
Translate between natural and formal languages
Work with quantifiers
Analyze validity of syllogisms