Computer Laboratory

Course pages 2012–13

Introductory Logic

Principal lecturer: Dr Bjarki Holm
Taken by: MPhil ACS, Part III
Code: R07
Hours: 8
Prerequisites: Basic familiarity with discrete mathematics and set theory (for example, to the level of Discrete Mathematics I and II from Part 1A of the Cambridge Computer Science Tripos).

Aims

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

Syllabus

  • Propositional calculus: truth-functional models, a deductive calculus and proofs of soundness and completeness.
  • First-order predicate logic: Tarskian truth and models, a deductive calculus, completeness and a proof of soundness.
  • 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, Peano arithmetic, real-closed fields.

Objectives

On completion of this module, students should have a good understanding of propositional logic and first-order logic, their proof systems and their models.

Coursework

Exercises will be provided.

Practical work

None.

Assessment

The course will be assessed by means of a written test to be set and marked by the course lecturer.

Recommended reading

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