# How does 'AND' distribute over 'OR' (Set Theory)?

In my textbook, there is a solved example:

Prove that $$A \cup (B \cap C) = (A \cup B)\cap(A\cup C).$$

Solution

Let $$x$$ be an arbitrary element of $$A \cup (B\cap C)$$. Then, \begin{aligned} &x\in A\cup (B\cap C)\\ \implies &x \in A \lor (x\in B\cap C)\\ \implies &x \in A \lor (x\in B \land x\in C)\\ \implies &(x \in A \lor x\in B) \land (x\in A \lor x\in C)\\ \implies &x\in(A \cup B) \land x\in(A\cup C)\\ \implies &x\in((A\cup B)\cap(A\cup C))\\ \therefore\ A\cup(B\cap C) \subseteq (A\cup B)\cap (A\cup C) \end{aligned} Similarly, $$(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$$.
Hence, $$A\cup (B\cap C) = (A\cup B)\cap(A\cup C)$$.

The book didn't prove $$(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$$. So, I tried to do it:

Let $$y$$ be an arbitrary element of $$(A\cup B)\cap(A\cup C)$$. Then, \begin{aligned} &y\in(A\cup B) \land y\in(A\cup C)\\ \implies &(y\in A \lor y\in B) \land (y\in A \lor y\in C)\\ \implies &((y\in A \lor y\in B)\land y\in A) \lor ((y\in A \lor y\in B)\land y\in C)\\ \implies &((y\in A \land y\in A)\lor (y\in B\land y\in A))\lor ((y\in A \land y\in C) \lor (y\in B \land y\in C)) \end{aligned}

I don't know how to proceed further. There could be a better way to prove this, but I just want to simplify this expression into something that could enable me to solve the problem.

• Do you want to solve it by expcitely simplifying the sentence? Otherwise I'd suggest taking the second line of your attempt and consider the possible cases Commented Aug 11, 2019 at 13:35

The reason "similarly" was written is because all the $$\implies$$ could be replaced with $$\iff$$, thus allowing a path from $$x\in(A\cup B)\cap(A\cup C)$$ to $$x\in A\cup(B\cap C)$$ by reading backwards. Thus, you actually need no effort to prove the reverse case; it has already been printed out for you.

The set operations $$\cap$$ and $$\cup$$ correspond exactly with the $$\land$$ and $$\lor$$ of Boolean logic.

Remember that Distribution goes two ways. That is, you can go from $$X \land (Y \lor Z)$$ to $$(X \land Y) \lor (X \land Z)$$, but you can go from $$(X \land Y) \lor (X \land Z)$$ back to $$X \land (Y \lor Z)$$.

Now, going the other way doesnt feel like 'Distribution' (it feels more like a 'Reverse Distribution' or 'Çollecting common Terms'), which is exactly why so many beginning students of logic miss it, and instead end up doing the exact same thing you do: going from $$(X \land Y) \lor (X \land Z)$$ to $$((X \land Y) \lor X) \land ((X \land Y) \lor Z)$$ ... But that, as you saw, doesn't really go anywhere. This is a very common 'mistake'!

So, the key is to do Distribution 'the reverse way' after line 2:

\begin{aligned} &y\in(A\cup B) \land y\in(A\cup C)\\ \implies &(y\in A \lor y\in B) \land (y\in A \lor y\in C)\\ \implies &y\in A \lor (y\in B \land y\in C)\\ \implies &y\in A \lor (y\in B \cap C)\\ \implies &y\in A \cup (B \cap C) \end{aligned}

And this, as @ParclyTaxel notes, just with all steps reversed from the first proof.

• That is not fleablood. That is me. Commented Aug 11, 2019 at 13:38
• @ParclyTaxel Oh my! Your icons look alike, and it's just something fleablood would point out! :) Commented Aug 11, 2019 at 13:41

Indeed, it is always true that $$(\alpha\lor\beta)\land(\alpha\lor\gamma)\equiv\alpha\lor(\beta\land\gamma)$$. You can see this by verifying it semantically using truth tables (so there is also a derivation for it, but I can't seem to remember it):

$$\begin{array}{|c|c|c|c|} \hline \alpha&\beta &\gamma & (\alpha\lor\beta)\land(\alpha\lor\gamma) &\alpha\lor(\beta\land\gamma) \\ \hline 0& 0& 0& 0 &0\\ \hline 0& 0& 1& 0 &0\\ \hline 0& 1& 0& 0 &0\\ \hline 0& 1& 1& 1 &1\\ \hline 1& 0& 0& 1 &1\\ \hline 1& 0& 1& 1 &1\\ \hline 1& 1& 0& 1 &1\\ \hline 1& 1& 1& 1 &1\\ \hline \end{array}$$

We can thus write the expression

$$(y\in A\lor y\in B)\land (y\in A\lor y\in C)$$

as

$$y\in A\lor (y\in B\land y\in C)$$

which gives your claim and you don't have to expand any further.

Well, you shouldn't expand it. The statement $$(y\in A \lor y \in B) \land (y\in A \lor y \in C)$$ is equivalent by the distributive law to $$y\in A \lor (y \in B \land y \in C)$$.

Assuming your text means for $$A,B,C$$ to be non-empty we have the following.

To prove $$A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$$, we must show that $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$$ and $$(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$$.

In order to show $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$$, let $$x\in A\cup (B\cap C)$$. Since $$x\in A\cup (B\cap C)$$, either $$x\in A$$ or $$x\in B\cap C$$.

Case 1: $$x\in A$$. If $$x\in A$$ then $$x\in A$$ or $$x\in B$$, so $$x\in A\cup B$$. Similarly, since $$x\in A$$, $$x\in A$$ or $$x\in C$$, so $$x\in A\cup C$$. Thus, $$x\in A\cup B$$ and $$x\in A\cup C$$, so $$x\in (A\cup B)\cap (A\cup C)$$. Hence $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$$.

Case 2. $$x\in B\cap C$$. Argue similarly to case 1, conclude $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$$. Try it out.

Still need to prove $$(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$$. Let $$x\in (A\cup B)\cap (A\cup C)$$. Since $$x\in (A\cup B)\cap (A\cup C)$$, it follows that $$x\in (A\cup B)$$ and $$x\in(A\cup C)$$.

Case 1. $$x\in A$$. If $$x\in A$$, we are done since $$x\in A$$ implies that $$x\in A\cup (B\cap C)$$, so $$(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$$.

Case 2. $$x\not\in A$$. If $$x\not\in A$$, then $$x\in B$$ and $$x\in C$$. So, $$x\in B\cap C$$ which gives us that $$x\in A\cup (B\cap C)$$. Conclusion, $$(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$$.

Finally, we've shown $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$$ and $$(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$$ and so we can conclude that $$A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$$.