Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют. - презентация

1 Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А. (однородное отношение) Если (x, y) R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R. n-местным (n-арным) отношением, заданным на множествах M 1, M 2,…, M n, называется подмножество прямого произведения этих множеств. Иногда понятие отношения определяется только для частного случая M=M 1 =M 2 =…=M n.

2 Примеры Отношение a= {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел. Из школьного курса На множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты"; на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают"; на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".

3 Пример Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение R 1 = { (x, y) | x 2 + y 2 1 } определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение R 2 = { (x, y) | x y } полуплоскость, а отношение R 3 = { (x, y) | |x-y| 1 } полосу.

4 Способы задания Перечисление всех пар из базового множества А и базового множества В A={a 1,a 2 } B={b 1,b 2,b 3 }, ={(a 1, b 1 ), (a 1,b 3 ), (a 2, b 1 )} Отношения могут задаваться формулами: формулы y = x 2 +5x - 6 или x + y < 5 задают бинарные отношения на множестве действительных чисел; формула x + y = любовь, задает бинарное отношение на множестве людей.

5 Графический метод задания a= {(a, d), (a, c), (b, b), (c, a), (e,d), (e, a)}

6 Графовое представление Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x i, а наличие дуги, соединяющей вершины x i и x j, означает, что (x i,x j ) R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. А={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}

7 Матричная форма задания Пусть на некотором конечном множестве X задано отношение А. Упорядочим каким-либо образом элементы множества X = {x 1, x 2,..., x n } и определим матрицу отношения A = [a ij ] следующим образом:

8 Определения Диагональ множества A A, т.е. множество ={(x,x) | x A}, называется единичным бинарным отношением или отношением равенства в A. Областью определения бинарного отношения R называется множество R={ x A | y B, (x, y) R }. Областью значений бинарного отношения R называется множество R={ y B | x A, (x, y) R }. Образом множества X относительно отношения R называется множество R(X) = { y B | x X, (x, y) R }; прообразом X относительно R называется R -1(X).

9 Операции над бинарными отношениями Пересечение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 }. = > Объединение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 или (x, y) R 2 }. Разностью отношений R 1 и R 2 называется такое отношение, что: R 1 \R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 } Дополнение к отношению R={ (x, y) | (x, y) (A A)\R}.

10 Обратное отношение R –1 = { (x, y) | (y, x) R}.

11

12 Композиция отношений Двойственное отношение R d = Композиция (суперпозиция) отношений R=R 1 oR 2 содержит пару (x, y) тогда и только тогда, когда существует такое z A, что (x, z) R 1 и (z, y) R 2.

13 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность xM (xRx) Антирефлексивность xM ¬(xRx)

14 Рефлексивность отношений Обозначим через Ix отношение на множестве X, состоящее из пар вида (a, a), где a X: Ix = {(a, a)| a X}. Отношение Ix обычно называют диагональю множества X или отношением тождества на X. Очевидно, что отношение R на множестве X рефлексивно, если диагональ Ix является подмножеством множества a: Ix R. Отношение антирефлексивно, если диагональ Ix и отношение R не имеют ни одного общего элемента: Ix R = Ø.

15 Свойства отношений Симметричность xRy yRx или R=R -1

16 Свойства отношений Антисимметричность Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным. Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y) R означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x) R - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y. Отношение " " также антисимметрично: если x y и y x, то x=y. Асимметричность Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

17 Свойства отношений Для любого отношения R вводятся понятия симметричной части отношения R s = R R -1 и асимметричной части отношения R a = R \ R s. Если отношение R симметрично, то R= R s, если отношение R асимметрично, то R= R a. Примеры. Если R - " ", то R -1 - " ". Транзитивность отношений

18 Нетранзитивное отношение Отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz. Пример нетранзитивного отношения: «x отец y» Нетранзитивным является отношение " ". Пусть x=2, y=3, z=2, тогда справедливо x y и y z, но x=z, т.е. (x, z) R.

" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2" title="Негатранзитивность отношений (x,y) R и (y, z) R (x, z) R В графе негатранзитивного отношения отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z. Отношения R 1 - ">" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2" class="link_thumb"> 19 Негатранзитивность отношений (x,y) R и (y, z) R (x, z) R В графе негатранзитивного отношения отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z. Отношения R 1 - ">" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2 доп - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R 1 одновременно транзитивно и негатранзитивно, а R 2, как известно, транзитивным не является. " и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2"> " и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2 доп - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R 1 одновременно транзитивно и негатранзитивно, а R 2, как известно, транзитивным не является."> " и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2" title="Негатранзитивность отношений (x,y) R и (y, z) R (x, z) R В графе негатранзитивного отношения отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z. Отношения R 1 - ">" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2">

20 Свойства бинарных отношений Полнота (x, y) X либо xRy либо yRx, либо и то и другое одновременно – полносвязное или связное отношение Ацикличность Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы ). n x 1 Rx 2 x 2 Rx 3 x 3 Rx 4 … x n-1 Rx n но не наоборот.

21 Композиция транзитивного отношения Справедлива теорема: Для любого отношения транзитивное замыкание равно пересечению всех транзитивных отношений, включающих в качестве подмножества. Композиция транзитивного отношения – транзитивное отношение. Отношение R1 называется транзитивным относительно отношения R2, если: из (x, y) R1 и (y, x) R2 следует, что (x, z) R1; из (x, y) R2 и (y, x) R1 следует, что (x, z) R1.

22 Связи между бинарными отношениями Отношение R симметрично тогда и только тогда, когда R = R -1. Если R рефлексивно, то R d антирефлексивно, если R антирефлексивно, то R d рефлексивно. Отношение R слабо полно тогда и только тогда, когда R d антисимметрично. Отношение R асимметрично тогда и только тогда, когда R d полно.

23 Отношения эквивалентности (подобия, равносильности) Отношение R на множестве A 2 называется отношением эквивалентности, если оно обладает следующими свойствами: рефлексивность симметричность транзитивность Обозначается =,, ~,

24 Отношение эквивалентности х x для всех x A (рефлексивность) Если x y, то y x (симметричность) Если x y и y z, то x z (транзитивность)

25 Примеры отношение тождества I X = {(a, a)|a X} на непустом множестве X; отношение параллельности на множестве прямых плоскости; отношение подобия на множестве фигур плоскости; отношение равносильности на множестве уравнений; отношение "иметь одинаковые остатки при делении на фиксированное натуральное число m" на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m); отношение "принадлежать одному виду" на множестве животных; отношение "быть родственниками" на множестве людей; отношение "быть одного роста" на множестве людей; отношение "жить в одном доме" на множестве людей.

26 Классы экввалентности Система непустых подмножеств {M 1, M 2, …} множества M называется разбиением этого множества, если M = M 1 M 2 … и при ij M i M j =Ø. Сами множества M 1, M 2, … называются при этом классами данного разбиения.

27 Примеры Разложение всех многоугольников на группы по числу вершин - треугольники, четырехугольники, пятиугольники и т. д.; Разбиение всех треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные); Разбиение всех треугольников по свойствам сторон (разносторонние, равнобедренные, равносторонние); Разбиение всех треугольников на классы подобных треугольников; Разбиение множества всех учащихся данной школы по классам.

28 Пример 1

29 Пример 2 а и b равны по модулю n, если их остатки при делении на n равны. Например по модулю 5 равны 2, 7, 12 … [0] = {0, n, 2n, …} [1] = {1, n+1, 2n+1, …} … [n-1] = {n-1, n+n-1, 2n+n-1, …}

30 Класс эквивалентности Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a. Из вышеприведённого определения немедленно следует, что, если и bC(a), то C(a) = C(b).

31 Теорема Отношение эквивалентности, заданное между элементами базового множества Х, определяет разбиение множества Х на непересекающиеся классы эквивалентности базового множества

32 Фактор-множество Получающееся при этом множество классов называется фактор- множеством {c k }.или X / ˜.

33 Теорема Два класса эквивалентности либо совпадают, либо не пересекаются. Доказательство. Пусть A и B - два класса эквивалентности из X. Допустим, что они пересекаются и c - общий элемент, то есть c A, c B. Если x - произвольный элемент из A, то x ~ c. Поскольку c B, то и x B. Таким образом, A B. Аналогично доказывается, что B A. Итак, A = B. Теорема доказана

34 Представитель класса Как уже отмечалось, каждый элемент а из множества X полностью определяет класс эквивалентности, его содержащий, который далее обозначается символом ã, так что а ã (и ã =, если и только если а = y). Элемент а называется представителем класса A, если а A.