Boolean Functions: Theory, Algorithms, and Applications

Written by some of the most prominent experts in the field, this book provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions. It presents the fundamental elements of the theory (Boolean equations and satisfiability problems, prime implicants and associated representations, dualization, decomposition), an in-depth study of special classes of Boolean functions (quadratic, Horn, shellable, regular, threshold, read-once), and two fruitful generalizations of the concept of Boolean functions (partially defined and pseudo-Boolean functions). The book contains applications of Boolean methods in all areas where they play a significant role, including propositional logic, combinatorics, graph and hypergraph theory, complexity theory, integer programming, combinatorial optimization, game theory, reliability theory, electrical and computer engineering and artificial intelligence. Its unique depth and breadth and its emphasis on algorithms and applications will make this a key reference for researchers and graduate students in discrete mathematics, operations research, computer science, engineering, and economics.

Part I. Foundations: 1. Fundamental concepts and applications; 2. Boolean equations; 3. Prime implicants and minimal DNFs; 4. Duality theory; 5. Decomposition; Part II. Special classes: 6. Quadratic functions; 7. Horn functions; 8. Orthogonal forms and shellability; 9. Regular functions; 10. Threshold functions; 11. Convex functions; 12. Read-once functions; 13. Decomposition, approximation and other special classes; 14. Equational characterizations of special classes; Part III. Generalizations: 15. Partially defined Boolean functions; 16. Pseudo-Boolean functions; Appendix 1. Software section; Appendix 2. Algorithmic complexity.