- Spring 2017 offering of this class by Madhusudan Parthasarthy.
- A Mathematical Introduction to Logic, by H.B. Enderton.

- Instructor: Mahesh Viswanathan
- TA: Lucas Pena
- Lectures:

Tu/Th 12:30pm to 1:45pm in 1103 Siebel - Office Hours:

Tu/Th 1:45pm to 3:00pm (Mahesh in 3232 SC)

W 2:00pm to 3:00pm (Lucas in 2111 SC) - Discussion Group: Piazza

This course provides an introduction to mathematical logic from the perspective of computer science, emphasizing decidable fragments of logic and decision procedures.

__Course Objectives.__ The goal of the course is to prepare students for using logic as a formal tool in computer science. By the end of course, students will be exposed to different fragments of logics and decision procedures for them, and connections between logic and automata theory and between computational complexity and descriptive complexity. They will have seen tools and techniques that exploit logic to come up with algorithms to solve problems, and establish lower bounds. Students will be informed of some of the major open problems in the field and current efforts to solve them.

__Course Contents.__ Motivated by applications in artificial intelligence, databases, formal methods and theoretical computer science, the course will roughly cover the following topics: syntax, semantics and proof theory of propositional logic, sat-solvers, syntax of first-order, the resolution proof system, syntax of second-order logic, connections between monadic second order logic and regular languages (word and tree, finite and infinite), tree-width and Courcelle's theorem with applications to parametric complexity, finite model theory and descriptive complexity, games and inexpressiveness.

__Prerequisites.__ This course is aimed at advanced undergraduate and graduate students interested in logic and theoretical computer science. Familiarity with basic logic and discrete mathematics (CS 173), basic algorithms and theory of computation (CS 374), and mathematical maturity will be expected.

__Graded Work.__ There will one homework every 2 weeks (about 5 in total), and one final exam. The homework assignments and the final exam will be worth 50% each.

__Collaboration.__ Limited collaboration is allowed for assignments, unless otherwise specified: you can discuss the problems with others in the class, and can submit solutions in groups of upto 3 students. In particular, you should not look at solutions written up by other groups. All collaboration should be declared.

__Website Design.__ Thanks to Manoj Prabhakaran.

- Lecture 01 [Aug 28]: Propositional logic syntax and semantics.
**[notes]** - Lecture 02 [Aug 30]: Proof systems for propositional logic. Sections 1 and 2 of
**[notes]** - Lecture 03 [Sep 04]: Compactness Theorem. Section 3 of
**[notes]** - [Sep 06]:
**No lecture.**Mahesh is traveling. Homework 1 due 9/13:**[PDF, Tex]**. - Lecture 04 [Sep 11]: Recap of recursive enumerability and decidability.
**Notes coming soon** - Lecture 05 [Sep 13]: Introduction to Complexity Theory. Sections 1 to 3 of
**[notes]** - Lecture 06 [Sep 18]: P, NP, and coNP. Sections 3 and 4 of
**[notes]** - Lecture 07 [Sep 20]: Craig's Interpolation Theorem and Proof Complexity.
- Lecture 08 [Sep 25]: First order logic.