You are here

Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography

Yves Nievergelt
Publisher: 
Birkhäuser
Publication Date: 
2002
Number of Pages: 
415
Format: 
Hardcover
Price: 
69.95
ISBN: 
0-8176-4249-8
Category: 
Textbook
[Reviewed by
Tom Schulte
, on
03/2/2006
]

This text uses set theory as a basis for exploring fundamental approaches to boolean algebraic logic, logic and deductive reasoning through propositional and predicate calculus, number theory, coding, arithmetic, and more. The author moves efficiently, for instance, from setting up integer arithmetic from the axioms of set theory on to Gödel's Incompleteness Theorem. This type of coverage is achieved through consistently laid out sections containing a handful of theorems, nearly all of which are proved, along with a smaller number of definitions and examples. A page of exercises concludes each section. The book provides no answers to any of the exercises.

This book is subtitled "Applications to Computer Science and Cryptography". Most of the applications are only thinly glossed over. This includes bar codes, molecular topology, and circuit design. However, a few applications topics are dealt with in detail. Vintage cryptography enthusiasts will enjoy the seven-page section on the family of ENIGMA machines. This mostly covers recreating the mathematical steps taken to break the ENIGMA design starting from Polish efforts before World War II. There is also an exploration of the RSA algorithm, which includes the algorithm itself, a proof of its correctness, and an example of encrypting using RSA.

Being both concisely written and rather broad in scope, this book is an excellent resource to clear up issues on fundamentals from a variety of topics. The basic principles of group theory, probability, mathematical functions and more lie cheek by jowl in a clear and easy to follow manner. The chapter "Decidability and Completeness" is particularly worth mulling over with its comparisons of various approaches to incompleteness and a method for automated theorem proving. Further, this text includes a chapter covering the fundamentals of graph theory. This includes path-connected graphs, mathematical trees, bipartite graphs, and more.


Tom Schulte (http://www.oakland.edu/~tgschult/) is over the half-way point working on a graduate program in Industrial Applied Mathematics at Oakland University (http://www.oakland.edu).

 

Preface * Outline * Part A. Theory * 0. Boolean Algebraic Logic * 1. Logic and Deductive Reasoning * 2. Set Theory * 3. Induction, Recursion, Arithmetic, Cardinality * 4. Decidability and Completeness * Part B. Applications * 5. Number Theory and Codes * 6. Ciphers, Combinatorics, and Probabilities * 7. Graph Theory * Bibliography * Index