Date  Lectures & Tutorials  Notes & Readings  Assignments & Exams 

May 9  What is logic? Logic propositions and connectives. 
[


May 11  Truth tables; translations between English and propositional logic; propositional logic formulas; review of induction. 
[


May 12  No tutorial 
[

Assignment 1 out May 15 
May 16  Structural induction; propositional language semantics; satisfiability. 
[


May 18  Tautological consequence; proving arguments valid in propositional logic. 
[


May 19  Tutorial 
[

Assignment 1 due May 22 
May 23  No lecture: May 23 follows a Monday schedule  
May 25  Propositional calculus laws; disjunctive and conjunctive normal forms. 
[


May 26  Tutorial 
[


May 30  Adequate set of connectives; Boolean algebra; logic gates. 
[


June 1  Circuit design and minimization; code analysis and simplification. 
[


June 2  Tutorial 
[

Assignment 2 out June 5 
June 6  Formal deduction for propositional logic. 
[


June 8  Soundness and completeness of formal deduction for propositional logic (proof of completeness optional). 
[


June 9  Tutorial 
[

Assignment 2 due June 12 
June 13  Automated theorem proving: resolution, DavisPutnam procedure (proof of completeness of DPP optional). 
[


June 15  No lecture: self study for midterm  Midterm on June 15  
June 16  No tutorial 
[


June 20  Firstorder logic: domain, terms, relations, variables, quantifiers; translations from English to firstorder logic. 
[


June 22  Firstorder logic syntax and semantics. 
[


June 23  Tutorial 
[

Assignment 3 out June 26 
June 27  Logical consequence in firstorder logic. 
[


June 29  Formal deduction in firstorder logic. 
[


June 30  Tutorial 
[

Assignment 3 due July 4 
July 4  Formal deduction in firstorder logic: more proof examples, soundness and completeness. 
[


July 6  Resolution for firstorder logic: prenex normal form, existentialfree PNF, unification and resolution. 
[


July 7  Tutorial 
[

Assignment 4 out July 10 
July 11  Resolution for firstorder logic: proof examples. Computation and logic: the satisfiability problem, the halting problem. 
[


July 13  Turing machines; computability and decidability. 
[


July 14  Tutorial 
[

Assignment 4 due July 17 
July 18  Proving decision problems undecidable by reduction. 
[


July 20  Peano arithmetic; proving theorems in Peano arithmetic. 
[


July 21  Tutorial 
[

Assignment 5 out July 24 
July 25  Gödel's incompleteness theorem. Program verification: Hoare triples, partial and total correctness. 
[


July 27  Program verification: rules for assignment, implication, and composition, conditional statements. 
[


July 28  Tutorial 
[

Assignment 5 due July 31 
Aug 1  Program verification: partialwhile, program termination, undecidability of partial and total correctness. 
[

Final exam on August 11 
Assignments are due at 11:59 pm (Eastern Time) on the due dates. The due dates are subject to change.