Question: Question 3
a) Let $A = \{a, b, c, d\}$ and let $R$ and $S$ be relations on set $A$, represented by the following matrices:
$M_R = \begin{bmatrix}0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0\end{bmatrix}$ and $M_S = \begin{bmatrix}1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1\end{bmatrix}$.
Solve:
(i) $\overline{M_R}$
(ii) $M_R \cup S^{-1}$
(iii) $M_{(S \cap R)^{-1}}$
(iv) $M_{S \circ R}$
1. **State the problem:** We are given two relations $R$ and $S$ on set $A = \{a,b,c,d\}$ represented by matrices $M_R$ and $M_S$. We need to find:
(i) The complement of $M_R$, denoted $\overline{M_R}$.
(ii) The union of $M_R$ and the inverse of $S$, denoted $M_R \cup S^{-1}$.
(iii) The inverse of the intersection of $S$ and $R$, denoted $M_{(S \cap R)^{-1}}$.
(iv) The composition of $S$ and $R$, denoted $M_{S \circ R}$.
2. **Recall important rules and formulas:**
- The complement $\overline{M_R}$ is obtained by replacing every 0 with 1 and every 1 with 0.
- The inverse of a relation matrix $M$ is its transpose: $M^{-1} = M^T$.
- The union of two relations $M_A$ and $M_B$ is the element-wise logical OR.
- The intersection of two relations $M_A$ and $M_B$ is the element-wise logical AND.
- The composition $M_{S \circ R}$ is given by Boolean matrix multiplication: $(M_{S \circ R})_{ij} = \bigvee_k (M_R)_{ik} \wedge (M_S)_{kj}$.
3. **Given matrices:**
$$
M_R = \begin{bmatrix}0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0\end{bmatrix}, \quad M_S = \begin{bmatrix}1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1\end{bmatrix}
$$
4. **(i) Find $\overline{M_R}$:**
Replace 0 with 1 and 1 with 0 in $M_R$:
$$
\overline{M_R} = \begin{bmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1\end{bmatrix}
$$
5. **(ii) Find $M_R \cup S^{-1}$:**
First find $S^{-1} = M_S^T$ (transpose of $M_S$):
$$
S^{-1} = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1\end{bmatrix}
$$
Now compute element-wise OR with $M_R$:
$$
M_R \cup S^{-1} = \begin{bmatrix}
0 \lor 1 & 0 \lor 0 & 1 \lor 0 & 1 \lor 0 \\
0 \lor 0 & 1 \lor 1 & 0 \lor 0 & 0 \lor 0 \\
0 \lor 0 & 1 \lor 1 & 1 \lor 0 & 0 \lor 1 \\
1 \lor 1 & 1 \lor 0 & 0 \lor 1 & 0 \lor 1
\end{bmatrix} = \begin{bmatrix}1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\end{bmatrix}
$$
6. **(iii) Find $M_{(S \cap R)^{-1}}$:**
First find $S \cap R$ by element-wise AND:
$$
S \cap R = \begin{bmatrix}
1 \wedge 0 & 0 \wedge 0 & 0 \wedge 1 & 1 \wedge 1 \\
0 \wedge 0 & 1 \wedge 1 & 1 \wedge 0 & 0 \wedge 0 \\
0 \wedge 0 & 0 \wedge 1 & 0 \wedge 1 & 1 \wedge 0 \\
0 \wedge 1 & 0 \wedge 1 & 1 \wedge 0 & 1 \wedge 0
\end{bmatrix} = \begin{bmatrix}0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix}
$$
Now find the inverse (transpose):
$$
M_{(S \cap R)^{-1}} = (S \cap R)^T = \begin{bmatrix}0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0\end{bmatrix}
$$
7. **(iv) Find $M_{S \circ R}$ (composition):**
Recall Boolean matrix multiplication:
$$(M_{S \circ R})_{ij} = \bigvee_{k=1}^4 (M_R)_{ik} \wedge (M_S)_{kj}$$
Calculate each element:
- Row 1:
- $(1,1): (0\wedge1)\lor(0\wedge0)\lor(1\wedge0)\lor(1\wedge0) = 0$
- $(1,2): (0\wedge0)\lor(0\wedge1)\lor(1\wedge0)\lor(1\wedge0) = 0$
- $(1,3): (0\wedge0)\lor(0\wedge1)\lor(1\wedge0)\lor(1\wedge1) = 1$
- $(1,4): (0\wedge1)\lor(0\wedge0)\lor(1\wedge1)\lor(1\wedge1) = 1$
- Row 2:
- $(2,1): (0\wedge1)\lor(1\wedge0)\lor(0\wedge0)\lor(0\wedge0) = 0$
- $(2,2): (0\wedge0)\lor(1\wedge1)\lor(0\wedge0)\lor(0\wedge0) = 1$
- $(2,3): (0\wedge0)\lor(1\wedge1)\lor(0\wedge0)\lor(0\wedge1) = 1$
- $(2,4): (0\wedge1)\lor(1\wedge0)\lor(0\wedge1)\lor(0\wedge1) = 0$
- Row 3:
- $(3,1): (0\wedge1)\lor(1\wedge0)\lor(1\wedge0)\lor(0\wedge0) = 0$
- $(3,2): (0\wedge0)\lor(1\wedge1)\lor(1\wedge0)\lor(0\wedge0) = 1$
- $(3,3): (0\wedge0)\lor(1\wedge1)\lor(1\wedge0)\lor(0\wedge1) = 1$
- $(3,4): (0\wedge1)\lor(1\wedge0)\lor(1\wedge1)\lor(0\wedge1) = 1$
- Row 4:
- $(4,1): (1\wedge1)\lor(1\wedge0)\lor(0\wedge0)\lor(0\wedge0) = 1$
- $(4,2): (1\wedge0)\lor(1\wedge1)\lor(0\wedge0)\lor(0\wedge0) = 1$
- $(4,3): (1\wedge0)\lor(1\wedge1)\lor(0\wedge0)\lor(0\wedge1) = 1$
- $(4,4): (1\wedge1)\lor(1\wedge0)\lor(0\wedge1)\lor(0\wedge1) = 1$
So,
$$
M_{S \circ R} = \begin{bmatrix}0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\end{bmatrix}
$$
**Final answers:**
(i) $\overline{M_R} = \begin{bmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1\end{bmatrix}$
(ii) $M_R \cup S^{-1} = \begin{bmatrix}1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\end{bmatrix}$
(iii) $M_{(S \cap R)^{-1}} = \begin{bmatrix}0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0\end{bmatrix}$
(iv) $M_{S \circ R} = \begin{bmatrix}0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\end{bmatrix}$