## Introduction to Logic

Graduate Core Course in Computer Science
(August-December 2005)

 Instructor: Paritosh K. Pandya Room A249 Phone: (tifr) Ext. 2551 Email:  pandya@tifr.res.in Time: Tuesday & Thursday: 11:30 to 13:00  Room No. A 212 Course Page http://www.tcs.tifr.res.in/~pandya/logic05/index.html Yahoo Group

Not Yet!!

### Topics:

• Mathematical Preliminaries: Set, Relations, Partial Orders, Well-ordered sets and principle of Noetherian induction, Structural induction, Cardinality of Sets.
• Propositional Calculus:
Syntax and semantics
Hintikka's Lemma and Model Existence Theorem
Model theory: Compactness, Lowenheim-skolem theorem, normal forms, functional completeness
Semantic Tablaeux: soundness, completeness and decidability
Hilbert style proof system, Sequent calculus
• First-order logic:
Syntax and semantics
Hintikka's Lemma and model existence theorem
First-order semantic Tableaux: soundness and completeness
Hilbert style proof system for FOL, deduction theorem, Sequent calculus
Prenex normal form, Resolution
• First-order logic with equality:
Canonical models, Model existence theorem
Axiomatisation and completeness
Upward and downward Lowenheim-Skolem Theorems
• *** OMITTED Scope of First-order Logic:
Axiomatisation of some mathematical structures
ZFC set theory in FOL, Limitations of FOL
• Decision procedures: quantifier-free formulae with uninterpreted functions with equality, theory of lists and arrays, First order real-arithmetic,  Fourier-Motzkin Variable Elimination
• Basics of Modal Logics: Kripke semantics, Correspondances, Axiomatisation: systems K, KT4, S5, completeness, decidability using filteration.

• Introduction to Modal Logics
• Decision Procedures for Some Logical Theories
• Second order logic
•      Second order logic, Infinitary logic.
Nonaxiomatisability of Second-order logic ,
Tractanbrot's theorem
• Godel's Incompleteness Theorem

### Text Books

• J.H. Gallier: Logic for computer science, John Wiley and Sons, 1987.
• M. Fitting: First-order logic and automated theorem proving, Springer-Verlag, 1990.
• H.D. Ebbinghaus, J. Flum, W. Thomas: Mathematical Logic, Springer-Verlag, 1984.
• ### Assignments

Assignments 1 to 4 (To be submitted by November 15th)
Assignment 5 (manoj topics)