Welcome Page

Welcome to the CS 245 Resources Page! For now, this site is a quick one stop access to videos and content I have made for CS 245 at the University of Waterloo. This course is an first course in logic for computer science students. If you find any errors, please email me at cbruni@uwaterloo.ca.

 

All the best and happy learning!

Carmen Bruni

 

Lecture and Learning Outcomes.

 

Learning Outcomes (Special thanks to Alice Gao for creating these!)

 

Workbook Exercises Again special thanks to Alice Gao for these!

• Workbook (No Solutions)
• Workbook (With Solutions)

 

Lectures for the course:
This is mentioned in every single file, but I would also like to take this opportunity to thank the plethora of people who made these slides possible. This list includes the original authors (in most cases) Jonathan Buss and Borzoo Bonakdarpour along with the work of Lila Kari, Anna Lubiw and Steve Wolfman with thanks to Alice Gao, Daniela Maftuleac, Collin Roberts, Ryan Trefler, and Peter Van Beek.

 

Fall 2018 Lectures (This will be updated throughout the term! Do not batch download everything!):

• Lecture 1 - Introduction
• Lecture 2 - Propositional Logic: Syntax (start of structural induction)
• Lecture 3 - Propositional Logic: Structural Induction Continued
• Lecture 4 - Propositional Logic: Semantics, Logical Equivalences, Dead Code
• Lecture 5 - Propositional Logic: Semantic Entailment, Adequate Sets of Connectives, Conjunctive Normal Form
• Lecture 6 - Resolution Part 1
• Lecture 7 - Resolution Part 2
• Lecture 8 - Natural Deduction
• Lecture 8 - Natural Deduction Handout
• Website to help verify Natural Deduction Proofs
• Lecture 9 - Natural Deduction Soundness and Completeness
• Lecture 10 - Predicate Logic: Syntax and Translations
• Lecture 11 - Predicate Logic: Syntax, Translations, Free and Bound Variables, Substitutions, Semantics
• Lecture 12 - Predicate Logic: Semantics (Interpretations, Environments, others)
• Lecture 13 - Predicate Logic: Natural Deduction
• Lecture 14 - Predicate Logic: Natural Deduction and Equality Axioms
• Lecture 14 - Natural Deduction Handout
• Lecture 15 - Predicate Logic: Peano Arithmetic
• Lecture 16 - Predicate Logic: Natural Deduction Soundness and Completeness
• Lecture 17 - Program Verification - Introduction
• Lecture 18 - Program Verification - Assignment, Implied, Composition, Conditional (If then statements)
• Lecture 19 - Program Verification - While Loops
• Lecture 19 - Program Verification - While Loops Handout
• Lecture 20 - Program Verification - Arrays
• Lecture 21 - Array Reversing Example
• Lecture 21 - Program Verification - Array Reversing Handout
• Lecture 22 - Decidability Introduction and Reductions
• Lecture 23 - Decidability Halting Problem Proof
• Lecture 24 - Beyond CS 245
• Playlist on Infinity (Thanks to Sara Abdelrahman)

 

Spring 2018 Lectures:

• Lecture 1 - Introduction
• Lecture 2 - Propositional Logic: Syntax (start of structural induction)
• Lecture 3 - Propositional Logic: Structural Induction Continued
• Lecture 4 - Propositional Logic: Semantics
• Lecture 5 - Propositional Logic: Semantics Continued (Logical equivalence, dead code, circuits)
• Lecture 6 - Entailment and start of Natural Deduction
• Lecture 7 - Natural Deduction
• Lecture 8 - Natural Deduction
• Lecture 8 - Natural Deduction Handout
• Website to help verify Natural Deduction Proofs
• Lecture 9 - Natural Deduction Soundness and Completeness
• Lecture 10 - Predicate Logic: Syntax and Translations
• Lecture 11 - Predicate Logic: Syntax, Translations, Free and Bound Variables, Substitutions
• Lecture 12 - Predicate Logic: Semantics (Interpretations)
• Lecture 13 - Predicate Logic: Semantics (Environments)
• Lecture 14 - Predicate Logic: Semantic Entailment
• Lecture 15 - Predicate Logic: Natural Deduction
• Lecture 16 - Predicate Logic: Natural Deduction Continued
• Lecture 16 - Natural Deduction Handout
• Lecture 17 - Natural Deduction - Soundness and Completeness
• Lecture 18 - Program Verification - Introduction
• Lecture 19 - Program Verification - Assignment, Implied, Composition, Conditional (If then statements)
• Lecture 20 - Program Verification - While Loops
• Lecture 20 - Program Verification - While Loops Handout
• Lecture 21 - Program Verification - Arrays
• Lecture 22 - Program Verification - Array Reversing Example
• Lecture 22 - Program Verification - Array Reversing Handout
• Lecture 23 - Decidability Introduction and Reductions
• Lecture 24 - Decidability Halting Problem Proof

Videos.