next up previous contents
Next: Complementary set Up: Operations with sets Previous: Union   Contents

Distributivity

Proposition 3.2.18 (distributive law)   Let $ A$, $ B$ and $ C$ be three sets. Then the following hold:
(i)
$ A \cap ( B \cup B) = (A \cup B ) \cap (A \cup C)$;
(ii)
$ A \cup ( B \cap B) = (A \cap B ) \cup (A \cap C)$.

Figure 8: Distributive law (i)
\begin{figure}
\centering
\mbox{\epsfig{file=DistributiveLaw-1.eps,height=4.5cm}}
\end{figure}

Figure 9: Distributive law (ii)
\begin{figure}
\centering
\mbox{\epsfig{file=DistributiveLaw-2.eps,height=4.5cm}}
\end{figure}

Notre $ p=''x \in A''$, $ q=''x \in B''$ and $ r=''x \in C''$. Then we need to prove that the following predicates are tautologies:

$\displaystyle \begin{matrix}[p \wedge ( q \vee r ) ]\Longleftrightarrow [(p \ve...
...\wedge r ) ] \Longleftrightarrow [(p \wedge q) \vee (p \wedge r)]
 \end{matrix}$    

We use now Proposition prop logic:distributivity. A generalization of the distributive law is as follows. Let $ J$ be a set of indices and let $ A$ be a set and $ \{ b_j, \; j \in J \}$ be a family of sets. Then we have:

$\displaystyle A \cap \left( \underset{j \in J}{\bigcup} B_j \right)$ $\displaystyle = \underset{j \in J}{\bigcup} (A \cap B_j );$    
$\displaystyle A \cup \left( \underset{j \in J}{\bigcap} B_j \right)$ $\displaystyle = \underset{j \in J}{\bigcap} (A \cup B_j ).$    

For two sets of indices $ I$ and $ J$ and two families of sets $ \{ A_i , \; i \in I \}$ and $ \{ b_j, \; j \in J \}$, we have:

$\displaystyle \left( \underset{i \in I}{\bigcup} A_i \right) \cap \left( \underset{j \in J}{\bigcup} B_j \right)$ $\displaystyle = \underset{\begin{matrix}i \in I \\ j \in J \end{matrix}}{\bigcup} (A_i \cap B_j );$    
$\displaystyle \left( \underset{i \in I}{\bigcap} A_i \right) \cup \left( \underset{j \in J}{\bigcap} B_j \right)$ $\displaystyle = \underset{\begin{matrix}i \in I \\ j \in J \end{matrix}}{\bigcap} (A \cup B_j ).$    


next up previous contents
Next: Complementary set Up: Operations with sets Previous: Union   Contents
root 2002-06-10