Негатранзитивность отношений Транзитивное замыкание Транзитивным замыканием отношения 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, как известно, транзитивным не является.

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

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

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

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

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

Свойства операций над отношениями 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 )

Свойства операций над отношениями (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

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

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

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

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

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

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

Пример 1

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

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

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

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

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

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