WikiSort.ru - Не сортированное

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

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

Другими словами, ${\displaystyle R^{*}}$ — минимальное надмножество ${\displaystyle R}$ , выдерживающее ${\displaystyle P}$ .

Пример

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

См. также

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

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