3
$\begingroup$

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.

  • 0
    c) is a classical form of what is called a _bent function_ of $2n$ binary variables. It also arises in coding theory in studies of _subcodes of the second-order Reed-Muller codes_ and its image is one of the sequences in the _small set of Kasami sequences_ used in direct-sequence spread-spectrum communications. See papers by Kasami, Berlekamp, Berlekamp and Sloane published in the late 1960s and early 1970s. Incidentally, your calculation of $2^{2n-2}$ is not correct. For b) and d) consider what values the variables must have to get the OR to equal $0$.2012-12-18

1 Answers 1

1

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)