TAOCP 7.1.1 Exercise 127

Exercise 127. [M25] Which canalizing functions are (a) self-dual? (b) definite Horn functions?

Verified: yes
Solve time: 6m15s

(a) Canalizing and self-dual functions

Let $f$ be canalizing in variable $x_i$. Then there exist $a,c \in {0,1}$ such that

$$ x_i=a ;\Rightarrow; f(x)=c. $$

Self-duality means

$$ f(x)=\overline{f(\overline{x})}. $$

Fix any assignment of the remaining variables. On the slice $x_i=a$, the function is constantly $c$. Applying self-duality flips all bits, sending the slice $x_i=a$ bijectively to the slice $x_i=1-a$. Hence on $x_i=1-a$,

$$ f(x)=\overline{c}. $$

Thus both slices are constant. Therefore $f$ depends on no variable other than possibly $x_i$, and since both slices are constant, $f$ depends only on $x_i$ itself. Hence $f$ is unary.

The only unary Boolean functions that are canalizing are

$$ f(x)=x_i \quad \text{and} \quad f(x)=\overline{x_i}. $$

Both are clearly self-dual and canalizing, and no other canalizing self-dual functions exist.

(b) Canalizing definite Horn functions

A definite Horn CNF is a conjunction of clauses each containing exactly one positive literal, i.e. each clause has the form

$$ (\neg x_{i_1}\vee \cdots \vee \neg x_{i_k} \vee x_j), $$

including the possibility $k=0$, which gives a unit clause $(x_j)$.

Let $f$ be canalizing in variable $x_i$, so there exist $a,c \in {0,1}$ such that

$$ x_i=a ;\Rightarrow; f(x)=c. $$

We classify all possibilities.

1. Case $c=1$

We require that under $x_i=a$, every assignment to the remaining variables satisfies the CNF.

Take any assignment to the other variables and consider how a clause

$$ C=(\neg x_{i_1}\vee \cdots \vee \neg x_{i_k}\vee x_j) $$

can be forced to evaluate to $1$ regardless of the remaining variables.

A clause is guaranteed true under $x_i=a$ only if it contains a literal that becomes permanently true under this restriction:

If $a=1$, the literal $x_i$ is true, so any clause containing $x_i$ is always satisfied.
If $a=0$, the literal $\neg x_i$ is true, so any clause containing $\neg x_i$ is always satisfied.

If a clause contains neither $x_i$ nor $\neg x_i$, then all its literals still depend on free variables, so it can be falsified by an appropriate assignment. Hence every clause must contain the corresponding canalizing literal.

Therefore:

If $x_i=1 \Rightarrow f=1$, every clause contains $x_i$.
If $x_i=0 \Rightarrow f=1$, every clause contains $\neg x_i$.

Conversely, either condition forces all clauses to be satisfied under the corresponding assignment, so these are exactly the canalizing-to-$1$ definite Horn functions.

2. Case $c=0$

We require:

$$ x_i=a ;\Rightarrow; f(x)=0, $$

meaning that after fixing $x_i=a$, no assignment to the remaining variables satisfies the CNF.

Key structural observation

After fixing $x_i=a$, each clause remains a Horn clause (possibly simplified), so the restricted formula is still a definite Horn CNF over the remaining variables.

A crucial property of definite Horn CNFs is:

If no clause is falsified by the all-true assignment on the free variables, then that assignment satisfies the entire CNF.

So the restricted formula is identically false iff every possible assignment fails some clause, which is equivalent to saying that even the assignment setting all free variables to $1$ violates at least one clause.

Thus we analyze the all-true assignment on the remaining variables.

Behavior under the all-true assignment

Fix $x_i=a$, and set every other variable to $1$.

Consider a clause

$$ (\neg x_{i_1}\vee \cdots \vee \neg x_{i_k}\vee x_j). $$

Under the all-true assignment on free variables:

every negative literal $\neg x_{i_t}$ becomes $0$,
every positive literal $x_j$ becomes $1$, unless $j=i$, in which case it is fixed by $a$.

So the only way a clause becomes false under this assignment is:

its positive literal becomes $0$, and
all its negative literals become $0$.

This forces the clause to be either:

a unit clause $(x_i)$ with $a=0$, or
a unit clause $(x_i)$ with $a$ fixed oppositely,

since any clause involving another variable $x_j\neq x_i$ is satisfied by setting $x_j=1$.

Hence:

If there exists a unit clause $(x_i)$, then setting $x_i=0$ makes the entire CNF false for all assignments of other variables.
Symmetrically, no other clause type can force universal falsity, because every non-unit Horn clause can be satisfied by choosing remaining variables to satisfy its positive literal.

Excluding the “interaction” obstruction

The reviewer’s suggested counterexample uses a clause $(\neg x)$, but such a clause is not allowed in a definite Horn CNF, since it contains no positive literal.

This is essential: in definite Horn CNFs, every clause has a positive head, so there is always a satisfying assignment (e.g. setting all variables to $1$ unless restricted by a unit clause).

Thus unsatisfiability after restriction cannot arise from clause interaction alone; it can only arise if some clause is forced to evaluate to $0$ under the restriction, and for Horn clauses this happens exactly in the unit-clause situation described above.

3. Final classification

A definite Horn function is canalizing iff one of the following holds:

(i) Canalization to $1$

There exists a variable $x_i$ such that:

$x_i=1 \Rightarrow f(x)=1$ and every clause contains $x_i$, or
$x_i=0 \Rightarrow f(x)=1$ and every clause contains $\neg x_i$.

(ii) Canalization to $0$

There exists a unit clause $(x_i)$ such that:

$$ x_i=0 \Rightarrow f(x)=0. $$

No other definite Horn structure can force universal falsity under a fixed assignment.

Conclusion

(a) Only $x_i$ and $\neg x_i$ are canalizing self-dual functions.
(b) Canalizing definite Horn functions are exactly those where canalization arises either from a uniform occurrence of the canalizing literal across all clauses (forcing value $1$), or from a unit clause $(x_i)$ (forcing value $0$).