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

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

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

Отношение  называется отношением строгого порядка, если оно транзитивно (Ф•Ф = Ф), и антирефлексивно (МФ = ).

Введем понятие отношения связности. Отношение  = <Ф, М> называется связным, если выполняется условие М²\М  ФФ^-1.

Отношение  называется отношением совершенно нестрогого порядка, если оно является отношением связности (М²\М  ФФ^-1) и является отношением нестрогого порядка.

Отношение  называется отношением совершенно строгого порядка, если оно является отношением связности (М²\М  ФФ^-1) и является отношением строгого порядка.

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

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

Примеры:

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

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

3) х,у X  Y  X  Y. В данном случае имеет отношение нестрогого порядка.

4) х,у X  Y  X  Y. В данном случае имеет отношение строгого порядка.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ф•ФФ  МФ.

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

М  Ф  Ф = Ф^-1.

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

(хМ)(х  х),

(х, уМ)(х  у  у  х).

Примеры:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Пусть заданы произвольные отношения  = <F, X> и  = <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. Найти и записать теоретическим, матричным и графическим способом:

а)   ;

б)   ;

в)  \ ;

г)  • ;

д) дополнение отношения  до отношения ;

е) дополнение отношения  до отношения .

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

а)  • (  )  (• )  (• );

б)   (  )  (  )  (  );

в)  • (  )  ( • )  ( • );

г)   (  )  (  )  (  ).

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

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

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

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

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

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

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

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