سوال ۱۱۱ کنکور ارشد علوم کامپیوتر ۱۴۰۵

The relation matrix, with rows and columns ordered $a,b,c$, is

$M(R)=\begin{pmatrix}0&1&1\\0&1&0\\1&0&1\end{pmatrix}.$

The composition $R\circ R=R^{2}$ has as its matrix the boolean square $M(R)\odot M(R)$, whose $(i,j)$ entry is $\bigvee_{k}\left(M_{ik}\wedge M_{kj}\right)$:

$M(R)\odot M(R)=\begin{pmatrix}1&1&1\\0&1&0\\1&1&1\end{pmatrix}.$

Thus $R\circ R=\{(a,a),(a,b),(a,c),(b,b),(c,a),(c,b),(c,c)\}$. Test the four properties on this result:

• Reflexive — yes: the diagonal is all $1$, so $(a,a),(b,b),(c,c)\in R\circ R$. Vertex $a$ acquires a self-loop through the walk $a\to c\to a$.
• Symmetric — no: $(a,b)\in R\circ R$ but $(b,a)\notin R\circ R$.
• Antisymmetric — no: both $(a,c)$ and $(c,a)$ lie in $R\circ R$ with $a\ne c$.
• Transitive — yes: every two-step chain stays inside the relation (e.g. $(c,a),(a,b)\Rightarrow(c,b)\in R\circ R$); since $a$ and $c$ already reach all three elements and $b$ reaches only itself, no required pair is missing.

Therefore $R\circ R$ is reflexive and transitive (a preorder), matching option 1.

Exam trick: $R$ itself is not reflexive ($a$ has no self-loop), yet $R\circ R$ is — a length-2 closed walk $a\to c\to a$ manufactures $(a,a)$. Composing a relation with itself can create properties the original relation lacks.