CS 245: Logic and Computation (Spring 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 (June 13) will cover material from the first four assignments; roughly, the basics of propositional logic. We will announce a precise cut-off later.

Week Lectures Tutorials Assignments and Exams References
Tuesdays Thursdays Fridays
1: May 6–10 Course overview; Introduction to propositional logic; Translations from English into Propositional Logic. Syntax of Propositional Logic; Structural Induction. Translations from English into Propositional Logic. Structural Induction Asmt. 1 available.

H&R: §§1.0, 1.1 (pp. 1–4).

Overheads: 1–39.

2: May 13–17 Parse Trees; Unique Readability of Propositional Formulae. Semantics of Propositional Logic; Equivalence of Formulae; Logical Identities. Structural induction. Semantics of propositional logic. Asmt. 1 due May 15

Asmt. 2 available.

H&R: §1.3 (pp. 31–36). §1.4.2 (pp. 40–45).

Overheads: 40–69.

3: May 20–24 Code Simplification Examples; Circuit Design. Semantic Entailment; Proof Systems in Propositional Logic; Natural Deduction for Propositional Logic (Reflexive, And). Applications of Semantics of Propositional Logic. Natural Deduction for Propositional Logic. Asmt. 2 due May 22

Asmt. 3 available.

H&R: §§1.4.1–2 (pp. 36–45). §§1.5.1 (pp. 53–58). §§1.2 (pp. 5–7).

Overheads: 70–110.

4: May 27–31 Natural Deduction for Propositional Logic (Implication, Or, Negation). Natural Deduction for Propositional Logic (Derived, Examples). Natural Deduction for Propositional Logic. Asmt. 3 due May 29

Asmt. 4 available.

H&R: §1.2 (pp. 5–31).

Overheads: 111–127.

5: June 3–7 Soundness and Completeness of ND for Propositional Logic. Soundness and Completeness of ND for Propositional Logic. Soundness and Completeness of ND for Propositional Logic. Asmt. 4 due June 5

Asmt. 5 available.

H&R: §§1.2 (pp. 8–31). §1.4.3-.4 (pp. 45–52).

Overheads: 128–140.

6: June 10–14 Intro to Predicate Logic; Translations from English into Predicate Logic; Mid-Term Exam Review. Translations between English and Predicate Logic. Tutorials are cancelled on June 14 Asmt. 5 due June 12

Midterm Exam June 13

Asmt. 6 available.

H&R: §2.1 (pp. 93–98).

Overheads: 141–158.

7: June 17–21 Syntax of Predicate Logic; Substitutions. Semantics of Predicate Logic. Predicate Logic: Translations. Syntax. Substitutions. Semantics of Predicate Logic. No assignment due.

H&R: §2.2 (pp. 98–107); §2.4.1 (pp. 122–129).

Overheads: 159–198.

8: June 24–28 Validity and Satisfiability of Formulae; Semantic Entailment. Natural deduction for Predicate Logic. Validity and Satisfiability of Formulae; Semantic Entailment. Asmt. 6 due June 26

Amst. 7 available.

H&R: §2.4.2 (pp. 129–130); H&R: §2.3 (pp. 107–122).

Overheads: 199–210.

9: July 1–5 No lecture (July 2 follows a Monday schedule). Natural deduction for predicate logic. Proofs in Natural Deduction for Predicate Logic. Asmt. 7 due July 3

Amst. 8 available.

H&R: §2.3 (pp. 107–122).

Overheads: 211–224.

10: July 8–12 Soundness and Completeness of ND for Predicate Logic. Intro to Program Verification; Assignment Statements. Soundness and completeness of Natural Deduction for Predicate Logic. Program Verification: Introduction, Assignment Statements. Asmt. 8 due July 10

Asmt. 9 available.

H&R: ch. 4, §4.1–4.2.1–2 (pp. 256–265.)

Overheads: 225–266.

11: July 15–19 Program Verification; Conditional Statements. Program Verification; While Loops. Assignment Statements. Conditional Statements. Program Verification; While Loops. Asmt. 9 due July 17

Asmt. 10 available.

Overheads: 270–311.

H&R: ch. 4, §4.1–4.2.1–2 (pp. 267–298.)

12: July 22–26 Program Verification: Arrays. Decidability/Undecidability; Reduction from the halting problem. Program Verification: Arrays. Decidability/Undecidability; Halting Problem. No assignment due.

Proofs and Programs, §5, pp. 16–19

Overheads: 299–353

13: July 29–30 Decidability/Undecidability - Examples. No lecture. No tutorial. Asmt. 10 due July 30

Proofs and Programs, §5, pp. 16–19

Overheads: 354–362