Parity of a boolean function

Question

In the following list check all the functions, for which the function parity, gives $1$. All functions in the list map $n$ bit to $1$ bit $n>1$

1. Function f, which returns the least significant bit of its argument

2. Function f_j, which returns the bit with number j of it's argument

3. The constant function $f(x)=1$

4. The constant function $f(x)=0$

5. An indicator (characteristic) function of the set $S={2,4,6,8,10}$

The parity function is defined as: $$y_i = 1-2x_i$$ $$ \text{parity}(y) = \prod_{i=0}^{n-1} y_i$$

Example of evaluating the parity function

An example would be lets take a binary string $x = 1010110110$ the Parity function would give $1$ since even number of ones, otherwise $-1$ if odd number of ones.

Also when asking parity of functions its actually asking the parity of the bit string acquired after plugging in the all the input value of the n-bit function.

For example lets take the option number 3
$$f:\{0,1^n\} \mapsto \{0,1\}$$ $$A\ constant\ function f({x}) = 1$$ Let take $n=4$, For it, all the possible input values $(x)$ a function can take are from $0$ to $15$ and for every value the functional output is $1$.
Hence a we need to calculate the parity of $1111111111111111$ (16 ones) which is $1$

Now my question is ,The option two ($2$), is it Correct? does it always give $1$ (even) as output ? According to the answers of the quiz, it is showing it is correct, but is it? I've run some test on n=4, n=5, unfortunately both are unsatisfying the answer here.
Thank you.

Answer 1

The parity of a Boolean function, $f$, is given by

$$Parity(f) = \prod_{\forall x \in \{0,1\}^n} 1 - 2f(x).$$

Notice that the product ranges over all $x \in \{0,1\}^n$ and that

$$\{0,1\}^n = \{0,1\}^{n-1} \times \{0,1\}.$$

It is possible to factor out one bit, $z \in \{0,1\}$, from the product so that

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\biggr({\prod_{\forall z \in \{0,1\}} 1 - 2f(y,z)}\biggr),$$

and, by expanding the innermost product,

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg),$$

in which $z$ has been substituted with ${\bf 0}$ and ${\bf 1}$.

Now for the special case where $f$ is a Boolean function that returns the least significant bit of the argument, we have that, for all $y \in \{0,1\}^{n-1}$,

$$f(y,{\bf 0}) = {\bf 0}$$ $$f(y,{\bf 1}) = {\bf 1}.$$

Substituting these into the innermost product we find that

$$\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg) \;\; = \;\; -1$$

so that the parity function becomes

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}-1 \;\; = \;\; (-1)^{2^{n-1}}$$

which shows that the function has even parity when $n>1$ and odd parity when $n=1$.

It does not matter that we chose to factor out the least-significant bit. Choosing a bit from anywhere else, $j$, in the input argument would just have given a different order of the products and, since products are commutative, we could rearrange them into exactly the form given above.