CS 245: Logic and Computation (Spring 2020)

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.

Midterm #1 will cover material from the first four assignments; roughly, the basics of Propositional Logic. We will announce a precise cut-off later.

Midterm #2 will cover material from assignments five through seven; roughly, the basics of Predicate Logic. We will announce a precise cut-off later.

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: May 11–15 What is logic? Logic propositions and connectives. Truth tables; Translations between English and propositional logic Truth tables; Translations between English and propositional logic A01 available.

[Lu] 2.1;

Logic01-intro-h.pdf

2: May 18–22 Well-formed propositional logic formulas; Structural induction. Propositional calculus, semantics: value assignments, satisfiability. Structural induction. Semantics of propositional logic. A01 due May 20

A02 available.

[Lu] 1.2, 2.2, 2.3, 2.4, 2.5;

Logic02-prop-logic-syntax-h.pdf,

Logic03-prop-logic-semantics-h.pdf
(up to slide 20)

3: May 25–29 Proving arguments valid in propositional logic. Propositional calculus laws; Disjunctive and Conjunctive Normal Forms. Proving arguments valid in propositional logic; Disjunctive and Conjunctive Normal Forms. A02 due May 27

A03 available.

[Lu] 2.5, 2.7

Logic03-prop-logic-semantics-h.pdf (from slide 21)

Logic04-prop-logic-laws-CNF-h.pdf

Logic03ExampleP30.mp4, Logic03ExamplsP35.mp4

4: June 1–5 How to obtain DNF and CNF from truth tables; Adequate sets of connectives. Formal deduction for Propositional Logic. How to obtain DNF and CNF from truth tables; Adequate sets of connectives; Formal Deduction for Propositional Logic. A03 due June 3

A04 available.

[Lu] 2.8, 2.6

5: June 8–12 Formal deduction for Propositional Logic. Soundness and Completeness of Formal Deduction. Soundness and Completeness of FD for Propositional Logic. A04 due June 10

MT1 available.

[Lu] 2.6

6: June 15–19 Automated theorem proving by Resolution; Davis Putnam Procedure. Predicate Logic; Quantifiers. Resolution; Predicate Logic; Quantifiers MT1 due June 17

A05 available.

[Lu] 3.1

7: June 22–26 Predicate Logic translations; Predicate Logic syntax: terms, atoms, formulas. Predicate Logic semantics: domains and interpretations; Proving argument validity in predicate logic. Predicate Logic: Translations. Syntax. Substitutions. Semantics of Predicate Logic. Proving argument validity in predicate logic A05 due June 24.

A06 available.

[Lu] 3.3.

8: June 29–July 3 Proving that arguments in predicate logic are invalid; Formal deduction in Predicate Logic. Formal deduction in Predicate Logic: Examples and exercises. Formal deduction in Predicate Logic. A06 due July 2

A07 available.

[Lu] 3.4, 3.5

9: July 6–10 Resolution for predicate logic: Prenex Normal Form; Existential-free PNF, unification and resolution, automated theorem provers/verifiers. Computation and Logic: Turing Machines, Undecidability, The Halting Problem, undecidable problems in logic Resolution for predicate logic: Prenex Normal Form; Existential-free PNF, unification and resolution, automated theorem provers/verifiers; Undecidability. A07 due July 8

MT2 available.

[Lu] 3.6, [Hopcroft.et.al] (Section 8.1, 8.2, 9.3.1 - FYI)

10: July 13–17 Peano Arithmetic. Proving theorems in Peano Arithmetic; Godel's Incompleteness Theorem. Proving theorems in Peano Arithmetic; Godel's Incompleteness Theorem. MT2 due July 15

A08 available.

TBD

11: July 20–24 Program Verification: Assignments, Conditional Statements. Program Verification: While Loops. Program Verification: Assignments, Conditional Statements,While Loops. A08 due July 22

A09 available.

H&R: ch. 4, §4.1–4.4

12: July 27–31 Program Verification: Arrays. Program Verification: Arrays; Course Review. Program Verification: Arrays; Course Review. A09 due July 29.

A10 available.

H&R: ch. 4, §4.1–4.4

13: Aug 3–5 N/A. N/A. N/A. A10 due Aug 5

N/A.