Evaluating the boolean sum $\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) \neg(x_4 \oplus x_3 \oplus x_2 \oplus x_7)$

Question

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

Answer 1

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$.