You are here

Handbook of Logic and Proof Techniques for Computer Science

Steven G. Krantz
Birkhäuser and Springer Verlag
Publication Date: 
Number of Pages: 
[Reviewed by
Daniel Bilar
, on

Penned by the indefatigable Steven G. Krantz (Professor of Mathematics , Washinton University in St. Louis) , this concise book is offered as an accessible reference on mathematical logic for the professional computer scientist. It is a sweeping sketch of ideas from logic, presented in a somewhat unorthodox order. Starting off with the basics of notation, first order logic, semantics, syntax, and set theory; moving on to more advanced topics that are by and large self-contained; among them Gödel’s theorems, the continuum hypothesis, proof techniques , number systems and their constructions, proof theory, category theory, NP-completeness; culminating in Boolean algebra and the word problem.

Of special interest to computer scientists are his insightful chapters on recursive functions, axiomatics, decidability, model theory and complexity theory with NP-complete problem examples. Since Krantz did not intend to write a textbook, the handbook contains only a handful of proofs. However, he does provide an useful index, logic notation and term glossary, a bibliography thoroughly referenced in the text, and an extensive guide to the literature.

His exposition is pithy, consistent, and effective: Definitions are presented, discussed and illustrated with straightforward examples. Each chapter is preceded by a smattering of whimsical quotations ("If logic is the hygiene of the mathematician, it is not his source of food") which hint at the playful delight Krantz took in putting this polished little jewel together. Synoptic commentary annotating the 150+ items in the literature guide would be a welcome addition to the next edition.

Daniel Bilar has held visiting faculty appointments at Oberlin and Colby. He gets excited about teaching students and network security: risk analysis of networks, malicious code analysis and computer forensics. This interest was sparked at the Institute for Security and Technology Studies which conducts counter-terrorism technology research for the Department of Homeland Security. He has degrees from Brown University (BA, Computer Science), Cornell University (MEng, Operations Research and Industrial Engineering) and Dartmouth College (PhD, Engineering Sciences).


Notation and First-Order Logic

Semantics and Syntax

Axiomatics and Formalism in Mathematics

The Axioms of Set Theory

Elementary Set Theory

Recursive Functions

The Number Systems

Methods of Mathematical Proof

The Axiom of Choice

Proof Theory

Category Theory

Complexity Theory

Boolean Algebra

The Word Problem

List of Notation and Logic

Glossary Terms from Mathematical and Sentential Logic

A Guide to the Literature