Boolean functions. Theory, algorithms, and applications.(English)Zbl 1237.06001

Encyclopedia of Mathematics and its Applications 142. Cambridge: Cambridge University Press (ISBN 978-0-521-84751-3/hbk; 978-1-139-06424-8/ebook). xxi, 687 p. (2011).
Various fields of pure and applied mathematics, such as propositional logic, combinatorial analysis, computer science, operations research, voting games, artificial intelligence and many others, make extensive use of functions with 0-1 arguments and values, known as Boolean functions. This monograph provides a comprehensive and unified presentation of the structural, algorithmic and applied aspects of the theory of these functions.
The book has three parts: Part I: Foundations (Chapters 1–4); Part II: Special classes (Chapters 5–11); and Part III: Generalizations (Chapters 12, 13). Some chapters are co-authored by several contributors. There are also three Appendices, A, B, and C, a Bibliography of 941 items and an Index.
Chapter 1 introduces Boolean functions. It is mentioned that, although in algebra the term “Boolean functions” designates the algebraic functions $$f: B^n\to B$$ (i.e., functions generated by Boolean expressions) over an arbitrary Boolean algebra $$B$$, the restricted framework of the Boolean algebra $$\{0,1\}$$ “is already sufficiently rich to model a variety of interesting applications and allows us to handle a lot of challenging algorithmic problems of a combinatorial nature”. The emphasis of the presentation is on Boolean expressions rather than other representations of Boolean functions. Duality, normal forms, with emphasis on disjunctive normal forms (DNF), implicants and prime implicants, restrictions of functions, geometric interpretation, monotone Boolean functions, recognition of functional and DNF properties, and other representations of Boolean functions, are introduced. The presentation is very careful, with many examples and counterexamples; for several theorems of the form “if $$h$$ then $$p\Leftrightarrow q$$” it is noticed that in fact the implication $$p\Rightarrow q$$ holds even without the hypothesis $$h$$. The chapter ends with a sketch of several applications which will be resumed in more detail in subsequent chapters.
Boolean equations are treated in some detail in Chapter 2, as their solution is a cornerstone in many Boolean algorithms occurring in this book. Like Chapter 1, this chapter begins with a sketchy presentation of a few applications to be resumed in subsequent chapters. Any system of equations $$\varphi_k(X)= \psi_k(X)$$ $$(k= 1,\dots, p)$$ and inequalities $$\varphi_k(X)\leq \psi_k(X)$$ $$(k= p+ 1,\dots, q)$$, where $$\varphi_k$$ and $$\psi_k$$ are Boolean functions of $$n$$ variables, is equivalent to a single DNF equation, that is, an equation $$\varphi(X)= 0$$, with the Boolean function $$\varphi$$ expressed in DNF (as required in many applications). Moreover, if new variables are introduced, this transformation is carried out in linear time. The remainder of the chapter is devoted to several procedures for solving a Boolean equation $$\varphi(X)= 0$$. The section on branching procedures discusses strategies for choosing the branching variable and for constructing the subroutine which is called after the branching variable has been fixed. The next procedure is variable elimination, with a discussion of the elimination ordering. The consensus procedure for solving a DNF equation is then presented. Another approach consists in transforming a Boolean equation into an equivalent mathematical programming problem with 0-1 variables, linear or nonlinear. The last topics of this chapter are recent trends and algorithmic performance, the complexity of Boolean equations, the number of solutions, generation of all the solutions, parametric solutions, and the special problem of maximum satisfiability.
Chapter 3, Prime implicants and minimal DNFs, is written by Peter L. Hammer and Alexander Kogan. After the basic definitions and a few preliminary properties, the discussion is concentrated on the generation of all prime implicants in the cases in which the function $$f$$ is given by the list of all its true points, or by an arbitrary DNF (two proofs are given for the basic fact that the consensus method produces the disjunction of all prime implicants) or, dually, by a CNF. The next problem is logic minimization, or Boolean function minimization, that is, the construction of a prime DNF (made up of prime implicants) minimizing the number of terms. The Quine-McCluskey approach reduces this problem to a set covering problem, which is expressed here as a linear Boolean programming problem. The special features of this covering problem are used in order to simplify its solution. Efficient approximation algorithms for logic minimization are also suggested. The last section discusses several numerical parameters that provide important information about Boolean functions and their DNFs.
Duality theory is the topic of Chapter 4, written by Yves Crama and Kazuhisa Makino. First, we find here the duality principle of Boolean algebras, normal forms and implicants of dual functions, functions that imply or are implied by their duals, and a bijection between the set of Boolean functions of $$n$$ variables and the set of self-dual Boolean functions of $$n+1$$ variables, namely, every function in the former set is mapped to an extension of it in the latter set. Then, duality properties of positive (i.e., increasing) functions are pointed out, with applications. Further, the generic terms of dualization and dual recognition mean the problems of constructing the dual $$f^d$$ of a function $$f$$ and of answering whether given functions $$f$$, $$g$$ satisfy $$g=f^d$$, respectively. Algorithms are given for solving specific problems obtained by specifying the required forms of the input and of the output. Theorems are given which determine the complexity of these problems. Many theorems refer to positive functions.
A DNF is called quadratic if all its terms contain at most two literals; the corresponding Boolean function is also termed quadratic. Bruno Simeone is the author of Chapter 5, devoted to quadratic functions and equations. The interest in this topic comes from the fact that quadratic Boolean functions are “abundant in nature” and many significant combinatorial problems can be reduced to quadratic Boolean equations; Chapter 5 is a convincing argument for this claim. After noticing that several important classes of quadratic functions are characterized by functional equations, this chapter studies relationships between quadratic DNFs and graphs. The consistency of a quadratic equation $$\varphi(X)= 0$$ can be characterized in two ways by a graph associated with $$\varphi$$. Then it is shown that checking bipartiteness in a graph, balance in signed graphs, recognition of split graphs, recognition of the König-Egerváry property and single-bend drawings of electronic circuits, can efficiently be reduced to quadratic equations. For some of these problems the reduction can even be performed in linear time. Four fast algorithms for the solution of quadratic Boolean equations are given, with an experimental comparison of their performances on 400 randomly generated test problems with up to 2000 variables and 8000 terms; the general conclusion is that quadratic equations are easy to solve. The last topics of this chapter are the generation of all the solutions and of parametric solutions of quadratic equations, the determination of all prime implicants and of irredundant DNFs of a quadratic function, and the dualization of a quadratic function.
Chapter 6, written by Endre Boros, is devoted to Horn functions. An elementary conjunction is said to be Horn (pure Horn) if it contains at most (exactly) one complemented variable. Horn (pure Horn) DNFs and Horn (pure Horn) Boolean functions are then defined in a natural way. The prime implicants of a Horn (pure Horn) function are Horn (pure Horn). A few examples of applications of Horn functions are given: in expert systems, functional dependencies in databases, directed graphs, hypergraphs and Petri nets, integer programming and polyhedral combinatorics. A procedure is given which detects in polynomial time a possible false point of a given Horn DNF $$\eta$$ or establishes that $$\eta$$ is identically 1. Another procedure generates the complete list of prime implicants of a Boolean function represented by a prime DNF. Three minimization problems of Horn DNFs are then presented: minimizing the number of terms, minimizing the number of literals, and minimizing the number of source sides. It is computationally difficult to decide whether a given DNF represents the dual of a Horn function (which need not be Horn). Several interesting special classes of Horn functions are discussed. A few generalizations of Horn functions and expressions conclude this chapter.
Orthogonal disjunctive normal forms (ODNFs), which occur in the theory of Boolean equations, are treated in Chapter 7. A DNF is said to be orthogonal if its terms are pairwise disjoint, i.e., $$st= 0$$ if $$s\neq t$$. If $$\varphi=\bigvee^m_{i=1} C_k$$ is an arbitrary DNF, then, setting $$\psi_k= \overline{C_1}\dots\overline{C_{k-1}}C_k$$, the expression $$\psi= \bigvee^m_{k=1}\psi_k$$ is equivalent to $$\varphi$$, and if the $$\psi_k$$s are ODNFs then $$\psi$$ is an ODNF. In general, orthogonal equivalent forms are difficult to compute, however, shellable DNFs can be orthogonalized and dualized in polynomial time. A DNF $$\bigvee^m_{k=1} C_k$$ is called shellable if it admits a shelling, that is, a permutation $$\pi$$ of $$\{1,\dots,m\}$$ such that, for each $$k=1,\dots, m$$, the expression $$\overline{C_{\pi(1)}}\dots \overline{C_{\pi(k-1)}} C_k$$ is equivalent to an elementary conjunction. A positive Boolean function is called shellable if its complete DNF is shellable. The chapter studies these concepts in detail. Applications to undirected all-terminal reliability, matroids, threshold functions and majority games are briefly described.
Every Boolean function $$f$$ induces a preorder $$\succeq_f$$ on the set of its variables, defined as follows: $$x_i\succeq_f x_j$$ if $$i= j$$ or $$f|_{x_i= 1,x_j=0}\geq f|_{x_i=0, x_j=1}$$. A positive Boolean function $$f$$ is called regular if the strength relation $$\succeq_f$$ is total. Chapter 8 investigates the main properties of regular functions. A striking example is the “voting mechanism in Booleland”, which is described by a threshold function, a particular case of regular functions. After this short introduction, the chapter continues with basic properties and applications to integer programming, game theory and combinatorics. Other subjects are regularity and left-shifts, and recognition of regular functions, for which an algorithm is provided which has $$O(n^2m)$$ time complexity, where $$n$$ is the number of variables and $$m$$ is the number of prime implicants of the function. An algorithm of time complexity $$O(n^2m)$$ is also given for the dualization of regular functions. The linear Boolean program, maximize $$\sum^n_{i=1} c_ix_i$$ subject to a Boolean equation $$f(X)= 0$$, has several applications; a procedure is given which solves the problem in the case when $$f$$ is a regular function, and it has time complexity $$O(nm)$$. The last topics of this chapter are the approximation of a positive function by a regular function, a strength relation between subsets of variables, a generalization of monotonicity, as well as several generalizations of regularity.
Chapter 9 deals with threshold functions, a subclass of regular functions. A threshold function is a Boolean function $$f$$ such that there exist $$n$$ “weights” $$w_1,\dots, w_n\in\mathbb{R}$$ and a “threshold” $$t\in\mathbb{R}$$ such that $$f(X)= 0\Leftrightarrow\sum^n_{i=1} w_ix_i\leq t$$; the tuple $$(w_1,\dots, w_n,t)$$ is called a separating structure of $$f$$. The chapter points out applications of threshold functions to electrical engineering, artificial neural networks, reliability theory, game theory, integer programming, distributed computing, mathematical psychology and social choice. Then several necessary and sufficient conditions for a function to be threshold and two characterizations of threshold functions are provided. A fundamental algorithmic problem is to recognize whether a given Boolean function $$f$$ is threshold and, when the answer is affirmative, to produce a separating structure of $$f$$. The complexity of this problem depends very much on the format of its input. Thus, if the positive function $$f$$ is expressed by its complete DNF, the problem is polynomially solvable; in the general case it is co-NP-complete. The converse problem is to generate all prime implicants of the threshold function corresponding to a given separating structure; a procedure is given which solves this problem in $$O(nm)$$ time, where $$n$$ is the number of variables and $$m$$ is the number of prime implicants of the input function. The last section studies the Chow parameters of threshold functions.
Chapter 10, written by Martin C. Golumbic and Vladimir Gurvich, studies read-once functions, that is, functions having an expression in which every variable appears exactly once. After some prerequisites concerning the prime implicants of the dual of a Boolean function, several graph-theoretical characterizations of read-once functions are provided. An important role is played by $$\mathrm{P}_4$$-free graphs, i.e., graphs with no four-vertex chain; several characterizations of these graphs are also given. The algorithmic recognition of read-once functions is studied as well. Read-Once Exact Learning is the problem whose input is a black-box oracle to evaluate $$f$$ at any given point, where $$f$$ is known a priori to be a positive read-once function, while the output is a read-once expression for $$f$$. A procedure is given which solves this problem in $$O(n^2)$$ time, using $$O(n^2)$$ queries to the oracle. Related topics, applications and historical notes are briefly mentioned.
Lisa Hellerstein is the author of Chapter 11, on characterizations of special classes by functional equations. It is shown that a Boolean function $$f$$ is: positive iff it satisfies $$f(X)\leq f(X\vee Y)$$, Horn iff it satisfies $$f(XY)\leq f(X)\vee f(Y)$$, linear iff it satisfies $$f(X)\vee f(Y)= f(X\vee Y)\vee f(XY)$$, and quadratic iff it satisfies $$f(XY\vee XZ\vee YZ)\leq f(X)\vee f(Y)\vee f(Z)$$. The latter characterization is generalized to positive Boolean functions of degree at most $$k$$ where $$k\geq 2$$. Then it is proved that a class $${\mathcal K}$$ of Boolean functions can be characterized by a (possibly infinite) set of functional equations if and only if $${\mathcal K}$$ is closed under identification of variables and addition of inessential variables. Another theorem provides a necessary and sufficient condition for a class $${\mathcal K}$$ of Boolean functions to be characterized by a finite set of functional equations, hence by a single functional equation. These theorems imply that none of the following classes of functions can be characterized by functional equations: 1) monotone, 2) shellable, 3) of degree at most $$k$$ where $$k\geq 3$$, 4) regular, and 5) read-once, whereas threshold functions can be characterized by an infinite set of functional equations, but not by a single one.
Partially defined Boolean functions (pdBfs) are functions defined on a subset of $$\{0,1\}^n$$ with values in $$\{0,1\}$$; they are the subject of Chapter 12, written by Toshihide Ibaraki. First, the chapter studies in detail the exentions of pdBfs to Boolean functions and their representations. Then the problem of obtaining extensions of pdBfs that belong to a specific class of Boolean functions is treated for the classes which consist of: all Boolean functions, all positive functions, all unate functions, all functions representable by a DNF of degree at most $$k$$, all Horn functions, all threshold functions, all decomposable functions, all $$k$$-convex functions, respectively. Another problem is to cope with errors that may occur during the extension process. A related problem is the extension of pdBfs which describe real-world data sets from which one or several bits may be missing. The design of logic circuits leads to problems with don’t care conditions, meaning that for certain combinations of the input values, the value of the function can be chosen arbitrarily; this freedom is used to optimize the designed function.
Chapter 13 deals with pseudo-Boolean functions (pBfs), that is, functions $$f:\{0,1\}\to\mathbb{R}$$. There are countless publications on this subject, due to their numerous applications. The chapter sketches applications to graph theory, linear algebra, artificial intelligence, data mining, classification, learning theory, computer vision, operations research, production management and logistics. The next section deals with algebraic representations of pBfs, such as polynomial expressions, disjunctive and conjunctive normal forms; the theory of (prime) implicants and (prime) implicates is extended to the pseudo-Boolean case. Extensions of pBfs $$f: \{0,1\}^n\to\mathbb{R}$$ to functions $$g: [0,1]^n\to\mathbb{R}$$ are also studied. The next section mentions a few fundamental results about pseudo-Boolean optimization, that is, nonlinear 0-1 optimization. The chapter is concluded with a few special classes of pseudo-Boolean functions, defined by analogy with their Boolean counterparts: quadratic, monotone, supermodular and submodular, unimodular, threshold and unimodal functions.
Appendix A and Appendix B, included for the sake of self-containedness, are primers on graph theory and algorithmic complexity, respectively; Appendix B includes a proof of the Cook theorem which establishes the NP-completeness of the DNF Equation problem (also known as the SAT problem). Appendix C, written by Claude Benzaken and Nadia Brauner, sketchily presents JBool, a software tool which allows users to work with Boolean functions expressed in DNF or CNF; it is suitable for small-size examples.
Each chapter contains numerous examples and applications, and ends with exercises. There are also “Questions for thought”.
Because of the unique depth and breadth of the unified treatment that it provides and its emphasis on algorithms and applications, this monograph and its companion book [Y. Crama (ed.) and P. L. Hammer (ed.), Boolean models and methods in mathematics, computer science and engineering. Encyclopedia of Mathematics and its Applications 134. Cambridge: Cambridge University Press (2010; Zbl 1196.06001)] will have special appeal for a large circle of readers.

MSC:

 06-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to ordered structures 06E30 Boolean functions

Zbl 1196.06001

Software:

JBool; Leibniz; Chaff