Last modified on 21 September 2010, at 20:00

Logic for Computer Science

This book discusses logic as a tool for computer science; a field that uses logic at all levels. It provides a survey of mathematical logic and its various applications. Some areas where it is particularly important include:

Digital circuit design
Complexity theory (NP equivalent to Existential second-order logic)
Database Systems (SQL; roughly predicate/first-order logic)
Computer-aided verification (Temporal logic & model checking)
Programming languages (lambda calculus)
AI, expert systems, inference engines
Distributed Systems
Logic Programming
Computer Security

After covering basic material of propositional logic and first-order logic, the course presents the foundations of finite model theory and descriptive complexity. Other topics, including logic programming, non-monotonic reasoning, temporal logic, and reasoning about knowledge and belief, are surveyed as time allows. These notes were taken by student scribes.

Table of ContentsEdit

ReferencesEdit

You may also find the following references useful

  • Mathematical Logic. H.-D. Ebbinghaus, J. Flum, and W. Thomas
  • Foundations of Databases. Abiteboul, Hull, Vianu. Available here: http://www-cse.ucsd.edu/users/vianu/BOOK/book.html
  • Computational Complexity. Christos H. Papadimitrou.
  • Elements of Finite Model Theory. Leonid Libkin.
  • Finite Model Theory and Its Applications. Grädel, Kolaitis, Libkin, Marx, Spencer, Vardi, Venema, Weinstein
  • Gödels Proof. Ernest Nagel and James R. Newman
  • Language, Proof, and Logic. John Barwise and John Echtermendy
  • A Profile of Mathematical Logic. Howard DeLong