1

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

Note that $\overline{B}$ denotes the complement of B.

One thing I notice is that $(\overline{A} \cap \overline{B}) = \overline{A \cup B}$ using De Morgan's laws, so the equation becomes

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

Visually in a Venn diagram, the left hand side is everything outside of A and B, as well as the shared overlap between A and B. The right hand side is harder to explain in words; it's the intersection of the following two regions: everything outside of B as well as the shared overlap between A and B, and everything outside of A as well as the shared overlap between A and B. When I draw a picture, the equality is clear.

Is there an elegant way to prove this equality? Anything other than showing that the left is a subset of the right and also that the right is a subset of the left?

EDIT: A truth table works well, since there are only 4 possibilities (neither, A, B, or both) to inspect. Are there alternatives?

an4s
  • 3,716
jskattt797
  • 1,731

2 Answers2

3

DeMorgan is not a bad idea (always a good idea to know what tools you have at your disposal), but it's not really necessary here--distributivity for the win!

\begin{align} (A\cup\overline{B})\cap(\overline{A}\cup B) &=[(A\cup\overline{B})\cap\overline{A}]\cup[(A\cup\overline{B})\cap B]\\[0.5em] &=[(A\cap\overline{A})\cup(\overline{B}\cap\overline{A})]\cup[(A\cap B)\cup(\overline{B}\cap B)]\\[0.5em] &= (\overline{B}\cap\overline{A})\cup(A\cap B). \end{align}

Daniel W. Farlow
  • 22,531
2

Let $X$ be the universal set. Here we use distributive property of unions and intersections and the fact $\overline{A} \cup A=X$ for any $A \subseteq X$.

$\begin{split}(\overline{A} \cap \overline{B}) \cup (A \cap B) &=((\overline{A} \cap \overline{B}) \cup A) \cap((\overline{A} \cap \overline{B}) \cup B)\\ &=((\overline{A}\cup A) \cap (\overline{B}\cup A) ) \cap((\overline{A} \cup B) \cap (\overline{B}\cup B) )\\ &=(X \cap (\overline{B}\cup A) ) \cap((\overline{A} \cup B) \cap X)\\ &=(\overline{B}\cup A) \cap(\overline{A} \cup B)\\ \end{split}$

Prabath Hewasundara
  • 1,644