1
$\begingroup$

Say that we have the following boolean function function ($x_{i} \in \{0,1\}$):

$$f = \sum_{x_1, x_2, x_3, x_4, x_6, x_7 \in \{0,1\}^6} \neg(x_1 \oplus x_4 \oplus x_3 \oplus x_6) \land \neg(x_4 \oplus x_3 \oplus x_2 \oplus x_7)$$

I was trying to evaluate that function.

I realized that the way to evaluate it is by counting how many times both negation functions for the xors are 1 however, I have had a hard time counting in a cleaver way because of the over lap of variables (if we even had more overlaps and more negations being multiplied, I didn't really see how to find a general argument without brute force).

If we only had 4 terms as in:

$$\sum_{x_1, x_4, x_3, x_6 \in \{0,1\}^4 } \neg(x_1 \oplus x_4 \oplus x_3 \oplus x_6)$$

the way I thought of doing this was that the negation function is only 1 when the inside is zero. The inside is zero only when either all $x_i$s are zero or 1, or when pairs of them are 0 or 1. So I thought, there are only 2 values for the whole lot to be the same value, then there are $ \binom {4}{2}$ pairs of these. Each pair could take 2 values, either 1 or zero. Therefore yielding the following count:

$$\binom {4}{2} 2^2 + \binom{4}{4}2 = \binom {4}{2} 2^2 + 2$$

Which I think is correct.

However, when there is a intersection of variables, how do you count this? Do you use the inclusion exclusion principle? I am a little stuck, not sure how to generalize this

$\endgroup$
  • $\begingroup$ On the LHS you have variables but on the RHS you are summing over those same variables. Which is it? Are you summing over all tuples? $\endgroup$ – Alexander Vlasev Nov 12 '14 at 1:57
  • $\begingroup$ variables only take values 1 or 0. Not sure if I understand the confusion, I updated my question though. $\endgroup$ – Pinocchio Nov 12 '14 at 2:06
  • $\begingroup$ The $x_i$'s are not variables for the function $f$ because you can't just plug in some values. So your expression should read as something like $f = \sum_{x_1,\ldots}\cdots$. $\endgroup$ – Alexander Vlasev Nov 12 '14 at 2:16
  • $\begingroup$ @AleksVlasev your right, duh, sorry. $\endgroup$ – Pinocchio Nov 12 '14 at 2:18
1
$\begingroup$

I suggest let $a = x_3 \oplus x_4$, $b = x_1 \oplus x_6$, and $c = x_2 \oplus x_7$

then

$$\sum_{x_1, x_2, x_3, x_4, x_6, x_7} \neg(x_1 \oplus x_4 \oplus x_3 \oplus x_6) \land \neg(x_4 \oplus x_3 \oplus x_2 \oplus x_7)$$

becomes

$$2^3 \sum_{a,b,c} \neg(a \oplus b) \land \neg(a \oplus c)$$

Now apply the observation that binary $\oplus$ is just another way of writing $\ne$, so you get:

$$2^3 \sum_{a,b,c} \neg(a \ne b) \land \neg(a \ne c)$$ $$2^3 \sum_{a,b,c} a = b \land a = c$$ $$2^3 \times 2$$


Edit, adding details

where did you get your $2^3$ at the front

There are 4 values of $\{x_3, x_4\}$. Each value of $x_3 \oplus x_4$ occurs twice. So:

$$\sum_{x_3, x_4} f(x_3 \oplus x_4) = f(1 \oplus 1) + f(1 \oplus 0) + f(0 \oplus 1) + f(0 \oplus 0) = 2f(1) + 2f(0) = 2 \sum_a f(a)$$

Do this a total of 3 times and you get $2^3$.

can you provide details of how you got that 2 on the last equation?

$\sum_{a,b,c} a = b \land a = c$ is asking the question, "how many ways can a,b and c all be equal?". In two ways: $a = b = c = 0$ and $a = b = c = 1$.

$\endgroup$
  • $\begingroup$ where did you get your $2^3$ at the front and can you provide details of how you got that 2 on the last equation? $\endgroup$ – Pinocchio Nov 12 '14 at 2:57
  • $\begingroup$ @Pinocchio Added details $\endgroup$ – DanielV Nov 12 '14 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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