Бинарные отношения. Транзитивное замыкание Для произвольного отношения A можно найти минимальное транзитивное отношение a такое, что ab. Минимальность. - презентация

1 Бинарные отношения

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

3 Транзитивное замыкание Транзитивным замыканием отношения 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.

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

5 Транзитивность Отношение R 1 называется транзитивным относительно отношения R 2, если: из (x, y) R 1 и (y, x) R 2 следует, что (x, z) R 1 ; из (x, y) R 2 и (y, x) R 1 следует, что (x, z) R 1.

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

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

8 Свойства операций над отношениями R k -1 =( R k -1 (R 1 o R 2 ) -1 = R 1 -1 o R (R 1 o R 2 )oR 3 = R 1 o(R 2 o R 3 ). (R 1 R 2 )oR 3 = (R 1 oR 3 ) ( R 2 o R 3 ).

9 Свойства операций над отношениями (R 1 R 2 )oR 3 (R 1 oR 3 ) ( R 2 o R 3 ). если R 1 R 2 то R 1 o R 3 R 2 o R 3 ; если R 1 R 2 то R 1 -1 R 2 -1 ; если R 1 R 2 то R 3 oR 1 R 3 oR 2. (R 1 R 2 ) d = R 1 d R 2 d ; (R d ) d = R.

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

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

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

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

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

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

16 Пример 1

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

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

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

20 Отношение порядка Бинарное отношение a на множестве X называется отношением порядка, если оно Транзитивно x,y,z A xRy yRz xRz и антисимметрично x,y A xRy yRx x=y Множество X с определенным на нем отношением порядка a называется упорядоченным множеством и обозначается.

21 Отношение строгого порядка Отношение порядка R называется отношением строгого порядка на множестве X, если a антирефлексивно xX ¬(xRx) Отношение строгого порядка обозначается символом < или Pуп Пусть f и g - функции с одинаковыми областями определения. Определим отношение > следующим образом: f > g, если для любого x из области определения функции f(x) > g(x). Очевидно, что данное отношение является отношением строгого порядка.

22 Пример f > g. Пары функций f и h, а также g и h несравнимы.

23 Отношение толерантности Отношение безразличия является отношением симметрии и рефлексивности. x I уп y ( x P уп у и y P уп x ). Так как (x, y) и (y, x) не принадлежат P уп, то нельзя сказать, что x лучше y, или x лучше y.

24 Основные свойства P уп P d уп = P d уп ; P уп P d уп = P уп ; I = P уп P d уп. R уп = P d уп ; P уп = R d уп, т.е. P уп и R уп образуют двойственную пару. P P -1 I=Х × Х – все декартово произведение

25 Отношение нестрогого порядка На базе введенных отношений строгого упорядочения и безразличия можно построить новое отношение R уп = P уп I уп, которое называется нестрогим упорядочением. Отношение нестрогого упорядочивания (xy) это полное и рефлексивное отношение.

26 Отношение безразличия Пусть мы имеет некоторое произвольное отношение R, причем R R -1 =R s – симметричная часть R. Если R было рефлексивным, то R s можно считать отношением безразличия.

27 Теорема R\R -1 =R s =I, R\R s =P, а значит, R=P U Любое полное отношение R с R\R -1 =R s =I, R\R s =P индуцирует отношения строгого упорядочения P и безразличия I. I – симметричная часть R, P – асимметричная часть.

28 Отношение слабого порядка Асимметричное, негатранзитивное отношение Pсл назовем слабым порядком. x>y (слабый порядок, т.к. ассиметрично и его дополнение xy, транзитивно, а значит и негатранзитивно). Кроме того, по аналогии с I уп введем отношение I сл xI сл y ((x, y) P сл и (y, x) P сл ) или xI сл y ((y, x) P сл и (x, y) P сл ). Назовем его отношением эквивалентности.

29 Отношение нестрогого слабого порядка Введем также отношение R сл = P сл I сл, называемое нестрогим слабым порядком. Из определения следует, что P сл P уп. Так как P уп только асимметрично, а P сл асимметрично и негатранзитивно, то из (x, y) P сл всегда следует (x, y) P уп. В качестве примера R сл можно привести отношение " ".

30 Свойства слабого порядка R сл = P d сл, R d сл = P сл. I сл = R s сл, P сл = R d сл. Для любых x,y A выполняется одно и только одно из соотношений: xP сл y, yP сл x, xI сл y. Отношение P сл транзитивно. Отношение I сл рефлексивно, симметрично, транзитивно. Отношение R сл транзитивно и полно.

31 Отношение качественного порядка Дополним отношение строгого упорядочения P уп свойством транзитивности. Назовем полученное отношение качественным порядком P кач.. Пусть х, у - вещественные числа. Введем качественный порядок: хР кач у x > у +1. Очевидно, что в данном случае отношение Р кач асимметрично и транзитивно, но оно не является негатранзитивным. Дополнение к введенному отношению определим как х Р кач у х у +1 Положим у = 0; х = 0.9; z = Тогда, очевидно, выполняются отношения (х, y) Р кач ; (y, z) Р кач ; (х, z) Р кач. Т.е. условие негатранзитивности не выполняется.

32 Отношение Парето Введем на множестве точек n-мерного евклидова пространства следующее отношение Par, называемое отношением Парето: х, у Раr i : х i y i и j : х j > у j. Отношение Парето называется также безусловным критерием предпочтения (БКП).

33 Пример а) x1 y1 в) x1 < y1 x2 > y2 x2 = y2 x2 < y2 нет отношения Раr; есть отношение Раr, есть отношение Раr, x лучше y; y лучше x. x y y x y x

34 Производные отношения I кач - отношение качественного безразличия хI кач у ( x Р кач у) и (у Р кач х ); R кач - нестрогий качественный порядок R кач = Р d кач.

35 Качественный порядок – это ассиметричные и транзитивные отношения. Так как асимметрия+негатранзитивность=транзитивность, значит слабый порядок качественный, но не наоборот.

36 Другие отношение Отношение R част называется нестрогим частичным порядком, если оно рефлексивно, транзитивно и антисимметрично. Нестрогий частичный порядок можно определить по формуле R част = P кач I. Рефлексивное и транзитивное бинарное отношение называется предпорядком. Симметричный предпорядок является отношением эквивалентности, антисимметричный предпорядок - нестрогим частичным порядком.