Logic for Computer Science
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 secondorder logic)
 Database Systems (SQL; roughly predicate/firstorder logic)
 Computeraided 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 firstorder logic, the course presents the foundations of finite model theory and descriptive complexity. Other topics, including logic programming, nonmonotonic 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]

References[edit]
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://wwwcse.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