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)