Fall, 2015

Final marks for undergraduates have been submitted.

They are posted on the secure CDF web site.

(Grad students may send me an email to find out their marks.)

There was a large variation on the final exam marks.

Three students got 100%, while five students got below 10%.

** Announcements **

Chapter's I and II in ** Logical Foundations of Proof Complexity **
by Cook and Nguyen

(available on line through the U of T library)
closely follows pp 1 - 52 in the Notes.

** Lectures: ** MW 4 in SS 1085

** Tutorial: ** F12 in SS 1085

** Tutor: ** Robert Robere

** Instructor: **
Stephen Cook
,
email: sacook@cs,
Office: Sandford Fleming 2303C, 416-978-5183

Office Hours: MW 5:15 - 6:00
Or make an appointment, or drop in.

QUESTIONS VIA EMAIL ARE WELCOME.

** Text: ** None. See Lecture Notes below.

** Marking Scheme: **

- 4 assignments worth 15% each (Due at beginning of tutorial Oct 2, Oct 23, Nov 20, Monday Lecture Dec 7.)
- 1 closed-book test worth 10%: Oct 30
- final exam worth 30%

** Reference Link: **
Handbook of Proof Theory, Chapters I and II
by Sam Buss

** Other References: **

- Herbert Enderton:
**A Mathematical Introduction to Logic**. Academic Press, 1972. - E. Mendelson:
**Introduction to Mathematical Logic**. Wadsworth & Brooks/Cole, 1987 - Pavel Pudlak:
**Logical Foundations of Mathematics and Computational Complexity**`A Gentle Introduction.'

This is a new book, full of interesting historical notes and philosophical comments.

Michael Sipser:

** Lecture Notes **

Please send corrections and comments to the instructor.

- Notes pp1-18: Propositional Calculus (slightly revised)
- Notes pp1-17: Propositional Calculus
- Notes pp18-30: Predicate Calculus (page 21, 3) clarified
- Notes pp31-38: Completeness of LK
- Notes pp39-53: Herbrand Theorem, Equality and Compactness
- Notes pp54-70: Computability Theory
- Notes pp71-82: Recursive and Recursively Enumerable Sets
- Notes pp83-95: Incompleteness and Undecidability Part I.
- Notes pp96-108: Peano Arithmetic
- Notes pp109-112: Godel's Incompleteness Theorems

** Problem Sets ** (.pdf files)