Boolean Functions: Theory, Algorithms, and Applications
, by Yves Crama , Peter L. Hammer- ISBN: 9780521847513 | 0521847516
- Cover: Hardcover
- Copyright: 5/16/2011
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.