1
$\begingroup$

My question is about the proof of the distributive laws of boolean operations, more specifically I have some trouble understanding this equality: $B \cup (A_1 \cap \cdots \cap A_n) = (B \cup A_1) \cap \cdots \cap (B \cup A_n)$.

Denoting $(A_1 \cap \cdots \cap A_n)$ by $C$, the left hand side reads as $x \in B$ or $C$, that is $x$ is in at least one of $B$ and $C$.

Now, I interpret the right hand side the following way: If $x$ is not in $B$, then $x$ must be in all the $A_i$, because for each term, $x$ has to be in at least one of $B$ or $A_i$, and if $x \notin B$ for one term, then $x \notin B$ for all terms. That's about as far as I get, because I feel like the right hand side implies that $x$ can be in $B$ and just some of the $A_i$, which would contradict the left hand side. Like, if we look at the first term $B \cup A_1$, one valid possibility is that $x$ is in $B$ and $A_1$. At the same time, for the second term, $B \cup A_2$, it seems like it would be valid to say that $x$ is in $B$ but not in $A_2$, but this contradicts the left hand side, which implies that $x$ must be in every $A_i$ if it is in one of them.

So if I were given just the right hand side, $(B \cup A_1) \cap \cdots \cap (B \cup A_n)$, I would say, OK, $x$ can be in $B$ and $A_i$ for all $i$, $x$ can be in not $B$ and $A_i$ for all $i$, but $x$ cannot be in not $B$ and just some of the $A_i$, since for every term $x$ must be in at least $B$ or $A_i$. And then finally, the part which seems irreconcilable with the left hand side of the equation at the top: $x$ can be in $B$ and some of the $A_i$.

$\endgroup$

2 Answers 2

1
$\begingroup$

Your interpretation of RHS is okay ("if $x$ is not in $B$ then $x$ must be in all $A_i$").

Also if $x$ is an element of the RHS then $x$ can indeed be an element of $B$ and some of the $A_i$.

This however does not contradict that $x$ is an element of the LHS (as you seem to think). Every element that is in $B$ is an element of the LHS simply because $B$ is a subset of the LHS, and the question whether $x$ is an element of some, none or all of the $A_i$ is not relevant.

Observe that the LHS can be interpretated exactly the same as RHS: $x$ is an element of LHS if it is an element of $B$ or is an element $A_i$ for some $i\in\{1,\dots,n\}$.

Does this help?

$\endgroup$
2
  • $\begingroup$ I think so. For instance, if $x$ is in $B$ and $A_1,A_2$, but not for any other $A_i$, this does not contradict the LHS, b.c. $x$ is still in $B$, which is consistent with the LHS? $\endgroup$
    – goblinb
    Commented Jan 28, 2019 at 12:06
  • $\begingroup$ Yes, that is what I am saying. $\endgroup$
    – drhab
    Commented Jan 28, 2019 at 12:44
0
$\begingroup$

A $\cup$ (B $\cap$ C) = (A $\cup$ B) $\cap$ (A $\cup$ B).
Proof.
x in A $\cup$ (B $\cap$ C) iff x in A or x in B $\cap$ C
if x in A or (x in B and x in C)
iff (x in A or x in B) and (x in A or x in B)
iff x in A $\cup$ B and x in A $\cup$ B
iff x in (A $\cup$ B) $\cap$ (A $\cup$ B)

By induction this proof can be extended to any finite number of intersections.

If C is any collection of sets, then
A $\cup$ $\cap$C = $\cap${ A $\cup$ X : X in C }.
Proof.
x in A $\cup$ $\cap$C iff x in A or x in $\cap$C
iff x in A or for all X in C, x in X
iff for all X in C, (x in A or x in X)
iff for all x in C, x in A $\cup$ X
iff x in $\cap${ A $\cup$ X : X in C }.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .