TAOCP 7.1.1 Exercise 10
From the definition of the “random” function (22) in TAOCP, the Boolean function on two variables is f(0,0)=0,\quad f(1,0)=1,\quad f(0,1)=1,\quad f(1,1)=1.
Exercise 10. [17] [17] What is the multilinear representation of the "random" function (22)?
Verified: yes
Solve time: 5m01s
From the definition of the “random” function (22) in TAOCP, the Boolean function on two variables is
$$ f(0,0)=0,\quad f(1,0)=1,\quad f(0,1)=1,\quad f(1,1)=1. $$
This is the truth table of the disjunction (logical OR).
We now compute its multilinear representation over $\mathbb{F}_2$.
Step 1: General form
A Boolean function of two variables has the multilinear (algebraic normal) form
$$ f(x,y)=a_0 \oplus a_1 x \oplus a_2 y \oplus a_3 xy. $$
Step 2: Determine coefficients from the truth table
From $(x,y)=(0,0)$:
$$ a_0 = f(0,0)=0. $$
From $(x,y)=(1,0)$:
$$ 1 = f(1,0)=a_0 \oplus a_1 = 0 \oplus a_1, \quad \Rightarrow \quad a_1=1. $$
From $(x,y)=(0,1)$:
$$ 1 = f(0,1)=a_0 \oplus a_2 = 0 \oplus a_2, \quad \Rightarrow \quad a_2=1. $$
From $(x,y)=(1,1)$:
$$ 1 = f(1,1)=a_0 \oplus a_1 \oplus a_2 \oplus a_3. $$
Substitute known values:
$$ 1 = 0 \oplus 1 \oplus 1 \oplus a_3. $$
Simplify in $\mathbb{F}_2$:
$$ 1 \oplus 1 = 0, \quad \text{so} \quad 1 = a_3. $$
Thus:
$$ a_3 = 1. $$
Step 3: Multilinear representation
Substituting all coefficients:
$$ f(x,y)=x \oplus y \oplus xy. $$
Final answer
$$ \boxed{f(x,y)=x \oplus y \oplus xy} $$
This is the multilinear (algebraic normal form) representation of function (22).