CS 245 — Fall 2018

LEC 002 with Stephanie McIntyre
David R. Cheriton School of Computer Science


Best of luck on the final!!!

Beware: Online materials can have different syntax, definitions, rules... Use at your own risk!


Resources and Handouts
Textbook Resources: errata, some quizzes and sample solutions.
Algebra of Formulas (Equivalence Laws)
Inference Rules for Natural Deduction
Code Examples from Class in Dafny
Additional Exercises for Peano Arithmetic
Additional Exercises for Semantic Entailment


Lecture Notes: These pdfs roughly outline what was covered in class.
For more details, please look at the Common Overheads on Propositional Logic.
Here is the Schedule of Lectures.

Lecture 1
Lecture 2: Intro to Propositional Logic
Lecture 3: Structural Induction and Truth Valuations
Lecture 4: Equivalence and Semantic Entailment
Lecture 5: Connectives and CNF
Lecture 6: Resolution
Lecture 7: Soundness and Completeness for Resolution
Lecture 8: Natural Deduction
Lecture 9: Soundness and Completeness for Natural Deduction (Prop)
Informal Introduction to Predicate Logic (see common slides for examples)
Lecture 11: Syntax and (some) Semantics of Predicate Logic
Lecture 12: Semantics of Predicate Logic
Lecture 13: Natural Deduction for Predicate Logic
Lecture 14: Equality Axioms
Lecture 15: Peano Arithmetic (see Carmen's slides).
Lecture 16: Soundness and Completeness (see Carmen's slides).
Lecture 17: Introduction to Formal Verification and Assignments
Lecture 18: Conditionals and start of Partial-While
Lecture 19: Loops, Invariants, Arrays (see Course Overheads)
Lecture 20: Arrays and Reversing Array Example (see Course Overheads)
Lecture 21: Continuing Arrays and Sorting (see Course Overheads)
Lecture 22 and 23: Decidability, Halting Problem and Reductions: For examples, see Course Overheads and Carmen's Slides.
Lecture 24: Summary and Review

All lecture notes are based off the textbook Logic in Computer Science, by Huth and Ryan, and the lecture slides from Carmen Bruni, Jonathan Buss and Alice Gao.

Need Help?
If you find yourself struggling with course content, I encourage you to seek help:

Special thanks to Alex Borgida, Grant Weddell, and my advisor David Toman
for their resources, tips and words of encouragment.