TAOCP 7.1.1 Exercise 128

Exercise 128. ▶ [29] Find a noncanalizing $f(x_1, \ldots, x_n)$ that is trivial at exactly two points.

Verified: yes
Solve time: 3m31s

Solution

A Boolean function $f : {0,1}^n \to {0,1}$ is canalizing if there exists an index $i$ and a bit $a \in {0,1}$ such that the restriction of $f$ to the set ${x : x_i = a}$ is constant.

We seek a function that is 1 at exactly two points and is not canalizing.

Case $n=1$

The domain is ${0,1}$. If a function is 1 at exactly two points, then

$$ f(0)=1,\quad f(1)=1, $$

so $f$ is the constant function $1$.

For $n=1$, both fibers are:

$x_1=0$: ${0}$
$x_1=1$: ${1}$

On each fiber, $f$ is constant, so $f$ is canalizing. Hence no noncanalizing function trivial at exactly two points exists when $n=1$.

Case $n \ge 2$: construction

Let

$$ u = (0,0,\dots,0), \quad v = (1,1,\dots,1). $$

Define $f : {0,1}^n \to {0,1}$ by

$$ f(x) = \begin{cases} 1, & x = u \text{ or } x = v, \ 0, & \text{otherwise}. \end{cases} $$

Then $f$ is trivial at exactly two points by construction.

Noncanalizing property

Fix any index $i \in {1,\dots,n}$.

Fiber $x_i = 0$

The point $u = (0,\dots,0)$ lies in this fiber and satisfies $f(u)=1$.

Since $n \ge 2$, choose $j \ne i$ and define

$$ w = u \text{ with the } j\text{-th coordinate flipped to }1. $$

Then $w_i = 0$, $w \ne u,v$, and $f(w)=0$.

Thus the restriction of $f$ to ${x : x_i=0}$ is not constant.

Fiber $x_i = 1$

The point $v = (1,\dots,1)$ lies in this fiber and satisfies $f(v)=1$.

Again choose $j \ne i$ and define

$$ z = v \text{ with the } j\text{-th coordinate flipped to }0. $$

Then $z_i = 1$, $z \ne u,v$, and $f(z)=0$.

Thus the restriction of $f$ to ${x : x_i=1}$ is not constant.

Conclusion for $n \ge 2$

For every variable $x_i$, neither fiber $x_i=0$ nor $x_i=1$ is constant. Hence no variable is canalizing, so $f$ is noncanalizing.

Final conclusion

For $n=1$, no such function exists.
For $n \ge 2$, the function defined above is trivial at exactly two points and is noncanalizing.