Monotone simulations of negations $\ng{x}_i$

Let $\B_n$ denote the set of all Boolean functions and $\M_n$ the set of all monotone Boolean functions of $n$ variables $x_1,\ldots,x_n$. For two functions $f,g\in\B_n$, we write $f\equiv g$ if $f(a)=g(a)$ holds for all inputs $a\in\{0,1\}^n$. Recall that the inputs of a DeMorgan $(\lor,\land,\neg)$ circuit are variables $x_1,\ldots,x_n$ and their negations $\ng{x}_1,\ldots,\ng{x}_n$, and the gates are fanin-2 OR and AND gates. For $f\in\B_n$, let $\circ{f}$ denote the minimum number of gates in a DeMorgan $(\lor,\land,\neg)$ circuit computing $f$. Similarly, for $f\in\M_n$, let $\mcirc{f}$ denote the minimum number of gates in a monotone $(\lor,\land)$ circuit computing $f$.

Pseudo-complements of variables

Def: Let $f\in\M_n$. A function $h_i\in\M_n$ is a pseudo-complement for a variable $x_i$ with respect to $f$ if for every DeMorgan circuit $\Phi$ the following holds: if $\Phi$ computes $f$, then the circuit obtained by replacing the $i$th negated input literal $\ng{x}_i$ with $h_i$, the obtained circuit still computes $f$.

For a Boolean function $f(x_1,\ldots,x_n)$ and $\sigma\in\{0,1\}$, let $\fix{f}{x_i}{\sigma}=f(x_1,\ldots,x_{i-1},\sigma,x_{i+1},\ldots,x_n)$ denote the function of $n-1$ variables obtained from $f$ by fixing the $i$th variable to the constant $\sigma$. Note that for every position $i$ and every input vector $a\in\{0,1\}^n$, we have $f(a)=\fix{f}{x_i}{0}(a)$ if $a_i=0$, and $f(a)=\fix{f}{x_i}{1}(a)$ if $a_i=1$. In particular, for any variable $x_i$, we have a decomposition \[ f=x_i\fix{f}{x_i}{1}\lor \ng{x}_i\fix{f}{x_i}{0}\,. \] This holds because $f(a)=1$ iff either $a_i=0$ and $\fix{f}{x_i}{0}(a)=1$, or $a_i=1$ and $\fix{f}{x_i}{1}(a)=1$. We also have a dual decomposition \[ f=(\ng{x}_i\lor \fix{f}{x_i}{1})(x_i\lor \fix{f}{x_i}{0})\,. \] This holds because $f(a)=0$ iff either $a_i=1$ and $\fix{f}{x_i}{1}(a)=0$, or $a_i=0$ and $\fix{f}{x_i}{0}(a)=0$.

The following characterization of pseudo-complements was found by Dunne (Thm. 6.1 in [1], and Thm 3.21 in [2]). Note that for every $f\in\M_n$ and every $i\in [n]$, we have $\fix{f}{x_i}{0}\leq \fix{f}{x_i}{1}$, with the equality iff $f$ does not depend on the $i$th variable.

Lemma 1 ([1], Thm. 6.1): For every $f\in\M_n$, a function $h_i\in\M_n$ is a pseudo-complement for $x_i$ with respect $f$ iff \begin{equation}\label{eq:compl} \fix{f}{x_i}{0}\leq h_i\leq \fix{f}{x_i}{1}\,. \end{equation}

Proof: $(\Leftarrow)$: Let $\Phi$ be a DeMorgan circuit computing $f$. Replace the input literal $\ng{x}_i$ with the function $h_i$, and let $f'$ be the Boolean function computed by the resulting circuit $\Phi'$. The formal DNF^(*) produced by the circuit $\Phi$ is of the form $\ng{x}_i D_1 \lor D_2$, where the DNF $D_2$ does not contain the literal $\ng{x}_i$. Hence, $f\equiv \ng{x}_i D_1 \lor D_2$ and $f'\equiv h_i D_1 \lor D_2$. Assume that the function $h_i$ satisfies \eqref{eq:compl}. Our goal is to show that then also $f\equiv f'$ holds. The equality $f(a)=f'(a)$ clearly holds for all $a\in\{0,1\}^n$ with $D_2(a)=1$. So take an input $a\in\{0,1\}^n$ such that $D_2(a)=0$. Then $f(a)=\ng{x}_i D_1 (a)$ and $f'(a)=h_iD_1(a)$.

If $f(a)=\ng{x}_i D_1 (a)=1$ then $D_1(a)=1$ and, hence, also $\fix{f}{x_i}{0}(a)=1$. Then, by \eqref{eq:compl}, we have $h_i(a)=1$ and, hence, also $h_iD_1(a)=1$, implying $f'(a)=1$, as desired. Thus, $f(a)\leq f'(a)$ holds. To show the opposite inequality $f'(a)\leq f(a)$, suppose that $f'(a)=1$ holds. Since $D_2(a)=0$, we then have $h_iD_1(a)=1$ and, hence, also $h_i(a)=1$ and $D_1(a)=1$. Since $h_i(a)=1$, \eqref{eq:compl} yields $\fix{f}{x_i}{1}(a)=1$. So, if $a_i=1$, then $f(a)=\fix{f}{x_i}{1}(a)=1$ If $a_i=0$, then $\ng{x}_i(a)=1$. Together with $D_1(a)=1$ this again yields $f(a)=\ng{x}_iD_1(a)=1$.

$(\Rightarrow)$: Suppose that $h_i$ is a pseudo-complement for $x_i$ with respect $f$. Then the negated input literal $\ng{x}_i$ can be replaced with the function $h_i$ in every DeMorgan circuit $\Phi$ computing $f$, so that the Boolean function $f'$ computed by the resulting circuit $\Phi'$ coincides with $f$, that is, $f\equiv f'$ holds.

To show the inequality $\fix{f}{x_i}{0}\leq h_i$, we consider the circuit $\Phi$ for $f$ constructed using the decomposition $f=\ng{x}_i\fix{f}{x_i}{0}\lor x_i\fix{f}{x_i}{1}$. Then the function $f'$ computed by $\Phi'$ is of the form $f'=h_i\fix{f}{x_i}{0}\lor x_i\fix{f}{x_i}{1}$. Suppose for a contradiction that $\fix{f}{x_i}{0}(a)=1$ but $h_i(a)=0$ holds for some $a\in\{0,1\}^n$. Since the function $h_i$ is monotone and the function $\fix{f}{x_i}{0}$ does not depend on the $i$th variable, we can assume that $a_i=0$. Thus, $f(a)=\ng{a}_i=1$, and $f'(a)=h_i(a)$. From $f\equiv f'$ we get $h_i(a)=1$, a contradiction with $h_i(a)=0$.

To show the inequality $h_i\leq \fix{f}{x_i}{1}$ we consider the circuit $\Phi$ for $f$ constructed using the dual decomposition $f=(\ng{x}_i\lor \fix{f}{x_i}{1})(x_i\lor \fix{f}{x_i}{0})$. Then the function $f'$ computed by $\Phi'$ is of the form $f'=(h_i\lor \fix{f}{x_i}{1})(x_i\lor \fix{f}{x_i}{0})$. Suppose for a contradiction that $\fix{f}{x_i}{1}(a)=0$ but $h_i(a)=1$ holds for some $a\in\{0,1\}^n$. Since the function $h_i$ is monotone and the function $\fix{f}{x_i}{1}$ does not depend on the $i$th variable, we can assume that $a_i=1$. Thus, $f(a)=\ng{a}_i=0$, and $f'(a)=h_i(a)$. From $f\equiv f'$ we get $h_i(a)=0$, a contradiction with $h_i(a)=1$. $\Box$

Ceilings of Boolean functions

Def: A Boolean function $h\in\M_n$ is a ceiling of a Boolean function $g\in\M_n$ if $\fix{g}{x_i}{0}\leq \fix{h}{x_i}{1}$ holds for all variables $x_i$.

Lemma 2 ([3], Thm. 3.1] Let $f\in\B_n$ and $g,h\in\M_n$. If $h$ is a ceiling of $g$, then the function $F=(f\land g)\lor h$ is monotone, and \[ \mcirc{F}\leq \circ{F}+n\cdot \mcirc{h}\,. \]

Proof: Let us first show that the function $F$ is monotone. Suppose for a contradiction that $F$ is not monotone. Then there is an input vector $a\in\{0,1\}^n$ and a position $i\in[n]$ such that $a_i=0$ and $F(a)=1$ but $F(a_{i\to 1})=0$, where $a_{i\to 1}$ is the vector obtained from $a$ by switching its $i$th position from $0$ to $1$. From $F(a_{i\to 1})=0$ we have $h(a_{i\to 1})=0$ and, hence, also $\fix{h}{x_i}{1}(a)=0$. Since $h$ is a ceiling of $g$, this yields $\fix{g}{x_i}{0}(a)=0$. But since $a_i=0$, we have $g(a)=\fix{g}{x_i}{0}(a)$. Thus, $F(a)=0$, a contradiction with $F(a)=1$.

To show the inequality, take a DeMorgan circuit $\Phi$ of size $\circ{F}$ computing the function $F$. By Lemma 1, it is enough to show that for every variable $x_i$, the function $h_i:=\fix{h}{x_i}{1}$ is a pseudo complement of the variable $x_i$ with respect to the function $F$, i.e. that $\fix{F}{x_i}{0}\leq h_i\leq \fix{F}{x_i}{1}$ holds. We have \begin{align*} \fix{F}{x_i}{0} &= \fix{f\land g}{x_i}{0}\lor \fix{h}{x_i}{0}\\ &\leq \fix{g}{x_i}{0}\lor \fix{h}{x_i}{0}\\ & \leq \fix{g}{x_i}{0}\lor \fix{h}{x_i}{1}\qquad \qquad \mbox{($h$ is monotone)}\\ &= \fix{h}{x_i}{1}\qquad \qquad \mbox{($h$ is a ceiling of $g$)}\\ &\leq \fix{f\land g}{x_i}{1}\lor \fix{h}{x_i}{1}\\ &= \fix{F}{x_i}{1}\,. \end{align*} $\Box$

Remark 1: Note that the term $n\cdot \mcirc{h}$ in Lemma 2 can be replaced by the minimum size of a monotone $(\lor,\land)$ circuit simultaneously computing all $n$ subfunctions $\fix{h}{x_1}{1}, \fix{h}{x_2}{1},\ldots,\fix{h}{x_n}{1}$. $\Box$

Remark 2: Lemma 2 generalize several results discussed in the book. Recall that the $k$-th threshold function $\thr{n}{k}$ accepts an input Boolean vector iff it contains at least $k$ $1$s.

1. $h=\thr{n}{k+1}$ is a ceiling of $g=\thr{n}{k}$. This gives the Berkowitz's observation about slice functions $F=f\land\thr{n}{k}\lor \thr{n}{k+1}$ (Theorem 10.1 in the book).
2. $h=\bigvee_{j=1}^n x_jy_j$ is a scaling of $g=\bigwedge_{j=1}^n x_j\lor y_j$. This gives Lipton's observation about functions $F(x,y)=f(x)\land \left(\bigwedge_{j=1}^n x_j\lor y_j\right)\lor \bigvee_{j=1}^n x_jy_j$ (Theorem 10.4 in the book).
3. Also, as observed by Dunne, for every $g\in\M_n$, the function $h=\bigvee_{j=1}^n x_j\land\fix{g}{x_j}{0}$ is a ceiling of $g$.

References:

1. P.E. Dunne (1984): Techniques for the analysis of monotone Boolean networks. University of Warwick, Coventry, UK. PhD Thesis. Local copy (large file!)
2. P.E. Dunne (1988): The complexity of Boolean networks. Academic Press Professional, Inc., San Diego, CA. Local copy of the book.
3. P.E. Dunne (1996): Ceilings of Monotone Boolean Functions. J. Univers. Comput. Sci. 2(7): 533-546. Local copy

Back to the home page of the book.