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:

- Attend someone's office hours
- Post on Piazza
- Ask questions in class and/or tutorials
- Send an email (srmcintyre).

Special thanks to Alex Borgida, Grant Weddell, and my advisor David Toman

for their resources, tips and words of encouragment.