Алгебра бинарных отношений

Булеан на декартовом произведении АВ множество бинарных отношений на паре множеств А,В 2^(А*В).

Элементы даного булеана — бинарное отношение, поэтому с ними как с множествами можно производить операции то есть можно сказать, что совокупность этих отношений образует булеву алгебру

1) Операция объединений бинарных отношений 





a()b<=>a b или a b

<> ≠

<= ≤

≤> всюду истинно

2) операция пересечения бинарных отношений 





ababилиa b

<> всюду ложно

≤= =

< пустое множество

3) Дополнение до декартового произведения А*В





ab

ab <=> неверно ab

Кроме операций  дополненияважными операций над бинарными отношениями является отрицание и произведение бинарных отношений.

4) Обращение бинарного отношения Обратным бинарным отношением ^(-1)(или обращением) называется бинарное отношение, опред. На В*А такое, что b^(-1)a<=> ab

aba1<^(-1)a2<=>a2<a1<=> a1>a2

<^(-1) = >

≥

Произведение бинарных отношений

C

aсC

acсуществует babbc

Если C*D, то их произведение считается неопределённым.

*={(a1,c2), (a2, c2), (a3,c2)}

Два элемента aсC тогда и только тогда, когда в их графическом изображении есть путь из «а» в «с»

Если , то их произведение тоже определено на множестве А.

Алгеброй бинарных отношений на множестве А называется множество всех бинарных отношений на множестве А вместе с операциями (2^(A*A),^(-1), *)

Булеан на множестве А^2 замкнут относительно операций 2^(A*A),^(-1), *, то есть применяя эти операции к элементам данного булеана в результате получим элементы этого же булеана.

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

1.Бинарным отношением на множестве А называется диагональным, если оно состоит из всевозможных пар одинаковых элементов. В графичном изображении диагонального бинарного отношения каждый элемент имеет петлю, других дуг нет.

2.Бинарное отношение на множестве А называется рефлексивным, если каждый элемент этого множества находится в отношении с самим собой.

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

3.Бинарное отношение  на множестве А называется транзитивным, если abbc =>ac

Бинарное отношение транзитивно тогда и только тогда, когда из а есть дуга в b из b есть дуга в с

4.Бинарное отношение на множине А называется симметричным, если ab =>ba

5.Бинарное отношение на множине А называется антисимметричным, если ab,ba => a=b

6.Бинарное отношение на множине А называется отношением эквивалентности, если оно одновременно рефлективно, симметрично и транзитивно

7.Бинарным отношением на множине А называется отношением порядка, если оно одновременно рефлективно, антисимметрично и транзитивно.

Два элемента a и b ищ множ. А назыв. Сравнимыми, если справедливо аb и ba.