Boolean Functions : Theory, Algorithms, and Applications.

✍ Scribed by Yves Crama, Peter L. Hammer

• Publisher: Cambridge University Press
• Year: 2011
• Tongue: English
• Leaves: 711
• Series: Encyclopedia of Mathematics and its Applications
• Category: Library

✦ Table of Contents

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