Take the 2-minute tour ×
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.

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,

Thanks

share|improve this question
2  
Unless if I am missing something, this only seems to be true when $b=C$. –  Ryan Oct 6 '13 at 5:46
1  
Yes, but how to prove it other than using truth table. I think you're saying to prove it using indirect proof? –  Hooman 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

1 Answer 1

$\;\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|improve this answer

Your Answer

 
discard

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.