1

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.

an4s
  • 3,716
Tom el Safadi
  • 177
  • start with an element on left side set and show that it belongs to the right side set.. start with an element on the right side set and show that it belongs to the left side set.. Have you tried something like this? – Praphulla Koushik Jan 18 '20 at 05:26
  • thanks for your help! With right and left side I assume you mean right and left side of the equal sign? – Tom el Safadi Jan 18 '20 at 05:27
  • HINT: $A^\complement\cap B^\complement =A^\complement \setminus B$ – Masacroso Jan 18 '20 at 05:28

2 Answers2

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}$$

an4s
  • 3,716
2

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}$.
indnwkybrd
  • 981