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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove Whether this statement is True or False:

Other than solving by Truth Table

If $A \oplus b = A \oplus C$ then $A=C$

I saw this question online and I've been thinking about it for days now and I'm pretty sure this question may have been asked already but I didn't it so far,


share|cite|improve this question
Unless if I am missing something, this only seems to be true when $b=C$. – Ryan Oct 6 '13 at 5:46
Yes, but how to prove it other than using truth table. I think you're saying to prove it using indirect proof? – Node.JS Oct 6 '13 at 5:48
It suffices to prove only the case where $A$, $b$ and $C$ are single-bits (assuming a bitwise XOR). You can then further reduce this down into two cases: where $b=C$, and where $b= \neg C$. – Ryan Oct 6 '13 at 5:55
If you consider arithmetic mod 2 (in $\mathbb{Z}_2$) then XOR is really just addition. I think that simplifies the picture a lot! – Evan Oct 6 '13 at 18:28
up vote 2 down vote accepted

$\;\oplus\;$ ('exclusive or') is just the opposite of boolean equivalence, which I usually write as $\;\equiv\;$. So $\;\oplus\;$ is just $\;\not\equiv\;$.

Since $\;\equiv\;$ is associative (which you may or not be allowed to use, if not you'll have to prove it first), it is allowed to leave out parentheses in the middle lines below, and calculate \begin{align} & (A \not\equiv b) \equiv (A \not\equiv C) \\ \equiv & \;\;\;\;\;\text{"negate both sides of $\;\equiv\;$"} \\ & A \equiv b \equiv A \equiv C \\ \equiv & \;\;\;\;\;\text{"symmetry of (middle) $\;\equiv\;$"} \\ & A \equiv A \equiv b \equiv C \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & b \equiv C \\ \end{align}

Note that if you're allowed to use that $\;\equiv\;$ and $\;\not\equiv\;$ are mutually associative, then the proof becomes even shorter.

share|cite|improve this answer

Your Answer


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.