Операции над бинарными отношениями
Мы уже знаем, что бинарные отношения являются множествами и, следовательно, можно говорить о равенстве бинарных отношений и о включении одного бинарного отношения в другое: j = y, j Í y.
На бинарные отношения, заданные на некотором множестве переносятся общие операции над множествами. Пусть j и y - бинарные отношения заданные на множестве A. Тогда
1) jÇy - есть бинарное отношение в A являющееся пересечением отношений j и y,
2) jÈy - есть бинарное отношение в A являющееся объединением отношений j и y,
3) jy - есть бинарное отношение в A являющееся разностью отношений j и y,
4) `j - есть бинарное отношение в A являющееся дополнением к бинарному отношению j в A, т.е. `j = A2j.
Примеры. Определим следующие бинарные отношения
j1 = {(n,m) Î 2 : n ³ m },
j2 = {(n,m) Î 2 : n > m },
j3 = {(n,m) Î 2 : n < m },
j4 = {(n,m) Î 2 : 4n = m2 },
тогда между ними имеют место следующие отношения включения:
j2 Ì j1; j1 Èj2 = j1, j1 Çj2 = j2, j1j2 = {(n,m) Î 2:n = m } последнее бинарное отношение является отношением равенства в ну и т.д.
Можно определить еще одну операцию над парой заданных на множестве A бинарных отношений j и y.
Определение. Назовем суперпозицией (композицией) этих двух бинарных отношений бинарное отношение (мы будем обозначать его как jy) определенное следующим образом: (a,c) Î jy Û когда в множестве A найдется хотя бы один элемент b такой, что (a,b) Î j и (b,c) Î y.
Примеры. Для бинарных отношений определенных в предыдущем примере показать, что справедливы следующие равенства:
1) j1 j2 = j2 j1 = j2. Действительно, поскольку n ³ m1, а m1 > m, то n > m; обратно, если n > m1 m1 ³ m, то n > m.
2) j1j3 = 2. Рассмотрим произвольную пару (n,m) Î 2, возможны два случая a)n ³ m; b)n < m. Рассмотрим случай a) (n,m-1) Î j1, (m-1,m) Î j3Þ (n,m) Î j1j3
в случае b) (n,n-1) Î j1, (n-1,m) Î j3Þ (n,m) Î j1j3. Итак, мы показали, что 2 Í j1j3 и следовательно j1j3 = 2.
3) j1j4 ¹ j4j1. Этот пример показывает, что суперпозиция бинарных отношений, вообще говоря, не обладает свойством коммутативности.
Доказательство. Поскольку (3,1) Î j1 и (1,2) Î j4 мы получаем, что пара (3,2) Î j1j4 Теперь надо показать, что пара (3,2) Ï j4j1 перепишем бинарное отношение j4 как j4 = {((m2)/ 4,m): $k Î , m = 2k} следовательно (3,n) Ï j4 причем для любого n; откуда получаем, что пара (3,2) Ï j4j1, ибо в противном случае (3,n) Î j4, что невозможно. Доказательство окончено.
Однако легко показать, что
|
здесь EM - бинарное отношение равенства в множестве M.
Немного сложнее доказательство следующих равенств. Пусть в множестве A заданы бинарные отношения y и ji, i Î I, здесь I - конечный или бесконечный набор индексов. Тогда
|
|
заметим, что в вышеприведенных соотношениях значки È нельзя заменить на Ç.
Докажем первое утверждение. Пусть (a,b) Î (Èi Î Iji)y Û $c : (a,c) Î Èi Î Iji и (c,b) Î yÛ $i0 Î I : (a,c) Î ji0 Þ (a,b) Î ji0y Þ (a,b) Î Èi Î I (jiy).
Утверждение. Для любых бинарных отношений j, y,r заданных на некотором множестве A справедливо следующее равенство
|
Оно означает, что суперпозиция бинарных отношений обладает свойством ассоциативности.
Доказательство.
Пусть пара (a,b) Î (jy)rÞ $c :(a,c) Î jy и (c,b) Î r. Это означает, что $d : (a,d) Î j и (d,c) Î yÞ(d,b) Î yr и (a,b) Î j(yr). Итак мы доказали, что если (a,b) Î (jy)r, то из этого следует, что (a,b) Î j(yr). Обратное включение доказывается аналогично.
Это утверждение говорит о том, что какими бы двумя различными способами мы ни расставляли скобки в выражении j1 j2... jn, чтобы получить суперпозицию двух отношений мы получим равные отношения.
Определение. Пусть на множестве A задано бинарное отношение j, тогда отношением обратным к j называется отношение j-1 также заданное на A, которое состоит из тех и только тех пар (b,a), для которых справедливо, что (a,b) Î j.
Пример. Пусть на множестве A = {0,1,2,3 } задано бинарное отношение j = {(0,1);(2,3);(1,3)}, тогда j-1 = {(1,0);(3,2);(3,1) }
Кроме того, справедливы следующие равенства:
|