Title:
Proofs and algorithms : an introduction to logic and computability / Gilles Dowek.
Undergraduate topics in computer science,
Undergraduate Topics in Computer Science.
Main Entry:
Dowek, Gilles.
Publisher:
Springer,
Publication Date:
c2011.
Publication Place:
London ; New York :
ISBN:
9780857291202
0857291203
Subject:
Logic, Symbolic and mathematical.
Algorithms.
Series:
Undergraduate topics in computer science,
Undergraduate Topics in Computer Science.
Contents:
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 -- Gèodel'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.
Cover Image:
Log in
Help
