Х j у Ù х ¹ у ® Ø (у j х).

Очевидно, что отношение j = < Ф, М > антисимметрично тогда и только тогда, когда

ФÇФ^-1 Í DМ.

Например, высказывания больше, меньше, неравно являются примерами отношений антисимметричности (x > y, x ¹ y).

Отношение j = < Ф, М > называется отношением транзитивности, если

("х,у,zÎM)(х j у & у j z ® x j z).

Например, если х = у & y = z ® x = z, то j - отношение транзитивности. Для отношения параллельности справедливо: x êê y & y êê z ® x êê z, следовательно, оно является отношением транзитивности.

Для отношения транзитивности (иногда говорят транзитивное отношение) справедливо:

Ф • Ф Í Ф.

Примеры:

1. Полное отношение j =<М², М> является транзитивным отношением. Пусть М = <1, 2>, тогда M² = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} и M² • M² = {<1, 1>, <1, 2>, <2, 2>, <2, 1>}, M² • M² Í M².

2. Пустое отношение является носителем всех свойств.

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

Отношение j называется отношением эквивалентности, если оно рефлексивно (DМ Í Ф), симметрично (Ф = Ф^-1) и транзитивно (Ф•Ф = Ф). Иногда имея в виду отношения рефлексивности, симметричности, транзитивности и т.п., говорят, что эти отношения соответственно рефлексивности, симметричности, транзитивности и т.п.

j ~ j   ~ — знак эквивалентности.

Отношение равенства является отношением эквивалентности, т.к. оно рефлексивно(a = a), симметрично (a = b ® b = a) и транзитивно (a = b & b = c ® a = c) на множестве M={a,b,c}. Отношение параллельности является отношением эквивалентности, т.к. оно рефлексивно (a ïï a), симметрично (a ïê b ® b ïê a) и транзитивно (a êê b & b êê c ® a êê c) на множестве M={a,b,c}. Отношения больше, меньше, неравно, перпендикулярности и т.п. не являются отношениями эквивалентности, т.к. не обладают в совокупности тремя свойствами рефлексивности, симметричности и транзитивности.

Отношение эквивалентности связано с понятием разбиения множеств.

4.5. Разбиение множеств

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

Приведем формальное определение разбиения.

Система W множеств называется разбиением одного множества М, если она удовлетворяет четырем условиям:

1) ("X Î W)(X Í M).

2) ("X Î W)(X ¹ Æ).

3) ("X, Y Î W)(X ¹ Y ® X Ç Y = Æ).

4)

Первое условие говорит о том, что подмножество обязательно должно включаться и в систему, и в отдельное множество. Второе условие говорит, что подмножества разбиений не должны быть пустыми. Третье показывает, что подмножества должны быть разными и обязательно находиться в различных разбиениях. И, наконец, четвертое условие говорит о том, что все подмножества разбиения в совокупности должны представлять множество М.

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

Разбиение системы W множества М называется поэлементным, если каждый блок разбиения является одноэлементным множеством.

Наример, множество М = {1, 2, 3, 4} может быть разбито на четыре одноэлементных подмножества W = {M₁, M₂, M₃, M₄}, M₁ = {1}, M₂ = {2}, M₃ = {3}, M₄ = {4}.

Например,множество A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} можно разбить на 4 блока: M = { X 1, X 2, X 3, X 4 }, где X 1 = {1, 3, 5, 7, 9}, X 2 = {2}, X 3 = {4}, X 4 = {6, 8, 10}.

Разбиение системы называется целым, если W = {М}. Для предыдущего примера получим W = {1, 2, 3, 4}.

Поэлементное и целое разбиения называются тривиальными. Остальные разбиения, если они существуют, называются не тривиальными.

Примеры:

1. Пустое множество имеет единственное разбиение, т.е. пустую систему множеств (W = Æ).

2. Одноэлементное множество М = {a} имеет единственное разбиение W = М = {a}, которое одновременно является и целым, и поэлементным.

3. Множество М = { a, b } имеет два разбиения: W₁ = {M₁(a), M₂(b)}, W₂ = {M}.

4. Множество М = {a, b, c} имеет пять разбиений следующего вида: W₁ = {a, b, c}, W₂ = {{a}, {b}, {c}}, W₃ = {{a}, {b,c}}, W₄ = {{b}, {a,c}}, W₅ = {{c}, {a,b}}. Очевидно, что из пяти разбиений два являются тривиальными (W₁, W₂), а три – не тривиальными (W₃ – W₅).

5. Система курсов факультета является разбиением множества студентов, если ни один студент не учится одновременно на двух курсах.

Диаграмма Эйлера-Венна, иллюстрирующая возможное разбиение множества А = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} на четыре блока, приведена на рис 4.4. Если принять, что можность каждого из подмножеств разбиения пропорциональна величине занимаемого сектора окружности, то тогда можно записать следующее разбиение: X₁ = {1, 2, 3, 4, 5}; X₂ = {6}; X₃ = {7}; X₄ = {8, 9, 10}.

Рис. 4.4 Пример разбиения множества А на четыре блока

Известно, что отношение j на множестве М и разбиение этого множества сопряжены, если высказывание ("х,уÎМ хjу) является истинным, тогда, когда х и у принадлежат одному и тому же разбиению (к одному и тому же блоку разбиения).

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

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

Если два разбиения множества М сопряжены с одним и тем же отношением на этом же множестве, то они совпадают.

Другими словами, разбиение, сопряженное с данным отношением, единственно.

Теорема Т2. Об отношении, сопряженном с некоторым разбиением.

Если отношение j на множестве М сопряжено с каким-нибудь разбиением этого множества, то j — отношение эквивалентности.

Теорема Т3. О существовании разбиения, сопряженного с данным отношением эквивалентности.

Для любого отношения эквивалентности j, на множестве М существует сопряженное с ним разбиение множества М.

Итак, разбиение, сопряженное с данным отношением j существует тогда (Т3) и только тогда (Т2), когда j — отношение эквивалентности, причем в этом случае сопряженное разбиение единственно (Т1).

Теорема Т4. Пусть j — отношение эквивалентности на непустом множестве М, тогда различные классы эквивалентности определяют разбиение множества М.

4.6. Отношение порядка

Отношение порядка связано с отношениями типа £, <, >, ³.

Отношение j называется отношением нестрогого порядка, если оно транзитивно (Ф•Ф = Ф), рефлексивно (DМ Í Ф) и антисимметрично (ФÇФ^-1 Í DМ).

Отношение j называется отношением строгого порядка, если оно транзитивно (Ф•Ф = Ф), и антирефлексивно (D М Ç Ф = Æ).

Введем понятие отношения связности. Отношение j = <Ф, М> называется связным, если выполняется условие М²\DМ Í ФÈФ^-1.

Отношение j называется отношением совершенно нестрогого порядка, если оно является отношением связности (М²\DМ Í ФÈФ^-1) и является отношением нестрогого порядка.

Отношение j называется отношением совершенно строгого порядка, если оно является отношением связности (М²\DМ Í ФÈФ^-1) и является отношением строгого порядка.

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

 

Порядок	Транзитивность Ф•ФÍФ	Рефлексивность DМÍФ	Антирефлексивность DМÇФ = Æ	Антисимметричность ФÇФ-1 ÍDМ	Связность М2\DМÍФÇФ-1
нестрогий	+	+		+
совершенно нестрогий	+	+		+	+
строгий	+		+
совершенно строгий	+		+		+

 

Примеры:

1) х j у ® х > у. Данное высказывание говорит о том, что отношение j является отношением совершенно строгого порядка.

2) х j у ® х ³ у. Данное высказывание говорит о том, что отношение j является отношением совершенно нестрогого порядка.

3) "х,у X j Y ® X Í Y. В данном случае имеет отношение нестрогого порядка.

4) "х,у X j Y ® X Ì Y. В данном случае имеет отношение строгого порядка.

5) Отношение равенства на множестве М является нестрогим порядком, причем это самый маленький нестрогий порядок.

6) Отношение строгого порядка можно задать числовой осью х j у. Инверсию строгого порядка можно изобразить перевернутой числовой осью х j^-1 у.

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

Совершенно нестрогий порядок есть упорядоченная пара < Х, £ >, где отношение £ частично упорядоченное множество Х.

Например, если F есть некоторая система множеств, то < F, £ > есть частично упорядоченное множество. Для любого предложения об упорядоченных множествах можно указать эквивалентное ему предложение об отношениях порядка и обратно.

В тех случаях, когда множество Х означает множество объектов или группы объектов, говорят об отношении доминирования.

Будем говорить, что х доминирует у и писать х >> у, если х в чем-то превосходит у. Так, х может быть спортсменом или командой, победившей спортсмена или команду у, или лицом, пользующимся авторитетом у лица у, или свойством, которое мы предпочитаем свойству у. Будем говорить, что между элементами множества Х имеет место отношение доминирования, если эти элементы обладают следующими двумя свойствами:

1) Никакой элемент не может доминировать самого себя, т.е х >> х — ложно, т.е. имеет место отношение антирефлексивности (DМ Ç Ф = Æ).

2) В каждой паре элементов в точности один элемент доминирует второго, т.е. х >> у и у >> х — взаимоисключается, значит справедливо отношение антисимметричности (ФÇФ^-1ÍDМ).

В отношении доминирования свойство транзитивности не имеет места. Например, если в соревнованиях команда х победила команду у, а команда у победила команду z, то отсюда еще не следует, что команда х обязательно победит команду z. Для кортежей пример отношения доминирования имеет вид: a = <3, 4> >> b = <1,2>, то есть для первых элементов кортежей a и b справедливо: 3 >> 1, а для вторых элементов кортежей a и b справедливо: 4 >> 2.

Существует еще одно отношение порядка, которое называется квазипорядком (от «квази» — почти).

j = <Ф, М> — называется отношение квазипорядка, если оно транзитивно и рефлексивно.

Для отношения квазипорядка справедливо:

Ф•ФÍФ Ù DМÍФ.

 

Отношение j = <Ф, М> — называется отношением толерантности, если оно рефлексивно (DМ Í Ф) и симметрично (Ф =  Ф^-1). Следовательно, для отношения толерантности справедливо:

DМ Í Ф Ù Ф = Ф^-1.

Другими словами для отношения толерантности

(" х ÎМ)(х j х),

(" х, уÎМ)(х j у ® у j х).

Примеры:

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

2) Отношение А j В, где j определяет, что А не старше курсом, чем В, является примером отношения квазипорядка. Так как оно является транзитивным и рефлексивным.

3) Отношение параллельности является отношением толерантности, т.к. оно рефлексивно (a ïï a) и симметрично (a ïê b ® b ïê a) на множестве M = {a, b}.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение отношения.

2. Как строятся матрица и график отношения j = <Ф, Х>?

3. Перечислите основные операции над отношениями.

4. Что называется инверсией и композицией отношений?

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

6. В каком случае композиция двух отношений j и y будет являться:

а) функциональным отношением;

б) инъективным отношением;

в) биективным отношением?

7. Дайте определение и приведите пример рефлексивного отношения.

8. Дайте определение и приведите пример симметричного отношения.

9. Дайте определение и приведите пример транзитивного отношения.

10. Дайте определение и приведите пример связного отношения.

11. Может ли антисимметричное отношение быть также рефлексивным?

12. Может ли асимметричное отношение быть также рефлексивным?

13. Может ли рефлексивное отношение быть несвязным?

14. Приведите определение и примеры отношения толерантности.

15. Покажите каким образом отношение толерантности связано с отношениями эквивалентности, доминирования и порядка.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Пусть задано произвольное множество Х = { x, y, z, t }. Задайте произвольное отношение на этом множестве теоретическим, матричным и графическим способом.

2. Пусть заданы произвольные отношения j = < F, X > и y = < P, X >, где X = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₇ }; F = {< x ₁, x ₂ >; < x ₁, x ₃ >; < x ₁, x ₅ >; < x ₂, x ₃ >; < x ₂, x ₄ >; < x ₂, x ₆ >; < x ₃, x ₂ >; < x ₃, x ₄ >; < x ₄, x ₁ >; < x ₄, x ₄ >; < x ₅, x ₄ >; < x ₅, x ₆ >; < x ₆, x ₁ >; < x ₆, x ₂ >;}; P = {< x ₁, x ₃ >; < x ₁, x ₅ >; < x ₃, x ₆ >; < x ₃, x ₇ >; < x ₅, x ₁ >; < x ₅, x ₆ >; < x ₆, x ₃ >; < x ₇, x ₁ >; < x ₇, x ₇ >}.

3. Найти и записать теоретическим, матричным и графическим способом:

а) j È y;

б) j Ç y;

в) j \ y;

г) j • y;

д) дополнение   отношения j до отношения y;

е) дополнение   отношения y до отношения j.

4. Пусть заданы отношения j, y, s на множестве X. Доказать или опровергнуть истинность следующих тождеств:

а) j • (y È s) = (j• y) È (j• s);

б) j È (y Ç s) = (j È y) Ç (j È s);

в) j • (y Ç s) Í (j • y) Ç (j • s);

г) j Ç (y È s) = (j Ç y) È (j Ç s).

5. Построить график отношения, являющегося:

а) рефлексивным и симметричным;

б) нерефлексивным и связным;

в) асимметричным и транзитивным;

г) рефлексивным, симметричным и транзитивным;

д) антирефлексивным, несимметричным и связным;

е) рефлексивным, антисимметричным и транзитивным;

ж)рефлексивным, асимметричным, транзитивным и связным.