You are here

Boolean Functions: Theory, Algorithms, and Applications

Yves Crama and Peter L. Hammer
Cambridge University Press
Publication Date: 
Number of Pages: 
Encyclopedia of Mathematics and Its Applications 142
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Russell Jay Hendel
, on

What a delightful, current, comprehensive, clearly written, technically precise book!

Volume 142 of the Encyclopedia of Mathematics and Its Applications could serve as a) a text for a senior undergraduate course, b) a text for a one or two-semester advanced graduate course, c) a reference work and a d) source book for open or current problems or topics. While I would not use it as the only textbook in an introductory logic course, I would definitely supplement such a course with the rich set of applications presented in this book, many of which are easily understood but not found in standard textbooks.

Allow me to lightly sketch some of the book’s noteworthy features.

Style: The book has all the elements of a friendly style: Technical definitions are accompanied, as appropriate, by historical comments, heuristic descriptions, diagrams, applications and algorithms. It is, for example, a pleasure to see in a work written in the 21st century, actual citations from George Boole’s founding treatise.

Applications: Besides the usual applications to logic and electric circuits, the book covers applications of boolean algebras to database theory, voting theory, reliability theory, graph combinatorics, as well as artificial intelligence.

Specialization: Besides the general theory — boolean functions, equations, prime implicants, minimal forms and duality theory — the book covers specialized topics including quadratic, horn, orthogonal, read-once, regular and threshold functions. The book also covers advanced topics including defining classes of functions by functional equations, partially defined functions and pseudo functions. The appendices cover graphs and complexity including a statement and proof of Cook’s theorem.

Bibliography: The bibliography is comprehensive — 941 citations — covering a wide spectrum of journals, applications and publication vehicles.

Software and algorithms: Several software tools are listed and/or discussed, including JBool. Throughout the text and bibliography the latest and fastest algorithms are discussed. I found several papers and free downloadable software on rule inference particularly useful.

Problems: Each of the 13 chapters has 1–2 dozen problems. The problems span the gamut, including routine problems, problems connected with published papers as well as open problems. The problems deal with boolean algebra proper, with its applications as well as with issues of computational complexity.

Point of view: The authors carefully define the point of view of their work. They focus on (1) expressions vs. truth tables and circuits, (2) 2-element boolean algebras and (3) a combinatorial algorithmic approach vs. an algebraic or logical approach. Throughout the book, citations to alternate points of view are presented enhancing the book’s breadth.

Russell Jay Hendel, RHendel@Towson.Edu, holds a Ph.D. in theoretical mathematics and an Associateship from the Society of Actuaries. He teaches at Towson University. His interests include discrete number theory, applications of technology to education, problem writing, actuarial science and the interaction between mathematics, art and poetry.

Part I. Foundations: 1. Fundamental concepts and applications
2. Boolean equations
3. Prime implicants and minimal DNFs Peter L. Hammer and Alexander Kogan
4. Duality theory Yves Crama and Kazuhisa Makino
Part II. Special Classes: 5. Quadratic functions Bruno Simeone
6. Horn functions Endre Boros
7. Orthogonal forms and shellability
8. Regular functions
9. Threshold functions
10. Read-once functions Martin C. Golumbic and Vladimir Gurvich
11. Characterizations of special classes by functional equations Lisa Hellerstein
Part III. Generalizations: 12. Partially defined Boolean functions Toshihide Ibaraki
13. Pseudo-Boolean functions
Appendix A. Graphs and hypergraphs
Appendix B. Algorithmic complexity
Appendix C. JBool: a software tool Claude Benzaken and Nadia Brauner.