litceysel.ru
добавить свой файл
1

Нестрогое предпочтение


Нестрогое упорядочение.

Определение 3.1. Нестрогим упорядочением называется отношение , определяемое

.

Из данного определения следуют утверждения:

Утверждение 3.32.

, т.е. .

Докажем утверждение. Рассмотрим соотношения:

(3.16)

(3.17)

(3.18)

Так как всегда выполняется одно из (3.16), (3.17), (3.18), то .

Утверждение 3.33. Отношение – связно. Следует из утверждения 3.32.

Утверждение 3.34. Отношение – рефлексивно. Следует из утверждения 3.33.

Утверждение 3.35. Строгое упорядочение и нестрогое упорядочение образуют двойственную пару отношений


.


Следует из соотношений и . Симметричной частью отношения называется отношение, определяемое . Асимметричной частью отношения называется отношение, определяемое . Очевидны соотношения ,.

Утверждение 3.36. ,.

Следует из соответствующих определений.

Существует иное определение нестрогого упорядочения.

Определение 3.2. Связное отношение называется отношением нестрогого упорядочения.

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

Утверждение 3.37. Если связное отношение, то , , и .


симметрично по определению. Т.к. связно, то оно и рефлексивно, а значит рефлексивно и . Таким образом – рефлексивное симметричное отношение – толерантность.

­– асимметрично по определению, т.е. является строгим упорядочением.

Окончательно,

.

Таким образом, если строгое предпочтение представлено отношением упорядочения (свойство – асимметрия), то индуцируемое им отношение безразличия обладает свойствами рефлексивности, симметричности и относится к классу толерантности, а отношение нестрогого упорядочения обладает свойствами рефлексивности и связности.


Нестрогий слабый порядок.

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

Из данного определения и свойств отношений и следуют утверждения:

Утверждение 3.38. т.е. . по определению.


Утверждение 3.39. Отношение рефлексивно. Следует из рефлексивности .

Утверждение 3.40. Отношение связно. По определению.

Утверждение 3.41. Отношение транзитивно. Следует из обобщенной транзитивности и .

Утверждение 3.42. Отношение отрицательно транзитивно. Следует из транзитивности и связности.

Докажем от противного. Пусть , и в то же время . В силу связности справедливо , в силу транзитивности , что противоречит .

Утверждение 3.43. Строгий слабый порядок и нестрогий слабый порядок образуют двойственную пару отношений

,


.

Доказательство следует из соотношений

,

.

Утверждение 3.44. Отношение безразличия является симметричной частью нестрогого слабого порядка , а строгий слабый порядок – асимметричной частью , т.е. ,

Может быть дано иное определение нестрогому слабому порядку.

Определение 3.4. Связное транзитивное отношение называется отношением нестрогого слабого порядка.

Покажем эквивалентность определений 3.3. и 3.4.

Утверждение 3.45. Если связное транзитивное отношение, то , и .

симметрично по определению. Т.к. связно, то оно рефлексивно, а значит рефлексивно и. Т.к. транзитивно, то транзитивно и и , таким образом – эквивалентность.


асимметрично по определению. Докажем отрицательную транзитивность. Пусть выполняется , из связности справедливо , с учетом транзитивности выполняется . Так как , имеет место таким образом, т.е. – отрицательно транзитивно.

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

Нестрогий порядок.

Определение 3.5. Нестрогим порядком называется отношение, определяемое ,


где – диаганальное отношение.

Существует иное определение нестрогого порядка.

Определение 3.6. Рефлексивное, транзитивное, антисимметричное отношение называется строгим порядком.

Покажем что эти определения эквивалентны.

Утверждение 3.46. обладает свойствами рефлексивности, транзитивности, антисимметричности.

Поскольку рефлексивно, то рефлексивно и .

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

(3.19)

(3.20)

(3.21)

(3.22)

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

Если имеет место (3.19), то и выполняется . Если выполняется (3.20), то и выполняется. Если выполняется (3.21), то и справедливо. И, наконец, если имеет место (3.22), то в силу транзитивности выполняется .


Таким образом, всегда выполняется , т.е. – транзитивное отношение.

Докажем антисимметричность . Поскольку рефлексивно, оно не может быть антисимметрично, значит существуют такие что и одновременно.

В силу справедливости может иметь место одна из следующих ситуаций :

(3.23)

(3.24)

(3.25)

(3.26)

Соотношение (3.34) невозможно, поскольку из следует , что одновременно с невозможно. По тем же соображениям невозможно (3.25). Ситуация (3.26) невозможна в силу асимметричности . Наконец, (3.23) свидетельствует, что и в этом случае всегда выполняется (в силу рефлексивности ).


Таким образом, отношение антисимметрично. Утверждение доказано.

Теперь для завершения доказательства эквивалентности определений 3.5 и 3.6 остается доказать следующее утверждение.

Утверждение 3.47. Пусть рефлексивное, транзитивное, антисимметричное отношение. Тогда его симметричная часть – диагональное отношение, а асимметричная часть – строгий порядок.

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

Таким образом .

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


Таким образом – асимметричное транзитивное отношение – отношение строгого порядка. Утверждение доказано.

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

Квазипорядок.

Определение 3.7. Квазипорядком называется отношение, определяемое : ,

где – отношение равноценности, принадлежащее к классу эквивалентности такое, что имеет место обобщенная транзитивность по , т.е.

,

.

Содержательно это требование означает, что из утверждений « предпочтительней , а равноценно » и « равноценно , а предпочтительней » следует одинаковый вывод « предпочтительней ».


Утверждение 3.48. Отношение квазипорядка рефлексивно. Следует из рефлексивности .

Утверждение 3.49. Отношение квазипорядка транзитивно.

Докажем утверждение. Пусть имеет место это значит, что имеет место одна из следующих ситуаций:

(3.27)

(3.28)

(3.29)

(3.30)

В случае (3.27) в силу транзитивности выполняется и, следовательно, . В случае (3.28) в силу транзитивности выполняется и, следовательно, . В случае (3.29) или (3.30) в силу обобщенной транзитивности по выполняется и, следовательно, . Таким образом, из всегда следует . Утверждение доказано.


Существует иное определение квазипорядка.

Определение 3.8. Рефлексивное транзитивное отношение называется отношением квазипорядка.

Покажем, что определения 3.7 и 3.8 равносильны.

Утверждение 3.50. Если отношение рефлексивно и транзитивно, то


  1. – отношение эквивалентности;

  2. – отношение строгого порядка;

  3. – обобщенно транзитивно по .

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

асимметрично по определению асимметричной части. Покажем обобщенную транзитивность и транзитивность .

Пусть выполняется :

(3.31)

тогда выполняется и по транзитивности выполняется , а это значит, что выполняется одно из двух соотношений :


,

(3.32)

Пусть тогда из симметричности выполняется и, с учетом (3.31) имеет место (по транзитивности ).

Последнее соотношение противоречит исходному положению , так как . Таким образом в (3.32) реализуется и, окончательно:

.

Пусть выполняется :

(3.33)

Тогда справедливо и по транзитивности выполняется , т.е. выполняется одно из двух соотношений (3.32) Пусть , тогда и с учетом (3.33) , что противоречит из (3.33). Таким образом из (3.32) реализуется и, окончательно : . Обобщенная транзитивность по доказана.


Пусть выполняется

(3.34)

тогда справедливо , а значит и , что реализуется одним из двух соотношений (3.32). Пусть , тогда . С учетом (3.34) выполняется . Тогда, в силу обобщенной транзитивности , что противоречит (3.34). Таким образом из (3.32) реализуется и, окончательно:

.

Утверждение доказано.

Утверждение 3.51. Факторизация отношения квазипорядка по симметричной части дает отношения нестрогого порядка на фактор-множестве.

Докажем, что рефлексивное, транзитивное, антисимметричное отношение на .

Рефлексивность следует из того, что для любого класса и любого представителя верно , а следовательно, справедливо .


Докажем транзитивность . Пусть для классов верны соотношения и . Это значит, что для некоторых представителей и выполнено и для некоторых представителей и выполнено . Поскольку и , имеем , а значит . Из в силу транзитивности квазипорядка получим . Значит, для классов выполняется .

Докажем антисимметричность. Пусть выполнено . Это значит что справедливо:

(3.35)


Предположим, что одновременно верно , т.е. существуют такие представители и , что

(3.36)

По определению класса эквивалентности . Тогда по транзитивности из (3.35) и следует

(3.37)

С другой стороны из (3.36) и следует . Сравнивая это соотношение с (3.37) получим , т.е. и принадлежат общему классу по . Значит и, следовательно , что доказывает антисимметричность отношения .

Итак, структура отношения квазипорядка на может быть представлена следующим образом : «склеивая» некоторые объекты из (принадлежащие одному классу эквивалентности) получим нестрогий порядок.


Утверждение 3.52. Пусть – связный квазипорядок на . Тогда – связный нестрогий порядок на .

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

Рассмотрим следующий пример. Пусть задано отображение , где – множество вещественных чисел. Введем на отношение следующим условием : .


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

Таким образом, введенное отношение является отношением связного квазипорядка.

Множества, на которых функция принимает фиксированные значения известны как области уровня.

Важно не путать понятия асимметричной части и фактор-отношения по симметричной части. На рис.3.3.а. представлен граф квазипорядка ; на рис.3.3.б. представлен граф симметричной части ( в входят только двухсторонние стрелки и петли из ); на рис.3.3.в. представлен граф асимметричной части ( в входят только те стрелки из , которые не входят в ); и, наконец, на рис.3.3.г. представлен граф фактор-отношения (каждый связный подграф графа склеивается в одну вершину, дуга из одной вершины графа к другой проводится только тогда, когда есть дуга от представителя этой вершины к представителю другой вершины в графе ).


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

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

Связный квазипорядок задает связный нестрогий порядок на фактор множества , т.е. мы можем так пронумеровать классы разбиения , что будет выполняться для всех . Тогда искомое отображение может быть построено следующим образом : , где – номер класса разбиения , в который входит .

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


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

Взаимосвязь классов отношений.

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


Взаимосвязь классов отношений по свойствам.

На рис.3.4, 3.5 представлена взаимосвязь рассмотренных классов отношений по свойствам. На рис.3.4 представлены отношения, формализующие строгие предпочтения, на рис.3.5 – нестрогие предпочтения.

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

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

Нестрогое упорядочение обладает свойством связности, дополнительное свойство транзитивности трансформирует его в нестрогий слабый порядок или связный квазипорядок, свойство симметрии – в связный нестрогий порядок.

Взаимосвязь классов отношений по операциям.

Выделение симметричной и асимметричной части.

Симметричная часть нестрогого упорядочения является толерантностью, асимметричная – строгое упорядочение.


Симметричная часть нестрогого слабого порядка – эквивалентность, асимметричная – строгий слабый порядок.

Симметричная часть нестрогого порядка – отношение равенства , асимметричная – строгий порядок.

Симметричная часть квазипорядка – отношение эквивалентности, асимметричная – строгий порядок.

Взятие двойственного отношения.

Нестрогое упорядочение и строгое упорядочение образуют пару взаимодвойственных отношений

,

.

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

,

.

Факторизация

Факторизация строгого порядка по соответствующему отношению безразличия дает отношение слабо связного строгого слабого порядка на фактор-множестве .


Факторизация квазипорядка по симметричной части дает отношение связного нестрогого порядка на фактор-множестве

Отметим, что в случае представления нестрогого предпочтения нестрогим упорядочением или нестрогим слабым порядком, его структура полностью определяется конкретной структурой строгого упорядочения или строгого слабого порядка соответственно, т.е. на основе информации о строгом предпочтении строится отношение строгого предпочтения, полностью определяющее структуру соответствующего нестрогого предпочтения.

То же касается нестрогого порядка, поскольку , а структура всегда жестко определена.

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


Вопросы и задания для самоконтроля


  1. – множество членов семьи :

  1. отец;

  2. мать;

  3. сын Петр;

  4. сын Александр;

  5. дочь Татьяна;

  6. дочь Наталья;

На задано отношение свойством «быть братом». Задать это отношение перечислением, матрицей, графом, верхними и нижними сечениями


  1. Что представляет собой отношение , если – отношение «быть отцом», отношение – «быть матерью».

  2. Пусть . Доказать соотношения , для всех .

  3. Исследовать свойства отношения на множестве действительных чисел:

  4. Показать, что симметричная часть квазипорядка – эквивалентность.

  5. Привести пример нестрогого слабого порядка задающего разбиение на три класса эквивалентности.


Список литературы для самостоятельного изучения


  1. Шрейдер Ю.А. Равенство, сходство, порядок. – М.: Наука 1971. – 256 с.

  2. Макаров И.М., Виноградская Т.М., Рубинский А.А., Соколов В.Б. Теория выбора и принятия решений. – М.: Наука. 1982. – 328 с.

  3. Розен В.В. Цель – оптимальность и решение ( математические модели принятия оптимальных решений). – М.: Радио и связь. 1982. – 168 с.

  4. Юдин Д.Б. Вычислительные методы теории принятия решений. – М.: Наука. 1989. – 320 с.
  5. Павлов А.А., Гриша С.Н., Томашевский В.Н. и др. Основы системного анализа и проектирования АСУ. – К.: Вища школа. 1991. – 367 с.

  6. Фишберн П. Теория полезности для принятия решений. – М.: Наука. 1978. – 352 с.