Introductory course on logic

Patrick Blackburn

This course is an introduction to the basic ideas of classical logic. Two main themes are emphasized: logic as a representation language (that is, we will discuss what can and cannot be talked about in various classical languages) and logic as a tool for reasoning (to this end, we will introduce the idea of tableaux proofs). At the end of the course the student should have a good grasp of a number of key logical concepts, and be ready to tackle the advanced logic course offered in week two.

Lecture 1. Propositional Calculus. In this lecture we discuss propositional calculus, the simplest classical logic of all. We introduce a simple tableau system for reasoning with it, and discuss a number of key properties, notably decidability and completeness.

Lecture 2. First-Order Languages. In this lecture we start exploring a more powerful and interesting system: first-order logic. We introduce the first-order language, discuss their interpretation in relational structures, and note some examples of the expressive power they offer us.

Lecture 3. First-Order Tableaux. We extend the tableaux system introduced in Lecture 1 to a full first-order tableaux system, and give a number of examples of its use. We also discuss the limitations of this type of tableaux system for automated reasoning, and discuss how to fix this.

Lecture 4. The limits of first-order logic. The first part of this lecture is devoted to the Compactness theorem, and what it has to tell us about first-order expressivity. The second part of the lecture discusses other tools for talking about relational structures, notably second-order logic.