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– |
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 |