CS 245: Logic and Computation (Fall 2019)

Schedule of Lectures

We will adjust this schedule as required.

Each tutorial will provide a forum for you to practice with the ideas and techniques presented in the preceding lectures. The following assignment allows further practice and feedback. Each assignment will focus on the recent topics, but includes everything that came before, as well—everything is cumulative.

The midterm exam (November 7) will cover material from the first six assignments. We will announce a precise cut-off later.

Week Lectures Tutorials Assignments and Exams References
Tuesdays Thursdays Fridays
0: Sept 4–6 N/A Course overview; Introduction to Propositional Logic. Introduction to Propositional Logic. N/A

p. 17.

1: Sept 9–13 Syntax of Propositional Logic Structural Induction. Syntax of Propositional Logic. Structural Induction. a01 available.

pp. 18-26.

2: Sept 16–20 Syntax of Propositional Logic. Structural Induction. Semantics of Propositional Logic. Structural Induction. Semantics of Propositional Logic. a01 due Sept 18.

a02 available.

pp. 26-33

3: Sept 23–27 Translations. Tautological Consequence. Formal Deduction. Translations. Tautological Consequence. Formal Deduction. a02 due Sept 25.

a03 available.

pp. 33-61.

4: Sept 30–Oct 4 Formal Deduction. Soundness and Completeness of Formal Deduction for Propositional Logic. Formal Deduction. Soundness and Completeness. a03 due Oct 2.

a04 available.

pp. 40-44.

5: Oct 7–11 Soundness and Completeness of Formal Deduction for Propositional Logic. Intro to Predicate Logic. Translations. Soundness and Completeness; Translations. a04 due Oct 9.

a05 available.

pp. 69-74.

6: Oct 21–25 Syntax of Predicate Logic. Semantics of Predicate Logic. Syntax of Predicate Logic; Semantics of Predicate Logic. a05 due Oct 23.

a06 available.

pp. 72-82; pp.97-105.

7: Oct 28–Nov 1 Semantics of Predicate Logic. Tautological Consequence. Formal Deduction for Predicate Logic. Semantics of Predicate Logic; Tautological Consequence. Formal Deduction for Predicate Logic. a06 due Oct 30.

pp. 83-96.

8: Nov 4–8 Soundness and Completeness of Formal Deduction for Predicate Logic. Peano Arithmetic. Tutorials are cancelled on Nov 8.

Midterm Exam Nov 7.

a07 available.

pp. 117-139.

9: Nov 11–15 Peano Arithmetic. Undecidability of the Halting Problem. Compactness; Halting Problem.

a07 due Nov 13.

a08 available.

pp. 147-156.

10: Nov 18–22 Reductions. Intro to Program Verification: Partial / Total Correctness. Reductions; Intro to Program Verification: Partial / Total Correctness.

a08 due Nov 20.

a09 available.

N/A

11: Nov 25–29 Program Verification; Conditional Statements. Program Verification; While Loops. Conditional Statements; While Loops.

a09 due Nov 27.

a10 available.

N/A

12: Dec 2–3 Program Verification: Examples; Course Review. N/A N/A

a10 due Dec 3.

N/A