Minimum Nonlinearity of boolean function I have studied many literature on boolean functions. The nonlinearity of a boolean function is defined as min of hamming distance of the function from all the linear functions in the set. There is also formulas for calculating nonlinerity of boolean function  in terms of no of inputs (n). Now i have following two doubts


Is the nonlinearity of all boolean functions in the same boolean space(say V5) is same or different for different functions ? IF different then how to calculate nonlinearity of each one seperatly ?
How to calculate minimum nonlinearity of a given boolean function in a given boolean space say(V5).
You can give a boolean function by it's truth table.
For example if $f(x, y, z) = x + z$ you have the following truth table:

  x   y   z   f(x, y, z) = x + z
 ----------------------
  0   0   0     0
  0   0   1     1
  0   1   0     0
  0   1   1     1
  1   0   0     1
  1   0   1     0
  1   1   0     1
  1   1   1     0


just enumerating the last columns gives you $(0, 1, 0, 1, 1, 0, 1, 0)$. This $f$ is by its definition clearly a linear function. If you want to enumerate all linear functions you can look at the Hadamard matrix and Hadamard transform.

To calculate the linearity of a boolean function $g$ as explained in this question you take the minimum Hamming distance between the output vector of $g$ and all linear functions.

So if your function would for example be $g = (1, 0, 0, 0, 1, 1, 0, 1)$ the Hamming distance to $f$ would be.

g: 1 0 0 0 1 1 0 1
f: 0 1 0 1 1 0 1 0
------------------
   1 1 0 1 0 1 1 1 =&gt; HD 6 =&gt; non-linearity at most 6


In fact if you where to try all linear functions you would find $h = (0, 0, 0, 0, 1, 1, 1, 1)$ with 

g: 1 0 0 0 1 1 0 1
h: 0 0 0 0 1 1 1 1
------------------
   1 0 0 0 0 0 1 0 =&gt; HD 2


and this is the lowest value so the non-linearity of $g$ is 2.

I hope this answers your second question.

Now we can answer your first question simply by finding examples.
Here are two 4-bit functions with different non-linearity:


[1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
Non-linearity here is 2. It cannot be more than 2 because the middle two bits are swapped from

[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0] 
which is clearly linear (depends only on highest value bit). And it cannot be less than 2 because the function is non-linear and balanced.
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0] has non-linearity 4.


This, I hope answers your first questions negatively. Not all functions have the same non-linearity.