CS 245E: Logic & Computation

University of Waterloo, Fall 2025

Overview

In this course, we will see how to formalize the notions of logic and computation. In doing so, we will see how logic can be used to prove the correctness of arguments and algorithms. We will also see how this formalization can help us establish some of the limits of what computers can do.

The course will cover three main topics:

Propositional Logic. The study of logical arguments which will enable us to verify when a conclusion correctly follows from a set of premises.
First-Order Logic. A richer form of logic that will enable us to formalize mathematical statements, notably.
Computation. With Turing machines, we will introduce a formal model of computation that lets us establish fundamental limits on what algorithms can do.

The lecture notes below will be updated throughout the term to include the essential results that we cover in class. They represent starting points for the discussions we hold in class and a reference for reviewing the lectures; not a self-contained complete introduction to the topic.

If you are enrolled in the class, you can find more information about the course itself in the official Learn page.

And if you are not enrolled in the class, you are most welcome to use these notes in your independent study as well. If you do and find them useful, please let me know! And because these notes are meant to complement the in-person lectures and discussions, you may find them most useful when combined with additional complementary resources. Luckily, there are many great resources (online and in the form of textbooks) available for this purpose. I include some recommendations below.

Happy explorations!

Eric Blais
Waterloo, ON, Canada
September 2, 2025

Lecture Notes

The preliminary version of the notes for each lecture are listed below, as they are added. One word of warning: all of the notes provided below are new, and are sure to contain errors. I will be updating these notes throughout the term with additions and corrections.

1. Introduction
Propositional Logic
2. Syntax of Propositional Logic
3. Semantics of Propositional Logic
4. Logical Equivalence and Consequence
5. Formal Proofs
6. Examples of Formal Proofs
7. Soundness for Propositional Logic
8. Completeness for Propositional Logic
First-Order Logic
9. Syntax of First-Order Logic
10. Semantics of First-Order Logic

Additional Resources

The lecture notes above do not correspond to a single textbook. And, unfortunately, the terminology and notation varies between different resources. Nevertheless, here are some of the many books that can help in providing alternative perspectives and additional insights into the material covered in the course. All of these books are available online to UWaterloo students.

Beginning Mathematical Logic by Peter Smith.

This book is my strongest recommendation for the first place to look for additional references. It presents a brief summary of the highlights of the three topics we cover in the course and of many additional topics that go beyond the scope of this course as well. And it includes a great annotated list of recommendations for references that are useful for independent study of each topic.
Forall x: Calgary and Sets, Logic, Computation by the Open Logic Project.
Mathematical Logic by Ian Chiswell and Wilfrid Hodges.
Propositional and Predicate Calculus by Derek Goldrei.
Mathematical Logic for Computer Science by Zhongwan Lu.