logo
Дискретная математика

Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.

Пусть р и p’ отношения на множестве А. Отношение р’ называется замыканием р относительно свойства С, если:

  1. р’ обладает свойством С, т.е. С(р’)

  2. р’ является надмножеством р:р с р’

  3. Р’ является наименьшим: С(р’’) и р с р’’ => р’ c р’’ (любое р’’, обладающее свойством С и содержащее в себе р, содержит в себе также и р’)

Пусть р+ - объединение положительных степеней р, а р* - объединение неотрицательных степеней р, т.е. р+= и р*= . Тогда р+ - транзитивное замыкание р, а р* - рефлексивно-транзитивное замыкание р.

  1. Yandex.RTB R-A-252273-3
    Yandex.RTB R-A-252273-4