Evaluation:
Assignments 25%, midsemester exam 25%, final exam 50%
Copying is fatal.
Teaching assistants: Debdyuti Banerjee, Ranadeep Biswas
Textbook:
There are many, but we won't follow any one book.
Initially we will follow these notes: Introduction to Logic
Supplementary Reading:
An Introduction to First-Order Logic by Jon Barwise, in Handbook of Mathematical Logic, North-Halland (1977).
Elements of Finite Model Theory by Leonid Libkin
Mathematical Logic for Computer Science by Mordechai Ben-Ari
Applied Automata Theory by Wolfgang Thomas (Chapters 0,1)
How to submit assignments:
Submit all assignments on Moodle.
Only electronic submissions will be evaluated.
You can submit pdf (either generated from a word processor or scanned) or text (use notational conventions similar to the lecture summaries below).
Use your CMI login-id to name your submitted file. For instance madhavan.pdf or madhavan.txt
Propositional and first-order logic: soundness, completeness, compactness, … (Chapters 1 and 4 from the notes Introduction to Logic)
Some finite model theory
First order arithmetic: decidable fragments, incompleteness
Monadic Second Order logic (MSO) over sequences
Introduction to logic, syntax and semantics of propositional logic, validity and satisfiability.
Propositional logic: Hilbert-style axiomatization, soundness, derivability under additional assumptions.
Propositional logic: deduction theorem and applications, maximal consistent sets, completeness.
Propositional logic: strong completeness, compactness, finite satisfiability.
Propositional logic: finite satisfiability.
First order logic: introductory examples.
First order logic: syntax and semantics.
First order logic: expressing properties of structures.
First order logic: substitution, reducing satisfiability to propositional logic.
First order logic: reducing FO satisfiability to propositional logic.
First order logic: finite satisfiability, compactness, Lowenheim-Skolem theorems, expressing finiteness and infiniteness of structures.
First order logic: A sound and complete Hilbert-style axiom system, introduction to sequent calculus.
First order logic: Sequent calculus.
First order logic: Model theory -- elementary and delta-elementary classes, elementary equivalence, examples.
Discussion of mid-semester exam. Expressiveness of first order logic: introductory remarks.
First order logic: Model theory -- elementary and delta-elementary classes, elementary equivalence, examples.
First order logic: Model theory -- elementary and delta-elementary classes, elementary equivalence, examples.
First order logic: Model theory -- elementary and delta-elementary classes, elementary equivalence, examples.
First order logic: Validity is undecidable.
Monadic Second Order Logic: introduction to MSO over finite words.
Monadic Second Order Logic: examples, constructions on DFAs and NFAs.
Monadic Second Order Logic: Buchi-Elgot-Trakhtenbrot theorem.
MSO over state sequences, linear time temporal logic.
FO, star-free and LTL, model-checking, branching time.
CTL model-checking