Файл: Линейная Алгебра от 2 октября 2013.doc

Бинарные отношения – это множества упорядоченных пар. Следовательно, над ними можно выполнять любые теоретико-множественные операции, в частности, операции объединения и пересечения. Определим еще две операции над отношениями.

Определение 2.7. Обратным к отношению P  A  B (или инверсией) называется множество P^–1, подмножество прямого произведения B  A такое, что P^–1 = {(y, x) | (x, y)  P}.

Пример 2.6. Пусть P = {(a, 1), (b, 2), (c, 3), (d, 4), (e, 5)}. Тогда P^–1 = {(1, a), (2, b), (3, c), (4, d), (5, e)}.

Определение 2.8. Композицией (или суперпозицией) отношений P  A  B и Q  B  C называется множество PQ = {(x, y) | x  A, y  C, ( z  B) : (x, z)  P, (z, y)  Q}, рис. 2.4.

Пример 2.7. Если P = {(a, b), (b, c), (b, d), (a, d), (c, a)}, Q = {(b, d), (c, a), (d, c)}, то PQ = {(a, d), (b, a), (b, c), (a, c)} и QP = {(c, b), (c, d), (d, a)}.

Утверждение 2.1. Для любых бинарных отношений P, Q и R выполняются следующие свойства:

(P^–1)^–1 = Р;
(PQ)^–1 = Q^–1P^–1;
(PQ)R = P(QR).

2.2. Свойства бинарных отношений

Пусть бинарное отношение Р задано на непустом множестве А, т. е. Р  А².

Определение 2.9. Бинарное отношение P на множестве А называется рефлексивным, если для любого элемента х из множества А пара (х, х)  Р.

Другими словами, отношение P рефлексивно тогда и только тогда, когда каждая вершина графа имеет петлю.

Примерами рефлексивных отношений являются отношение делимости на множестве целых чисел; отношение включения на булеане непустого множества; отношение быть одинаково направленными на множестве всех направленных лучей.

Пример 2.8. Выяснить обладает ли отношение R = {(m, n), (m, k), (m, m), (n, n), (k, n)}, заданный на множестве А = {m, n, k}, свойством рефлексивности.

Решение. Данное бинарное отношение R  А², не будет рефлескивным так как для k  A пара (k, k)  R.

Определение 2.10. Бинарное отношение P на множестве А называется антирефлексивным, если  х  А : (х, х)  Р.

Отношение антирефлексивно тогда и только тогда, когда ни одна вершина графа не имеет петли.

Например, отношение неравенства на некотором числовом множестве, отношение перпендикулярности на множестве всех прямых евклидовой плоскости являются антирефлексивными.

Пример 2.9. Выяснить обладает ли отношение R = {(x, y) | x, y  R : x + y = 2}, свойствами рефлексивности и антирефлексивности.

Решение. Имеем пара (1, 1)  R и (2, 2)  R, следовательно данное бинарное отношение R, не является рефлескивным и не является антирефлексивным.

Определение 2.11. Бинарное отношение P на множестве А называется симметричным, если  х, y  А из того что пара (х, y)  Р следует (y, x)  Р.

Отношение симметрично тогда и только тогда, когда всякий раз вместе с ребром (х, y) граф содержит ребро (y, x).

Примерами симметричных отношений являются отношение равенства на некотором числовом множестве, отношение параллельности на множестве всех прямых евклидовой плоскости, отношение перпендикулярности на множестве всех прямых евклидовой плоскости.

Пример 2.10. Выяснить обладает ли отношение R = {(1, 2), (1, 3), (1, 1), (2, 3), (3, 1)}, заданное на множестве А = {1, 2, 3}, свойством симметричности.

Решение. Данное бинарное отношение R  А², не будет симметричным так как для пары (2, 3)  R пара (3, 2)  R.

Определение 2.12. Бинарное отношение P на множестве А называется антисимметричным, если  х, y  А из того, что пара (х, y)  Р и (y, x)  Р следует что x = y.

Отношение антисимметрично тогда и только тогда, когда вместе с каждым ребром (х, y) граф не содержит ребро (y, x). Граф антисимметричного отношения может содержать петли.

Примерами антисимметричных отношений являются отношение меньше (<) на множестве действительных чисел, отношение включения на булеане непустого множества.

Замечание 2.1. Если отношение не является симметричным, то это не означает, что оно антисимметрично. Например, отношение R = {(a, b), (b, a), (a, c)} на множестве A = {a, b, c} не симметрично, поскольку (a, c)  R, а (c, a)  R, и не антисимметрично, так как (a, b)  R и (b, a)  R, но a  b. Диагональ непустого множества А (id_A) является примером симметричного и антисимметричного отношения. Вообще, любое подмножество id_A обладает одновременно свойствами симметричности и антисимметричности.

Определение 2.13. Бинарное отношение P на множестве А называется асимметричным, если  х, y А если пара (х, y)  Р, то (y, х)  Р.

Отношение асимметрично тогда и только тогда, когда если граф содержит ребро (х, y), то он не содержит ребра (y, x).

Примерами асимметричных отношений являются отношение быть меньше (<) на числовом множестве. Отношение параллельности (||) на множестве прямых плоскости не является асимметричным, так как если а || b, то b || a и оно является симметричным.

Определение 2.14. Бинарное отношение P на множестве А называется транзитивным, если  х, y, z  А из того, что пара (х, y)  Р и (y, z)  Р следует что (х, z)  Р.

Отношение транзитивно тогда и только тогда, когда вместе с каждой парой ребер (х, y) и (y, z) граф содержит ребро (х, z).

Например, отношение параллельности на множестве всех прямых евклидовой плоскости, отношение включения на булеане непустого множества являются транзитивными.

Утверждение 2.2. Пусть A ≠  и P  A². Тогда справедливы следующие соотношения:

P – рефлексивно  id_A  P;
P – антирефлексивно  P  id_A = ;
P – симметрично  P = P^–¹;
P – антисимметрично  P  P^–1  id_A;
P – транзитивно  PP  P.

2.3. Отношение эквивалентности

Определение 2.15. Бинарное отношение на множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности обычно обозначают символами  или .

Примерами отношения эквивалентности являются отношение равенства на множестве действительных чисел, отношение параллельности на множестве прямых евклидовой плоскости, подобие треугольников на плоскости.

Определение 2.16. Пусть R – отношение эквивалентности на множестве А и а  А. Классом эквивалентности, порожденным элементом а, называется множество a/R = [a]_R = {х  А | (х, а)  R}.

Совокупность всех классов эквивалентности отношения R на множестве А обозначается через А/R.

Определение 2.17. Представителем класса эквивалентности называется любой элемент этого класса.

Определение 2.18. Пусть А – непустое множество. Фактор- множеством множества А по отношению эквивалентности R называется множество A/R всех классов эквивалентности.

Определение 2.19. Разбиением непустого множества А называется совокупность его непустых подмножеств, таких что объединение всех подмножеств есть множество А, а пересечение любых двух различных подмножеств есть пустое множество.

Теорема 2.1. Пусть R – отношение эквивалентности на непустом множестве А. Тогда фактор-множество A/R является разбиением множества А.

Доказательство. Так как отношение R рефлексивно, то для любого a  A имеем (а, а)  R. Это значит, что каждый элемент a множества А принадлежит классу эквивалентности a/R. Итак, имеем семейство непустых классов a/R (a/R содержит по крайней мере один элемент a) и = A. Осталось доказать, что пересечение любых двух различных классов пусто. Для этого достаточно показать, что классы эквивалентности, имеющие хотя бы один общий элемент, совпадают. Пусть a/R и b/R – классы эквивалентности, имеющие общий элемент c. Тогда (с, а)  R и (c, b)  R. В силу симметричности отношения R из (c, a)  R следует (a, c)  R. Пусть х – любой элемент из a/R , тогда (х, a)  R. Имеем, (х, a)  R и (а, с)  R. Следовательно, в силу транзитивности отношения R (х, с)  R. Имеем, (х, с)  R и (с, b)  R. Тогда (х, b)  R, так как отношение R транзитивно. Следовательно, x  b/R. Таким образом, a/R  b/R. Аналогично доказывается, что b/R  a/R. Следовательно, a/R = b/R.

Смотрите также файлы

Лекция_2.doc

Лекция_1.doc

Лекция.docx

Лекция физиология почек.docx

лекция по терморегуляции.docx

Файл: Линейная Алгебра от 2 октября 2013.doc

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

2.2. Свойства бинарных отношений

2.3. Отношение эквивалентности

Смотрите также файлы

Информация

Списки файлов

Дополнительно