XOR VS $(a-b)^2$

87 Views Asked by At

These two well-known identities are really similar.

$$(a-b)^2=a^2+b^2-2ab$$ $$|A\Delta B|=|A|+|B|-2|A\cap B|$$

Is there any deep connection or ideally a generalization of this formula for an abstraction of these spaces?

....

PS. I know you can consider the operation $\Delta$ like sum modulo 2 and intersection as product modulo 2. And squaring is somehow like inner product. But I couldn't find a deep connection.

1

There are 1 best solutions below

1
On BEST ANSWER

If $a(x)$ and $b(x)$ are the indicator functions for sets $A$ and $B$ respectively ($a(x) = 1$ when $x \in A$, $0$ when $x \notin A$), then

$$ \eqalign{|A \Delta B| &= \sum_x (a(x)-b(x))^2\cr &= \sum_x \left(a(x)^2 + b(x)^2 - 2 a(x) b(x)\right)\cr &= \sum_x a(x) + \sum_x b(x) - 2 \sum_x a(x) b(x) \cr &= |A| + |B| - 2 |A\cap B|}$$