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 XOR y) = f(x) XOR 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, f(100),f(010) and f(001) have 2 options each 0 or 1.
So, the number functions possible is 2^{3} = 8.
Now, come 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 XOR 100) = f(100) XOR f(100) = 0 XOR 0 = 0
f(101) = f(100 XOR 001) = f(100) XOR f(001) = 0 XOR 0 = 0
f(110) = f(100 XOR 010) = f(100) XOR f(010) = 0 XOR 0 = 0
f(011) = f(010 XOR 001) = f(010) XOR f(001) = 0 XOR 0 = 0
f(111) = f(100 XOR 011) = f(100) XOR f(011) = f(100) XOR f(010) XOR 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, generalise the problem suppose the function is from {0,1}^{n} to {0,1}
In this case if we fix the values of f(100...0),f(010...0),f(001...0),.....,f(000...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...0) , f(010...0) , f(001...0),.....,f(000...1) has 2 options each 0 or 1.
So, the number of functions possible is 2^{n}. (Answer)