Proofs and algorithms : an introduction to logic and computability /
Dowek, Gilles.
Proofs and algorithms : an introduction to logic and computability / Gilles Dowek. - London ; New York : Springer, 2011. - xii, 155 p. : ill. ; 24 cm. - Undergraduate topics in computer science, 1863-7310 . - Undergraduate topics in computer science. .
Includes bibliographical references (p. 151) and index.
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ödel'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.
9780857291202 0857291203
2011282450
015659649 Uk
Logic, Symbolic and mathematical.
Algorithms.
QA9 / .D68 2011
004.015113
Proofs and algorithms : an introduction to logic and computability / Gilles Dowek. - London ; New York : Springer, 2011. - xii, 155 p. : ill. ; 24 cm. - Undergraduate topics in computer science, 1863-7310 . - Undergraduate topics in computer science. .
Includes bibliographical references (p. 151) and index.
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ödel'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.
9780857291202 0857291203
2011282450
015659649 Uk
Logic, Symbolic and mathematical.
Algorithms.
QA9 / .D68 2011
004.015113