Computer Laboratory

Course pages 2011–12

Introductory Logic

Principal lecturer: Prof Alan Mycroft
Taken by: MPhil ACS, Part III
Code: R07
Hours: 8
Prerequisites: Some mathematical maturity

Aims

This module aims to provide the basic mathematical logic which will be assumed in later courses.

Syllabus

Based on Enderton A mathematical introduction to logic

  • Propositional Calculus: truth-functional models, a deductive calculus and a proof of soundness and completeness.
  • First-Order Predicate logic: Tarskian truth and models, a deductive calculus and a proof of soundness and completeness.
  • Compactness and Loewenheim-Skolem theorems.
  • First-order theories and their models: some examples with indications (and in some cases proofs) of which theories are complete/incomplete: Dense linear orders, Natural numbers with successor, Pressburger arithmetic, Peano arithmetic, Real-closed fields.

[There are plans to revise this syllabus for 2011-12; these replace some existing material with lectures on Intuitionistic Logic and the Curry-Howard Correspondence.]

Objectives

On completion of this module, students should:

  • have a good understanding of propositional and first order logic, their proof systems and models.

Coursework

See below.

Practical work

None.

Assessment

Based on a take-home test exam, possibly supplemented by weekly handout exercises.

Recommended reading

Enderton, H.B. (2001). A mathematical introduction to logic. Academic Press (2nd ed.).