CS 474 - Logic in Computer Science (Spring 2023)

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 27
[Intro Slides]

Motivation, Introduction to Logic, The place of logic in Computer Science, Themes covered in the course, Logic in the AI era, Administrivia

August 29

Informal introduction to the classical logic results covered in this course: first order logic; syntax of FO logic for any signature, informal semantics over first-order structures, FO over a single structure, over a class of structures, and over all structures, theories of a structure and a class of structures, theory of a set of axioms; main results

LCS (Logic in CS notes, see resources page for link); Chapter 1

Resource references:

See Resource page for links to resources.
[WT] - Languages, Automata, and Logic by Wolfgang Thomas
[MS] - Notes by Madhavan and Suresh
[LCS] - Logic in Computer Science, by P. Madhusudan and Mahesh Viswanathan
[Vardi-LectureNotes] - Notes by Vardi
[CC] - Calculus of Computation by Manna and Bradley
[LL] - Elements of Finite Model Theory by Leonid Libkin