Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  Dilip Sarwate Dec 18 '12 at 16:32
add comment

1 Answer 1

up vote 1 down vote accepted

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.