by user356478
Last Updated October 09, 2019 17:20 PM

The symmetric difference $A$ △ $B$ of $A$ and $B$ is defined as $(A - B) \cup (B - A)$. (The set of elements that belong to A or B but not both.)

(a) Construct a truth table to show that △ is associative.

(b) Show that $x$ belongs to $A$ △ $(B$ △ $C)$ if and only if $x$ belongs to an odd number of the sets $A$, $B$ and $C$ and use this observation to give a second proof that △ is associative.

For part (a), I'd be grateful is someone could post the full truth table, as I'm not entirely sure what column headings they are looking for.

For part (b), this is what I did:

(For the left to right implication) Let $x \in $ $A$ △ $(B$ △ $C)$. Then, by the definition of △, we have either $x \in $ $A$ or $x \in $ $(B$ △ $C)$ but not both. So if $x \in A$ then either it is not in $B$ nor $C$ or it is in both $B$ and $C$. So here $x$ can be in just $A$, or in $A, B$ and $C$. If $x \in (B$ △ $C)$, then $x \notin A$. So by a similar logic $x$ can be in $B$ or $C$, but not both. The implication works both ways, hence the 'iff'.

However, I'm not sure how this proves associativity. I tried to write it as

$A$ △ $(B$ △ $C)$ = ($A$ △ $B$) $\cap$ ($A$ △ $C$) $\cap$ ($B$ △ $C$) $ \cup$ $ (A\cap B\cap C)$ And then associativity would follow by swapping $A$ and $C$ but I'm not sure if this is the right way of doing it.

Here is a truth table with an intermediate column;

$$\ \begin{array}{|ccc|c|c|} \hline A&B&C&A\Delta B&(A\Delta B)\Delta C\\ \hline 0&0&0&0&0\\ 0&0&1&0&1\\ 0&1&0&1&1\\ 0&1&1&1&0\\ 1&0&0&1&1\\ 1&0&1&1&0\\ 1&1&0&0&0\\ 1&1&1&0&1\\ \hline \end{array}$$

Here is a proof:

$\left(A\triangle B\right)\triangle C=\left(A\cup B\cup C\right)\cap\left(A\cup B^{c}\cup C^{c}\right)\cap(A^{c}\cup B\cup C^{c})\cap(A^{c}\cup B^{c}\cup C)=(B\cup C\cup A)\cap(B\cup C^{c}\cup A^{c})\cap(B^{c}\cup C\cup A^{c})\cap(B^{c}\cup C^{c}\cup A)=(B\bigtriangleup C)\bigtriangleup A=A\bigtriangleup(B\bigtriangleup C)$

The proof of symmetric difference operator associativity comes from late professor David Meredith home page: http://online.sfsu.edu/meredith/Exploration_and_Proof/divided_difference.pdf

practically one page paper contains prepositions and eventually proof of associativity. Proof assume that operator $\triangle$ is commutative as proven below from preposition 7:

$A\triangle B=(A\cup B)\cap(A^{c}\cup B^{c})=(B\cup A)\cap(B^{c}\cup A^{c})=B\triangle A$

Hope it helps.

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query