**NOTE 2:**
One small "subtlety" was not made explicit in the given proof of
this theorem. It concerns the "border cases" when one of $\CC{f}$ or $\DD{f}$
becomes *empty* (has no clauses or no monomials at all).
In these cases, the Monotone Switching Lemma (Lemma 9.15) does not hold, and it remained not clear how to assign approximators of gates in such cases.
This may happen, say, when we are at an AND gate $f=g\land h$, and $\CC{f}$
consists of $r$ or more *disjoint* clauses. The application of the
the Monotone Switching Lemma (Lemma 9.15) to $\CC{f}$ gives then an empty DNF $\DD{f}$.
As customary, we interpret an empty CNF as the constant $1$ function, and an empty DNF as the constant $0$ function.

So, let us now make this "subtlety" explicit. Recall that we assigned approximators $(\CC{f},\DD{f})$ inductively as follows; here $\left(\CC{f} \right)^*$ stays for the DNF obtained by applying the Switching Lemma to the CNF $\CC{f}$, and dually for $\left(\DD{f} \right)^*$: \begin{align} f&=g\land h \ \ \Longrightarrow\ \ \CC{f}:=\CC{g}\land\CC{h}\ \mbox{ and }\ \DD{f}:=\left(\CC{f} \right)^*\\ f&=g\lor h \ \ \Longrightarrow\ \ \DD{f}:=\DD{g}\lor\DD{h}\ \mbox{ and }\ \CC{f}:=\left(\DD{f} \right)^* \end{align} In the case when one of $\CC{f}$ or $\DD{f}$ is empty, we do the following: \begin{align} f&=g\land h \ \mbox{ and }\ \CC{f}\equiv 1\ \ \Longrightarrow\ \ \DD{f}:=\DD{g}\\ f&=g\lor h \ \mbox{ and }\ \DD{f}\equiv 0\ \ \Longrightarrow\ \ \CC{f}:=\CC{g} \end{align} Note that the "cross intersection" property $\DD{f}\leq\CC{f}$ is then trivially fulfilled.

Recall that an approximator $(\CC{f},\DD{f})$ of $f$ introduces a new error on input $x\in\{0,1\}^n$ if the approximators of $g$ and of $h$ did not make an error on $x$, but the approximator of $f$ does. That is, $\CC{g}(x)=\DD{g}(x)=g(x)$ and $\CC{h}(x)=\DD{h}(x)=h(x)$, but either $\CC{f}(x)\neq f(x)$ or $\DD{f}(x)\neq f(x)$ holds.

Suppose now that one of $\CC{f}$ or $\DD{f}$ is empty, say, $\CC{f}\equiv 1$. We claim that then no new error is introduced at $f=g\land h$. To see this, let $x\in\{0,1\}^n$ be an input on which a new error is introduced. Since there was no error on $x$ at input gates $g$ and $h$, we have that $\CC{g}(x)=\DD{g}(x)=g(x)$ and $\CC{h}(x)=\DD{h}(x)=h(x)$. Hence, $\CC{f}(x):=\CC{g}(x)\land \CC{h}(x)=g(x)\land h(x)=f(x)$, meaning that the left approximator $\CC{f}$ introduces no error on $x$. So, the error must be introduced at the right approximator $\DD{f}:=\DD{g}$, i.e. $f(x)=1$ and $\DD{f}(x)=0$. But $f(x)=g(x)\land h(x)=1$ implies that $g(x)=1$, and hence also $\DD{g}(x)=1$, since $x$ was not an error at gate $g$. Hence, $\DD{f}(x)=\DD{g}(x)=1=f(x)$, and we have no error at $f$.

The case of an Or gate $f=g\lor h$ is dual.

S. Jukna, June 2014

Back to the home page of the book.