6. Control questions and tasks / Контрольні запитання і завдання #

Properties of relations #

1. What is a binary relation on a set $A$? How is it related to $A \times A$?
2. Define reflexivity. Why does checking it require the underlying set $A$ and not just the list of pairs?
3. Define symmetry and transitivity. For each, give a small relation that has the property and one that does not.
4. Is the relation $\{(1,2),(2,3)\}$ on $\{1,2,3\}$ transitive? If not, which pair must be added?

Equivalence relations #

5. Define an equivalence relation. What three properties must it have?
6. What is an equivalence class? Explain how an equivalence relation partitions its set.
7. A relation on $\{1,2,3\}$ contains $(1,2)$ and $(2,3)$ and is known to be an equivalence relation. Which other pairs must it contain, and why?

Inverse and implementation #

8. Define the inverse $R^{-1}$ of a relation $R$. What is the inverse of $\{(1,2),(3,4),(5,6)\}$?
9. Show that $R$ is symmetric if and only if $R = R^{-1}$.
10. What is the time complexity of your transitivity check? How would a hash-based membership test improve it?

Tasks by hand #

11. Let $A = \{1,2,3\}$ and $R = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}$. Is $R$ reflexive? symmetric? transitive? Is it an equivalence relation? If so, list its equivalence classes.
12. Give the smallest relation on $\{1,2,3\}$ that contains $(1,2)$ and $(2,3)$ and is an equivalence relation. List all its pairs.
13. Compute the inverse of $R = \{(1,3),(2,3),(3,1)\}$.

Laboratory/Laboratory3/6questions.md · 1.6 KB · updated 2026-07-31 21:14