CS 245: Logic and Computation (Fall 2018)

Schedule of Lectures

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.

By late October, we will announce a cutoff for the midterm material.

Week Lectures Tutorials Assignments and Exams References
(See also instructors' pages)
Tuesdays Thursdays Fridays
0: Sept. 6&7 (n/a) Introduction and overview. Basic examples. Review of mathematical concepts. Review MATH 135.

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

Overheads: 1–17.

1: Sept. 10–14 Formal syntax of propositional logic. Inductive proofs. Meaning (semantics) of propositional formulas. Unambiguity of formulas. Expressing concepts in logic. Handling formal definitions. Asmt. 1 due Sept. 19

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

Overheads: 18–54.

2: Sept. 17–21 Equivalence of formulas. Logical identities. Example: code simplification. Adequate sets of connectives. Normal forms.
Additional examples.
Identities; adequacy; normal forms. Asmt 2 due Sept. 26

H&R: §§1.4.1 (pp. 36–40) and 1.5.1 (pp. 53–58).

Overheads: 55–85.

3: Sept. 24–28 Formal deduction and the "resolution" method. The power and limitations of resolution. Normal forms and resolution. Asmt 3 due Oct. 3

(Material not in H&R.)

Overheads: 86–113.

4: Oct. 1–5 Another formalism: "natural deduction". Derived rules in natural deduction. Soundness and completeness. Using natural deduction. Asmt 4 due Fri., Oct. 12

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

Overheads: 114–152.

5: Oct. 8–12 (Study break) Concepts for predicate logic: Domains, functions, relations and quantifiers. (Wednesday schedule)

H&R: §§2.1, 2.2 (pp. 93–106).

Overheads: 153–170.

6: Oct 15–19 Formal syntax and semantics; substitutions; free & bound variables. Interpretations. Natural deduction in predicate logic. Reasoning in predicate logic. Asmt. 5 due Oct. 24

H&R: §§2.2, 2.3 (pp. 93–122).

Overheads: 171–246.

7: Oct. 22–26 Deduction, continued. Axioms. Equality. Additional examples. Peano Arithmetic. Examples in natural deduction. Asmt. 6 due Oct. 31

Proofs and Programs, §§1,2 (pp. 1–6) (see also H&R, §2.4.3 (pp. 130–1))

8: Oct. 29–Nov. 2 Additional topics in predicate logic.
Overview of soundness and completeness.
TBA, and/or midterm review Midterm: Thursday, Nov. 1, 4:30pm–6:20pm. Locations TBA.

All of the above.

 

Also, Overheads: 256–282.

9: Nov. 5–9 Introduction to logical analysis of program correctness. Pre- and post-conditions. Deduction rules for assignment statements. Deduction rules for conditional statements. Introduction to loops. Specification and verification of programs. Asmt. 7 due Nov. 14

H&R: §§4.1–4.3.2 (pp. 256–287)

Overheads: 307–370.

10: Nov. 12–16 Loops, continued. partial and total correctness. Verifying code that uses arrays. Verification of conditionals and loops. Asmt. 8 due Nov. 21

H&R: TBA

11: Nov. 19–23 Larger examples: searching and sorting. Introduction to undecidability. Verification: additional examples. Asmt 9 due Nov. 28

H&R: TBA

12: Nov. 26–30 Undecidability, continued. Other limitations of logic. Looking ahead. Undecidability. Asmt. 10 due Mon., Dec. 3.

Overheads: ??