TAOCP 7.1.1 Exercise 126

A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is **canalizing** if there exist an index $i$, a value $a\in\{0,1\}$, and a value $b\in\{0,1\}$ such that x_i=a \;\Rightarrow\; f(x)=b.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.1: Boolean Basics

Exercise 126. [23] (a) Show that a Boolean function is canalizing if and only if its sets of prime implicants and prime clauses have a certain simple property. (b) Show that a Boolean function is canalizing if and only if its Chow parameters $N(f)$ and $\Sigma(f)$ have a certain simple property (see Theorem T). (c) Define the Boolean vectors

$$\vee(f) = \bigvee{x \mid f(x) = 1} \quad \text{and} \quad \wedge(f) = \bigwedge{x \mid f(x) = 1};$$

by analogy with the integer vector $\Sigma(f)$. Show that it's possible to decide whether or not $f$ is canalizing, given only the four vectors $\vee(f)$, $\wedge(f)$, $\wedge(f)$, and $\wedge(\bar{f})$.

Verified: yes
Solve time: 7m33s

Solution to Exercise 7.1.1.126 (corrected)

A Boolean function $f:{0,1}^n \to {0,1}$ is canalizing if there exist an index $i$, a value $a\in{0,1}$, and a value $b\in{0,1}$ such that

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

Equivalently, one cofactor $f_{x_i=a}$ is constant.

(a) Prime implicants and prime clauses

A prime implicant of $f$ is a minimal term implying $f=1$. A prime clause of $f$ is a minimal clause implied by $f=0$, equivalently a prime implicant of $\bar f$.

Claim

$f$ is canalizing if and only if there exists a literal $x_i=a$ that is either a prime implicant of $f$ or a prime clause of $f$.

Proof

(If)

If $x_i=a$ is a prime implicant of $f$, then $x_i=a \Rightarrow f(x)=1$, so $f$ is canalizing.

If $x_i=a$ is a prime clause of $f$, then $x_i=a \Rightarrow f(x)=0$, so $f$ is canalizing.

(Only if)

If $f$ is canalizing via $x_i=a$, then either:

  • $x_i=a \Rightarrow f=1$, so $x_i=a$ is an implicant of $f$, hence a prime implicant after minimization, or
  • $x_i=a \Rightarrow f=0$, so $x_i=a \Rightarrow \bar f=1$, making it a prime implicant of $\bar f$, hence a prime clause of $f$.

(b) Chow parameters

Let

$$ N(f)=|{x:f(x)=1}|,\qquad \sigma_i=\sum_{x:f(x)=1} x_i. $$

Define

$$ A_i = |{x:f(x)=1, x_i=1}|,\quad B_i = |{x:f(x)=1, x_i=0}|. $$

Then

$$ \sigma_i=A_i,\qquad N(f)=A_i+B_i. $$

Canalization analysis

  • If $x_i=a \Rightarrow f=1$, then the entire slice $x_i=a$ lies in $f^{-1}(1)$, so that slice has size $2^{n-1}$ and contributes only to $N(f)$.
  • If $x_i=a \Rightarrow f=0$, then the slice $x_i=a$ contains no 1-inputs, so $A_i=0$ or $B_i=0$.

Thus one of the two slices contributes either all or none of its points to $f^{-1}(1)$, giving:

$$ \sigma_i \in {0,2^{n-1}} \quad \text{or} \quad N(f)-\sigma_i \in {0,2^{n-1}}. $$

Conversely, if one of these equalities holds, then one coordinate slice is monochromatic, so $f$ is canalizing.

(c) Decision from $\vee(f), \wedge(f), \vee(\bar f), \wedge(\bar f)$

Define coordinatewise:

$$ \vee_i(f)=\max{x_i : f(x)=1},\qquad \wedge_i(f)=\min{x_i : f(x)=1}. $$

Thus:

  • $\vee_i(f)=\wedge_i(f)=a$ means all 1-inputs satisfy $x_i=a$.
  • Similarly for $\bar f$, which encodes the 0-inputs of $f$.

Key observation

A function is canalizing iff there exists a coordinate $i$ and value $a$ such that one full slice is monochromatic, i.e. either:

  • all 1-inputs lie in a single slice $x_i=a$, or
  • all 0-inputs lie in a single slice $x_i=a$.

Exact characterization

$f$ is canalizing if and only if there exist $i$ and $a\in{0,1}$ such that either:

  1. (forcing 0 on a slice)

$$ \vee_i(f)=\wedge_i(f)=1-a, $$

meaning all 1-inputs satisfy $x_i=1-a$, hence the slice $x_i=a$ contains no 1-inputs and is therefore all 0s. 2. (forcing 1 on a slice)

$$ \vee_i(\bar f)=\wedge_i(\bar f)=1-a, $$

meaning all 0-inputs satisfy $x_i=1-a$, hence the slice $x_i=a$ contains no 0-inputs and is therefore all 1s.

Justification

(If)

If either condition holds, then one coordinate slice contains no 1s or no 0s, so fixing $x_i=a$ forces $f$ to be constant.

(Only if)

If $f$ is canalizing via $x_i=a$, then one slice $x_i=a$ is constant. Hence either all 1-inputs avoid that slice or all 0-inputs avoid that slice, giving one of the two extremal conditions above.

Summary

  • (a) Canalizing iff some literal is a prime implicant of $f$ or a prime clause of $f$.
  • (b) Canalizing iff for some $i$,

$$ \sigma_i \in {0,2^{n-1}}\ \text{or}\ N(f)-\sigma_i \in {0,2^{n-1}}. $$

  • (c) Canalizing is decidable from $\vee(f),\wedge(f),\vee(\bar f),\wedge(\bar f)$ because it is equivalent to the existence of a coordinate $i$ for which all 1-inputs or all 0-inputs lie in a single fixed slice, detectable by equality of the corresponding extremal vectors.