Course Information
Instructor: Purandar Bhaduri (Email:pbhaduri)
Department: Computer Science & Engineering
Semester: Winter, 2025-2026
Class Schedule: Tue 7:55 - 8:50, Wed 9 - 9:55, Thu 10 - 10:55
Head Teaching Assistant: Siddharth Gaur (email: sgaur)
Evaluation
- Mid-semester Exam: 40%
- End-semester Exam: 60%
Syllabus
The course will cover a selection from the following topics. Additional topics may also be touched upon.
- Propositional Logic: Syntax and Semantics; Satisfiability and Validity; Compactness; Proof Systems and Completeness.
- First-order Logic: Syntax and Semantics; Satisfiability and Validity; First-order Theories; Compactness; Proof Systems and Completeness.
- Quantifier Elimination and Decision Procedures: Dense Linear Orders without Endpoints; Linear Arithmetic -- Quantifier elimination over integers and rationals, Fourier-Motzkin method, Ferrante-Rackoff method; Quantifier-free Linear Arithmetic -- Linear Programs and the Simplex method; Presburger Arithmetic -- Cooper's method
- Finite Model Theory: First-order Logic over Finite Models -- Properties; Expressive Power -- Ehrenfeucht-Fraïssé games.
- Modal Logic: Syntax and Semantics; Basic Correspondence Theory; Bisimulation and Expressiveness; Completeness and Decidability; Logic of Knowledge.
Reference Books
- A Concise Introduction to Mathematical Logic, Wolfgang Rautenberg, Springer 2010
- A Friendly Introduction to Mathematical Logic, Christopher Leary and Lars Kristiansen, Creative Commons, 2015. The book can be freely downloaded from the link provided.
- Elements of Finite Model Theory, Leonid Libkin, Springer 2004. The book can be freely downloaded from the link provided.
Other Sources
- Logic in Computer Science: Rough course notes, P. Madhusudan and Mahesh Viswanathan, UIUC, December 12, 2024. Additional course material by the authors can be found at CS 474: Logic in Computer Science at UIUC, 2021.
- CSIE 5111: Introduction to mathematical logic, Lecture notes by Tony Tan, NTU, Taiwan 2018/19.
- CSC 438F/2404F: Computability and Logic, includes Lecture Notes by Stephen Cook at Toronto, Fall, 2017.
- Introduction to Logic, Madhavan Mukund and S P Suresh, CMI, August 2011.
- Lecture Notes in Logic, Yiannis N Moschovakis, UCLA, March 2014.
- CS156: The Calculus of Computation, Course material at Stanford by Zohar Manna, Winter 2010.
Contact Information
For any questions regarding the course, use the MS Teams group for this class. You can also schedule an appointment in my office by email.