Jump to content

Logic for Computer Science

50% developed
From Wikibooks, open books for an open world

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 Contents

[edit | edit source]

References

[edit | edit source]

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