Prove that $A^c = (A^c∩B)∪(A^c∩B^c)$

Question

Could someone help me with this problem? I have no idea how to attempt to solve it nor do I know where I can ask for help besides her.

Answer 1

Set unions and intersections distribute over each other, so we can rewrite $$ (\overline{A}\cap B) \cup (\overline{A} \cap \overline{B}) $$ Instead as: $$ \overline{A} \cap (B\cup\overline{B}) $$ The union of a set and its complement is just the universal set $U$ in which $A$ and $B$ reside, and the intersection of any set with $U$ in turn is just that set: $$ \overline{A} \cap (B\cup\overline{B}) = \overline{A}\cap U = \overline{A} $$

---

You can also prove it directly, like so.

• Let $X:=(\overline{A}\cap B) \cup (\overline{A} \cap \overline{B})$ be your set in question.
• Take any arbitrary $x\in \overline{A}$. By definition, $x\in U = B\cup\overline{B}$, so either $x\in B$, or $x\in \overline{B}$. In the former case, $x\in(\overline{A}\cap B) \Rightarrow x\in X$, while in the latter case, $x\in(\overline{A}\cap \overline{B}) \Rightarrow x\in X$. So we have proved $x\in\overline{A}\Rightarrow x\in X$.
• In the other direction, take any $x\in X$. Because $X$ is a union of sets, either $x\in (\overline{A}\cap B)$, or $x\in(\overline{A}\cap \overline{B})$, but both of these statements imply $x\in \overline{A}$. So we have also proved $x\in X \Rightarrow x\in\overline{A}$.
• Combine both implicational directions, and universally instantiate $x$, and we have in fact proved $\forall x :x\in X \Leftrightarrow x\in\overline{A}$. This is the definition of equality of sets, therefore $X = \overline{A}$.

Answer 2

$$\begin{alignat}{2}(A^c\cap B)\cup(A^c\cap B^c) &= (A^c\cup A^c)\cap(A^c\cup B^c)\cap(B\cup A^c)\cap(B\cup B^c) & \text{(distributive law)}\\ &= A^c\cap(A^c\cup B^c)\cap(B\cup A^c)\cap(B\cup B^c) & \text{(idempotent AND law)}\\ &= A^c(1\cap B^c)\cap(B\cup A^c)\cap(B\cup B^c) & \text{(distributive law)}\\ &= A^c\cap (B\cup A^c)\cap(B\cup B^c) & \text{(identity OR law)}\\ &= A^c(1\cap B)\cap(B\cup B^c) & \text{(distributive law)}\\ &= A^c\cap(B\cup B^c) & \text{(identity OR law)}\\ &= A^c\cap1 & \text{(complement law)}\\ &= A^c & \text{(annulment law)}\end{alignat}$$