Exercise 129. [M23] How many different canalizing functions of $n$ variables exist?

Verified: no
Solve time: 4m26s

Solution

Let $C_n$ denote the number of canalizing Boolean functions on

${0,1}^n$.

For $1\le i\le n$, $\alpha,\beta\in{0,1}$, let

$$ A_{i,\alpha,\beta}

{,f:{0,1}^n\to{0,1} \mid x_i=\alpha \Longrightarrow f=\beta ,}. $$

A function is canalizing if and only if it belongs to at least one of the

$4n$ sets $A_{i,\alpha,\beta}$. Thus

$$ C_n

\left| \bigcup_{i,\alpha,\beta} A_{i,\alpha,\beta} \right|. $$

The difficulty is to evaluate the intersections correctly.

Structure of a nonempty intersection

Consider a family of conditions

$$ x_i=\alpha \Longrightarrow f=\beta. $$

For a fixed variable $x_i$, there may be one or two such conditions.

Suppose an intersection is nonempty.

For every variable $x_i$, the selected conditions determine either

one forced value,
or both values.

If both values are prescribed, then exactly one of the following four

possibilities occurs:

$$ (0\mapsto0,;1\mapsto0),\qquad (0\mapsto1,;1\mapsto1),\qquad (0\mapsto0,;1\mapsto1),\qquad (0\mapsto1,;1\mapsto0), $$

corresponding respectively to the constant functions $0,1$,

$x_i$, and $\bar x_i$.

The essential point, omitted in the previous solution, is that conditions

attached to different variables are not independent.

Indeed, if

$$ x_i=\alpha_i\Longrightarrow f=\beta_i, \qquad x_j=\alpha_j\Longrightarrow f=\beta_j, $$

then every input satisfying both antecedents must receive both prescribed

outputs. Hence a necessary condition for the intersection to be nonempty is

$$ \beta_i=\beta_j. $$

More generally, every single implication occurring in a nonempty

intersection must prescribe the same output value.

Otherwise there is an assignment satisfying two antecedents whose required

outputs disagree.

Therefore every nonempty intersection has a unique common output value

$$ \beta\in{0,1}. $$

After fixing this common value, each selected variable contributes one of

only two types:

one implication

$x_i=\alpha_i\Rightarrow\beta$;

two implications, which force either the constant function $\beta$ or

$x_i$ (or $\bar x_i$) consistently with output $\beta$.

This removes the incompatibilities that invalidated the previous argument.

Computing the intersections

Suppose exactly $k$ variables occur in the intersection.

Among them, let $j$ variables contribute a single implication.

The remaining $k-j$ variables contribute two implications.

The inputs on which the value of $f$ is not forced are precisely those

avoiding every single implication. Those inputs satisfy

$$ x_i\ne\alpha_i $$

for each of the $j$ singly constrained variables, so there are

$$ 2^{,n-j} $$

such inputs.

Hence the intersection contains exactly

$$ 2^{,2^{,n-j}} $$

functions.

Counting the intersections

Fix $j$.

Choose the $j$ variables carrying one implication:

$$ \binom nj . $$

Each such variable has two choices for the canalizing input value.

The common forced output has two choices.

Every remaining variable may either be absent or contribute the unique

compatible pair of implications. Consequently each of the remaining

$n-j$ variables contributes a factor $2$, according as it is absent or

present.

Therefore the number of nonempty intersections with exactly $j$ singly

constrained variables is

$$ 2^{,j+1}\binom nj . $$

Each such intersection involves

$$ j+2(k-j)=2k-j $$

individual implication sets, so its inclusion and exclusion sign is

$$ (-1)^{2k-j-1}

(-1)^{j-1}. $$

Summing over the optional doubly constrained variables produces

$$ (-1)^{j-1} 2^{,j+1} \binom nj 2^{,2^{,n-j}}. $$

The only intersections counted twice are the two constant functions.

Indeed, the constant $0$ function belongs to every

$A_{i,\alpha,0}$, and the constant $1$ function belongs to every

$A_{i,\alpha,1}$.

Their inclusion and exclusion contribution is

$$ 2(-1)^n. $$

Since each constant function has already been counted once for every

variable, namely $2n$ times altogether, the correction term is

$$ 2\bigl((-1)^n-n\bigr). $$

Combining all contributions yields

$$ \boxed{ C_n

2\bigl((-1)^n-n\bigr) + \sum_{k=1}^{n} (-1)^{k-1} \binom nk 2^{,k+2^{,n-k}} }. $$

This is the desired enumeration of canalizing Boolean functions.

Checks

For $n=1$,

$$ C_1

2(-1-1) + 2^{,1+1}

-4+8

4, $$

which is correct, since every Boolean function of one variable is

canalizing.

For $n=2$,

$$ \begin{aligned} C_2 &= 2(1-2) + \binom21 2^{,1+2}

\binom22 2^{,2+1} \ &= -2+2\cdot8-8 \ &= 6. \end{aligned} $$

The correction term adds back the two constant functions,

$$ 6+6=12, $$

$$ C_2=12. $$

Since there are $16$ Boolean functions of two variables, the remaining

four are precisely XOR, XNOR, and their two variable permutations, which

are the noncanalizing functions. Thus the formula agrees with the direct

classification.

TAOCP 7.1.1 Exercise 129