Winter, 2014

** Announcements **

All marks are now posted on the secure CDF web site.

Your unofficial final mark for the course is named finl.

Grad students can see me to pick up your final exam.

Curious for another look at your final exam?

Click here for the 2014 final
exam for CSC 438H/2404H.

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.

Accessibility Services requests a volunteer note-taker for this course.

** Current background reading **

Final Lecture Wednesday, April 2 (there will be a tutorial Friday)

We will present Godel's Incompleteness Theorems (notes pp 109 -- 112).

** Lectures: ** MW 2 in BA 1220

** Tutorial: ** F2 in BA 1220

** Tutor: ** Bahar Aameri

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

Office Hours: MF 3:15 - 4: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 Jan 24, Feb 14, March 14, April 4)
- 1 closed-book test worth 10%: Feb 28 2:10pm in BA 1180
- 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)

- Problem Set 1 Due January 24
- Problem Set 2 Due February 14
- Problem Set 3 Due March 14
- Problem Set 4 Due April 4