Handbook of logic and proof techniques for computer science

Publication date 17 February 2002

Boolean algebra category theory complexity theory computer science logic elementary set theory first-order logic number systems proof techniques recursive functions word problem

Mathematics Subject Classification ID

General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations (03-00) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science (68-00) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01)

Review text

This is really what it promises to be, i.e. a good handbook (a book at hand): supple, self-contained, providing the necessary and sufficient working resources (definitions, examples, complete references) for computer scientists, engineering or systems scientists, and mathematicians. All the key ideas in basic logic and proof techniques, including introductions to critical advanced topics are contained. A thorough index, a glossary, a lexicon of notation, a guide to the literature, and an extensive bibliography constitute also very useful tools. The orientation of the logic and reasoning technique contents towards computer scientists is truthfully conforming to the handbook title. The same is strictly true concerning the titles of the 14 contained chapters, surveyed in what follows for getting a clearer idea on the whole landscape: Chapter 1: Notation and first-order logic; Chapter 2: Semantics and syntax (first-order logic); Chapter 3: Axiomatics and formalism in mathematics (models, consistency, Gödel's incompleteness theorem, decidability, independence); Chapter 4: The axioms of set theory; Chapter 5: Elementary set theory (relations, functions, cardinals, fuzzy set theory, lambda-calculus); Chapter 6: Recursive functions; Chapter 7: The number systems; Chapter 8: Methods of mathematical proof; Chapter 9: The axiom of choice; Chapter 10: Proof theory (cut elimination, resolution, interpolation, finite type, Beth's definability theorem); Chapter 11: Category theory; Chapter 12: Complexity theory (polynomial, exponential, class P, problems in class NP, NP-completeness, Cook's theorem, examples of NP-complete problems, P/NP questions); Chapter 13: Boolean algebra; Chapter 14: The word problem. To summarize, this (hand)book not only contains what corresponds to its title, but is more than you expect: the rigour of usefulness and conciseness exceeds or is equal to the pleasure of reading it.

Recommendations

Cited in

(11)

This page was built for publication: Handbook of logic and proof techniques for computer science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2771587)