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

 Chapter 1: Propositional Logic Basic concepts in logic Deductive systems ("Natural Deduction") Propositional Resolution Complexity of various problems Chapter 2: First-Order Logic (FO) Syntax and semantics A deduction calculus Gödel's completeness theorem Chapter 3: Around and about FO Fragments of FO Characteristics of FO Higher-Order Logics Chapter 4: Querying I: Expressive Power Query and definability Results for FO on popular structures Results for other logics and structures Chapter 5: Querying II: Games Ehrenfeucht's games and Fraisse's theorem Ehrenfeucht-Fraisse method Higher order games and 0-1 Laws Chapter 6: Reasoning Deduction Non-monotonic reasoning Uncertain and Case-based reasoning Chapter 7: Some Applications Database theory Complexity theory Expert systems

## References

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