| Contributors | p. xiii |
| Preface | p. xv |
| Acknowledgments | p. xix |
| Notations | p. xxi |
| Foundations | |
| Fundamental concepts and applications | p. 3 |
| Boolean functions: Definitions and examples | p. 3 |
| Boolean expressions | p. 8 |
| Duality | p. 13 |
| Normal forms | p. 14 |
| Transforming an arbitrary expression into a DNF | p. 19 |
| Orthogonal DNFs and number of true points | p. 22 |
| Implicants and prime implicants | p. 24 |
| Restrictions of functions, essential variables | p. 28 |
| Geometric interpretation | p. 31 |
| Monotone Boolean functions | p. 33 |
| Recognition of functional and DNF properties | p. 40 |
| Other representations of Boolean functions | p. 44 |
| Applications | p. 49 |
| Exercises | p. 65 |
| Boolean equations | p. 67 |
| Definitions and applications | p. 67 |
| The complexity of Boolean equations: Cook's theorem | p. 72 |
| On the role of DNF equations " | p. 74 |
| What does it mean to "solve a Boolean equation"? | p. 78 |
| Branching procedures | p. 80 |
| Variable elimination procedures | p. 87 |
| The consensus procedure | p. 92 |
| Mathematical programming approaches | p. 95 |
| Recent trends and algorithmic performance | p. 103 |
| More on the complexity of Boolean equations | p. 104 |
| Generalizations of consistency testing | p. 111 |
| Exercises | p. 121 |
| Prime implicants and minimal DNFs | p. 123 |
| Prime implicants | p. 123 |
| Generation of all prime implicants | p. 128 |
| Logic minimization | p. 141 |
| Extremal and typical parameter values | p. 159 |
| Exercises | p. 165 |
| Duality theory | p. 167 |
| Basic properties and applications | p. 167 |
| Duality properties of positive functions | p. 176 |
| Algorithmic aspects: The general case | p. 183 |
| Algorithmic aspects: Positive functions | p. 189 |
| Exercises | p. 198 |
| Special Classes | |
| Quadratic functions | p. 203 |
| Basic definitions and properties | p. 203 |
| Why are, quadratic Boolean functions important? | p. 205 |
| Special classes of quadratic functions | p. 207 |
| Quadratic Boolean functions and graphs | p. 209 |
| Reducibility of combinatorial problems to quadratic equations | p. 218 |
| Efficient graph-theoretic algorithms for quadratic equations | p. 230 |
| Quadratic equations: Special topics | p. 243 |
| Prime implicants and irredundant forms | p. 250 |
| Dualization of quadratic functions (Contributed by Oya Ekin Karasan) | p. 263 |
| Exercises | p. 266 |
| Horn functions | p. 269 |
| Basic definitions and properties | p. 269 |
| Applications of Horn functions | p. 273 |
| False points of Horn functions | p. 277 |
| Horn equations | p. 281 |
| Prime implicants of Horn functions | p. 286 |
| Properties of the set of prime implicants | p. 292 |
| Minimization of Horn DNFs | p. 297 |
| Duaiization of Horn functions | p. 306 |
| Special classes | p. 309 |
| Generalizations | p. 314 |
| Exercises | p. 321 |
| Orthogonal forms and sheUability | p. 326 |
| Computation of orthogonal DNFs | p. 326 |
| Shellings and sheUability | p. 330 |
| Duaiization of shellable DNFs | p. 336 |
| The lexico-exchange property | p. 338 |
| Shellable quadratic DNFs and graphs | p. 346 |
| Applications | p. 348 |
| Exercises | p. 349 |
| Regular functions | p. 351 |
| Relative strength of variables and regularity | p. 351 |
| Basic properties | p. 355 |
| Regularity and left-shifts | p. 362 |
| Recognition of regular functions | p. 365 |
| Duaiization of regular functions | p. 369 |
| Regular set covering problems | p. 377 |
| Regular minorants and majorants | p. 380 |
| Higher-order monotonicity | p. 391 |
| Generalizations of regularity | p. 397 |
| Exercises | p. 401 |
| Threshold functions | p. 404 |
| Definitions and applications | p. 404 |
| Basic properties of threshold functions | p. 408 |
| Characterizations of threshold functions | p. 413 |
| Recognition of threshold functions | p. 417 |
| Prime implicants of threshold functions | p. 423 |
| Chow parameters of threshold functions | p. 428 |
| Threshold graphs | p. 438 |
| Exercises | p. 444 |
| Read-once functions | p. 448 |
| Introduction | p. 448 |
| Dual implicants | p. 450 |
| Characterizing read-once functions | p. 456 |
| The properties of P4-free graphs and cographs | p. 463 |
| Recognizing read-once functions | p. 466 |
| Learning read-once functions | p. 473 |
| Related topics and applications of read-once functions | p. 476 |
| Historical notes | p. 480 |
| Exercises | p. 481 |
| Characterizations of special classes by functional, equations | p. 487 |
| Characterizations of positive functions | p. 487 |
| Functional equations | p. 488 |
| Characterizations of particular classes | p. 491 |
| Conditions for characterization | p. 495 |
| Finite characterizations by functional equations | p. 500 |
| Exercises | p. 506 |
| Generalizations | |
| Partially defined Boolean functions | p. 511 |
| Introduction | p. 511 |
| Extensions of pdBfs and their representations | p. 514 |
| Extensions within given function classes | p. 531 |
| Best-fit extensions of pdBfs containing errors | p. 547 |
| Extensions of pdBfs with missing bits | p. 551 |
| Minimization with don't cares | p. 558 |
| Conclusion | p. 561 |
| Exercises | p. 562 |
| Pseudo-Boolean functions | p. 564 |
| Definitions and examples | p. 564 |
| Representations | p. 570 |
| Extensions of pseudo-Boolean functions | p. 578 |
| Pseudo-Boolean optimization | p. 585 |
| Approximations | p. 593 |
| Special classes of pseudo-Boolean functions | p. 593 |
| Exercises | p. 607 |
| Graphs and hypergraphs | p. 609 |
| Undirected graphs | p. 609 |
| Directed graphs | p. 612 |
| Hypergraphs | p. 614 |
| Algorithmic complexity | p. 615 |
| Decision problems | p. 615 |
| Algorithms | p. 617 |
| Running time, polynomial-time algorithms, and the class P | p. 618 |
| The class NP | p. 619 |
| Polynomial-time reductions and NP-completeness | p. 620 |
| The class co-NP | p. 621 |
| Cook's theorem | p. 622 |
| Complexity of list-generation and counting algorithms | p. 624 |
| JBool: A software tool | p. 627 |
| Introduction | p. 627 |
| Work interface | p. 628 |
| Creating a Boolean function | p. 629 |
| Editing a function | p. 632 |
| Operations on Boolean functions | p. 633 |
| Bibliography | p. 635 |
| Index | p. 677 |
| Table of Contents provided by Ingram. All Rights Reserved. |
