How to prove using only set identities? I have given three sets A, B and C and I need to prove that following to statements are equivalent:

S1 =  (( − ) − ) ∪ ( − ( − ( ∪ ))) − ( ∩ ( ∩ ))
S2 = ( ∩ ) − ( ∩ ( ∩ )) ∪ ( − )

prove that S1 is equivalent to S2 without using venn diagram.
How can I prove this?
 A: I would have added this reply as a comment but as I am under 50 "reputation" I cannot do it. Anyways, to prove that two sets are equivalent, you just need to show that they contain the same elements. So pick any $x\in S_1$ and show that $x$ must then be in $S_2$. This means that $S_1\subseteq S_2$. Next, pick any $y\in S_2$ and show that $y$ must be in $S_1$. That proves that $S_2\subseteq S_1$. Then you know that $S_1$ is contained in $S_2$ while $S_2$ is contained in $S_1$... What do you conclude from this fact?
A: Using Boolean algebra you consider the Boolean variables


*

*$a,b,c$ with $a=1$ ($1$ stands for $True$) iff $x \in A$. Similarly, with $b$ and $c$.


Now, write for each set the corresponding Boolean expressions


*

*$x \in S_1 = (cb')a' + b(b(a+c)')'(abc)'$

*$x \in S_2 = ab(abc)'+ca'$
Now, the only thing you need to show is that these two expressions are logically equivalent. To do so, you can simply transform them into a normal form (for example here I use disjunctive normal form (DNF)).
If the DNF's are equal, the statements are equivalent:
\begin{eqnarray*} (cb')a' + b(b(a+c)')'(abc)'
& = & a'b'c + b(b'+(a+c))(abc)' \\
& \stackrel{uu'=0, 0+v=v}{=} & a'b'c + (ab+bc)(a'+b'+c') \\
& \stackrel{uu'=0, 0+v=v}{=} & \boxed{a'b'c + abc' + a'bc}
\end{eqnarray*}
\begin{eqnarray*} ab(abc)'+ca'
& = & ab(a'+b'+c') + c(b+b')a' \\
& \stackrel{uu'=0, 0+v=v}{=} & \boxed{abc' + a'bc + a'b'c}
\end{eqnarray*}
They are equal. So, the sets are equal.
A: $$S_1=(((C\setminus B)\setminus A)\cup (B\setminus (B\setminus(A\cup C)) \setminus A\cap B\cap C$$
$$S_2=(A\cap B \setminus (A\cap C\cap B)) \cup (C\setminus A)$$
Because $(A\cap C\cap B)) \cap C\setminus A=\emptyset$, we can remove $(A\cap C\cap B))$ from both $S_1$ and $S_2$.
$$S'_1=((C\setminus B)\setminus A)\cup (B\setminus (B\setminus(A\cup C)$$
$$S'_2=(A\cap B)\cup (C\setminus A)$$
Using $X\setminus Y=X\cap Y^c$ we get:
$$S'_1=(C\cap (A\cup B)^c) \cup (B\cap (A\cup C))$$
$$S'_2=(A\cap B)\cup (C\cup A^c)$$
Using De Morgan and distributive laws gives:
$$S'_1=(C\cap A^c\cap B^c) \cup (B\cap (A\cup C))$$
$$S'_2=(A\cup C)\cap (A\cup A^c)\cap (B\cup C) \cap (B\cup A^c)$$
and then:
$$S'_1=(C\cup B)\cap (A^c\cup B)\cap (B^c\cup B)\cap(C\cup (A\cup C))\cap (A^c\cup (A\cup C))\cap (B^c\cup (A\cup C))$$
$$S'_2=(A\cup C)\cap (A\cup A^c)\cap (B\cup C) \cap (B\cup A^c)$$
Removing $\omega$ and like-terms:
$$S''_1=(C\cup (A\cup C))\cap (A^c\cup (A\cup C))\cap (B^c\cup (A\cup C))$$
$$S''_2=A\cup C$$
$S''_1$ further simplifies:
$$S''_1=(A\cup C)\cap (A^c\cup (A\cup C))\cap (B^c\cup (A\cup C))$$
and because $A\subset B \implies A\cap B=A$:
$$S''_1=A\cup C$$
As $S''_1=S''_2$ is true, so is $S_1=S_2$.
