<s>[INST] Find the solutions of Boolean equations It's given 4 Boolean equations. I need to find the number of solutions of each.
$a)\  x_{1}x_{2}\oplus x_{2}x_{3}\oplus\ ...\ \oplus\ x_{n-1}x_{n}=1$ 
$b)\ x_{1}x_{2}\vee  x_{2}x_{3}\vee\ ...\ \vee\ x_{n-1}x_{n}=1$
$c)\ x_{1}x_{2}\oplus x_{3}x_{4}\oplus\ ...\ \oplus\ x_{2n-1}x_{2n}=1$
$d)\ x_{1}x_{2}\vee  x_{3}x_{4}\vee\ ...\ \vee\ x_{2n-1}x_{2n}=1$
I have solved $c)$ in the following way. First $2n-2$ variables can have any values. The sum of $\ x_{1}x_{2}\oplus x_{3}x_{4}\oplus\ ...\ \oplus\ x_{2n-3}x_{2n-2}$ can be $0$ or $1$, then the value of $x_{2n-1}x_{2n}$ depends on it so it is fixed. So the number of solutions is $2^{2n-2}$. Is it right?
Please give me solution or hint for the others.
 [/INST] Part d)
There are $4^n$ possible values for $(x_1, x_2, \ldots, x_{2n-1}, x_{2n})$ which
we can divide into $n$ $2$-bit vectors $(x_1,x_2), (x_3,x_4),\ldots, (x_{2n-1},x_{2n})$
each of which can take on $4$ values. Then,
$$x_{1}x_{2}\vee  x_{3}x_{4}\vee\ ...\ \vee\ x_{2n-1}x_{2n}= 0$$
if and only if $(x_1,x_2) \neq (1,1)$ and $(x_3,x_4) \neq (1,1)$ and
$\cdots$ and $(x_{2n-1},x_{2n}) \neq (1,1)$. Thus, $3^n$ of the $4^n$ values
of $(x_1, x_2, \ldots, x_{2n-1}, x_{2n})$ result in the expression above having
value $0$. 

Thus, the number of solutions to
  $x_{1}x_{2}\vee  x_{3}x_{4}\vee\ ...\ \vee\ x_{2n-1}x_{2n}= 1$
  is $4^n-3^n$.

Part c)
Let $x_{2i-1}x_{2i} = y_i$ where we think of $Y_i$ as a 
Bernoulli random variable with parameter $p = \frac{1}{4}$, and
$Z = Y_1+Y_2+\cdots+Y_{n}$ as a binomial random variable with
parameters $(n,p)$. Now, the value of $Z$ is an odd number
if and only if 
$$x_{1}x_{2}\oplus x_{3}x_{4}\oplus\ ...\ \oplus\ x_{2n-1}x_{2n}=1$$
and we have that
$$\begin{align*}P\{Z ~\text{is an odd number}\}
&= \binom{n}{1}p(1-p)^{n-1}+\binom{n}{3}p^3(1-p)^{n-3} + \cdots\\
&= \frac{1}{2}\left[\sum_{j=0}^n \binom{n}{j}p^j(1-p)^{n-j} 
- \sum_{j=0}^n \binom{n}{j}(-1)^jp^j(1-p)^{n-j}\right]\\
&= \frac{1}{2}\left[(p + (1-p))^n - ((1-p)-p)^n\right]\\
&= \frac{1}{2}\left[1 - (1-2p)^n\right]\\
&= \frac{1}{2} - \frac{1}{2^n}.\end{align*}$$
Turning back to Boolean variables, we conclude that 

The
  number of solutions to 
  $x_{1}x_{2}\oplus x_{3}x_{4}\oplus\ ...\ \oplus\ x_{2n-1}x_{2n}=1$
  is $2^{2n-1}-2^{n-1}$.

I will leave it to you to try and apply these ideas to parts a) and b)
</s>