MA 481 Course Description



Prerequisite: Permission of instructor

Offered: Every Third Winter (2010)

Course Description
The propositional and predicate calculi, syntax and semantics, consistency and completeness and undecidability. Included are Goedel's theorems, recursive function theory, model theory and applications.

Course Content

  1. Introduction to the Propositional and Predicate Calculi
    1. Propositional Calculus
      1. fundamental logical connectives
      2. truth tables
      3. equivalence
      4. conjunctive and disjunctive normal forms
      5. characterization of universally valid sentences
      6. principle of duality
    2. Predicate Calculus
      1. quantifiers
      2. free and bound variables
      3. equivalence
      4. substitution and replacement
      5. Prenex and Skolem normal forms
      6. extended principle of duality
  2. Formal Deduction
    1. Examples of formal deduction
      1. Herbrand's deduction theorem
      2. some consequences of Herbrand's deduction theorem
      3. consistency, completeness, and decidability in formal systems
    2. Formal propositional calculus
      1. axioms of the propositional calculus
      2. examples of proof from the axioms
      3. consistency
      4. independence of the axioms
      5. completeness
      6. decision procedure for the propositional calculus
    3. Formal predicate calculus
      1. axioms of the predicate calculus
      2. examples of proof from the axioms
      3. consistency and independence of the system of axioms
      4. Godel's completeness theorem
      5. Lowenheim's theorem
      6. decision problem
      7. reductions of the decision problem
      8. Church's theorem
  3. Additional Topics on Formal Deduction
    1. Formal number theory; Godel's undecidability theorem
    2. Recursive functions and formal systems
    3. Recursiveness and computability