Winter, 2014

** Announcements **

Solutions to Problem Set 4 are posted below.

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

(NOTE: The exam is a bit long -- this year's will be shorter.)

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

Link to CSC 438/2404 2008 website

** Problem Sets ** (.pdf files)

- Problem Set 1 Due January 24
- Solutions to Problem Set 1
- Marker's comment for Problem Set 1
- Statistics for Problem Set 1
- Problem Set 2 Due February 14
- Solutions to Problem Set 2
- Problem Set 3 Due March 14
- Solutions to Problem Set 3
- Problem Set 4 Due April 4
- Solutions to Problem Set 4