Exercise 1.1

Question

Check the distributive laws for $\cup$ and $\cap$ and DeMorgan's laws.

Dan Whitman · Accepted Answer

Suppose that $A$, $B$, and $C$ are sets.
First, we show that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
\begin{proof}
We show this as a series of logical equivalences:
\begin{align*}
x \in A \cap (B \cup C) &\Leftrightarrow x \in A \land x \in B \cup C \
&\Leftrightarrow x \in A \land (x \in B \lor x \in C) \
&\Leftrightarrow (x \in A \land x \in B) \lor (x \in A \land x \in C) \
&\Leftrightarrow x \in A \cap B \lor x \in A \cap C \
&\Leftrightarrow x \in (A \cap B) \cup (A \cap C) \,,
\end{align*}
which of course shows the desired result.
\end{proof}

Next, we show that $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
\begin{proof}
We show this in the same way:
\begin{align*}
x \in A \cup (B \cap C) &\Leftrightarrow x \in A \lor x \in B \cap C \
&\Leftrightarrow x \in A \lor (x \in B \land x \in C) \
&\Leftrightarrow (x \in A \lor x \in B) \land (x \in A \lor x \in C) \
&\Leftrightarrow x \in A \cup B \land x \in A \cup C \
&\Leftrightarrow x \in (A \cup B) \cap (A \cup C) \,,
\end{align*}
which of course shows the desired result.
\end{proof}

Now we show the first DeMorgan's law that $A - (B \cup C) = (A - B) \cap (A - C)$.
\begin{proof}
We show this in the same way:
\begin{align*}
x \in A - (B \cup C) &\Leftrightarrow x \in A \land x 
otin B \cup C \
&\Leftrightarrow x \in A \land \lnot (x \in B \lor x \in C) \
&\Leftrightarrow x \in A \land (x 
otin B \land x 
otin C) \
&\Leftrightarrow (x \in A \land x 
otin B) \land (x \in A \land x 
otin C) \
&\Leftrightarrow x \in A - B \land x \in A - C \
&\Leftrightarrow x \in (A - B) \cap (A - C) \,,
\end{align*}
which is the desired result.
\end{proof}

Lastly, we show that $A - (B \cap C) = (A - B) \cup (A - C)$.
\begin{proof}
Again we use a sequence of logical equivalences:
\begin{align*}
x \in A - (B \cap C) &\Leftrightarrow x \in A \land x 
otin B \cap C \
&\Leftrightarrow x \in A \land \lnot (x \in B \land x \in C) \
&\Leftrightarrow x \in A \land (x 
otin B \lor x 
otin C) \
&\Leftrightarrow (x \in A \land x 
otin B) \lor (x \in A \land x 
otin C) \
&\Leftrightarrow x \in A - B \lor x \in A - C \
&\Leftrightarrow x \in (A - B) \cup (A - C) \,,
\end{align*}
as desired.
\end{proof}

Exercise 1.1

Answers

Comments

Exercise 1.1

Answers

Comments

Add answer