# commutative operation

• Jul 19th 2010, 11:10 PM
demode
commutative operation
Here's a question:
http://img826.imageshack.us/img826/6948/80437125.gif

For part (a) is it sufficient to show using the commutative law of union and the commutative law of intersection that:

$\displaystyle (A \star B) = (A \cup B) \backslash (A \cap B)$

$\displaystyle = (B \cup A) \backslash (B \cap A) = (B \star A)$

Or do I need to show some other steps?

Also, could anyone please show me how to prove that:

$\displaystyle (A \star B) \star C = (A \cap B \cap C) \cup (C \backslash (A \cup B)) \cup (A \backslash (B \cup C)) \cup (B \backslash (A \cap C))$

P.S.: is that a simplification of:
$\displaystyle (A \star B) \star C = (((A \cup B) \backslash (A \cap B)) \cup C) \backslash (((A \cup B) \backslash (A \cap B)) \cap C)$ ? :confused:
• Jul 20th 2010, 05:48 AM
Ackbeet
You're dealing with the symmetric difference there. By far the slickest way I've seen to prove associativity is by emakarov here.
• Jul 20th 2010, 03:30 PM
demode
So, did I show the commutativity correctly??

And I know this is about symmetric difference but I didn't understand emakarov's post. Is there a more simple way of showing that it holds?
• Jul 20th 2010, 05:59 PM
Ackbeet
I wasn't able to show associativity any other way. I showed the correspondence between the symmetric difference and the boolean xor function, showed the xor function was associative by the use of truth tables, and then I was done, essentially. Perhaps it was laziness: I didn't want to slog through all the boolean logic I would have had to do anyway.

I think your commutativity proof is fine.
• Jul 22nd 2010, 03:02 AM
demode
Quote:

Originally Posted by Ackbeet
I wasn't able to show associativity any other way. I showed the correspondence between the symmetric difference and the boolean xor function, showed the xor function was associative by the use of truth tables, and then I was done, essentially. Perhaps it was laziness: I didn't want to slog through all the boolean logic I would have had to do anyway.

I think your commutativity proof is fine.

So how would you show that the following holds

$\displaystyle (A \star B) \star C = (A \cap B \cap C) \cup (C \backslash (A \cup B)) \cup (A \backslash (B \cup C)) \cup (B \backslash (A \cap C))$

? We didn't study anything about "boolean xor function"...
• Jul 22nd 2010, 05:01 AM
Ackbeet
I think you have a typo there: in your last unionand, you should have $\displaystyle B\setminus(A\cup C).$

Proving this identity, with which I definitely agree, is probably just a matter of using DeMorgan's laws and other identities multiple times. You could start out with this:

$\displaystyle (A\star B)\star C\equiv ((A\cup B)\setminus(A\cap B))\star C$
$\displaystyle \equiv (((A\cup B)\setminus(A\cap B))\cup C)\setminus(((A\cup B)\setminus(A\cap B))\cap C).$

There are some identities you'll need here, which you should prove if you haven't already:

1. $\displaystyle A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C).$
2. $\displaystyle A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C).$
3. $\displaystyle \;(B\setminus A)\cap C=(B\cap C)\setminus A=B\cap(C\setminus A).$
4. $\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus(A\setminus C).$

Another important identity you should know is that

$\displaystyle A\star B=(A\cup B)\setminus(A\cap B)=(A\setminus B)\cup(B\setminus A).$

You can see here for a nice Venn diagram of the symmetric difference as you've written it. That might help direct your proof.

I should point out that I'm giving suggestions here. I haven't proven it the way you are proposing. I got too bogged down in the details. There are more than one thread in this forum dealing with the symmetric difference of sets. You can search for them. They might give you some more ideas.

Like I said, though, the boolean exclusive or function approach is the easiest approach, in my opinion:

1. Define the characteristic function $\displaystyle \chi_{X}:X\to\{0,1\}$ by
$\displaystyle \chi_{X}(x)=\begin{cases}1\quad x\in X\\ 0\quad x\not\in X\end{cases}.$
2. Prove this Lemma: $\displaystyle x\in X$ if and only if $\displaystyle \chi_{X}(x)=1.$
3. Corollary: $\displaystyle x\not\in X$ if and only if $\displaystyle \chi_{X}(x)=0.$
4. Prove this Lemma: $\displaystyle \chi_{X\star Y}=\chi_{X}\otimes\chi_{Y}.$ The $\displaystyle \otimes$ symbol there is for exclusive or.
5. Show that the exclusive or function is associative by using a truth table.
6. Then you show that $\displaystyle x\in(A\star B)\star C$ if and only if $\displaystyle x\in A\star(B\star C).$ This is easy, because you just run through the logic you've just proven in the previous steps. You're done.
• Jul 28th 2010, 01:45 AM
demode
To prove this question I must use the set-theoretic way, and not any other way. I tried to use the identities you showed me. But I need some more help here:

$\displaystyle (A\star B)\star C = ((A\cup B)\setminus(A\cap B))\star C$

$\displaystyle =(((A\cup B)\setminus(A\cap B))\cup C)\setminus(((A\cup B)\setminus(A\cap B))\cap C)$

$\displaystyle =(((A \backslash B) \cup (B \backslash A)) \cup C) \backslash (((A \backslash B) \cup (B \backslash A)) \cap C)$

$\displaystyle =((A \setminus B) \cup C \cup (B \cup C) \setminus (A \setminus C)) \setminus (((A \setminus B) \cap C) \cup (B \setminus A) \cap C))$

$\displaystyle =(A \cup C) \setminus (B \setminus C) \cup (B \cup C) \setminus (A \setminus C) \setminus (((A \setminus B) \cap C) \cup (B \setminus A) \cap C))$

So, I'm kind of stuck here... What can I do?
• Jul 28th 2010, 02:15 AM
Ackbeet
If you're allowed to use compliments, then try this proof. Or here.
• Jul 30th 2010, 11:15 PM
demode
Quote:

Originally Posted by Ackbeet
If you're allowed to use compliments, then try this proof. Or here.

I'm not getting how to use the compliments here and there isn't much time for me, so could you maybe help me to prove this without using the compliments?
• Jul 31st 2010, 03:22 AM
Ackbeet
Well, instead of set compliments, you could use some envelope set. That is, define set $\displaystyle S$ as

$\displaystyle \displaystyle{S\equiv A\cup B\cup C}.$

Then, everywhere these proofs use a set compliment, you could use instead the symbol $\displaystyle S\setminus A$. That is, you insert $\displaystyle S\setminus A$ for $\displaystyle A'$ or $\displaystyle A^{c}$.

So, for the proof here, you could start out as follows:

By definition, we know that

$\displaystyle A\Delta B=(A\setminus B)\cup(B\setminus A).$ Therefore,

$\displaystyle (A\Delta B)\Delta C=((A\Delta B)\setminus C)\cup(C\setminus(A\Delta B))$
$\displaystyle =((A \Delta B)\cap (S\setminus C)) \cup (C \cap (S\setminus(A \Delta B)))$
$\displaystyle =(((A\setminus B)\cup(B\setminus A))\cap (S\setminus C)) \cup (C \cap (S\setminus((A\setminus B)\cup(B\setminus A)))).$

Then you continue with the development in the link.