15325

,

an introduction to logic and computability

Gilles Dowek

Springer

xii, 155 p. , ill

Undergraduate topics in computer science,1863-7310

Part. 1. Proofs: -- 1. Predicate logic. --Inductive definitions -- Languages -- The languages of predicate logic -- Proofs -- Examples of theories -- Variations on the principle of the excluded middle -- 2. Models. -- The notion of a model -- The Soundness Theorem -- The Completeness Theorem -- Other applications of the notion of model -- Part 2. Algorithms: -- 3. Computable functions. -- Computability over lists and trees -- Eliminating recursion -- Programs -- 4. Computation as a sequence of small steps. -- Rewriting -- The Lambda-Calculus -- Turing Machines -- Part 3. Proofs and algorithms: -- 5. Churchʹs Theorem. -- The notion of reduction -- Representing programs -- Churchʹs Theorem -- Semi-decidabilty -- Geodelʹs First Incompleteness Theorem -- 6. Automated theorem proving. -- Sequent Calculus -- Proof search in the sequent Calculus without cuts -- 7. Decidable theories -- 8. Constructivity -- 9. Epilogue.

QA

9

.D68

2011

9780857291202 ,

Includes bibliographical references (p. 151) and index.

c2011