1 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность. - презентация

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

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

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

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

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

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

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

9 Транзитивное замыкание Для произвольного отношения A можно найти минимальное транзитивное отношение a такое, что ab. Минимальность отношения понимается в том смысле, что для любого транзитивного отношения g из a g следует b g. Таким отношением является транзитивное замыкание отношения a. Если X это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками).

10 Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение R такое, что x R y тогда и только тогда, когда существует такая цепочка элементов из X: z 0 = x, z 1, z 2,..., z n = y, что между соседями в этой цепочке выполнено отношение R: z 0 Rz 1, z 1 R z 2,..., z n-1 Rz n.

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

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

13 Отношение эквивалентности Условия 1-3 в таких обозначениях выглядят более естественно: x=x для всех x A (рефлексивность) Если x=y, то y=x (симметричность) Если x=y и y=z, то x=z (транзитивность)

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

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

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

17 Пример 1

18 Пример 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, …}

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

20 Фактор-множество Получающееся при этом множество классов называется фактор- множеством {c k }.или X / ˜. Для класса эквивалентности элемента используются следующие обозначения: : [a], a / ˜, a.