Свойства бинарных отношений

План лекции №11

1. Рефлексивность и антирефлексивность отношений
2. Симметричность, асимметричность и антисимметричность отношений
3. Необходимое и достаточное условие асимметричности бинарного отношения
4. Полносвязность и слабосвязность отношений
5. Необходимое и достаточное условие полносвязности бинарного отношения
6. Транзитивность и ацикличность отношений, негатранзитивность
7. Необходимое и достаточное условие ацикличности бинарного отношения
8. Понятие негатранзитивного отношения
9. Двойственность свойств бинарных отношений
10. Связи между свойствами бинарных отношений

Отношение R называется рефлексивным, если для всех х пара (х, х) входит в R (все петли ∈ в граф).

Отношение R называется антирефлексивным, если для всех х пара (х, х) не входит в R.

Граф антирефлексивного отношения не содержит ни одной петли. Граф рефлексивного отношения содержит все петли.

Утверждения о свойствах рефлексивности и антирефлексивности отношения

1. Операции: инверсии, объединения, пересечения бинарных отношений сохраняют свойство рефлексивности Р (антирефлексивности АР) этих отношений.
2. Операции дополнения и перехода к двойственному бинарному отношению преобразуют свойство Р в свойство АР этих отношений (и обратно).
3. Вычитание рефлексивного отношения из рефлексивного отношения преобразует свойство Р в свойство АР.

Отношение R называется симметричным, если всегда, когда пара (х, y) входит в R, то и пара (y, x) входит в R (инверсия R совпадает с R). (С)

Отношение R называется антисимметричным, если в него входит не более одной из каждых двух пар (х, y) или (y, x). (АнтиС)

Отношение R называется асимметричным, если оно и антисимметрично, и антирефлексивно

Утверждения о свойствах С, АнтиС, АС отношений

1. Операции инверсии и пересечения бинарных отношений сохраняют свойства симметричности (С), антисимметричности (АнтиС), асимметричности (АС) этих отношений.
2. Операции объединения, дополнения и вычитания симметричных бинарных отношений сохраняют свойство С этих отношений.
3. Вычитание произвольного отношения из антисимметричного (асимметричного) отношения сохраняет свойство АнтиС (АС) .
4. Пересеченние произвольного отношения с антисимметричным (асимметричным) отношения сохраняет свойство АнтиС (АС) .

Симметричная и асимметричная части бинарного отношения

Из всякого отношения R путем удаления колец и петель можно выделить его асимметричную часть R^ас.

Удаленные кольца и петли образуют симметричную часть отношения R^с .

Бинарное отношение R асимметрично тогда и только тогда, когда оно совпадает с асимметричной частью двойственного отношения R^дв.

Отношение называется полносвязным (П), если для всех х,у в него входит хотя бы одна из двух пар: (х,у) или (у,х).

Отношение называется слабо полносвязным (СП)(слабосвязным), если для всех неравных х,у в него входит хотя бы одна из двух пар: (х,у) или (у,х).

Утверждения о свойствах полносвязности отношений

1. Полносвязное отношение всегда рефлексивно.
2. Полносвязное отношение является частным случаем слабосвязного отношения с дополнительным условием рефлексивности.
3. Операции объединения и инверсии полносвязных (слабосвязных) бинарных отношений сохраняют свойство П (СП) этих отношений.
4. Объединение полносвязного (слабосвязного) отношения с произвольным отношением сохраняет свойство П (СП) .
5. Свойства полносвязности и асимметричности отношений являются двойственными.
6. Свойства слабосвязности и антисимметричности отношений являются двойственными.

Бинарное отношение R полносвязно тогда и только тогда, когда его асимметричная часть совпадает с двойственным отношения R^дв.

Отношение R называется транзитивным, если всегда, когда две пары (х, у) и (у,z) входят в R, то и пара (х,z) тоже входит в R.

Свойство транзитивности: примеры отношений с кольцами

Если отношение R содержит кольца, то у студентов могут возникнуть типичные ошибки:

Утверждения о свойстве транзитивности (Т) отношений

1. Операции инверсии и пересечения транзитивных отношений сохраняют их свойство транзитивности (Т).
2. Добавление к графу транзитивного отношения петель не изменит свойства Т этих отношений.
3. Возведение в квадрат транзитивного отношения не приводит к появлению новых пар : R² ⊆ R .
4. Возведение транзитивного отношения в любую степень не приводит к появлению новых пар : R^k ⊆ R .
5. Свойство 3 является необходимым и достаточным условием транзитивности отношения R .

Понятие ацикличного отношения

Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы ).

В ацикличном отношении не должно быть никаких циклов (в т.ч. – ни петель, ни колец).

Свойство ацикличности. Примеры.

Отношение R является ациклическим тогда и только тогда, когда никакая его степень R^k не имеет пересечений с инверсным отношением R^-1.

Отношение R является ациклическим тогда и только тогда, когда любая его степень R^k является антирефлексивным отношением (АР).

Отношение R называется негатранзитивным, если отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z .

Двойственность свойств транзитивности и негатранзитивности:
Отношение R является негатранзитивным, если его дополнение R^доп транзитивно и наоборот.
Если из графа негатранзитивного отношения удалять петли, то свойство негатранзитивности сохранится.
В графе негатранзитивного отношения отсутствие связи (кольца или дуги) между двумя вершинами влечет отсутствие петель в обоих вершинах.

Негатранзитивность бинарных отношений (примеры)

Понятие сильнотранзитивного отношения

Отношение R называется сильно транзитивным , если оно одновременно транзитивно и негатранзитивно.
Если отношение R является сильнотранзитивным, то его дополнение R^доп сильнотранзитивно и наоборот.
При переходе к инверсному или двойственному отношению свойство сильной транзитивности также сохраняется.
В графе сильнотранзитивного отношения отсутствие связи (кольца или дуги) между двумя вершинами влечет отсутствие петель в обоих вершинах, но, если есть кольцо, то должны быть и петли.

Транзитивные и негатранзитивные отношения: (примеры)

1. Асимметричная и симметричная части транзитивного отношения транзитивны.

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

Маршрут, проходящий через кольца графа транзитивного отношения, может укорачиваться только через кольцо.

2. Антирефлексивное и транзитивное бинарное отношение R всегда ациклично.

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

3. Асимметричное и транзитивное бинарное отношение R всегда ациклично.

Это утверждение является следствием утверждения 2, так как асимметричное отношение обязательно является антирефлексивныи.

4. Негатранзитивное и асимметричное бинарное отношение R всегда транзитивно.

5. Транзитивное и полносвязное бинарное отношение R всегда негатранзитивно.

Для доказательства надо применить принцип двойственности к утверждению 4.

6. Ацикличное и слабосвязное бинарное отношение R всегда сильно транзитивно.

7. Транзитивное, антирефлексивное и слабосвязное бинарное отношение R всегда сильно транзитивно. (Следствие 6. и 2.)