M.Tech.(CS)
ISI Kolkata, 2023-2024 Session
Semester: Second
Instructor: Sujata Ghosh
Meeting Times : Mondays, Wednesdays 9:30 - 11:15 am
First Class: Monday, January 08, 2024
Location: Online
Instructor: Sujata Ghosh
Meeting Times : Mondays, Wednesdays 9:30 - 11:15 am
First Class: Monday, January 08, 2024
Location: Online
[Teaching staff | Course overview | References | Grading | Lecture schedule | Homeworks/Handouts]
Teaching staff
Instructor
Sujata Ghosh
Email: sujata AT isichennai DOT res DOT in
Office Hours: By Arrangement (please send an e-mail)
Office Hours: By Arrangement (please send an e-mail)
TA
Soham Banerjee
Email: sohamsbanerjee AT gmail DOT com
Office Hours: By Arrangement (please send an e-mail)
Office Hours: By Arrangement (please send an e-mail)
Smiha Samanta
Email: smi1995ha AT gmail DOT com
Office Hours: By Arrangement (please send an e-mail)
Office Hours: By Arrangement (please send an e-mail)
Course overview
Course Description: This course can be considered as an introductory course on mathematical logic with theoretical
computer science in mind. We will deal with both model-theoretic and proof-theoretic techniques. We will
also give an introduction to logics of computation and connections with algorithms and complexity.
The complete syllabus of the course can be
found here.
This course is also about building up mathematical maturity, e.g., how to read and write mathematics, especially mathematical proofs, and how to communicate mathematics.
This course is also about building up mathematical maturity, e.g., how to read and write mathematics, especially mathematical proofs, and how to communicate mathematics.
Pre-requisites: A course on Discrete Mathematics.
References
Text book(s): The main text books for the course include A mathematical introduction to logic
by H.B. Enderton, and A course on mathematical logic by S.M. Srivastava.
Some other books which might prove to be helpful are Logic for computer science by M. Huth and M. Ryan, Mathematical logic for computer science by M. Ben-Ari, Modal Logic by P. Blackburn, M. de Rijke and Y. Venema, and Modal Logic for open minds by J. van Benthem.
Some other books which might prove to be helpful are Logic for computer science by M. Huth and M. Ryan, Mathematical logic for computer science by M. Ben-Ari, Modal Logic by P. Blackburn, M. de Rijke and Y. Venema, and Modal Logic for open minds by J. van Benthem.
Grading
Grades are based on mid-semester examination (20%), home assignments (20%), project (10%)
and end-semester examination (50%). The home assignments would include sets of homework
which will be uploaded here at regular intervals, and algorithmic questions. The projects
would be decided along the way depending upon the interests, and the deadline for submission
will be one week after the end-semester examination.
The latex template for the scribe can be found here.
The latex template for the scribe can be found here.
Lecture schedule
08.01.2024 | First order logic: Introduction (Class notes) |
10.01.2024 | First order logic: Syntax and Semantics (Class notes) |
Notes | Arnab and Debarshi: Scribe |
13.01.2024 | Free and bound variables (Class notes) |
17.01.2024 | Consequence relation (Class notes) |
Notes | Basudeb and Ritam: Scribe |
24.01.2024 | On consequence and satisfiability (Class notes) |
Notes | Sruti: Scribe |
31.01.2024 | Compactness theorem: First steps (Class notes) |
Notes | Rashmi: Scribe |
05.02.2024 | Compactness theorem: A model (Class notes) |
07.02.2024 | Compactness theorem: On substitutions (Class notes) |
Notes | Kuntal and Vamsi: Scribe |
12.02.2024 | Compactness theorem: The quantifier case (I) (Class notes) |
15.02.2024 | Compactness theorem: Finishing (Class notes) |
Notes | Debanjan: Scribe |
17.02.2024 | Tutorial |
19.02.2024 | No class (Class notes) |
21.02.2024 | Definability (Class notes) |
Notes | Arpan: Scribe |
24.02.2024 | Tutorial |
26.02.2024 | MID-SEM EXAM |
06.03.2024 | Deductive consequence relation (Class notes) |
Notes | Rashmi: Scribe |
11.03.2024 | Classical propositional logic (CPL) (Class notes) |
13.03.2024 | CPL completeness (Class notes) |
Notes | Basudeb and Ritam: Scribe |
18.03.2024 | Theorems in CPL and FOL (Class notes) |
Notes | Sruti: Scribe |
20.03.2024 | Modal logic: An introduction (Class notes: slides) |
27.03.2024 | Bisimulation (Class notes) |
Notes | Arnab: Scribe |
01.04.2024 | Modal logic vs. first order logic (Class notes) |
03.04.2024 | On frame characterizations (Class notes) |
Notes | Kuntal and Vamsi: Scribe |
08.04.2024 | Consequence relations (Class notes) |
10.04.2024 | Completeness (Class notes) |
Notes | Debanjan and Sruti: Scribe |
13.04.2024 | Tutorial |
15.04.2024 | Decidability (Class notes) |
Notes | Arpan: Scribe |
17.04.2024 | Project Presentations |
Basudeb: Write-up Slides Debanjan: Write-up Slides Kuntal: Write-up Slides Rashmi: Slides Ritam: Write-up Sruti: Write-up Slides Vamsi: Slides |
Homeworks/Handouts
Homework 1
Deadline for submission: February 21, 2024.Homework 2
Deadline for submission: March 31, 2024.Homework 3
Deadline for submission: April 23, 2024.