1. **Problem statement:** Given sets and relations, solve parts (a) to (f). **(a)(i) Find the composition relation $R \circ S$ where $R: A \to B$, $S: B \to C$: $A = \{1,2,3\}$, $B = \{a,b,c\}$, $C = \{x,y,z\}$ $R = \{(1,b), (2,a), (2,c)\}$ $S = \{(a,y), (b,x), (c,y), (c,z)\}$. Recall: $R \circ S = \{(a,c) \mid \exists b\in B, (a,b) \in R \text{ and } (b,c) \in S\}$. - For $1 \in A$: $R(1) = \{b\}$, $S(b) = \{x\}$, so $(1,x) \in R \circ S$. - For $2 \in A$: $R(2) = \{a,c\}$; $S(a) = \{y\}$, $S(c) = \{y,z\}$, so $2$ relates to $y,z$; So $(2,y)$ and $(2,z)$ are in $R \circ S$. - For $3 \in A$: no $(3,b)$ in $R$, so no pairs. **Thus:** $$R \circ S = \{(1,x), (2,y), (2,z)\}$$ 2. **(a)(ii) Find matrices $M_R, M_S, M_{R\circ S}$ and compare $M_{R\circ S}$ to $M_R M_S$: Order rows by $A$ and columns by $B$ or $C$: - $M_R$ (3 x 3), rows $A=\{1,2,3\}$, cols $B=\{a,b,c\}$, Entries 1 where $(a,b)\in R$, else 0: $$M_R = \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$ - $M_S$ (3 x 3), rows $B=\{a,b,c\}$, cols $C=\{x,y,z\}$: $$M_S = \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix}$$ - Compute $M_R M_S$ (3 x 3): Row 1: $(0,1,0) \times M_S = (1,0,0)$ Row 2: $(1,0,1) \times M_S = (0,2,1)$ but convert to binary (relation) means any nonzero is 1: So $(0,1,1)$ Row 3: $(0,0,0)$ zero row. Hence: $$M_R M_S = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$ - $M_{R\circ S}$ for $R \circ S = \{(1,x), (2,y), (2,z)\}$ is: $$M_{R \circ S} = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$ **Comparison:** $M_{R \circ S} = M_R M_S$ (standard boolean matrix multiplication). 3. **(b) Show $A \cap B = A \cap C$ without $B=C$:** Example: Let $A=\{1,2\}$, $B=\{1,2,3\}$, $C=\{1,2,4\}$. Then: $A \cap B = \{1,2\} = A \cap C$ but $B \neq C$ since $3 \neq 4$. 4. **(c) Find $A \times B \times C$ for $A=\{1,2\}$, $B=\{x,y,z\}$, $C=\{3,4\}$:** Triple Cartesian product consists of ordered triples $(a,b,c)$ with $a\in A$, $b\in B$, $c\in C$. Total elements = $|A| \times |B| \times |C| = 2 \times 3 \times 2 = 12$. Explicitly: $(1,x,3),(1,x,4),(1,y,3),(1,y,4),(1,z,3),(1,z,4),(2,x,3),(2,x,4),(2,y,3),(2,y,4),(2,z,3),(2,z,4)$ 5. **(d) Given $f:A \to B$ and $g:B \to C$, find $g \circ f$: $A=\{a,b,c\}$, $B=\{x,y,z\}$, $C=\{r,s,t\}$ $f=\{(a,y),(b,x),(c,y)\}$ $g=\{(x,s),(y,t),(z,r)\}$ Compute for each $a \in A$: - $g(f(a))$: $f(a)$ maps: $a \to y$, $b \to x$, $c \to y$ Then $g$ maps: $y \to t$ and $x \to s$ Hence: $g \circ f = \{(a,t), (b,s), (c,t)\}$ 6. **(e) Illustrate De Morgan’s Law $(A \cup B)^C = A^C \cap B^C$ with Venn diagrams:** - Consider Universe $U$ - Left diagram: shade outside $A \cup B$ - Right diagram: shade outside $A$ and outside $B$, then overlap (intersection) The shaded areas in both diagrams are the same, proving the law visually. 7. **(f)(i) Draw bipartite graphs for $R$ and $S$ with: $A=\{1,2,3,4\}, B=\{a,b,c\}, C=\{x,y,z\}$ $R=\{(1,b),(3,a),(3,b),(4,c)\}$ $S=\{(a,y),(c,x),(a,z)\}$ Edges connect elements as described between sets. 8. **(f)(ii) Find matrices $M_R, M_S, M_{R \circ S}$:** - Rows $A$ and cols $B$ for $M_R$ (4 x 3): $$M_R = \begin{bmatrix}0 & 1 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ - Rows $B$ and cols $C$ for $M_S$ (3 x 3): $$M_S = \begin{bmatrix}0 & 1 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}$$ - Compute $M_R M_S$ (4 x 3): Row 1: $(0,1,0)\times M_S = (0,0,0)$ Row 2: $(0,0,0)\times M_S = (0,0,0)$ Row 3: $(1,1,0)\times M_S = (0+0,1+0,1+0) = (0,1,1)$ Row 4: $(0,0,1)\times M_S = (1,0,0)$ Hence: $$M_{R \circ S} = \begin{bmatrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}$$