Так как бинарные отношения являются множествами, то к ним применимы все понятия, которые вводятся для множеств: понятие равенства, включения, а также операции пересечения, объединения и дополнения. В этом разделе мы будем считать, что все отношения заданы на одном и том же множестве X.
Пусть a и b - два бинарных отношения на множестве X. Каждому из них соответствует некоторое множество пар (подмножества 
и 
).
Определение 2.1. Пересечением отношений a и b, заданных на множестве X, называется отношение 
такое, что:
Пример 2.1. Пересечением отношений "не меньше" и "не равно", определенных на множестве действительных чисел R, является отношение "строго больше":
.
Определение 2.2. Объединением отношений a и b, заданных на множестве X, называется отношение, такое, что:
является отношение "быть ребенком".
Определение 2.3. Разностью отношений a и b, заданных на множестве X, называется отношение a\b, такое, что:
Пример 2.3. Разностью отношений "не меньше" и "не больше" на R является отношение "больше":
.
Пример 2.4. Разностью отношений "быть ребенком" и "быть дочерью", определенных на множестве всех людей, является отношение "быть сыном".
Определение 2.4. Дополнением 
отношения a, определенного на множестве X, называется отношение, определяемое подмножеством пар из X x X, не входящих в:
x y 
.
Пример 2.5. Дополнением отношения "не меньше" на R является отношение "не меньше":
.
Отметим, что приведенные выше определения являются просто перефразировками соответствующих определений для обычных множеств и все свойства теоретико-множественных операций пересечения, объединения и дополнения, имеющие место для произвольных множеств, выполняются и для отношений.
Кроме теоретико-множественных операций для отношений вводятся некоторые дополнительные операции, которые связаны с их специфической структурой. Мы рассмотрим две такие операции.
Определение 2.5. Если в каждой упорядоченной паре, принадлежащей отношению a, поменять местами первую и вторую компоненты, то получим новое отношение, которое называется обратным для отношения a и обозначается через a-1:
.
Пример 2.6. Обратным для отношения "не меньше" на множестве действительных чисел R является отношение "меньше":
.
Пример 2.7. Обратным для отношения "быть родителем" на множестве людей является отношение "быть ребенком".
Граф отношения a-1 получается из графа отношения переориентацией всех дуг (рис. 4).
(а) Отношение a (б) Отношение a-1
Рис. 4. Графы отношений a и a-1
Если отношение задано с помощью булевой матрицы, то, поменяв в ней местами строки и столбцы, получим булеву матрицу отношения a-1 (рис 5).
(а) Матрица отношения a (б) Матрица отношения a-1
Рис. 5. Матрицы отношений a и a-1
Определение 2.6. Произведением или композицией отношений a и b, заданных на множестве X, называется отношение a°b, состоящее из таких кортежей (x, z), для которых существует элемент 
, удовлетворяющий условию 
и 
:
.
Пример 2.8. Произведением отношений "быть братом" и "быть отцом" является отношение "быть братом одного из родителей", т. е. "быть дядей".
Если отношения a и b на некотором множестве X заданы с помощью графов, то принадлежность пары (x, z) к отношению a °b означает, что из вершины x в вершину z можно попасть точно за два шага, причем первый из них делается по дуге отношения a, а второй - по дуге отношения b.
На рисунке 6 изображены графы, представляющие отношения a (точечные дуги) и b (пунктирные дуги), и графы, представляющие произведения отношений a°b и b°a.
(а) Графы отношений a и b (б) Граф отношения a°b
(в) Граф отношения a°b
Рис. 6. Пример произведения отношений (a°b 
b°a)
Пример, приведенный на рисунке 6, показывает, что для произведения отношений коммутативный закон не выполняется.
Для выражения матрицы произведения двух отношений a и b, заданных булевыми матрицами 
и 
, введем понятие "булево сложение" 
, определив его следующим образом:
0 0 = 0, 0 
1 = 1, 1 0 = 1, 1 1 = 1.
Если теперь
M = (aij), M = (bjk), (i, j, k = 1, 2, …, n),
то
M a°b = (cik),
где
cik = ai1 b1k … ain bnk
Матрица M a°b называется булевым произведением матриц M a и M b. Легко проверить, что M a°b является булевой матрицей произведения a°b.
Пример 2.9. Вычислим матрицы произведений a°b и b°a отношений a и b, представленных графами на рисунке 6.
Для этого перемножим соответствующие матрицы M a и M b (строки и столбцы матриц упорядочены в соответствии с алфавитным порядком букв a, b, c, d, обозначающих вершины графа).
Определим еще одну унарную операцию над отношением.
Определение 2.7. Транзитивным замыканием отношения a называется бинарное отношение 
такое, что x y тогда и только тогда, когда существует такая цепочка элементов из X:
z0 = x, z1, z2,..., zn = y,
что между соседями в этой цепочке выполнено отношение a:
z0 a z1, z1 a z2,..., zn-1 a zn.
Пример 2.10. На рисунке 7 изображены графы, представляющие отношение a и его транзитивное замыкание .
Рис. 7. Транзитивное замыкание отношения a
В матричной форме операция транзитивного замыкания отношения a выражается через объединение степеней матрицы M a отношения a:
В приведенной формуле объединение матриц понимается следующим образом:
.
