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– 
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– 
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– 
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– 
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– 
(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– 
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– 
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– 
Additional topics in predicate logic.
Overview of soundness and completeness. 
TBA, and/or midterm review 
Midterm: Thursday, Nov. 1, 4:30pm– 
All of the above.
Also, Overheads: 256–282. 

9: Nov. 5– 
Introduction to logical analysis of program correctness. Pre and postconditions. 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– 
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– 
Larger examples: searching and sorting.  Introduction to undecidability.  Verification: additional examples.  Asmt 9 due Nov. 28  H&R: TBA 
12: Nov. 26– 
Undecidability, continued.  Other limitations of logic. Looking ahead.  Undecidability.  Asmt. 10 due Mon., Dec. 3. 
Overheads: ?? 