$A \oplus B = A \oplus C$ imply $B = C$?

Question

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving problems with them or proving equalities I have no idea how to use $\oplus$.

For example: I'm trying to do a problem in which I have to prove or disprove with a counterexample whether or not $A \oplus B = A \oplus C$ implies $B = C$ is true.

I know that the venn diagram of $\oplus$ in this case includes the regions of A and B excluding the areas they overlap. And similarly it includes regions of A and C but not the areas they overlap. It would look something like this:

I feel the statement above would be true just by looking at the venn diagram since the area ABC is included in the $\oplus$, but I'm not sure if that's an adequate enough proof. On the other hand, I could be completely wrong about my reasoning.

Also just for clarity's sake: Would $A\cup B = A \cup C$ and $A \cap B = A \cap C$ be proven in a similar way to show whether or not the conditions imply $B = C$? A counterexample/ proof of this would be appreciated as well.

Answer 1

Think of $\oplus$ as $\neq$. That is $A \oplus B$ iff $A \neq B$.

Note that $A \oplus A$ is always false, and $\text{False}\oplus A = A$.

Then $A \oplus (A \oplus B) = (A \oplus A) \oplus B = \text{False} \oplus B = B $.

Similarly, $A \oplus (A \oplus C) = C$, hence $B=C$.

Aside: A 'cute' (as in amusing but not of any practical significance) use of $\oplus$ is to swap the values of two bit variables in a programming language without using an intermediate variable: \begin{eqnarray} x = y \oplus x \\ y = y \oplus x \\ x = y \oplus x \\ \end{eqnarray} Show that the values of $x,y$ are swapped!

Answer 2

Hint: $A\oplus(A\oplus B)=(A\oplus A)\oplus B = B$.

And of course $A\cup B=A\cup C$ does not imply $B=C$ (consider the case $B=A\ne \emptyset = C$). And $A\cap B=A\cap C$ does not imply $B=C$ either (consider the case $A=\emptyset$)

Answer 3

Hint: $\oplus$ is associative with unit $\emptyset$, and $A \oplus A = \emptyset$. Does this give you an idea for canceling?

Answer 4

This can be done using a simple calculation. But I don't know how to interpret your question, so I'll give two answers. :-)

---

I'm assuming $\;A,B,C\;$ are booleans. I will write $\;\not\equiv\;$ instead of $\;\oplus\;$, and $\;\equiv\;$ instead of $\;=\;$ on booleans.

First, note that $\;\equiv\;$ and $\;\not\equiv\;$ are not only both associative, but they are also mutually associative. Therefore no parentheses are needed in the following calculation.

We can now simplify $\;A \oplus B = A \oplus C\;$ as follows: \begin{align} & A \not\equiv B \equiv A \not\equiv C \\ \equiv & \;\;\;\;\;\text{"rearrange"} \\ & A \not\equiv A \equiv B \not\equiv C \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{false} \equiv B \not\equiv C \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & B \equiv C \\ \end{align}

---

If instead $\;A,B,C\;$ are sets, and your $\;\oplus\;$ is the symmetric difference of two sets (which is normally written as $\;\triangle\;$), then the proof is slightly longer, but with essentially the same structure.

The simplest definition of symmetric difference is $$ x \in A \oplus B \equiv x \in A \not\equiv x \in B $$

We can expand the definitions and simplify using logic, as follows: \begin{align} & A \oplus B = A \oplus C \\ \equiv & \;\;\;\;\;\text{"set extensionality; definition of $\;\oplus\;$, twice"} \\ & \langle \forall x :: x \in A \not\equiv x \in B \equiv x \in A \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rearrange"} \\ & \langle \forall x :: x \in A \not\equiv x \in A \equiv x \in B \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: \text{false} \equiv x \in B \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: x \in B \equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & B = C \\ \end{align}

---

In both cases, we have found a stronger conclusion than was asked: we proved equivalence of the two expressions.

Answer 5

You asked this additional question in the last paragraph:

Also just for clarity's sake: Would $A\cup B = A \cup C$ and $A \cap B = A \cap C$ be proven in a similar way to show whether or not the conditions imply $B = C$? A counterexample/ proof of this would be appreciated as well.

---

$A\cup B=A\cup C$ $\Rightarrow$ $B=C$ is not true in general.

Counterexample: Take any non-empty set $A$ and also take $B=A$ and $C=\emptyset$. Then $A\cup B=A\cup C=A$, but $B\ne C$.

---

$A\cap B=A\cap C$ $\Rightarrow$ $B=C$ is not true in general.

Take some element $x\notin A$ and put $B=A$, $C=A\cup\{x\}$. Then $A\cap B=A\cap C=A$, but $B\ne C$.