TAOCP 7.1.1 Exercise 125
A Boolean function $f(x,y)$ is canalizing if there exists a variable, say $x$, and a value $a \in {0,1}$ such that $f(a,y)$ is independent of $y$, and therefore constant as a function of $y$.
Exercise 125. [18] Which of the function classes in (95) are canalizing?
Verified: yes
Solve time: 1m33s
Solution
A Boolean function $f(x,y)$ is canalizing if there exists a variable, say $x$, and a value $a \in {0,1}$ such that $f(a,y)$ is independent of $y$, and therefore constant as a function of $y$. The same condition is required with the roles of $x$ and $y$ interchanged.
The classes in (95) correspond to the Boolean functions listed in Table 1, grouped by their standard logical interpretations: constants, projections, conjunction and disjunction with possible negations, implication-type operations, and the two parity-type operations $\oplus$ and $\equiv$.
The constant functions $0$ and $1$ are canalizing because fixing either variable leaves the value unchanged, hence independent of the remaining variable. Each projection function $x$ and $y$ is canalizing because fixing the variable on which the function depends yields a constant value, and fixing the other variable leaves the function unchanged and therefore still independent of that variable. The negations $\bar{x}$ and $\bar{y}$ behave in the same way, since fixing the relevant variable determines a constant output.
For conjunction and its variants, canalization occurs through a forcing value. For $x \wedge y$, setting $x=0$ yields $f(0,y)=0$ for both $y=0$ and $y=1$, and setting $y=0$ yields the same constant value, so the function is canalizing. For disjunction $x \vee y$, setting $x=1$ gives $f(1,y)=1$ for all $y$, and setting $y=1$ gives the same constant value, so it is canalizing. The same reasoning applies to all functions obtained from these by negating one argument or the output, since negation preserves the property that one input value forces a constant output.
For implication $x \supset y$ (equivalently $\bar{x} \vee y$), fixing $x=0$ yields $f(0,y)=1$ independent of $y$, so this function is canalizing. For converse implication $x \leftarrow y$ (equivalently $x \vee \bar{y}$), fixing $y=0$ yields $f(x,0)=1$ independent of $x$, so this function is also canalizing. The same argument applies to the remaining non-equivalence, nonimplication, NAND, and NOR functions, since each contains a row in its truth table where a single input value forces all outputs in that row to be identical.
The exclusive-or function $x \oplus y$ is not canalizing. Fixing $x=0$ gives $f(0,y)=y$, which depends on $y$, and fixing $x=1$ gives $f(1,y)=\bar{y}$, which also depends on $y$. The same holds symmetrically for fixing $y$, so no input value forces a constant output. The equivalence function $x \equiv y$ behaves identically up to complementation, since fixing $x=0$ yields $f(0,y)=\bar{y}$ and fixing $x=1$ yields $f(1,y)=y$, both depending on $y$.
Every other function in (95) has at least one input assignment that forces a constant value independent of the remaining variable, and therefore each of those functions is canalizing.
The only functions for which no such forcing assignment exists are $x \oplus y$ and $x \equiv y$.
This completes the classification. ∎