MA481

Prerequisite: Permission of instructor

Course Content

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
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
Additional Topics on Formal Deduction
1. Formal number theory; Godel's undecidability theorem
2. Recursive functions and formal systems
3. Recursiveness and computability