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

Так как всякое бинарное отношение — это множество упорядоченных

пар, то над бинарными отношениями можно выполнять все теоретико-

множественные операции: объединение, пересечение, разность, дополнение.

Если R — бинарное отношение, то в качестве универсального

множества в этом случае рассматривают множество U = F (R)´ F (R),

где F (R) —полеотношения R. Еслисовместнорассматриваетсянесколько

бинарных отношений, то в качестве универсального множества рассматривают множество U = A ´ A, где А есть объединение полей

каждого из рассматриваемых отношений.

Например, пусть рассматриваются отношения

R = {(1,1), (1,2), (1,3), (3,3)} и

S = {(1,1), (2,2), (3,3)}.

В этом случае универсальное множество имеет вид

U={(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), 3,3)}.

Тогда результаты некоторых теоретико-множественных операций

будут следующими

R = (), (2,2), (2,3), (), (3,2);

S = (), (), (), (2,3), (), (3,2); R / S = (), ();

R Ç S = (), (3,3).

Кроме обычных теоретико-множественных операций, над бинар-

ными отношениями определяют специальную операцию.

Композицией бинарных отношений R и S называют бинарное отно-шение Т,состоящееизвсехупорядоченных пар (a, b),длякаждойиз

которых существует элемент

c Î R Ç S -

такой, что

(a, c)Î R, (c, b)Î S

(то есть aRc, cSb). Операцию композиции записывают так T = R  S.

Например, пусть

R = {(1,1), (1,2), (2,3), (3,3)}, S = {(2,4), (2,5), (3,2), (5,5)}.

Тогда

T = R  S = (),(),(2,2),(3,2), S  R ={(3,3 }.

}

{

3,1

2,1

}

{

2,1

1,3

1,2

3,1

{

}

1,2

1,3

{

}

1,1

+

}

{

)

1,4

1,5

Лекция 8

Дата добавления: 2015-11-16