# COT 3100 - Homework 2
*Michael Akinyemi*
*Tue/Thu 9:00 AM*
### Problem 1: Venn Diagrams (15)
> Consider sets $A$, $B$, and $C$, and draw Venn diagrams for the following composite sets:
> 1. $(A \cap B) \cup (C)$
![[History of Microbiology.png|300]]
---
> 2. $(\neg A) \cup (\neg B) \cup (\neg C)$
![[History of Microbiology-1.png|300]]
---
> 3. $A - (B \cap C)$
![[History of Microbiology-2.png|300]]
### Problem 2: Proof of Laws (20)
>Consider sets $A$ and $B$, and:
>
> 1. Prove the absorption law $A \cup (A \cap B) = A$ by universal generalization, applied twice to use the double-subset property.
By the double-subset property, it suffices to show:
- $A \cup (A \cap B) \subseteq A$
- $A \subseteq A \cup (A \cap B)$
**Case 1:** Show that $A \cup (A \cap B) \subseteq A$
Consider an arbitrary $x \in A \cup (A \cap B)$.
By definition of union, $x \in A$ for all $x \in A \cup (A \cap B)$.
Then by universal generalization with subset, $A \cup (A \cap B) \subseteq A$.
**Case 2:** Show that $A \subseteq A \cup (A \cap B)$
Consider an arbitrary element $x \in A$
Without loss of generality, $x \in B$ or $x \notin B$. Consider each case
- **Case 2.1:** $x \in B$
- From above, $x \in A$. So with $x \in B$, $x \in (A \cap B)$ by definition of intersection.
- Then by definition of union, we have $x \in A \cup (A \cap B)$
- **Case 2.2:** $x \notin B$
- From above, $x \in A$. So with $x \not \in B$, $x \in (A \cap B)$ by definition of intersection.
- Then by definition of union, we have $x \in A \cup (A \cap B)$
In either case, $x \in A \cup (A \cap B)$.
Then by universal generalization with subset, $A \subseteq A \cup (A \cap B)$.
Shown $A \cup (A \cap B) \subseteq A$ and $A \subseteq A \cup (A \cap B)$.
By double-subset, $A \cup (A \cap B) = A$ as desired.
---
> 2. Prove the associative law $A \cap (B \cap C) = (A \cap B) \cap C$ by membership table.
| $A$ | $B$ | $C$ | $(B \cap C)$ | $A \cap (B \cap C)$ | $(A \cap B)$ | $(A \cap B) \cap C$ |
| --- | --- | --- | :---: | :---: | :---: | :---: |
| T | T | T | T | T | T | T |
| T | T | F | F | F | T | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | T | F | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
### Problem 3: Proof of Equalities (25)
> 1. (5) Prove $(A \cup B) \subseteq (A \cup B \cup C)$ by universal generalization.
Consider an arbitrary $x \in (A \cup B)$.
By definition of union, we have two cases:
**Case 1:** $x \in A$
If $x \in A$, then by definition of union $x \in (A \cup B \cup C)$.
**Case 2:** $x \in B$
If $x \in B$, then by definition of union $x \in (A \cup B \cup C)$.
In either case, $x \in (A \cup B \cup C)$.
Then by universal generalization, $x \in (A \cup B \cup C)$ for any $x \in (A \cup B)$.
Then by definition of subset, $(A \cup B) \subseteq (A \cup B \cup C)$.
---
> 2. (5) Prove $(A \cap B \cap C) \subseteq (A \cap B)$ by universal generalization.
Consider an arbitrary $x \in (A \cap B \cap C)$.
By definition of intersection, we have $x \in A$, $x \in B$, and $x \in C$
Since $x \in A$ and $x \in B$, by definition of intersection we have $x \in (A \cap B)$
Then by universal generation $x \in (A \cap B)$ for any $x \in (A \cap B \cap C)$.
Then by definition of subset, $(A \cap B \cap C) \subseteq (A \cap B)$.
---
> 3. (5) Prove $(A - C) \cap (C - B) = \emptyset$ by membership table.
| $A$ | $B$ | $C$ | $\emptyset$ | $(A-C)$ | $(C-B)$ | $(A-C) \cap (C-B)$ |
| --- | --- | --- | --- | :---: | :---: | :---: |
| T | T | T | F | F | F | F |
| T | T | F | F | T | F | F |
| T | F | T | F | F | T | F |
| T | F | F | F | T | F | F |
| F | T | T | F | F | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | T | F |
| F | F | F | F | F | F | F |
---
> 4. (10) Prove $(B-A) \cup (C - A) = (B \cup C) - A$ by universal generalization, applied twice to use the double-subset property.
By the double-subset property, it suffices to show:
- $(B-A) \cup (C - A) \subseteq (B \cup C) - A$
- $(B \cup C) - A \subseteq (B-A) \cup (C - A)$
**Case 1:** Show that $(B-A) \cup (C - A) \subseteq (B \cup C) - A$
Consider an arbitrary $x \in (B-A) \cup (C-A)$
By definition of relative complement, $x \in (B-A) \cup (C-A)$
**Case 2:** Show that $(B \cup C) - A \subseteq (B-A) \cup (C - A)$
Consider an arbitrary $x \in (B \cup C) - A$
By definition of intersection we have two cases:
- **Case 2.1:** $x \in (B \cup C)$
- **Case 2.2:** $x \not \in A$
### Problem 4: Set Equality Laws (30)
>Consider sets $A$ and $B$, and use set equality laws to prove that:
> $((A \cap B) \cup (A \cap \neg B) \cup (\neg A \cap B)) = (A \cup B)$
$ \begin{aligned}
\\ \text{1. } & (A \cap B) \cup (A \cap \neg B) \cup (\neg A \cap B) && \text{Given}
\\ \text{2. } & (A \cap (B \cup \neg B)) \cup (\neg A \cap B) && \text{Distributive}
\\ \text{3. } & (A \cap U) \cup (\neg A \cap B) && \text{Negation}
\\ \text{4. } & A \cup (\neg A \cap B) && \text{Identity}
\\ \text{5. } & (A \cup \neg A) \cap (A \cup B) && \text{Distributive}
\\ \text{6. } & U \cap (A \cup B) && \text{Negation}
\\ \text{7. } &A \cup B && \text{Identity}
\end{aligned}$
### Problem 5: Disproof (10)
> Show, any way you wish, that $(A - B) = (B - A)$ is not always true.
**Proof by case:**
Let $A = \{ a, b, c \}$
Let $B = \{ b, c \}$
$A-B = \{ a \}$
$B - A = \{ \}$
$\{ a \} \neq \{ \}$
Thus, it is shown that $A-B \neq B-A$ in this case