How can I prove that $(a + b )\oplus(a + c)$ is not possible to simplify. Or is it? I was trying to simplify the following expression $(a + b )\oplus(a + c)$, where $+$ is just a simple addition of two numbers and $\oplus$ is a binary xor operation. By simplifying I mean exanding or finding any alternative form.
After a couple of attempts I was not able to find any simplification and started to think that it is impossible. But I do not have any justification for this except of handwaving like this 'xor operates on individual bits, and is incompatible with normal summation'. This looks closer to a joke then to a normal proof.
So how can one prove that you can't simplify this expression? Or can it be simplified?
 A: Essentialy you ask about expressing bitwise operation in terms of other functions. I cannot prove those can or cannot be simplified, but I want to share some thoughts which can maybe lead you onto something.
Three "main" bitwise operations, AND, OR and XOR are "distorted" $min$, $max$ and $abs(a-b)$ (absolute value) functions. It can be easily seen when you write output of any of those functions as two dimensional table for numbers greater than 1.
Example of $min$, $max$ and $abs$ for 2-bit numbers:
$$
% outer vertical array of arrays
\begin{array}{c}
% inner horizontal array of arrays
\begin{array}{ccc}
% inner array of minimum values
\begin{array}{c|cccc}
\text{min} & 0 & 1 & 2 & 3\\
\hline
0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 1\\
2 & 0 & 1 & 2 & 2\\
3 & 0 & 1 & 2 & 3
\end{array}
&
% inner array of maximum values
\begin{array}{c|cccc}
\text{max}&0&1&2&3\\
\hline
0 & 0 & 1 & 2 & 3\\
1 & 1 & 1 & 2 & 3\\
2 & 2 & 2 & 2 & 3\\
3 & 3 & 3 & 3 & 3
\end{array}
\end{array}
&
% inner array of delta values
\begin{array}{c|cccc}
abs(a-b)&0&1&2&3\\
\hline
0 & 0 & 1 & 2 & 3\\
1 & 1 & 0 & 1 & 2\\
2 & 2 & 1 & 0 & 1\\
3 & 3 & 2 & 1 & 0
\end{array}
\end{array}
$$
Now those are tables for AND, OR, XOR:
$$
% outer vertical array of arrays
\begin{array}{c}
% inner horizontal array of arrays
\begin{array}{ccc}
% inner array of minimum values
\begin{array}{c|cccc}
\text{AND} & 0 & 1 & 2 & 3\\
\hline
0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1\\
2 & 0 & 0 & 2 & 2\\
3 & 0 & 1 & 2 & 3
\end{array}
&
% inner array of maximum values
\begin{array}{c|cccc}
\text{OR}&0&1&2&3\\
\hline
0 & 0 & 1 & 2 & 3\\
1 & 1 & 1 & 3 & 3\\
2 & 2 & 3 & 2 & 3\\
3 & 3 & 3 & 3 & 3
\end{array}
\end{array}
&
% inner array of delta values
\begin{array}{c|cccc}
\text{XOR}&0&1&2&3\\
\hline
0 & 0 & 1 & 2 & 3\\
1 & 1 & 0 & 3 & 2\\
2 & 2 & 3 & 0 & 1\\
3 & 3 & 2 & 1 & 0
\end{array}
\end{array}
$$
As you see, the differences are on (1,2) and (2,1). If you could see tables for 4, 8 or 16 bit numbers, you would quickly recognize that those differences occur for numbers with specific bits set or not set. So in fact you could write:
$$
xor(a,b) = \sqrt{(a-b)^2} + f(a,b)
$$
Where $f(a,b)$ is a function correcting for those "distortions".
Now, because $min$ and $max$ can be expressed with $abs$ and AND and OR can be expressed as XOR (you can easily find formulas for that), the only thing to do is to find this mysterious $f(a,b)$. Now this is the hardest part as this function seems to deal specifically with bits and their configurations and it seems to me that this is impossible to avoid some integer arithmetic functions like integer division, floor, ceiling as you need individual bits. But this does not simplify anything at all, as that is precisely original problem with simplyfing XOR: how not to calculate on individual bits. It just makes it much more visible that you can't escape the bit part. This may lead you to some idea of proof that XOR cannot be simplified.
Another thing you can do to try simplify XOR is to make some use of finite sums. Bitwise operations can be expressed in terms of finite sums as binary numbers are results of finite sums of powers of 2. Someone already shared some on Stack Exchange, but this is easy to derive them without much effort:
$$
xor(a,b)=\sum_{n=0}^{\lfloor log_2(max(a,b))\rfloor}2^n\left\lvert\left\lfloor \frac{a}{2^n} \right\rfloor mod 2 - \left\lfloor \frac{b}{2^n} \right\rfloor mod 2 \right\rvert
$$
This is $xor$ of all individual bits between two numbers. Absolute value and $mod 2$ can be expressed in basic algebraic operations but you'll still have to deal somehow with floor operation and $log_2$. Eventually, you could rewrite it as infinite sum. This could be interesing and maybe with some more advanced mathematics used something new could be found.
If you happen to find some solution to the problem you stated, please share it under your question. I'll be very interested.
