8
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ For still more fun show that the power set of a set $X$, together with the xor operation, is a group. And, of course, groups have the cancellation law you ask about. $\endgroup$ – GEdgar Oct 23 '13 at 17:41
  • $\begingroup$ The xor being, in that case, called the symmetric difference. @user101279 : By the way, $\oplus$ is addition modulo $2$. $\endgroup$ – xavierm02 Oct 23 '13 at 18:04
  • $\begingroup$ Remark also that xor is the addition operation when we regard a Boolean algebra as essentially the same as a Boolean ring. $\endgroup$ – user43208 Oct 23 '13 at 18:05
  • $\begingroup$ Think of $\oplus$ as $\neq$. $\endgroup$ – copper.hat Oct 23 '13 at 18:06
  • $\begingroup$ If we omit the question about intersection and union in the last paragraph, this is the same as math.stackexchange.com/questions/294460/… $\endgroup$ – Martin Sleziak Aug 30 '14 at 15:30
8
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.