CS 498MP - Logic in Computer Science (Spring 2017)

CS 498MP - Logic in Computer Science (Spring 2017)

Madhusudan Parthasarathy (aka Madhu)

Tue and Thu 9:30am-10:45pm, 1304 Siebel Center

Instructor
Madhusudan Parthasarathy
Lectures
Lecture Schedule
Homework
Homework Schedule
Resources
Papers, textbook chapters, tools
Piazza
Piazza Website
(access code: frege)
Moodle
Primarily for grades
Midterm Exam
Midterm Exam
Final Exam
Final Exam

About
This course will provide an introduction to mathematical logic from the perspective of computer science, emphasizing decidable fragments of logic, connections to computability and complexity, and decision algorithms. The topics covered will be motivated by applications in artificial intelligence, databases, formal methods, formal verification and theoretical computer science. The goal of the course is to prepare students for using logic as a formal tool in computer science. The course will roughly cover the following topics (in this order): syntax, semantics and proof theory of propositional logic, sat-solvers, syntax and semantics of first-order logic, proof systems for first order logic, syntax/semantics of second-order logic, decidable fragments of various first-order theories and tools to decide them effectively, 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 proving inexpressiveness.

We will use no textbook. All material will be available online.

Initial Logistics
WARNING: these pages are still tentative. Don't trust the details until the first few lectures are done. As soon as possible, you should get onto Piazza and Moodle, the two tools we will be using throughout the term. Instructions on how to sign up will appear soon here.

When you sign up for Piazza, ignore any warnings from the Piazza sign-up about requiring a U. Illinois email address: you should be able to register using any email address you like, including an anonymous email id.

Very little appears directly on this page. Routine announcements are posted on Piazza, Moodle, or the notes from each lecture. Check out the menu above for the Lectures page and information on other topics such as course policies, homeworks, and exams.