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

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

Lecture Schedule

Prerequisite Resources

Preliminary Material
Preliminary logic primer, P. Madhusudan (for CS173)
Notes on induction on natural numbers, P. Madhusudan (for CS173)
More notes on induction, Chandra Chekuri (for CS173)

Introduction and Motivation

August 25
[Intro Slides]

Motivation, Introduction and Administrivia

Aug 27, Sep 1

First Order Logic: Over a single structure, over a class of structures, and over all structures

Logic in CS; Chapter 1
Sep 3

Background: Theory of computation, Induction

Countable and uncountable sets; Turing machines; decidability; undecidability of the halting problem (and proof); Rice's theorem; Induction; "strong" and "weak" induction; induction over expressions generated by a grammar. Lecture notes by Sariel and Madhu: Turing machines, Undecidability, halting, and diagonalization

Resource references:

See Resource page for links to resources.
[MS] - Notes by Madhavan and Suresh
[LCS] - Logic in Computer Science, by Madhusudan
[Vardi-LectureNotes] - Notes by Vardi
[CC] - Calculus of Computation by Manna and Bradley