Негатранзитивность отношений Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение такое, что x R y тогда и только тогда, - презентация

1 Негатранзитивность отношений Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение такое, что x R y тогда и только тогда, когда существует такая цепочка элементов из X: z0 = x, z1, z2,..., zn = y, что между соседями в этой цепочке выполнено отношение R: z0 Rz1, z1R z2,..., zn­1 Rzn (x,y) R и (y, z) R (x, z) R В графе нега транзитивного отношения отсутствие связи (кольца или дуги) между двумя вершинами влечет отсутствие петель в обоих вершинах. Отношения R1 ­ ">" и R2 ­ " " негатранзитивны, как отношения R1 доп ­ " ", R2 доп ­ "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и нега транзитивности. Например, отношение R1 одновременно транзитивно негатранзитивно, а R2, как известно, транзитивным не является. " и R2 ­ " " негатранзитивны, как отношения R1 доп ­ " ", R2 доп ­ "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и нега транзитивности. Например, отношение R1 одновременно транзитивно негатранзитивно, а R2, как известно, транзитивным не является.">

2 Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение такое, что x R y тогда и только тогда, когда существует такая цепочка элементов из X: z0 = x, z1, z2,..., zn = y, что между соседями в этой цепочке выполнено отношение R: z0 Rz1, z1R z2,..., zn­1 Rzn

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

4 Транзитивность Отношение R1 называется транзитивным относительно отношения R2, если: из (x, y) R1 и (y, x) R2 следует, что (x, z) R1 ; из (x, y) R2 и (y, x) R1 следует, что (x, z) R1

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

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

7 Свойства операций над отношениями R k ­1 =( Rk ­1 Rk ­1 =( Rk ­1 (R1 o R2 ) ­1 = R1 ­1 o R2 ­1. (R1 o R2 )oR3 = R1o(R2 o R3 ). (R1 R2 )oR3 = (R1 oR3 )( R2o R3 )

8 Свойства операций над отношениями (R1 R2 )oR3 (R1 oR3 )( R2o R3 ). если R1 R2 то R1o R3 R2o R3 ; если R1 R2 то R1 ­1 R2 ­1 ; если R1 R2 то R3oR1 R3oR2. (R1 R2 ) d = R1 d R2 d ; (R d ) d = R

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

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

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

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

13 Классы эквивалентности Система непустых подмножеств {M1, M2, …} множества M называется разбиением этого множества, если M = M1 M2 … и при ij MiMj =Ø. Сами множества M1, M2, … называются при этом классами данного разбиения.

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

15 Пример 1

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

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

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

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

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

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