CS 153 Mechanical Reasoning, Theorem Proving, and AI (Spring 2027)
This site is still under construction.
Modern AI systems are radically changing software engineering and programming. They can generate massive amount code in seconds — but how do we know it is correct? This hands-on seminar course explores how proof assistants, automated reasoning, and modern AI can help us build reliable software and make our reasoning precise, explicit, and mechanically verifiable.
We will learn Lean, a programming language and proof assistant for writing mathematical proofs as functional programs and proof scripts. We will also study the “good old-fashioned AI” algorithms behind automated theorem provers, including Boolean satisfiability (SAT) and satisfiability modulo theories (SMT). Using these tools, we will reason about program behavior and develop programs with correctness guarantees. Finally, we will explore how AI/LLM agents can support and amplify rigorous, mechanical, and automated reasoning in various domains.
Instructor: Guannan Wei (guannan.wei@tufts.edu), Assistant Professor in Computer Science
Course URL: https://continuation.passing.style/teaching/cs153-spring27
Prerequisite: CS105 and CS/Math61 highly recommended.
Textbook: The Hitchhiker’s Guide to Logical Verification (2026 Edition)
Time: Monday, Wednesday 4:30–5:45 PM
Where: TBD
Office hours: TBD
1 Format
The course format includes a combination of lectures, student-led paper presentations, and project work. Lectures will provide an introduction to important and foundational concepts.
Students will lead a class by presenting and discussing a research paper from recent conferences or classical papers about theorem proving and applied AI. To ensure a lively discussion, students are responsible for reading assigned papers at sufficient level to summarize the research problem, the proposed solution, the relationship to the literature, and the evaluation of any claimed contributions.
Each student will work on a mini research project. The project will involve exploring a specific topic in depth, conducting a literature review, and implementing a solution or conducting an experiment.
2 Topics
Gain hands-on experience of theorem proving and programming in Lean
Learn how to reason and prove properties of programs and programming languages
Understand the intellectual ideas behind theorem provers from decades of research
Explore how cutting edge AI/agents can be applied to scale up in different domains
Foundations of theorem proving in Lean: logics and proposition, induction principles, equational reasoning, relations, Curry-Howard correspondence, functional programming in Lean
Programming languages semantics: Lambda calculus, operational semantics, type systems, denotational semantics, metatheory (type soundness, logical relations)
Program verification: program correctness, verifying algorithms, Hoare logic
Applied AI for theorem proving: ReAct agent, reasoning models, etc.
3 Grading
Tentative grading breakdown:
Project: 50%
Homework: 25%
Paper presentation and discussion: 25%
4 Schedule
Tentative schedule for the course:
Week |
| Date |
| Topic |
Week 1 |
| - |
| Introduction & Logistics |