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 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