For arbitrary sets A, B and C, decide whether complement[(A − B) ∪ (B − A)] − [(A ∩ B) − complement(C)] equals [(A ∩ B) − C] ∪ complement(A ∪ B). Prove it or give a counterexample.

Step-by-step solution

1. 1

   Rewrite every difference as an intersection with a complement. The single rule $X-Y=X\cap\overline{Y}$ makes the whole statement mechanical:

   $A-B=A\cap\overline{B},\qquad B-A=B\cap\overline{A}$

   so $(A-B)\cup(B-A)$ is the symmetric difference $A\triangle B$ — the elements in exactly one of $A$, $B$.

2. 2

   Complement the symmetric difference. An element fails to lie in exactly one of $A,B$ precisely when it lies in both or in neither:

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

   This is the structural heart of the proof, and the two pieces on the right of the target identity are already visible here.

3. 3

   Simplify the set being removed. Using $\overline{\overline{C}}=C$,

   $(A\cap B)-\overline{C}=(A\cap B)\cap\overline{\overline{C}}=A\cap B\cap C$

   So the left-hand side is

   $\Big[(A\cap B)\cup\overline{(A\cup B)}\Big]-\big(A\cap B\cap C\big)$

4. 4

   Distribute the removal over the union. Set difference distributes over union, $(X\cup Y)-Z=(X-Z)\cup(Y-Z)$, giving

   $\big[(A\cap B)-(A\cap B\cap C)\big]\cup\big[\overline{(A\cup B)}-(A\cap B\cap C)\big]$

5. 5

   Simplify each piece. For the first, removing $A\cap B\cap C$ from $A\cap B$ removes exactly the part inside $C$:

   $(A\cap B)-(A\cap B\cap C)=(A\cap B)-C$

   For the second, $\overline{(A\cup B)}$ is disjoint from $A\cap B$ (and hence from $A\cap B\cap C$), so removing that set changes nothing:

   $\overline{(A\cup B)}-(A\cap B\cap C)=\overline{(A\cup B)}$

6. 6

   Conclude. Putting the two pieces back together,

   $\text{LHS}=\big[(A\cap B)-C\big]\cup\overline{(A\cup B)}=\text{RHS}$

   $\boxed{\text{The identity is true for all sets }A,B,C}$

   Note that the hypothesis $A\cup B\cup C=U$ was never needed — the identity holds unconditionally.

7. 7

   Verify by exhaustive membership check. Each element sits in one of $8$ regions according to whether it is in $A$, $B$, $C$. Testing all eight: an element in $A\cap B$ belongs to both sides iff it is outside $C$; an element outside $A\cup B$ belongs to both sides always; an element in exactly one of $A,B$ belongs to neither side (it is excluded by the complemented symmetric difference on the left, and it is in neither piece on the right). All eight cases agree, confirming the algebra.