Logic for Computer Science

Logic for Computer Scientists 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 Chapter 1: Propositional Logic 100% Basic concepts in logic Deductive systems ("Natural Deduction") Propositional Resolution Complexity of various problems Chapter 2: First-Order Logic (FO) 100% Syntax and semantics A deduction calculus Gödel's completeness theorem Chapter 3: Around and about FO 25% Fragments of FO Characteristics of FO Higher-Order Logics Chapter 4: Querying I: Expressive Power 50% Query and definability Results for FO on popular structures Results for other logics and structures Chapter 5: Querying II: Games 50% Ehrenfeucht's games and Fraisse's theorem Ehrenfeucht-Fraisse method Higher order games and 0-1 Laws Chapter 6: Reasoning 00% Deduction Non-monotonic reasoning Uncertain and Case-based reasoning Chapter 7: Some Applications 50% 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 Mathematical logic University level mathematics books L 50% es:Aprende Lógica it:Logica pt:Lógica