# Does $(A\cup B)\cap(C\cup D)=(A\cap C)\cup(B\cap D)$?

Let $A$, $B$, $C$, and $D$ be nonempty sets.

Does $(A\cup B)\cap(C\cup D)=(A\cap C)\cup(B\cap D)$?

It seems to be true by looking at Venn diagram, but I'm getting mixed up with the proof.

-
Let $B=C=A^c$ the complement of $A$ and let $D=A$. Is it true? –  Thomas Andrews Sep 19 '12 at 21:09
An exhaustive search for a counterexample only needs to consider 16 possible cases. One of those (at least) is a counterexample. See my answer below. –  Michael Hardy Sep 19 '12 at 21:28
It is not hard to show that the right-hand side is a subset of the left-hand side. However, if you draw a Venn Diagram, you will see that "in general" the left-hand side has extra stuff. –  André Nicolas Sep 19 '12 at 22:17

No. Suppose $A=D=\emptyset$. Then $(A\cup B)\cap (C\cup D)=B\cap C$, but $(A\cap C)\cup (B\cap D)=\emptyset$.

This is still false if you require the sets to be nonempty. Let $A=D=\{0\}$. Then the first set is $(B\cap C)\cup \{0\}$ and the second is at most $\{0\}$, which are not equal in general.

-
Sorry, I meant to say nonempty sets. I will edit the question. –  ohmygoodness Sep 19 '12 at 21:14
@GradEwnder It doesn't matter. Let $A=D=\{0\}$. Then the first set is $(B\cap C)\cup \{0\}$ and the second is $\{0\}$. –  Alex Becker Sep 19 '12 at 21:15
@AlexBecker: the second can even be empty if $0 \not \in B$, for example. –  Ross Millikan Sep 19 '12 at 21:17
@RossMillikan Good point. –  Alex Becker Sep 19 '12 at 21:43

You could fill in this whole truth table. If there is one row in which the last two columns disagree, then that answers your question. $$\begin{array}{|c|c|c|c|c|c|} \hline x\in A & x\in B & x\in C & x\in D & x\in(A\cup B)\cap(C\cup D) & x\in(A\cap C)\cup(B\cap D) \\ \hline T & T & T & T & \cdots & \cdots \\ T & T & T & f & \cdots & \cdots \\ T & T & f & T & \cdots & \cdots \\ T & f & T & T & \cdots & \cdots \\ f & T & T & T & \cdots & \cdots \\ T & T & f & f & \cdots & \cdots \\ T & f & T & f & \cdots & \cdots \\ f & T & T & f & T & f \\ T & f & f & T & \cdots & \cdots \\ f & T & f & T & \cdots & \cdots \\ f & f & T & T & \cdots & \cdots \\ T & f & f & f & \cdots & \cdots \\ f & T & f & f & \cdots & \cdots \\ f & f & T & f & \cdots & \cdots \\ f & f & f & T & \cdots & \cdots \\ f & f & f & f & \cdots & \cdots \\ \hline \end{array}$$

-