Boolean Functions : Theory, Algorithms, and Applications.

Description

Cover Half-title Title Copyright Dedication Contents Contributors Preface Acknowledgments Notations Part I: Foundations 1 Fundamental concepts and applications 1.1 Boolean functions: Definitions and examples 1.2 Boolean expressions 1.3 Duality 1.4 Normal forms 1.5 Transforming an arbitrary expression into a DNF 1.6 Orthogonal DNFs and number of true points 1.7 Implicants and prime implicants 1.8 Restrictions of functions, essential variables 1.9 Geometric interpretation 1.10 Monotone Boolean functions 1.10.1 Definitions and examples 1.10.2 DNFs and prime implicants of positive functions 1.10.3 Minimal true points and maximal false points 1.11 Recognition of functional and DNF properties 1.12 Other representations of Boolean functions 1.12.1 Representations over GF(2) 1.12.2 Representations over the reals 1.12.3 Binary decision diagrams and decision trees 1.13 Applications 1.13.1 Propositional logic and artificial intelligence 1.13.2 Electrical and computer engineering 1.13.3 Game theory 1.13.4 Reliability theory 1.13.5 Combinatorics 1.13.6 Integer programming Question for thought 1.14 Exercises 2 Boolean equations 2.1 Definitions and applications 2.2 The complexity of Boolean equations: Cook's theorem 2.3 On the role of DNF equations 2.4 What does it mean to ``solve a Boolean equation''? 2.5 Branching procedures 2.5.1 Branching rules 2.5.2 Preprocessing Rewriting rules Davis-Putnam rules Heuristics Relaxation schemes 2.6 Variable elimination procedures 2.7 The consensus procedure 2.8 Mathematical programming approaches 2.8.1 Integer linear programming 2.8.2 Nonlinear programming 2.8.3 Local searchheuristics 2.9 Recent trends and algorithmic performance 2.10 More on the complexity of Boolean equations 2.10.1 Complexity of equation-solving procedures 2.10.2 Random equations 2.10.3 Constraint satisfaction problems and Schaefer ’s theorem 2.11 Generalizations of consistency testing 2.11.1 Counting the number of solutions 2.11.2 Generating all solutions 2.11.3 Parametric solutions 2.11.4 Maximum satisfiability 2.12 Exercises 3 Prime implicants and minimal DNFs 3.1 Prime implicants 3.1.1 Applications to propositional logic and artificial intelligence 3.1.2 Short prime implicants 3.2 Generation of all prime implicants 3.2.1 Generation from the set of true points 3.2.2 Generation from a DNF representation: The consensus method Variable depletion Term disengagement 3.2.3 Generation from a DNF representation: Complexity 3.2.4 Generation from a CNF representation 3.3 Logic minimization 3.3.1 Quine-McCluskey approach: Logic minimization as set covering 3.3.2 Local simplifications of DNFs 3.3.3 Computational complexity of logic minimization 3.3.4 Efficient approximation algorithms for logic minimization 3.4 Extremal and typical parameter values 3.4.1 Number of prime implicants 3.4.2 Extremal parameters of minimal DNFs 3.4.3 Typical parameters of Boolean functions and their DNFs 3.5 Exercises 4 Duality theory 4.1 Basic properties and applications 4.1.1 Dual functions and expressions 4.1.2 Normal forms and implicants of dual functions 4.1.3 Dual-comparable functions 4.1.4 Applications 4.2 Duality properties of positive functions 4.2.1 Normal forms and implicants of dual functions 4.2.2 Dual-comparable functions 4.2.3 Applications 4.3 Algorithmic aspects: The general case 4.3.1 Definitions and complexity results 4.3.2 Dualization by sequential distributivity 4.4 Algorithmic aspects: Positive functions 4.4.1 Some complexity results 4.4.2 A quasi-polynomial dualization algorithm 4.4.3 Additional results Question for thought 4.5 Exercises Part II: Special Classes 5 Quadratic functions 5.1 Basic definitions and properties 5.2 Why are quadratic Boolean functions important? 5.3 Special classes of quadratic functions 5.3.1 Classes 5.3.2 Characterizations by functional relations 5.4 Quadratic Boolean functions and graphs 5.4.1 Graphmodels of quadratic functions 5.4.2 The matched graph 5.4.3 The implication graph 5.4.4 Conflict codes and quadratic graphs 5.5 Reducibility of combinatorial problems to quadratic equations 5.5.1 Introduction 5.5.2 Bipartite graphs 5.5.3 Balance in signed graphs 5.5.4 Split graphs 5.5.5 Forbidden-color graphbipartition 5.5.6 Totally unimodular matrices withtwo nonzero entries per column 5.5.7 The Konig-Egerváry property for graphs 5.5.8 Single-bend wiring 5.5.9 Max-quadratic functions and VLSI design 5.5.10 A level graphdrawing problem 5.5.11 A final look into complexity 5.6 Efficient graph-theoretic algorithms for quadratic equations 5.6.1 Introduction 5.6.2 Labeling algorithm (L) 5.6.3 Alternative Labeling algorithm (AL) 5.6.4 Switching algorithm (S) 5.6.5 Strong Components algorithm (SC) 5.6.6 An experimental comparison of algorithms for quadratic equations 5.7 Quadratic equations: Special topics 5.7.1 The set of solutions of a quadratic equation 5.7.2 Parametric solutions 5.7.3 Maximum 2-satisfiability 5.7.4 On-line quadratic equations 5.8 Prime implicants and irredundant forms 5.8.1 Introduction 5.8.2 A transitive closure algorithm for finding all prime implicants 5.8.3 A restricted consensus method and its application to computing the transitive closure of a digraph 5.8.4 Irredundant normal forms and transitive reductions 5.9 Dualization of quadratic functions (Contributed by Oya Ekin Karasan) 5.9.1 Introduction 5.9.2 The dualization algorithm 5.10 Exercises 6 Horn functions 6.1 Basic definitions and properties 6.2 Applications of Horn functions 6.2.1 Propositional rule bases 6.2.2 Functional dependencies in databases 6.2.3 Directed graphs,hypergraphs,and Petri nets 6.2.4 Integer programming and polyhedral combinatorics 6.3 False points of Horn functions 6.3.1 Deduction in AI 6.4 Horn equations 6.4.1 Horn equations and the unit literal rule 6.4.2 Pure Horn equations and forward chaining 6.4.3 More on Horn equations 6.5 Prime implicants of Horn functions 6.6 Properties of the set of prime implicants 6.7 Minimization of Horn DNFs 6.7.1 Minimizing the number of terms 6.7.2 Minimizing the number of literals 6.7.3 Minimization of the number of source sides 6.8 Dualization of Horn functions 6.9 Special classes 6.9.1 Submodular functions 6.9.2 Bidual Horn functions 6.9.3 Double Horn functions 6.9.4 Acyclic Horn functions 6.10 Generalizations 6.10.1 Renamable Horn expressions and functions 6.10.2 Q-Horn functions 6.10.3 Extended Horn expressions 6.10.4 Polynomial hierarchies built on Horn expressions 6.11 Exercises 7 Orthogonal forms and shellability 7.1 Computation of orthogonal DNFs 7.2 Shellings and shellability 7.2.1 Definition 7.2.2 Orthogonalization of shellable DNFs 7.2.3 Shellable DNFs versus shellable functions 7.3 Dualization of shellable DNFs 7.4 The lexico-exchange property 7.4.1 Definition 7.4.2 LE property and leaders 7.4.3 Recognizing the LE property 7.4.4 Dualization of functions having the LE property 7.5 Shellable quadratic DNFs and graphs 7.6 Applications 7.7 Exercises Questions for thought 8 Regular functions 8.1 Relative strength of variables and regularity 8.2 Basic properties 8.3 Regularity and left-shifts 8.4 Recognition of regular functions Strength preorder and Winder matrix Efficient comparison of variables 8.5 Dualization of regular functions 8.6 Regular set covering problems 8.7 Regular minorants and majorants 8.7.1 Largest regular minorant withrespect to a given order 8.7.2 Smallest regular majorant withrespect to a given order 8.7.3 Regular minorization and set covering problems 8.8 Higher-order monotonicity 8.9 Generalizations of regularity 8.9.1 Weakly regular functions 8.9.2 Aligned functions 8.9.3 Ideal functions 8.9.4 Relations among classes 8.10 Exercises 9 Threshold functions 9.1 Definitions and applications 9.2 Basic properties of threshold functions 9.3 Characterizations of threshold functions 9.4 Recognition of threshold functions 9.4.1 A polynomial-time algorithm for positive DNFs 9.4.2 A compact formulation 9.4.3 The general case 9.5 Prime implicants of threshold functions 9.6 Chow parameters of threshold functions 9.6.1 Chow functions 9.6.2 Chow parameters and separating structures 9.6.3 Computing the Chow parameters 9.7 Threshold graphs 9.8 Exercises 10 Read-once functions 10.1 Introduction 10.2 Dual implicants 10.2.1 Implicants and dual implicants 10.2.2 The dual subimplicant theorem 10.3 Characterizing read-once functions 10.4 The properties of P4-free graphs and cographs 10.5 Recognizing read-once functions Testing normality Complexity analysis 10.6 Learning read-once functions Complexity 10.7 Related topics and applications of read-once functions 10.7.1 The readability of a Boolean function 10.7.2 Factoring general Boolean functions 10.7.3 Positional games 10.8 Historical notes 10.9 Exercises Questions for thought 11 Characterizations by functional equations 11.1 Characterizations of positive functions 11.2 Functional equations 11.3 Characterizations of particular classes 11.3.1 Horn functions 11.3.2 Linear functions and related classes 11.3.3 Quadratic and degree k functions 11.4 Conditions for characterization 11.5 Finite characterizations by functional equations 11.6 Exercises Part III: Generalizations 12 Partially defined Boolean functions 12.1 Introduction 12.2 Extensions of pdBfs and their representations 12.2.1 Definitions 12.2.2 Support sets of variables 12.2.3 Patterns and theories of pdBfs 12.2.4 Roles of theories and cotheories 12.2.5 Decision trees 12.3 Extensions within given function classes 12.3.1 Positive extensions 12.3.2 Monotone (unate)extensions 12.3.3 Degree-k extensions 12.3.4 Horn extensions 12.3.5 Threshold extensions 12.3.6 Decomposable extensions 12.3.7 k -convex extensions 12.4 Best-fit extensions of pdBfs containing errors 12.5 Extensions of pdBfs with missing bits 12.5.1 Three types of extensions 12.5.2 Complexity results 12.6 Minimization with don't cares 12.7 Conclusion 12.8 Exercises 13 Pseudo-Boolean functions 13.1 Definitions and examples Mathematics Computer science and engineering Operations research 13.2 Representations 13.2.1 Polynomial expressions,pseudo-Boolean normal forms and posiforms 13.2.2 Piecewise linear representations 13.2.3 Disjunctive and conjunctive normal forms 13.3 Extensions of pseudo-Boolean functions 13.3.1 The polynomial extension 13.3.2 Concave and convex extensions 13.3.3 The Lovász extension 13.4 Pseudo-Boolean optimization 13.4.1 Local optima 13.4.2 An elimination algorithm for global optimization 13.4.3 Extensions and relaxations The polynomial extension Linearization and concave extensions The Lovász extension 13.4.4 Posiform transformations and conflict graphs 13.5 Approximations 13.6 Special classes of pseudo-Boolean functions 13.6.1 Quadratic functions and quadratic 0-1 optimization 13.6.2 Monotone functions 13.6.3 Supermodular and submodular functions 13.6.4 Unimodular functions 13.6.5 Threshold and unimodal functions 13.7 Exercises Question for thought Appendix A: Graphs and hypergraphs A.1 Undirected graphs A.1.1 Subgraphs A.1.2 Paths and connectivity A.1.3 Special classes of graphs A.2 Directed graphs A.2.1 Directed paths and connectivity A.2.2 Special classes of digraphs A.2.3 Transitive closure and transitive reduction A.3 Hypergraphs Appendix B: Algorithmic complexity B.1 Decision problems B.2 Algorithms B.3 Running time, polynomial-time algorithms, and the class P B.4 The class NP B.5 Polynomial-time reductions and NP-completeness B.6 The class co-NP B.7 Cook's theorem B.8 Complexity of list-generation and counting algorithms Appendix C: JBool: A software tool C.1 Introduction C.2 Work interface C.2.1 Menu bar C.2.2 Function windows C.2.3 Text zone C.3 Creating a Boolean function C.3.1 Function syntax and presentation C.3.2 Creation modes C.3.3 Saving a function C.4 Editing a function C.4.1 Changing the normal form C.4.2 Modifying the variable set C.5 Operations on Boolean functions C.5.1 Equivalent presentations of a Boolean function C.5.2 Constructions C.5.3 Operations on two Boolean functions C.5.4 Testing properties of a function Bibliography Index