Замыкание отношения

Замыканием отношения $R$ относительно свойства $P$ называется такое множество $R^*$, что:

1. $R \subset R^*$.
2. $R^*$ обладает свойством $P$.
3. $R^*$ является подмножеством любого другого отношения, содержащего $R$ и обладающего свойством $P$.

Пример

• Пусть на множестве $A=\{1, 2, 3, 4\}$ задано отношение $R = \{(1, 2), (3, 4), (4, 2)\}$. Видно, что отношение $R$ не симметрично, не рефлексивно и не транзитивно. Замыканием $R$ относительно свойства симметричности является $R^* = \{(1, 2), (3, 4), (4, 2); (2, 1), (4, 3), (2, 4)\}$. Замыканием $R$ относительно рефлексивности является $R^* = \{(1, 2), (3, 4), (4, 2); (1, 1), (2, 2), (3, 3), (4, 4)\}$. Замыканием $R$ относительно транзитивности является множество $R^* = \{(1,2), (3, 4), (4, 2); (3, 2)\}$.

См. также

• Алгоритм Уоршелла

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.