Операции над бинарными отношениями

Так как бинарные отношения, определенные на фиксированной паре множеств А, В, являются подмножествами декартового произведения А × В, то над ними можно производить операции объединения, пересечения и дополнения (в множестве А × В). Так, если R, S – два бинарных отношения, определенных па паре множеств А, В, то для любых , тогда и только тогда, когда aRb или aSb; тогда и только тогда, когда aRb и aSb; тогда и только тогда, когда не aRb.

Помимо теоретико-множественных операций над отношениями важное значение имеют еще две операции над ними: обращение и умножение отношений.

Определение. Пусть – бинарное отношение, определенное на паре множеств А, В. Отношением, обратным к бинарному отношению R, называется отношение, определенное на паре множеств В и А и состоящее из всех тех и только тех пар (b, а), для которых (, ).

Бинарное отношение, обратное к отношению R, обозначается R ^–1. Таким образом, . Можно сказать, что (R ^-1)^-1= R.

ПРИМЕР. Если R – бинарное отношение «х является родителем у», то R ^–1 – отношение «х является ребенком (сыном или дочерью) у».

Определение. Пусть – бинарное отношение, определенное на паре множеств А, В, а – бинарное отношение, определенное на паре множеств В, С. Произведением отношений R и S называется бинарное отношение, определенное на паре множеств А и С и состоящее из всех тех и только тех пар (а, с) (, ), для которых существует элемент х из В такой, что aRx и xSc.

Произведение бинарных отношений и обозначим через RS. Таким образом, и a (RS) c тогда и только тогда, когда существует элемент такой, что aRx и xSc.

Кроме того, отношения могут задать новое отношение, называемое ком позицией.

R ₁° R ₂= R ={(a, b, c)|(a, b)Î R ₁ и с Î А и a R ₁ b R ₂ c }. Последовательная композиция отношения с самим собой называется степенью отношенияR ° R ° R °…° R = R ⁿ.

Имеем: R ⁰= I; R ¹= R; R ° R = R ²;…… R ° Rⁿ ^-1= Rⁿ.

Утверждение. Если некоторая пара (a, b) принадлежит какой-либо степени отношения R на множестве А мощности n, то эта пара принадлежит и степени R не выше n- 1. R Í A ²& | A |= n Þ (" a, b Î A) ($ k | aR^kb Þ k < n).

Определение. Композиция отношения с обратным называется ядром отношения и обозначается как ker R=R° R^-1. Ядро отношения само является отношением на А.

Теорема 3.1. Пусть , , – бинарные отношения. Тогда произведения (RS) T и R (ST)определены и (RS) T = R (ST). То есть умножение бинарных отношений ассоциативно.

Теорема 3.2. Пусть , – бинарные отношения. Тогда выражения (RS)^–1 и S ^–1 R ^–1 определены и имеет место равенство (RS)^–1 = S ^–1 R ^–1.

Рассмотрим операции бинарных отношений на языке матриц бинарного отношения.

1. Если то и , где сложение осуществляется по правилам 0+0=0, 1+1=0+1=1+0=1, а умножение – обычным способом. Итак,

2. Матрица получается перемножением соответствующих элементов из и : .

3. Если , то , где умножение матриц производится по обычному правилу умножения матриц, но произведение и сумма элементов – по определённым в свойстве 1 правилам.