Fall, 2017

Exclusions: MAT 309H, PHL 348H

Prerequisites for undergraduates: (CSC363H1/CSC463H1)/CSC365H1/CSC373H1/ CSC375H1/MAT247H1
(Send email to instructor if missing prerequisites)

** Announcements **

Read Notes Incompleteness and Undecidablility

Solutions to PS 3 are posted below.

Finish Notes Computability Theory and start Notes Recursive and Recursively Enumerable Sets.

=====================================

** Lectures: ** MW 4 in MP 134

** Tutorial: ** F12 in MP 134

** Tutor: ** Robert Robere

** Instructor: **
Stephen Cook ,
email: sacook@cs.toronto.edu
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 10% each (Due at beginning of tutorial Sept 29, Oct 20, Nov 17, Dec 1.)
- 1 closed-book test worth 20%: Oct 27
- final exam worth 40%

**The work you submit must be your own.
You may discuss problems with each other; however,
you should prepare written solutions alone.
Copying assignments is a serious academic offence and will be dealt with
accordingly. **

Click here for the course information sheet

** Lecture Notes **

- Notes pp1-18: Propositional Calculus (slightly revised)
- 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

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.

** 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 full of interesting historical notes and philosophical comments.

Michael Sipser:

** Problem Sets ** (.pdf files)

- Problem Set 1 (2017)
- Solutions to Problem Set 1 (2017)
- Marker's Comments on Problem Set 1 (2017)
- Problem Set 2 (2017)
- Solutions to Problem Set 2 (2017)
- Marker's Comments on Problem Set 2 (2017)
- Problem Set 3 (2017)
- Solutions to Problems Set 3 (2017)

- Midterm Test
- Solutions to Midterm Test
- Marker's Comments on Midterm Test

**LAST YEAR's Problem Sets**(.pdf files)

**LAST YEAR's Tests**(.pdf files)

Midterm Test (2016)