www.cs.ox.ac.uk/teaching/courses/2009-2010/logicandproof/index.html

You are here:

• Home
• Current Students
• Courses
• Logic and Proof

Logic and Proof:  2009-2010

Information

Lecturer	Stephan Kreutzer
Degrees	Moderations — Honour School of Computer Science Part A — Honour School of Mathematics and Computer Science
Term	Hilary Term 2010  (16 lectures)

Overview

The main aim of the course is to give a first introduction to formal logic for computer scientists.

• Introduction to propositional logic. Syntax of propositional logic. Truth tables. Sequent Calculus. Notions of soundness and completeness. Proofs by induction on the structure of formulas.
• Introduction to structures. Examples. Introduction to finite state transition systems.
• Introduction to first-order logic. Syntax of first-order logic. Semantics of first-order logic. Game-based semantics. Examples. Sequent Calculus. Notions of soundness and completeness.Logic as database query language.
• Introduction to temporal logics, especially Linear Temporal Logic (LTL) and Computation Tree Logic (CTL). Examples.

Learning outcomes

At the end of the course students are expected to:

• Understand and be able to explain and illustrate the meaning of given logical formulas, to translate such formulas into English and vice-versa.
• Construct simple, but rigorous, formal proofs for some given theorems, in a given proof system.
• Be able to express and formalize in a logical language useful properties of models such as transition systems, and be able to determine the truth or falsity of such formulas in a given model.

Synopsis

Approximately 16 lectures.

Propositional logic (5 Lectures).

1. Introduction. Syntax of propositional logic. Examples. Recursive definitions of functions over formulas.
2. Semantics of propositional logic. Validity and satisfiability of formulas. Truth tables. Modern SAT-solving.
3. Equivalence of formulas. Substitution. Normal forms.
4. Sequent calculus.
5. Sequent calculus (ctd.). Soundness and completeness.

First-Order Structures (1 Lecture).

1. Structures and examples for structures. Sub-structures.

First-order logic (5 Lectures).

1. Introduction. Syntax of first-order logic. Examples.
2. Semantics.
3. Examples. Satifiability and validity. Evaluation of formulas.
4. Sequent Calculus.
5. Sequent Calculus (ctd.). Examples. Soundsness and completeness.

Linear Temporal Logic [LTL] (3 lectures).

1. Introduction. Syntax of LTL. Examples.
2. Semantics of LTL.
3. Model checking LTL formulas.

Computation Tree Logic [CTL] (2 lectures).

1. Introduction. Syntax of CTL. Examples.
2. Semantics of CTL. Model checking CTL formulas

Syllabus

Syntax and Semantics of propositional and first-order logic. Proofs by induction on the structure of formulas. Formal proofs using sequent calculus. Brief discussion of issues of soundness and completeness. Mathematical models of computation, especially Kripke structures. Temporal logics: Linear Temporal Logic (LTL) and Computation Tree Logic (CTL). Determining the truth of a temporal logic formula in a given model.

Reading list

Primary text:

• Mathematical logic, 2nd edition, by H.-D. Ebbinghaus, J. Flum and W. Thomas (Springer 1996).
• Logic in computer science: modelling and reasoning about systems,2nd edition, by M. Huth and M. Ryan (Cambridge University Press, Cambridge 2004).

Other texts to be consulted

• Proof and Disproof in Formal Logic, by Richard Bornat (Oxford University Press, 2005).
• Logic for Computer Science, by S. Reeves and M. Clarke (International Computer Science Series, OMW, University of London, Addison-Wesley, 1990).
• The language of first-order logic: including the Mackintosh version of Tarski's World 4.0, by J. Barwise and J. Etchemendy (CSLI Lecture Notes no. 23, CSLI Publications, Stanford 1993).
• Hyperproof by J. Barwise and J. Etchemendy (CSLI Lecture Notes no. 42, CSLI Publications, Stanford 1994).