TAOCP 7.1.2 Exercise 6
We prove the statement: A Boolean function $f(x_1,\ldots,x_n)$ is normal (i.
Section 7.1.2: Boolean Evaluation
Exercise 6. [20] True or false: A Boolean function $f(x_1, \ldots, x_n)$ is normal if and only if it satisfies the general distributive law $f(x_1, \ldots, x_n) \wedge y = f(x_1 \wedge y, \ldots, x_n \wedge y)$.
Verified: yes
Solve time: 6m15s
Corrected Solution
We prove the statement:
A Boolean function $f(x_1,\ldots,x_n)$ is normal (i.e. $f(0,\ldots,0)=0$) if and only if
$$ f(x_1,\ldots,x_n)\wedge y ;=; f(x_1\wedge y,\ldots,x_n\wedge y) \quad \text{for all } x_1,\ldots,x_n,y\in{0,1}. $$
(⇒) Identity implies normality
Assume
$$ f(x_1,\ldots,x_n)\wedge y = f(x_1\wedge y,\ldots,x_n\wedge y) $$
holds for all inputs.
Set $y=0$. Then for any $x_1,\ldots,x_n$,
$$ f(x_1,\ldots,x_n)\wedge 0 = 0. $$
On the right-hand side,
$$ f(x_1\wedge 0,\ldots,x_n\wedge 0) = f(0,\ldots,0). $$
Hence,
$$ f(0,\ldots,0)=0, $$
so $f$ is normal.
(⇐) Normality implies the identity
Assume now that
$$ f(0,\ldots,0)=0. $$
We prove the identity directly by case analysis on $y\in{0,1}$.
Let $x=(x_1,\ldots,x_n)$.
Case 1: $y=0$
Left-hand side:
$$ f(x)\wedge 0 = 0. $$
Right-hand side:
$$ f(x_1\wedge 0,\ldots,x_n\wedge 0) = f(0,\ldots,0) = 0, $$
using normality.
Thus both sides are equal.
Case 2: $y=1$
Left-hand side:
$$ f(x)\wedge 1 = f(x). $$
Right-hand side:
$$ f(x_1\wedge 1,\ldots,x_n\wedge 1) = f(x_1,\ldots,x_n) = f(x). $$
Thus both sides are equal.
Since the identity holds in both possible cases for $y$, it holds for all Boolean values of $y$.
Conclusion
Both directions have been established, so the statement is true:
$$ f(x_1,\ldots,x_n)\wedge y ;=; f(x_1\wedge y,\ldots,x_n\wedge y) \quad \Longleftrightarrow \quad f(0,\ldots,0)=0. $$
Resolution of the reviewer’s objections
- No structural representation theorem is needed.
- No induction over Boolean syntax is required.
- Negation plays no role in the argument.
- The proof follows directly from the fact that Boolean variables take only the values $0$ and $1$, so the identity reduces to a two-case verification on $y$.