CS 245: Logic and Computation (Fall 2021)

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 Assessment will cover the material before the Reading Week.

There will be a Final Assessment due during the Final Exam period, which will cover the entire course.

Week Lectures Tutorials Assignments and Assessments References
Part 1 Part 2 Fridays
1: Sep 6–10 N/A What is logic? Logic propositions and connectives. N/A

Marked Quiz 1 available

Logic01

[Lu] 2.1

2: Sep 13–17 Truth tables; Translations between English and propositional logic; Propositional logic formulas; Review of induction. Structural induction; Propositional language semantics; Satisfiability. Structural induction. Semantics of propositional logic.

Marked Quiz 1 due Sep 15

Crowdmark Assignment 1 available

Logic02

Logic03 (up to slide 19)

[Lu] 1.2, 2.2, 2.3, 2.4

3: Sep 20–24 Proving arguments valid in propositional logic. Propositional calculus laws; Disjunctive and Conjunctive Normal Forms. Argument validity; Disjunctive and Conjunctive Normal Forms.

Crowdmark Assignment 1 due Sep 22

Marked Quiz 2 available

Logic03 (from slide 20 onwards)

Logic04

[Lu] 2.5, 2.7

4: Sep 27-Oct 1 Adequate set of connectives; Boolean algebra; Logic gates. Circuit design and minimization; Code analysis and simplification. Adequate sets of connectives, Circuit design, code analysis and simplification.

Marked Quiz 2 due Sep 29

Crowdmark Assignment 2 available

Logic05

[Lu] 2.8

5: Oct 4–8 Formal deduction for propositional logic. Soundness and completeness of formal deduction for propositional logic (proof of completeness optional). Formal Deduction for Propositional Logic; Soundness and completeness of formal deduction.

Crowdmark Assignment 2 due Oct 6

Logic06

[Lu] 2.6

Reading Week: Oct 11–15 N/A N/A N/A
6: Oct 18–22 Mid-Term Assessment Review. Automated theorem-proving: Resolution, Davis-Putnam Procedure (proof of completeness of DPP optional). (Notes only, no live tutorials this week) Resolution for propositional logic, DPP.

Midterm Assessment due Oct 20

Crowdmark Assignment 3 available

Logic07

[Lu] 3.6

7: Oct 25-29 First-order logic: Domain, terms, relations, variables, quantifiers. Translations from English to first-order logic. First-order logic syntax and semantics. First order logic: syntax, semantics.

Crowdmark Assignment 3 due Oct 27

Marked Quiz 3 available

Logic10

Logic11

Logic12

[Lu] 3.1, 3.2, 3.3

8: Nov 1–5 Logical consequence in first-order logic. Formal deduction in first-order logic. Logical consequence in first-order logic; Formal deduction in first-order logic.

Marked Quiz 3 due Nov 3

Crowdmark Assignment 4 available

Logic13

Logic14

[Lu] 3.4, 3.5

9: Nov 8–12 Formal deduction in first-order logic: Proof examples. Resolution for first-order logic: Prenex Normal Form, Existential-free PNF, unification and resolution, automated theorem provers/verifiers. Formal deduction in first-order logic; Resolution for first-order logic.

Crowdmark Assignment 4 due Nov 10

Marked Quiz 4 available

Logic14

Logic15

[Lu] 3.5, 3.6

10: Nov 15–19 Computation and Logic: Turing Machines, Undecidability, The Halting Problem, undecidable problems in logic. Computation and Logic: Turing Machines, Undecidability, The Halting Problem, undecidable problems in logic. Decidability; Undecidability.

Marked Quiz 4 due Nov 17

Crowdmark Assignment 5 available

Logic16

11: Nov 22–26 Peano Arithmetic. Proving theorems in Peano Arithmetic; Godel's Incompleteness Theorem. Peano Arithmetic; Godel's Incompleteness Theorem.

Crowdmark Assignment 5 due Nov.  24

Marked Quiz 5 available

Crowdmark Assignment 6 available

Logic17

12: Nov 29–Dec 3 Program Verification: Hoare triples, Partial and Total Correctness, Rules for Assignment, Implication, Composition. Program Verification: Conditional Statements. Program Verification: Assignment, Implication, Composition, Conditional Statements.

Marked Quiz 5 due Dec 1

Logic18

13: Dec 6–Dec 10 Program Verification: partial-while; Program termination; Undecidability of Partial and Total Correctness; Course Review. N/A N/A

Crowdmark Assignment 6 due Dec 7

Logic18