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: TBD
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.
- 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, Winter 2010, Course material at Stanford by Zohar Manna.
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.