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

Поскольку всякое отношение есть некоторое множество пар, над отношениями применимы все стандартные операции над множествами, т. е. объединение, пересечение, дополнение. Универсальным множеством для операции дополнения при этом является А  В.

Рассмотрим операцию композиции отношений. Заданы множества А, В, С и отношения R  А  В и S  В  С. Композиция отношений S и R (обозначается SR, не путать с пересечением множеств S и R!) – это такое отношение между элементами множеств А и С, что для всех а  А сечение множества SR по а совпадает с сечением множества S по подмножеству R(a)  B. Это записывается в виде (SR)(a)  S(R(a)). Например, пусть отношения R и S заданы соответственно следующими матрицами:

R = ,S = .

Тогда композиция SR этих отношений представится матрицей

SR = .