Что такое обратное отношение как найти

Обратное отношение в математике – это отношение, взятое в обратном порядке по отношению к данному.

Определение

Пусть на множестве задано бинарное отношение Тогда его обратным называется отношение построенное следующим образом:

Свойства

• Если отношение обладает одним из перечисленных свойств: рефлексивностью, нерефлексивностью, симметрией, антисимметрией, асимметрией, транзитивностью или полнотой, то и обратное отношение также обладает им.
• Если инъективно, сюръективно или функционально, то , вообще говоря, не обязано обладать таким же свойством.

Примеры

п·о·р Бинарное отношение
между двумя множествами: инъективное · сюръективное · биективное · полное слева · полное справа · функциональное
на множестве: рефлексивное · нерефлексивное · симметричное · антисимметричное · асимметричное · транзитивное · полное · евклидово

Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД)). Не менее важной считаю область принятия решений, которая состоит из двух основных статистической и алгебраической, основанной целиком на теории отношений. Образовательный уровень специалистов в этой теории близок к нулю.

Откройте учебник по специализации и там увидите в лучшем случае об эквивалентностях, которые авторами трактуются весьма своеобразно. Одного защитившегося уже ДТН спрашиваю: Вы рассматриваете отношение эквивалентности на указывая ни носителя отношения, ни конкретного отношения, как оно у Вас выглядит в записи? Ответ: как выглядит — обыкновенно. Выясняется, что он обо всем этом имеет весьма смутное представление.

Публикаций по проектированию РеБД, кроме иностранных статей назвать затрудняюсь. В 90-х годах был оппонентом, писал отзыв на диссертацию, где рассматривались и иерархические, и сетевые, и реляционные БД. Но как-то год, полтора назад опять на отзыв пришла работа, автор пишет уже только о РеБД, о нормализации отношений БД, но теоретической новизны не показал. Во многих ВУЗах читается курс о базах данных, но не о том, как их создать, создать СУБД, а как правило, о том как эксплуатировать готовую (зарубежную) БД.

Преп. состав не готов научить специалистов IТ-шников создавать отечественные СУБД, ОS, языки программирования, я уж не говорю о БИС, СБИС, заказных БИС. Здесь, по-видимому, поезд ушел давно и надолго. Так что напрасно надуваются у некоторых щеки от гордости (читай снобизма) это видно по комментариям к чужим публикациям, покажите сами, что можете, а не балуйтесь никчемными переводами и перепевками чужого ради предмета гордости — «рейтинга» и «кармы». Сказывается не только отсутствие креатива, но простой образованности и воспитания.

Вторая предметная область неразрывно, связанная с отношениями, — принятие решений. Каждый из нас постоянно занят этим. Мы без решения осознанного или неосознанного пальцем не пошевелим. Мало кто понимает, а еще меньше пишет о решениях. В основе решения любого ЛПР (лица, принимающего решение) лежит предпочтение альтернатив. А моделью предпочтения как раз и является такой тип отношений, который назван «пространством отношений предпочтения». Но кто их изучает. Когда я пришел к «специалисту» по отношениям с вопросом о количестве отношений каждого типа, он не зная ответа, «убил» встречным вопросом, а зачем это Вам?

Понятие отношения

Думаю, что термин отношение знаком каждому читателю, но просьба дать определение поставит большинство в тупик. Причин для этого много. Они чаще всего в преподавателях, которые, если и использовали отношения в процессе преподавания, внимания на этом термине не заостряли, запоминающихся примеров, по-видимому, не приводили.

В моей памяти есть несколько на всю жизнь запомнившихся примеров. Об отображениях и об отношениях. Расскажу вначале об отображениях. Имеется два ведерка с краской. В одном белая в другом — черная. И есть коробка с кубиками (очень много). Грани имеют рельефные номера. Сколькими способами можно раскрасить грани кубиков в два цвета? Ответ неожиданный — столькими, сколько 6-разрядных двоичных чисел, или 2⁶ = 64. Поясню подробнее ф: 2→6 отображаются 2 объекта в 6. Каждая строчка таблицы- дискретное отображение фi.

Построим таблицу с 6 колонками и краскам сопоставим число белая — нуль, черная — единица, а граням кубика колонки. Начинаем с того, что все 6 граней белые — это 6-мерный нулевой вектор. Вторая строчка одна грань черная, т. е. младший разряд заполнен 1. и так до исчерпания 6-разрядных двоичных чисел. Кубики ставим в общий длинный ряд. У каждого из них как бы появился номер от 0 до 63.

Теперь отображение наоборот. Пачка листов бумаги (много) и 6 красок (фломастеры).
Фломастерами разного цвета надо пометить обе стороны бумажных листов. Сколько листов потребуется. Ответ f: 6 → 2 или 6² =36. Речь идет о произвольных отображениях.

Перейдем к отношениям. Начнем с абстрактного множества — носителя отношения
А ={a1, a2, a3, …, an}.
О нем почитать можно здесь. Для лучшего понимания сократим множество до 3 элементов, т.е. А ={a1, a2, a3}. Теперь выполним декартово умножение А×А =А²,
А×А={(a1, a1),(a1, а2),(a1, a3),(a2, а1),(a2, a2),(a2, a3),(a3, a1),(a3, a2),(a3, a3)}.

Получили 9 упорядоченных пар элементов из А×А, в паре первый элемент из первого сомножителя, второй — из второго. Теперь попробуем получить все подмножества из декартова квадрата А×А. Вначале простенький пример.

Пример 1. Задано множество А ={a,b,c,d} из 4-х элементов. Выписать все его подмножества. В(А) ={Ø};{a};{b};{c};{d};{ab};{ac};{ad};{bc};{bd};{cd};{abc};{abd};{acd};{bcd};{abcd}; 2⁴ = 16 подмножеств. Это булеан В(А) множества А и в него включено пустое подмножество.

Подмножества будут содержать из А×А разное количество элементов (пар): одну, две, три и так до всех 9 пар, включаем в этот список и пустое множество (Ø). Сколько же получилось подмножеств? Много, а именно 2⁹= 512 элементов.

Определение. Любое подмножество декартова произведения (у нас квадрата) множества называется отношением. Заметим, в произведении используется одно и то же множество. Если множества разные, возникает не отношение, а соответствие.

Если декартово произведение из двух сомножителей, то отношение бинарное, если из 3-х -тернарное, из 4-х — тетрарное, из n — n-арное. Арность — число мест в отношении. Отношениям дают имена прописных букв R,H, P, S… Остановимся подробно на бинарных отношениях (БО), так как они играют очень важную роль в теории отношений. Собственно к бинарным отношениям могут быть сведены все остальные.

Символ отношения ставится слева от элементов R(x, y) или между ними x R y; х, у є А.
Определение Множество всех подмножеств множества А называется булеаном. Наш булеан состоит из 2^|А×А| элементов, здесь|А×А| — мощность множества.

Отношения можно задавать в разном представлении над А={a1,a2,a3,a4}:

• перечислением элементов; R1={(a1,a2),(a1,a3),(a2,a3)(a2,a4)(a3,a2)(a3,a4}
• двоичным n = 16-разрядным вектором; <0110001101010000>;
• матрицей;

Рисунок 1.2. а)Матрица 4×4 бинарного отношения б) нумерация клеток Матрицы

Здесь используются номера клеток, заполненные единицами на рис. 1б)
— Векторное представление. Двоичный вектор для представления бинарного отношения формируется из элементов {0,1} следующим образом:

Рассмотренный пример задания отношения в векторной форме будет иметь следующий вид:

— Представление графом. Поставим в соответствие элементам множества
А ={x1,x2,z3,…,xn} точки на плоскости, т.е. вершины графа G = [Q, R].

Проведем в графе дугу от (xi) к (xj) тогда и только тогда, когда пара (xi,xj) є R (при i = j дуга (xi,xi) превращается в петлю при вершине (xi). Пример (рис. 1а) представления бинарного отношения A[4×4] графом изображен на рис.2.2.

Рисунок 2.2. Представление отношения ориентированным графом

Каталог бинарных отношений (n = 3)

Большое видится на расстоянии. Чтобы почувствовать отношения их разнообразие, мощность мне пришлось вручную создать каталог бинарных отношений над множеством из 3-х элементов, который включил все (боле 500 отношений) отношения. После этого «дошло» или «зашло»об отношениях.

Очевидно, что в каталог войдут 2^3×3 = 2⁹ отношений, и каждое из них снабдим набором присущих им свойств. Ниже (табл. 3) приводится полный список всех 512 отношений над множеством А, |A| = 3, из трех элементов. Приводятся также результаты подсчета количества отношений (табл. 2), представленных сочетаниями номеров клеток декартова квадрата 3×3, различных подклассов для различных значений мощности множества-носителя (n = 3). Для каждого отношения указаны его основные свойства и принадлежность типу (табл. 3). Сокращения, используемые в каталоге раскрываются таблицей 2
Таблица 2. Количественные характеристики каталога при разных n

Сущность производимых операций с отношениями и их технику удобно пояснять на примерах, которые особенно просты и понятны для бинарных отношений. В операциях могут участвовать, два и/или более отношений. Операции, выполняемые над отдельными отношениями – унарные операции. Например, операции обращения (получение обратного) отношения, взятие дополнения, сужение (ограничение) отношения. Как пользоваться каталогом поясним примером примером.

Пример 2. Рассмотрим строку Nпр =14 таблицы каталога. Она имеет вид

Первые 9 символов строки (справа от равенства) — это двоичный вектор, соответствующий сочетанию из 9 по 2, а именно, номер первой клетки (отсчет слева направо) номер 5-й клетки матрицы бинарного отношения, т.е. элементы а1а1= а2а2 =1. Это сочетание имеет порядковый номер Ncч = 4 и сквозной номер Nпр = 14 в списке всех отношений. В остальных позициях этой строки стоят либо нули, либо единицы. Нули свидетельствуют об отсутствии свойства, соответствующего названию колонки нуля, а единицы – наличие такого свойства у рассматриваемого отношения.

Свойства и количественные характеристики отношений

Рассмотрим наиболее важные свойства отношений, которые позволят в дальнейшем выделить типы (классы) отношений, применяющиеся в реляционных базах данных в теории выбора и принятия решений и других приложениях. Далее будем обозначать отношение символом [R,Ω]. R- имя отношения, Ω — множество-носитель отношения.

1. Рефлексивность. Отношение [R,Ω] называется рефлексивным, если каждый элемент множества находится в отношении R сам с собой (рис. 2.3). Граф рефлексивного БО имеет во всех вершинах петли (дуги), а матрица отношения содержит (Е) единичную главную диагональ.

Рисунок 2.3. Рефлексивное отношение

2. Антирефлексивность. Отношение [R,Ω] называется антирефлексивным, если ни один элемент из множества не находится в отношении R сам с собой (рис. 2.4). Антирефлексивные отношения называют строгими.

Рисунок 2.4. Антирефлексивное отношение

3. Частичная рефлексивность. Отношение [R,Ω] называется частично
рефлексивным, если один или более элементов из множества не находится в отношении R сам с собой (рис. 2.5).

4. Симметричность. Отношение [R,Ω] называется симметричным, если вместе с упорядоченной парой (х, у) отношение содержит и упорядоченную пару (у, х) (рис. 2.6).

5. Антисимметричность. Отношение [R,Ω] называется антисимметричным, если, если для всякой упорядоченной пары (х, у) є R упорядоченная пара
(у, х)єR, только в случае х = у. Для таких отношений R∩R^-1 ⊆ E (рис. 2.7).

6. Асимметричность. Отношение [R,Ω] называется асимметричным, если оно антирефлексивно и для всякой упорядоченной пары (х, у) є R упорядоченная пара (у, х) ∉ R, для отношений R ∩ R^-1 = Ø (рис. 2.8).

7. Транзитивность. Отношение [R,Ω] называется транзитивным, если для всяких упорядоченных пар (х, у),(у, z) є R, в отношении R найдется упорядоченная пара (х, z) є R или если R×R⊆R (рис. 2.9).

8. Цикличность. Отношение [R,Ω] называется циклическим, если для его элементов {x1, x2, z3,…, xn} найдется подмножество элементов {xi,xi+1,…xr,…,xj,xi}, для которого можно выписать последовательность xiRxi+1R…RxjRxi. Такая последовательность называется циклом или контуром (рис. 2.10).

9. Ацикличность. Отношения, в которых отсутствуют контуры называются, ациклическими. Для ациклических отношений выполняется соотношение R^k∩R = Ø для любого k > 1 (рис. 2.11).

10. Полнота (связность). Отношение [R,Ω] называется полным (связным), если для любых двух элементов (у, z) є Ω один из них находится в отношении с другим (рис 2.12). Линейность. Линейные отношения – это минимально полные отношения.

Рисунок 2.12. Линейное отношение

Итак, нами установлено, что отношения, как математические объекты, обладают определенными свойствами, определение которых приведены ранее. В следующем пункте рассмотрим существо и проявление некоторых свойств:

1. Рефлексивность х є А (хRx).
2. Антирефлексивность х є А ¬(хRx).
3. Симметричность х, у є А (хRy→yRx).
4. Антисимметричность (xRy & yRx→x = y).
5. Транзитивность; х, у, z є А(хRy & yRz →xRz).
6. Цикличность; х, у є А; .
7. Полнота x,y є А (xRy, yRx);
8. Связность (x ≠ y→ xRy, yRx).
9. Линейность x,y є А (xRy, yRx).

Анализ пространства отношений представляет сложную задачу теории и, надо отметить, далек от завершения. К основным результатам следует отнести выделение подмножеств отношений, образующих полные пространства отношений со всеми вытекающими из этого следствиями.

Количественные соотношения таких дискретных пространств представляют большой как
теоретический, так и практический интерес. Ниже рассматриваются некоторые аспекты количественных характеристик, связанных со свойствами отношений разных типов.

Операции над отношениями

Как и большинстве систем счисления с отношениями выполняются операции:

• унарные;
• бинарные;
• n-арные.

Ниже приведены таблицы булева ⊕ сложения и умножения & двух переменных x1 и x2, сложение по mod 2 и суммирование двоичных чисел:

Выше было введено понятие бинарного отношения, как подмножества упорядоченных пар декартова произведения множеств, а также были рассмотрены свойства отношений. Кроме того, были упомянуты бинарные отношения и матричное представление отношений. Рассмотрим теперь понятие отношения более подробно, кроме того, рассмотрим основные операции бинарных отношений, наиболее важные из всего их множества для отношений.

Для них должны выполняться следующие условия:

• арность операндов в операции должна совпадать;
• результатом операции должно быть отношение той же арности.

Для бинарных и n-арных отношений должно быть выполнено: область прибытия первого операнда должна совпадать с областью отправления второго операнда.

Унарные операции над отношениями

Обращение отношений. Обратным к отношению R называется отношение R^-1, определяемое условием xR^-1y<=>yRx. Более корректно эту операцию следовало бы назвать псевдообращением, так как р·р^-1 ≠ Е = Δ.

Пусть отношение Р записано в форме перечисления входящих в него упорядоченных пар. Если в каждой паре поменять местами компоненты, то новые пары образуют отношение P^-1, которое называют обратным к Р.

Обратное отношение к отношению P – такое отношение, которое образовано парами (ai aj), для которых (aj ai) є P^-1. Для отношений в матричной форме обратные отношения получаются путем транспонирования матрицы Р.

9. Двойственное отношение (P^d) к отношению Р – отношение, образованное всеми теми парами, которые принадлежат универсальному отношению и не принадлежат обратному отношению (дополнение к обратному):

P^d = {(ai aj) | ((ai aj) єA×A) & (ai aj)∉

P

^-1)} =(A×A) P^-1.

Двойственное и обратное отношения в совокупности содержат все пары декартова произведения A×A и не имеют общих пар, они также как и отношения Р и

P

образуют разбиение A×A

Заметим, что ни для какого отношения Р не выполняется Р= P^d.

Сужение (РА1). Отношение [R1, A1] называется сужением отношения [R, A] на множество Ω1, если Ω1⊆ Ω и R1=R∩Ω1×Ω1. Отношение РА1 на множестве А1 ⊆ А – отношение РА1 на множестве А1, образованное всеми теми парами, которые принадлежат отношению Р и одновременно входят в состав декартова произведения А1 × А1. Другими словами, РА1 – пересечение отношений Р и А1×А1. Пусть А1 = {a1, a3, a4}, тогда для отношений Р и Q в матричной форме отношения сужения будут иметь вид:

Бинарные операции

Операции, требующие не менее двух отношений – n-арные (n-местные). В таких операциях могут участвовать отношения только одинаковой арности. Примеры таких операций: пересечение, объединение, разность, симметрическая разность отношений и некоторые другие. Если в операции используется более чем два отношения, то она выполняется последовательно для двух первых, а затем для итогового отношения и третьего и т.д.

Иначе говоря, эти операции определены для двух отношений. При операциях над отношениями предполагается, что области задания отношений (операндов и результата) совпадают, арности отношений совпадают, и результатом операции снова является отношение той же арности. В качестве примеров будем рассматривать операции над бинарными отношениями P и Q, заданными на дискретном множестве
А = {a1, a2, a3, a4} булевыми матрицами (нули в матрицу, как правило, не вписываются):

1. Пересечение (P ∩ Q) – отношение, образованное всеми теми парами элементов из А, которые входят в оба отношения, т.е. общие для P и Q,
P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.

Матрица отношения P ∩ Q получается как булево пересечение матриц P и Q:

При отсутствии таких общих пар говорят, что пересечение отношений пусто, т.е. оно является нуль-отношением. Пересечением отношений R1 и R2 (R1∩R2 ) называется отношение, определяемое пересечением соответствующих подмножеств из А×А.

2. Объединение (PUQ). Объединением отношений R1 и R2 (R1UR2 ) называется отношение, определяемое объединением соответствующих подмножеств из А×А. Отношение, образованное всеми парами, составляющими или отношение P, или отношение Q, т.е. парами, принадлежащими хотя бы одному из отношений (связка ∨ — или объединительная)
P U Q = {(ai aj) | ((ai aj) є P) ∨ ( (ai aj) є Q)}.

Если в множестве А×А нет других пар, не вошедших в отношение PUQ, а пересечение их нулевое, то говорят, что отношения P и Q при объединении образуют полное отношение А×А, а их система – разбиение этого полного отношения. Объединение матриц отношений образуется как булева сумма матриц отношений:

3.Разность (PQ) – отношение, образованное теми парами из Р, которые не входят в отношение Q
PQ = {(ai aj) | ((ai aj) є P)&((ai aj)∉Q)}.

Разность для отношений в матричном представлении имеет вид

4. Умножение отношений. Упорядоченные пары, образующие отношения могут содержать одинаковые элементы, а могут и не содержать. Среди пар, имеющих в своем составе одинаковые элементы, выделим такие упорядоченные пары, которые назовем смежными (примыкающими) и которые имеют во второй паре 1-й элемент, а в первой паре 2-й элемент один и тот же. Определим произведение смежных пар как упорядоченную пару:
( ai ak)∙( ak aj) => (ai aj).

В терминах теории графов сказанное означает, что смежные пары образуют маршрут из точки (ai) в точку (aj) транзитом через точку (ak), состоящий из 2-х смежных дуг. Произведение этих дуг – третья дуга из точки (ai) в точку (aj), реализующая переход между крайними точками маршрута в том же направлении, минуя промежуточную точку (ak). Говорят, что дуга (ai aj) замыкает эти точки напрямую.

5. Симметрическая разность (P∆Q) – отношение, образованное теми парами, которые входят в объединение PUQ, но не входят в пересечение P∩Q. Другая форма определения объясняет название операции: P∆Q образовано теми упорядоченными парами, которые являются объединением разностей PQ и QP. Таким образом, выражение для симметрической разности записывается двумя разными способами:
P∆ Q = (PU Q)(P ∩ Q) = (PQ)U (QP).

Матрица симметрической разности имеет вид:

Из последней записи следует, что операция симметрической разности допускает перестановку операндов, т. е. коммутативна.

5. Композиция или произведение (P∙Q) – отношение, образованное всеми парами, для которых выполняется:
P∙Q = {(ai aj)|((ai ak) є P) & ((ak aj) є Q)}.

Другими словами, каждая упорядоченная пара в результирующем отношении есть результат умножения смежных пар, из которых 1-я пара принадлежит первому сомножителю-отношению, 2-я – второму сомножителю-отношению. Операция композиции не коммутативна.

Композиция (Р◦Q) на множестве М – отношение R, заданное на том же множестве М, которое содержит пару (x, y), когда существует Z є M такое, что (x, z) є P и (z, y) є Q.

При матричном представлении отношений матрица композиции отношений равна булеву произведению матриц исходных отношений:

Частный случай композиции отношений – квадрат отношения.

Можно показать, используя индукцию, что n-я степень отношения определяется рекуррентно по формуле:Pⁿ=P^n-1◦Р, это означает, что пара (x,y) є Pⁿ в том случае, когда в матрице Р существует цепочка элементов: такая, что (xi, xi+1)є P, 1<i<n–1.

Операция композиции обладает свойством ассоциативности (как произведение матриц).

Композиция отношений на множестве М – результат попарной композиции отношений при любой расстановке скобок. Область задания результата композиции при этом не меняется.

Композиция для булевых матриц отношений образуется в результате булева произведения матриц этих отношений.

Таблица 3. Каталог бинарных отношений (n = 3). Кликабельно

Если мы хотим
определить такое понятие, как отношение,
мы должны, прежде всего, ввести такое
понятие, как упорядоченная
пара.

Различие между
неупорядоченной парой элементов {a,b}
и упорядоченной парой (a,b)
обычно поясняют на примере сравнения
двух пар элементов. Две неупорядоченные
пары {a,b}={c,d},
если a=b&c=da=c&b=d.
Для упорядоченных пар (a,b)=(c,d)

a=b&c=d.
То есть, в общем случае, для упорядоченных
пар (a,b)(b,a).
Иногда употребляют и такую запись:
R=(a,b)={a,{a,b}}.
Нетрудно догадаться, что существование
множества {a,b}
зависит от того, какое мы выберем a.
Если a,b
– числа, то мы можем описать множество
упорядоченных пар в виде графика,
откладывая по оси абсцисс значения a,
по оси ординат значения b,
для которых существует R=(a,b).

Упорядоченную
пару R
называют двухместным
или бинарным
отношением.
Упорядоченный набор из n
элементов (a₁,
… , a_n)
называют n-местным
отношением или
кортежем.

Элементы для
формирования упорядоченных наборов
мы можем выбирать как из одного множества,
так и из разных. При построении графиков,
которые отображают бинарные отношения
между множествами действительных чисел
X
и Y,
мы используем так называемую декартову
систему координат.

Прямым (декартовым)
произведением двух множеств A
и B
называется множество упорядоченных
пар (a,b),
в которых aA
и bB:
AB={(a,b)|
aA
& bB}.

Степенью множества
A
называется его прямое произведение
само на себя: Aⁿ=A…A
– всего n
раз.

Пользуясь введенным
понятием прямого произведения, можно
определить бинарное отношение как
подмножество
прямого произведения AB:
R=ab={(a,b)R|
RAB}.

Запись ab
обозначает
отношение между элементами a
и b
в общем виде, а запись (a,b)
обозначает конкретную упорядоченную
пару элементов, то есть один элемент
отношения.

Если у нас задан
некоторый универсум U,
то мы можем рассматривать понятия
принадлежности (),
включения (),
и равенства (=), как отношения на B(U)
– множестве всех подмножеств универсума
U.

Способы задания
отношений.
Если отношение содержит небольшое
количество пар (или наборов), его можно
задать, как и множество, перечислением.
Бинарные отношения, как уже говорилось,
могут быть заданы в виде графиков, если
A,B
– числовые множества. В общем случае
отношения могут быть заданы в виде
таблиц или графов. В реляционных базах
данных понятие «кортеж» соответствует
записи в таблице, а поля таблицы с
именами A,B,C,…,
из которых берутся элементы записи,
образуют прямое произведение множеств
ABC…
.

Основные понятия,
связанные с понятием бинарного отношения.

Пусть
R=ab={(a,b)R|
RAB}.
Тогда
существуют:

обратное отношение
R^-1={(b,a)|(a,b)R};

дополнение
отношения R={(a,b)|(a,b)R}=(AB)R;

тождественное
отношение I={(a,a)|aA};

однородное
отношение:
U_R={(a,b)|aA&bA}.

Композиция
отношений.

Пусть заданы два
бинарных отношения: R₁AB
и R₂BC
(говорят так: отношение из A
в B
и отношение из B
в C).

Композицией
отношений
R₁
и R₂
называется
отношение R
из A
в C:

R=
R₁
o R₂
={(a,c)|
aA
&
cC
&
bB
: (a,b)

R₁
& (b,c)

R₂}.

Пример.Пусть
A
– множество студентов ФПК, B
– множество специальностей, С –
множество учебных курсов, изучаемых
на этих специальностях. Нам нужно
определить, какие дисциплины будет
изучать каждый конкретный студент ФПК
(что будет включать его приложение к
диплому).

Здесь R₁
AB
– «студент aA
получает специальность bB»,
R₂
BC
– «на специальности bВ
изучается дисциплина cC».
Искомое отношение R
– «студент aA
изучает дисциплину cC»
есть композиция отношений R=
R₁
R₂.
То есть, чтобы студент aA
изучал дисциплину cC
нужно, чтобы он учился на специальности
bB,
что соответствует отношению ab,
и на этой специальности изучалась
данная дисциплина cC,
что соответствует отношению bc.
Значит, для решения задачи нам нужно
выяснить, для каких пар (a,b)
имеются пары (b,c),
и из этих пар составить новые пары
(a,c),
взяв первый элемент из пары (a,b),
а второй элемент – из пары (b,c).

Графически операцию
композиции можно проиллюстрировать
на следующей схеме.

В этой графической
схеме каждой упорядоченной паре
элементов (a,b)
и (b,c)
сопоставлены стрелки из множества А
в множество B
и из множества B
в множество C
соответственно. Искомым парам (a,c)
соответствуют возможные переходы по
стрелкам из множества A
в множество C.

Теперь составим
бинарные таблицы R₁
и R₂
для
представленных данной схемой отношений.
Элементы этих таблиц r_ij(1)
и r_jk(2)
соответствуют
отношениям (a_i,b_j)
и (b_j,c_k).
Первая таблица будет содержать |A|
строк и |B|
столбцов, вторая – |B|
строк и |C|
столбцов. Для нашего примера таблицы
будут иметь вид:

1	0	0
0	1	1
1	0	0
0	1	0

1	0	1	1	0	0
0	1	0	0	1	0
0	0	1	0	0	1

R₁

R₂

Одновременное
существование отношений r_ij(1)
и r_jk(2)
соответствует
логическому произведению (конъюнкции)
элементов таблицы r_ij(1)

r_ij(2),
и значение каждого элемента r_ik
итоговой таблицы R
будет зависеть от того, принимает ли
хотя бы одна из этих элементарных
конъюнкций значение «1», что соответствует
логическому сложению (дизъюнкции). Для
нашего примера r₁₁=(r₁₁₍₁₎
r₂₁₍₁₎
r₃₁₍₁₎
r₄₁₍₁₎
)(
r₁₁r₁₂₍₂₎
r₁₃₍₂₎
r₁₄₍₂₎
r₁₅₍₂₎
r₁₆₍₂₎),
и так далее. То есть при i=1,…,|A|,
j=1,…,|B|,
k=1,…,|C|
мы имеем: R=
R₁
o
R₂
= R₁
R₂
, где R₁
R₂
– логическое
перемножение матриц.

Степенью отношения
Rⁿ
называется композиция отношения R
n
раз с самим собой.

Ядром отношения
RAB
называется композиция R*=
R
o
R^-1.
Ядро отношения является отношением на
A.

9.Однородные
(универсальные) отношения. Примеры
универсальных отношений. Свойства
однородных отношений (рефлексивность,
симметричность, транзитивность).
Отношение эквивалентности и отношение
порядка.

однородным
отношением–
отношение R=
a

b={(a,b)|aA&bA}.

однородное отношение
– это отношение RA².
Однородные
бинарные отношения
– важный тип отношений для многих
приложений информатики и других разделов
дискретной математики, для задач теории
графов. Ребра любого графа задают
однородное бинарное отношение на
множестве его вершин V.
Множество точек на плоскости с заданной
системой координат (X,Y)
– это тоже однородное бинарное отношение,
где A
– множество действительных чисел.

Свойства однородных
отношений.

1. Рефлексивность:

aA
имеет место отношение (a,a).
То есть отношение (a,b)
всегда существует при a=b.
Свойство рефлексивности означает,
что IR.

2.
Антирефлексивность:

aA
имеет место (a,a).
То есть отношение (a,
b)
не существует
ни при каких a=b.
Если для каких-то a=b
отношение существует, а для каких-то
нет, то следует говорить, что отношение
просто не
рефлексивно.

Примеры рефлексивных
отношений
на множестве точек плоскости XY:

1) R={(x,y)
| x=y};

2) R={(x,y)
| |y|<|x|+1};

3) R={(x,y)
| x+y=2k,
k=1,2,…,n}.

3.
Симметричность:

a,bA
(a,b)R

(b,a)R.
Свойство
симметричности означает, что R^-1R.

Симметричными
отношениями на множестве точек плоскости
XY
являются отношения 1) и 3) из приведенных
выше.

4.
Антисимметричность:

a,bA
, ab,
(a,b)R


(b,a)R.
То есть
условие симметричности не
выполняется
ни при каких a,b.
Простейший пример антисимметричного
отношения на XY
– строгое неравенство x<y.

Если для каких-то
ab
симметричность выполняется, а для
каких-то нет, то следует говорить, что
отношение R
просто не
симметрично.
Примером такого отношения является
отношение 2).

5. Транзитивность.

a,b,cA
(a,b)R
& (b,c)R

(a,c)R.
Очень важное свойство отношений.

Свойство
транзитивности можно записать через
степень отношения (композицию отношения
с самим собой): R²
=R

R

R.

Антитранзитивность
обычно не рассматривают, хотя можно и
ее определить так же, как в первых двух
случаях.

Примеры транзитивных
отношений:

1) все три примера,
приведенных выше;

2) x<y
( в том числе и нестрогое неравенство);

3) отношение
вложенности на B(U):
пусть A,B,C

U.
Если A

B
& B

C

A

C.

6.
Полнота
(линейность):

a,bA
, ab


(a,b)R

(b,a)R
.
Полнота
отношения означает, что R

R^-1

I
= U_R.

Свойство полноты,
вообще говоря, довольно редкое. Пример
полного отношения – неравенство xy.

Отношения
эквивалентности и отношения порядка.

Определение 1.
Если однородное отношение RA²:

1. рефлексивно,
   2)симметрично, 3) транзитивно

то оно называется
отношением
эквивалентности. Отношение
эквивалентности часто обозначается
«»,
как и операция эквивалентности в логике.
Множество элементов aA,
для которых выполняется отношение
эквивалентности R,
называется классом
эквивалентности.
Класс эквивалентности будем обозначать
[x]_:

[x]_
= {y
| yA
& yx}.

Из рассмотренных
выше примеров отношениями эквивалентности
являются примеры 1) и 3).

Примером отношения
эквивалентности на B(U)
может служить отношение равномощности
множеств: |A|=|B|.
То есть все подмножества из U
одинаковой мощности образуют класс
эквивалентности.

Определееие 2.
Если однородное отношение RA²:

1. антисимметрично,
   2) транзитивно,

то
оно называется отношением
порядка.
Если отношение при этом еще и
антирефлексивно,
то это отношение
строгого порядка.
Отношение нестрогого порядка может
быть как рефлексивным, так и просто не
рефлексивным.Для обозначения отношения
порядка можно использовать обычный
знак неравенства.Если отношение порядка
не обладает свойством полноты
(линейности), то обычно говорят об
отношении частичного
порядка. В
задачах дискретной математики и
информатики чаще всего встречается
именно этот тип отношений.

Если на множестве
А определено отношение частичного
порядка, то оно называется частично
упорядоченным.
Множество, на котором определено
отношение полного порядка, называется
вполне
упорядоченным.
Например, числовые множества – это
вполне упорядоченные множества.

Теорема.
На всяком конечном, непустом, частично
упорядоченном множестве существует
минимальный
элемент y
| 
xy
y<x.

Вполне упорядоченное
множество содержит только один
минимальный элемент, на частично
упорядоченном множестве их может быть
несколько. Булеан B(U),
– это вполне упорядоченное множество
относительно отношения вложенности
().
Минимальным элементом в этом случае
является пустое множество .

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Определение:

Композицией (произведением, суперпозицией) бинарных отношений (англ. composition of binary relations) и называется такое отношение , что: .

Примером такого отношения может служить отношение на некотором множестве населенных пунктов — отношение “можно доехать на поезде”, а — отношение “можно доехать на автобусе”. Тогда отношение — отношение “можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)”.

Степень отношений

Определение:

Степень отношения (англ. power of relation) , определяется следующим образом: ;

В связи с этим понятием, также вводятся обозначения:

— Транзитивное замыкание (англ. transitive closure) отношения ;

— Транзитивно-рефлексивное замыкание отношения

Обратное отношение

Определение:

Отношение называют обратным (англ. inverse relation) для отношения , если:

Определение:

Ядром отношения (англ. kernel of relation) называется отношение

Свойства

Композиция отношений обладает следующими свойствами:

• Ядро отношения симметрично:  

• Композиция отношений ассоциативна:  

• Обратное отношение для отношения, являющемуся обратным к есть само  

• Обратное отношение к композиции отношений и есть композиция отношений, обратных к и  

• Обратное отношение к объединению отношений и есть объединение отношений, обратных к и  

• Обратное отношение к пересечению отношений и есть пересечение отношений, обратных к и  

См. также

• Бинарное отношение
• Транзитивное замыкание

Источники информации

• Новиков Ф. А. — Дискретная математика для программистов: Учебник для вузов. 3-е изд. — СПБ.: Питер, 2009 — 52 с.
• Wikipedia — Composition of relations
• UNC Charlotte — Lectures in Discrete Mathematics: Composition of Relations and Directed Graphs.