Take an example
Suppose the function $f$ is from $\{0,1\}^3$ to $\{0,1\}$
Now, here we have to find the number of functions possible from $\{0,1\}^3$ to $\{0,1\}$ such that
$f (x \oplus y) = f(x) \oplus f(y)$
Now, observe that if we maintain the linearity of XOR then the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001)$ (Reason given below)
So, if we fix the values of $f(100),f(010)$ and $f(001)$ then we will get the whole function.
Now, each of $f(100),f(010)$ and $f(001)$ has $2$ options, either $0$ or $1.$
So, the number of linear functions possible is $2^3 = 8.$
Now, we can see how the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001).$
Let $f(100) = 0 , f(010) = 0 , f(001) = 0$
Now,
- $f(000) = f(100 \oplus 100) = f(100) \oplus f(100) = 0 \oplus 0 = 0$
- $f(101) = f(100 \oplus 001) = f(100) \oplus f(001) = 0 \oplus 0 = 0$
- $f(110) = f(100 \oplus 010) = f(100) \oplus f(010) = 0 \oplus 0 = 0$
- $f(011) = f(010 \oplus 001) = f(010) \oplus f(001) = 0 \oplus 0 = 0$
- $f(111) = f(100 \oplus 011) = f(100) \oplus f(011) = f(100) \oplus f(010) \oplus f(001) = 0$
So, we have seen how the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001)$
Now, suppose the function is from $\{0,1\}^n$ to $\{0,1\}$
In this case if we fix the values of $f(100\ldots 0),f(010\ldots 0),f(001\ldots 0),\ldots ,f(000\ldots 1)$ then we will get the whole function since rest of the values are dependent on the above $n$ values.
Now, each of the $n$ values $f(100\ldots 0),f(010\ldots 0),f(001\ldots 0),\ldots ,f(000\ldots 1)$ has $2$ options - either $0$ or $1.$
So, the number of linear functions possible is $2^n$.
Correct Answer: $E$