commutative operation

**demode** · July 19th 2010, 11:10 PM

Here's a question:

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

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

$= (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:

$(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:
$(A \star B) \star C = (((A \cup B) \backslash (A \cap B)) \cup C) \backslash (((A \cup B) \backslash (A \cap B)) \cap C)$ ?

**Ackbeet** · July 20th 2010, 05:48 AM

You're dealing with the symmetric difference there. By far the slickest way I've seen to prove associativity is by emakarov here.

**demode** · July 20th 2010, 03:30 PM

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?

**Ackbeet** · July 20th 2010, 05:59 PM

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.

**demode** · July 22nd 2010, 03:02 AM

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

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

**Ackbeet** · July 22nd 2010, 05:01 AM

I think you have a typo there: in your last unionand, you should have $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:

$(A\star B)\star C\equiv ((A\cup B)\setminus(A\cap B))\star C$
$\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. $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C).$
2. $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C).$
3. $\;(B\setminus A)\cap C=(B\cap C)\setminus A=B\cap(C\setminus A).$
4. $(B\setminus A)\cup C=(B\cup C)\setminus(A\setminus C).$

Another important identity you should know is that

$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 $\chi_{X}:X\to\{0,1\}$ by
$\chi_{X}(x)=\begin{cases}1\quad x\in X\\ 0\quad x\not\in X\end{cases}.$
2. Prove this Lemma: $x\in X$ if and only if $\chi_{X}(x)=1.$
3. Corollary: $x\not\in X$ if and only if $\chi_{X}(x)=0.$
4. Prove this Lemma: $\chi_{X\star Y}=\chi_{X}\otimes\chi_{Y}.$ The $\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 $x\in(A\star B)\star C$ if and only if $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.

**demode** · July 28th 2010, 01:45 AM

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:

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

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

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

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

$=(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?

**Ackbeet** · July 28th 2010, 02:15 AM

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

**demode** · July 30th 2010, 11:15 PM

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?

**Ackbeet** · July 31st 2010, 03:22 AM

Well, instead of set compliments, you could use some envelope set. That is, define set $S$ as

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

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

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

By definition, we know that

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

$(A\Delta B)\Delta C=((A\Delta B)\setminus C)\cup(C\setminus(A\Delta B))$
$=((A \Delta B)\cap (S\setminus C)) \cup (C \cap (S\setminus(A \Delta B)))$
$=(((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.

Thread: commutative operation

LinkBack

Thread Tools

Display

commutative operation

Similar Math Help Forum Discussions

Operation of convoulution is commutative

Operation @

Operation

Commutative Operation 71.10

row operation

Search Tags