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

Так как отношения на M задаются подмножествами, R Í M ₁´ M ₂ (или R Í M ², если M ₁= M ₂= M), для них определимы те же операции, что и над множествами (см. параграф 1.2):

1. Объединение R ₁È R ₂: R ₁È R ₂={(a, b): (a, b)Î R ₁ или (а, b)Î R ₂}.

2. Пересечение R ₁Ç R ₂: R ₁Ç R ₂={(a, b): (a, b)Î R ₁ и (а, b)Î R ₂}.

3. Разность R ₁\ R ₂: R ₁\ R ₂={(a, b): (a, b)Î R ₁ и (а, b)Ï R ₂}.

4. Дополнение : = U \ R, где U = M ₁´ M ₂ (или U = M ²).

Кроме того, определяют другие операции над отношениями, в том числе:

5. Обратное отношение (инверсия) R ^–1:

R ^–1={(a, b): (b, a)Î R).

6. Составное отношение (композиция) R ₁ R ₂:

R ₁ R ₂={(a, b): ($ c) [< a, c >Î R ₁ и < c, b >Î R ₂]}.

Обозначим R R = R ⁽²⁾. Используя это обозначение, можно определить R ^{( n )} для любого n Î N, n >1 следующим образом:

R ^{( n )} ={(a, b): (a, с)Î R и (с, b)Î R ^{( n –1)}}.

7. Транзитивное замыкание R °:

R °={(a, b): (a, с ₁), (с ₁, с ₂), …, (с_k, b)Î R } (определение I).

Унарная операция транзитивного замыкания R ° может быть также определена как бесконечное объединение:

R °= R È R ⁽²⁾ È R ⁽³⁾ È…È R ^{( n )} È… (определение II).

Если отношение R транзитивно, то R °= R. Например, транзитивное замыкание отношения R – “быть больше” совпадает с этим отношением, т.е. R °= R.

8. Рефлексное замыкание R *.

Пусть тождественное отношение E ={(a, a): a Î M }. Тогда

R *= R °È E.

Если R транзитивно и рефлексивно, то R *= R.

Процедура вычисления транзитивного замыкания * R ° для отношения R Î M ´ M:

1) присвоить R ₁ R;

2) вычислить R ₁È R ₁⁽²⁾ = R ₁È R ₁° R ₁; присвоить R ₂ R ₁È R ₁⁽²⁾ ;

3) сравнить: R ₁= R ₂. Если R ₁¹ R ₂, то присвоить R ₁ R ₂ и перейти к шагу 2. В противном случае – к шагу 4;

4) конец: R ₁= R ₂= R °.

Пример 1. Пусть отношение R – “быть руководителем”, опреде-ленное на множестве сотрудников организации M. Назовите отношения: , R ^–1, R °, R *. Каковы свойства отношений?

=(M ´ M)\ R – “не быть руководителем”.

R ^–1={(b, a): (a, b)Î R } – “быть подчиненным”.

R °= R – “быть руководителем” (так как R – транзитивно).

R *= R °È E = R È E – трудно назвать такое отношение, возможно – “быть руководителем, в том числе по отношению к самому себе”.

Пример 2. Пусть на множестве M ={2, 4, 6}определено отношение R – “быть меньше”. Задать характеристическим свойством и списком отношение R, обратное отношение R ^–1 и дополнение . Сравнить отношения. Определить их свойства.

R ={(a, b): a < b } – “быть меньше”.

R ={(2, 4), (2, 6), (4, 6)}.

R ^–1={(a, b): (b, a)Î R }={(a, b): a > b } – “быть больше”.

R ^–1={(4, 2), (6, 2), (6, 4)}.

=(M ´ M)\ R ={(a, b): (a, b)Ï R }={(a, b): a ³ b } – “быть не меньше”.

={(2, 2), (4, 2), (4, 4), (6, 2), (6, 4), (6, 6)}.

Между R, R ^–1 и имеют место соотношения:

= R ^–1 È E; R ^–1Ç E =Æ, где E ={(a, b): a = b } – тождественное отношение;

R Ç = U, R È R ^–1 È E = U, где U = M ´ M;

R Ç =Æ; R Ç R ^–1 =Æ; R Ç E =Æ.

Отношения R и R ^–1 – антирефлексивны, антисимметричны, транзи-тивны, т.е. являются отношениями строгого порядка. Эти отношения задают полный порядок на множестве M.

Отношение – рефлексивно, антисимметрично, транзитивно, т.е. является отношением нестрогого порядка; оно также задает полный порядок на множестве М.

Пример 3. Пусть R – отношение на N: R ={(a, b): a > b } – “быть больше”. Выполнить операции над R.

R È R = R;

R Ç R = R;

R \ R =Æ;

R ^–1={(a b): a < b } – “быть меньше”;

= U \ R ={(a, b): a £ b }= R ^–1 È E – “быть не больше”, где E – тождественное отношение, E ={(a, b): a = b };

R R = R ⁽²⁾={(а, b): a –1> b } – “быть больше по крайней мере на 2”;

R °= R (так как R транзитивно);

R *= R °È E ={(a, b): a > b или a = b }={(a, b): a ³ b } – “быть не меньше”.

Пример 4. Пусть отношение R на множестве M точек действительной плоскости – “находиться на одинаковом расстоянии от начала координат”. Каков содержательный смысл отношений R ^–1 и ? Определить соотношения между отношениями R, R ^–1 и . Каковы свойства отношений?

R ^–1={(a, b): b R a }. Так как заданное отношение R симметрично, т.е. для любых a, b Î M a R b влечет b R a, то R ^–1= R – “находиться на одинаковом расстоянии от начала координат”.

= U \ R, т.е. соответствует отношению “находиться на разном расстоянии от начала координат”; U = M ´ M.

Очевидны следующие соотношения: Ç R =Æ; È R = U. Кроме того, R = R ^–1, поэтому Ç R ^–1=Æ, È R ^–1= U, а также R ^–1Ç R = R, R ^–1È R = R.

Отношения R и R ^–1 – рефлексивны, симметричны, транзитивны. Отношение – антирефлексивно, симметрично, нетранзитивно.

Пример 5. Пусть R ₁ и R ₂ – отношения на N:

R ₁={(a, b): b = a +2; a, b Î N },

R ₂={(a, b): b = a ²; a, b Î N }.

Определить составные отношения R ₁ R ₂, R ₂ R ₁, R ₁ R ₁= R ₁⁽²⁾, R ₂ R ₂= R ₂⁽²⁾, R ₁^{( n )}, R ₂^{( n )}.

R ₁ R ₂={(a, b): (a, c)Î R ₁; (c, b)Î R ₂; a, b, c Î N }={(a, b): c = a +2; c ²= b; a, b, c Î N }.

Таким образом: R ₁ R ₂={(a, b): (a +2)²= b; a, b Î N }=(1, 9), (2, 16), (3, 25), (4, 36), …

Аналогично: R ₂ R ₁={(a, b): a ²+2= b; a, b Î N }=(1, 3), (2, 6), (3, 11), (4, 18), …

R ₁⁽²⁾ = R ₁ R ₁={(a, b): a +4= b; a, b Î N }=(1, 5), (2, 6), (3, 7), (4, 8), …

R ₂⁽²⁾ = R ₂ R ₂={(a, b): a ⁴= b; a, b Î N }=(1, 1), (2, 16), (3, 81), …

R ₁^{( n )} ={(a, b): a +2 n = b; a, b Î N }=(1, 2 n +1), (2, 2 n +2), (3, 3 n +3), …

R ₂^{( n )} ={(a, b): a ^{2 n} = b; a, b Î N }=(1, 1), (2, 4 ⁿ), (3, 9 ⁿ), (4, 16 ⁿ), …

Пример 6. Пусть b(M) – множество всех подмножеств, составлен-ных из элементов множества M ={ a, b }. Задать списком отношение R ={(A, B): A Ì B)} – “являться строгим включением”, определенное на b(M), а также R ^–1, , R °, R *.

b(M)={Æ, { a }, { b }, { a, b }}.

R ={(A, B): A Ì B)} – “являться строгим включением”;

R ={(Æ, { a }); (Æ, { b }); (Æ, { a, b }); ({ a }, { a, b }); ({ b }, { a, b })}.

R ^–1={(A, B): A É B)} – “строго включать”;

R ^–1={({ a }, Æ); ({ b }, Æ); ({ a, b }, Æ); ({ a, b }, { a }); ({ a, b }, { b })}.

={(A, B): A Ë B } – “не являться строгим включением”;

={(Æ, Æ); ({ a }, Æ); ({ a }, { a }); ({ a }, { b }); ({ b }, Æ); ({ b }, { a }); ({ b }, { b }); ({ a, b }, Æ); ({ a, b }, { a }); ({ a, b }, { b }); ({ a, b }, { a, b })}.

R °= R ={ A, B): A Ì B } – “являться строгим включением” (так как R транзитивно);

R *= R °È E = R + E ={(A, B): A Ì B или A = B }={(A, B): A Í B } – “являться нестрогим включением”;

R *={(Æ, Æ); (Æ, { a }); (Æ, { b }); (Æ, { a, b }); ({ a }, { a }); ({ a }, { a, b }); ({ b }, { b }); ({ b }, { a, b }); ({ а, b }, { а, b })}.

Правила построения матриц отношений , R ^–1, R ⁽²⁾, R °, R *, по известной матрице отношения R:

· Матрица дополнения – в матрице исходного отношения R заменить единицы нулями, а нули – единицами.

· Матрица обратного отношения R ^–1 – проставить в ней единицы, симметричные (относительно главной диагонали) соответствующим единицам исходной матрицы. Очевидно, что матрица симметричного отношения совпадает с матрицей его обратного отношения.

· Матрица составного отношения R ⁽²⁾ – для каждой единицы исходной матрицы отношения R, принадлежащей i -й, строке, например единицы в j -м столбце, т.е. для =1, в i -й строке вычисляемой матрицы проставить единицы в тех k -х столбцах, в которых имеются единицы в j -й строке исходной матрицы.

· Матрица транзитивного замыкания R * нетранзитивного отношения R – выполнить серию (одну или более) итераций, заключающихся в следующем:

а) для каждой единицы исходной матрицы отношения R, принадлежащей i -й строке, например единицы в j -м столбце, т.е. для =1, в i -й строке вычисляемой матрицы проставляются единицы в тех k -х столбцах, в которых имеются единицы в i -й строке, а также в j -й строке исходной матрицы;

б) полученную матрицу отношений R È R R = R È R ⁽²⁾ принимают за исходную и повторяют процедуру а), выполняя таким образом следующий цикл вычислений (построения матрицы), и т.д. до тех пор, пока матрица не перестанет изменяться, т.е. пока в некотором цикле вычислений исходная и вычисленная матрицы не совпадут.

Очевидно, что матрица транзитивного замыкания R ° совпадает с матрицей исходного отношения R, если отношение R транзитивно.

· Матрица рефлексивного замыкания R * – построить матрицу транзитивного замыкания (см. выше), а затем в полученной матрице заменить нули на главной диагонали, если таковые имеются, на единицы. Очевидно, что отношение R рефлексивно, матрица рефлексивного замыкания R * совпадает с матрицей транзитивного R ° замыкания.

Пример 7. Каковы свойства отношения операции над R, заданного матрицей на рис. 2.5. Выполнить операции над R.

Отношение R ={(a, b), (b, a), (c, b)}:

· антирефлексивно (следовательно, нерефлексивно),

так как на главной диагонали только нули;

· не симметрично, поскольку имеется c R b, но нет b R c;

· не антисимметрично, так как имеются a R b и симметричная пара b R a;

· не транзитивно, поскольку, например, имеются c R b и b R a, но нет c R а.

Выполним операции над R ={(a, b), (b, a), (c, b)}:

R È R = R; R Ç R =Æ; R \ R =Æ;

= U \ R ={(a, a), (a, c), (b, b), (b, c), (c, a) (c, c)} (см. матрицу на рис 2.6, а);

R ^–1={(a, b), (b, a), (b, c)} (см. матрицу на рис 2.6, б).

Для получения транзитивного замыкания R ° выполним процедуру выявления нетранзитивностей для Таблица 2.2

Имеем	Отсутствует
(a, b) и (b, a) (b, a) и (a, b) (c, b) и (b, a)	(a, a) (b, b) (c, a)

исходного отношения R ={(a, b), (b, a), (c, b)}. Обнаруженная нетран-зитивность отражена в табл. 2.2 Других нарушений транзитив-ности нет.

Полученные пары представляют составное отношение R R = R ⁽²⁾= ={(a, a), (b, b), (c, a)}. Матрица R R = R ⁽²⁾ приведена на рис. 2.6, в.

Добавив пары {(a, a), (b, b), (c, a)} к R, получим:

R ¢= R È R ⁽²⁾={(a, a), (a, b), (b, a), (b, b), (c, a), (c, b)}.

Проверка на транзитивность отношения R ¢ не выявляет в нем нарушений транзитивности, поэтому:

R °= R ¢={(a, a), (a, b), (b, a), (b, b), (c, a), (c, b)} (см. матрицу на рис 2.6, г);

R *= R °È E ={(a, a), (a, b), (b, a), (b, b), (c, a), (c, b), (c, c)} (см. матрицу на рис 2.6, д);

Свойства исходного и полученных отношений после выполнения унарных операций приведены в табл. 2.3.

Таблица 2.3

Отношение	Рефлек-сивное	Антиреф-лексивное	Симмет-ричное	Антисим-метричное	Транзи-тивное
R	­­–	x	–	–	–
	x	–	–	–	–
R –1	–	x	–	–	–
R (2)	–	–	–	x	–
R °	–	–	–	–	x
R *	x	–	–	–	x

Вопросы для самопроверки и упражнения:

1. Назвать отношения , R ^–1, R ⁽²⁾, R °, R *, если отношение R означает:

а) “быть братом”, в) “жить в одном городе”,

б) “быть сыном”, г) “быть часть целого.

Каковы свойства отношений?

2. Пусть на множестве M ={1, 2, 3, 4} определено отношение R – “быть больше”. Выполнить операции над отношением R; задать полученные в результате операций отношения характеристическим свойством, списком, а также назвать отношения. Сравнить отношения; определить их свойства.

3. Пусть на множестве M ={1, 2, 3, 4, 5, 6} определено отношение R. Задать матрицами отношения R, , R ^–1, R °, R *, если R означает соответственно:

а) R ₁ – “быть меньше”;

б) R ₂ – “отличаться на 1”;

в) R ₃ – “иметь общий делитель, отличный от 1”.

4. Пусть отношения R ₁, R ₂, R ₃, заданные на N:

R ₁={(a, b): a < b }, R ₂={(a, b): a = b }, R ₃={(a, b): a ³ b }.

Выполнить операции над R ₁, R ₂, R ₃.

5. Пусть R ₁ и R ₂ – отношения на N из примера 5. Определить области определений и значений R ₁ и R ₂, а также составных отношений R ₁ R ₂, R ₂ R ₁, R ₁⁽²⁾ , R ₁^{( n )} , R ₂^{( n )} .

6. Пусть M ={1, 3, 5, 7} и отношение R Í M ´ M. Задать списком отно-шение R, обратное отношение R ^–1, дополнение , транзитное R ° и реф-лексивное R * замыкания, если:

а) R ={(a, b): a £ b }; г) R ={(a, b): (a + b –1)Î M };

б) R ={(a, b): a +2= b }; д) R ={(a, b): a –1= b };

в) R ={(a, b): (a + b)/2Î M }; е) R ={(a, b): (2 a + b)Î M }.

7. Пусть M ={ a, b, c } и b(M) – множество всех подмножеств множества M. Задать списком отношение R, заданное на b(M), а также отношения , R ^–1, R °, R *, если:

а) R ={(A, B): A Ì B }; г) R ={(A, B): A Ç B ¹Æ};

б) R ={(A, B): A Í B }; д) R ={(A, B): A Ç B =Æ};

в) R ={(A, B): A É B }; е) R ={(A, B): A Ç B =Æ и A È B = U }.

8. Пусть на множестве M ={1, 2, 3, …, 11} определено отношение R ₁ – “быть непосред-ственно связанным с”, графически проил-люстрированное рис. 2.7. Исходя из дан-ных рисунка, задать матрицами отношения R ₁ – “быть непосредственно связанным с” и R ₂ – “быть связанным с” на множестве M. Убедиться (используя определение I транзитивного замыкания) в том, что транзитивным замыканием отношений R ₁° и R ₂° является отношение R ₂ – “быть связанным с”, т.е. R ₁°= R ₂°= R ₂. Определить свойства отношений.

9. Отношение R на множестве M ={ a, b, c, d } задано матрицей на рис. 2.8. Каковы свойства отношения R? Почему отношение R нетранзитивно? Как будет выглядеть матрица его транзитивного замыкания R °?

Какова матрица рефлексивного замыкания R * отношения R?

10. Пусть R ₁ и R ₂ – отношения на M ={ a, b, c, d }, заданные матрицами. Осуществить опера-ции над отношениями R ₁ и R ₂ (рис. 2.9). Определить свойства исходных и полученных отношений.

11. Пусть отношение R Í M ´ M задано матрицей, M ={1, 2, 3, 4} (рис. 2.10, варианты а) – в)). Определить матрицы отношений R, , R ^–1, R ⁽²⁾, R °, R *. Каковы свойства исходных и полученных отношений?

12. Каковы свойства отношений, заданных матрицами на рис. 2.11.

К какому типу отношений относятся данные отношения? Выполнить унарные операции над отношениями и определить их свойства.

13. Пусть R ₁ и R ₂ – отношения на M ={ a, b, c, d }, заданные матрицами (рис. 2.12, варианты а), б)). Осуществить операции над отношениями R ₁ и R ₂. Определить свойства исходных и полученных отношений.