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

Отношения. Часть I

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношения можно задавать в разном представлении над А=:

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

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

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

— Представление графом. Поставим в соответствие элементам множества
А = точки на плоскости, т.е. вершины графа 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 9 отношений, и каждое из них снабдим набором присущих им свойств. Ниже (табл. 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.Разность (P\Q) – отношение, образованное теми парами из Р, которые не входят в отношение Q
P\Q = <(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 образовано теми упорядоченными парами, которые являются объединением разностей P\Q и Q\P. Таким образом, выражение для симметрической разности записывается двумя разными способами:
P∆ Q = (PU Q)\(P ∩ Q) = (P\Q)U (Q\P).

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

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

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 n =P n-1 ◦Р, это означает, что пара (x,y) є P n в том случае, когда в матрице Р существует цепочка элементов: такая, что (xi, xi+1)є P, 1 Литература

Источник

Специальные свойства бинарных отношений

Рефлексивные и иррефлексивные бинарные отношения

В этой лекции дана определенная классификация бинарных отношений на множестве. В основе этой классификации лежат специальные свойства отношений.

Указанные свойства бинарных отношений на множестве называют рефлексивностью и иррефлексивностью.

Симметричные и антисимметричные бинарные отношения

Бинарное отношение на множестве называют:

Соответствующие свойства бинарных отношений на множестве называют симметричностью и антисимметричностью.

График симметричного бинарного отношения на множестве симметричен относительно диагонали (рис. 1.8).

Транзитивность бинарного отношения

Докажем следующее важное свойство транзитивного бинарного отношения.

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

Плотное бинарное отношение

Классы бинарных отношений

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

Бинарное отношение на некотором множестве называют:

Определенные выше бинарные отношения называют отношениями эквивалентности, толерантности, порядка (частичного порядка), предпорядка (квазипорядка), строгого порядка, строгого предпорядка.

Пример 1.13. а. Бинарное отношение параллельности двух прямых или двух плоскостей в евклидовой геометрии, если считать каждую прямую (плоскость) параллельной самой себе, есть отношение эквивалентности.

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

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

е. Отношение строгого неравенства на числовом множестве, равно как и отношение строгого включения множеств, есть отношение строгого порядка.

Связь между классами бинарных отношений

Отношения толерантности, эквивалентности, предпорядка и порядка — важнейшие в современной математике. Связь между этими четырьмя классами бинарных отношений показана на рис. 1.10. Можно сказать, что эквивалентность есть транзитивная толерантность или симметричный предпорядок. Порядок же есть антисимметричный предпорядок.

Отношение называют рефлексивно-транзитивным замыканием бинарного отношения на соответствующем множестве.

В итоге получаем последовательность

Источник

Лекция 3. Отношения на множествах. Свойства бинарных отношений

п.3. Отношения на множествах. Свойства бинарных отношений.

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A´B) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S´K можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

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

Определение 3.1. Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество A´B, т. е.

.

В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит: r, t, j, s, w и т. д.

Пример 3.1. Пусть даны два множества A= <1; 3; 5; 7>и B=<2; 4; 6>. Отношение зададим следующим образом t=<(x; y)ÎA´B | x+y=9>. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t=<(3; 6), (5; 4), (7;2)>. В данном примере Dt= <3; 5; 7>и Rt= B=<2; 4; 6>.

Пример 3.2. Отношение равенства на множестве действительных чисел есть множество r=<(x; y) | x и y – действительные числа и x равно y>. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, Dr= Rr.

Пример 3.3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j=<(x; y)ÎA´B | y – цена x> – отношение множеств A и B.

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t=<(x; y)ÎA´B | x+y=9>, а потом записано в виде t=<(3; 6), (5;4), (7;2)>. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

4) в виде матрицы: пусть A=<a1, a2, …, an> и B=<b1, b2, …, bm>, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями

.

Кстати, матричное представление является представлением отношения в компьютере.

Пример 3.4. Пусть даны два множества A=<1; 3; 5; 7>и B=<2; 4; 6>. Отношение задано следующим образом t=<(x; y) | x+y=9>. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t= <(3; 6), (5; 4), (7; 2)>— есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

3) в матричном представлении это отношение имеет вид

Пример 3.5. Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M:

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении r, если из устройства mi поступает информация в устройство mj.

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n—арное) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей)

Многоместные отношения удобно задавать с помощью реляционных таблиц. Такое задание соответствует перечислению множества n-к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных. Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная» происходит от латинского слова relation, которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».

Определение 3.4. Пусть rÍA´B есть отношение на A´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A´B, которое определяется следующим образом:

Определение 3.5. Пусть r ÍA´B есть отношение на A´B, а s ÍB´C – отношение на B´C. Композицией отношений s и r называется отношение t ÍA´C,которое определяется следующим образом:

2) Используя определение композиции двух отношений, получаем

из (1, y)Îr и (y, d)Îs следует (1, d)Îs◦r;

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

1) ;

2) ;

3) — ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Свойство 3 доказать самостоятельно.

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

Рассмотрим специальные свойства бинарных отношений на множестве A.

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

1. Отношение r на A´A называется рефлексивным, если (a,a) принадлежит r для всех a из A.

2. Отношение r называется антирефлексивным, если из (a,b)Îr следует a¹b.

3. Отношение r симметрично, если для a и b, принадлежащих A, из (a,b)Îr следует, что (b,a)Îr.

4. Отношение r называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению r следует, что a=b.

5. Отношение r транзитивно, если для a, b и c из A из того, что (a,b)Îr и (b,c)Îr, следует, что (a,c)Îr.

Решение. 1) Это отношение рефлексивно, так как для каждого aÎA, (a; a)Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

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

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a

Пример 3.8. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3.9. Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для «x΢ имеем x—x=0, и, следовательно, оно делится на m;

это отношение симметрично, т. к. если (x—y) делится на m, то и (y—x) тоже делится на m;

это отношение транзитивно, т. к. если (x—y) делится на m, то для некоторого целого t1 имеем , а если (y—z) делится на m, то для некоторого целого t2 имеем , отсюда , т. е. (x—z) делится на m.

Определение 3.7. Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример 3.12. Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.

Пример 3.13. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта.

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.

Источник