CS 245 -- Logic and Computation, Spring 2026
Here I upload notes and/or problem sets from my tutorial sections, held 1:30-2:30 on Fridays in MC 4042.
Note that this is a personal webpage, thus is not “canonical” with regards to logistical or instructructional information pertaining to the course. While I try to be faithful to the notations and conventions adopted in the official course notes, doubtless I will make errors. Hopefully they will be small ones.
In general, anything I say or write that is contrary to what an Instructor (Prof. Ben-David) says, you should be skeptical of– especially when it comes to course logistics. Do not rely on me to tell you when and where your exams will be held! TAs and IAs are typically not kept in the loop on these things, so your guess is as good as mine. For all logistical information regarding the course, consult the official course webpage or talk to Dalibor or Prof. Ben-David.
Please point out typos or mistakes to me in the following notes, either by email or in class.
Notes
Tutorial 1: N/A
Tutorial 2: Notes
Tutorial 3:
Tutorial 4:
Tutorial 5:
Tutorial 6:
Tutorial 7:
Tutorial 8:
Tutorial 9:
Tutorial 10:
Unsolicited Personal Advice
This is a difficult course. For many of you, this will be your first time meeting many of the mathematical concepts associated with logic and theoretical computer science. This includes things that are not covered in typical undergrad math curricula, such as structural induction, formal proof, and decidability / universal Turing machines.
Not only that, but we have quite a bit of ground to cover. I’ve heard instructors say that realistcally, this should be split into two courses. But planning committees have tried and found it impossible to refactor the CS course sequence in a way that would allow for it, hence have given up trying.
So unfortunately, one simply to buckle down, lock in, and learn. There is some consolation in that this is a fun course, in addition to being difficult. Many of the ideas presented here are very deep and beautiful, and will blow your mind when you finally understand them. So don’t give up! :)
When you need help, please take the initiative to get it. We’re here for you– instructors, IAs, TAs. We want to help you understand this, and we were once in your position ourselves. Nobody starts out “getting” logic; it was only through a great deal of practice and hardship that we were able to master these topics. And that brings to my next point…
Please work out problems yourself. Please please please. This is by far the best way to become adept at working with the formalisms introduced in the notes and –better yet– being able to manipulate them to your own ends! We have several very good HW assignments planned for this purpose. Please don’t get an AI to do them for you. You’re robbing yourself of the opportunity to learn the math in a low-stakes environment, and throwing away money spent on your degree in the process.
And if you need more help, you can rework the problems presented in these tutorials, or on LEARN, or in Lu Zhongwan’s textbook. It’s a great book for the first 2/3 of this course, and contains lots of exercises ranging in difficulty from absurdly easy to quite challenging. And if you run out of exercises, just go back and prove the lemmas and yheorems without looking at the proofs, then check against what’s there.
The point is: to get good at something, you need to put in as many hours as you can (ideally >=10,000, but we’re all very busy and I know this probably isn’t realistic). And nowhere is this more true than in mathematics. I think Halmos really puts it best…
So yes– this course isn’t for the faint of heart. But, as I said before, it’s fun! When I first learned about these topics as an undergrad, it changed my life. And I know from personal conversations that many of the course staff feel the same way. We hope to be able to impart at least an epsilon of the curiosity and joy that we experienced learning about these topics to you in the coming term, and to possibly inspire some of you to continue studying theoretical CS in the future. :)
Contact:
JHS: j47smith (at) uwaterloo (dot) ca