Парадигма развития науки. Методологическое обеспечение (стр. 59 )

найдется z такое, что

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

найдется z такое, что На индукции определяется п-я степень отношения Р:

Тот факт, что означает, что существует цепочка эле-

ментов такая, что для і = 1, 2, . . ., п - 1.

Пример 2.7. Для отношений Р и Q из примера 2.1 композиция этих отношений имеет матрицу

Матрица композиции отношений Р и Q есть булево произведе­ние матриц этих отношений.

8. Сужением отношения Р на подмножество называется отношение РВ на множестве В, которое состоит из всех тех пар (х, у) Р таких, что хВ и уВ. Другими словами, РВ =Р∩ (В × В).

Пример 2.8. Сужение отношений Р из примера 1 на подмножество В, состоящего из первого и третьего элементов, имеет матрицу

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

Отношение включения которое выполнено тогда и

только тогда, когда каждая пара (х, у), принадлежащая Р, при­надлежит также и отношению Q.

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

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

1. Рефлексивность отношения R означает, что т. е. рефлексивное отношение выполняется между элементом и им самим (xRx). В матрице рефлексивного отношения на главной диа­гонали всегда стоят единицы.

2. Антирефлексивность отношения R означает, что т. е. отношение R выполняется только для несовпадающих эле­ментов. В матрице антирефлексивного отношения на главной диа­гонали стоят нули.

3. Симметричность отношения R означает, что если

то т. е. если для пары (ж, у) выполнено отношение R, то для пары (у, х) также выполнено отношение R. В мат­рице симметрического отношения элементы аij и аji, расположен­ные симметрично относительно главной диагонали, равны между собой.

4. Антисимметричность отношения R означает, что если

Для элементов матрицы анти­симметричного отношения выполняется следующее условие:

аij•аji =0 при i ≠ j.

5. Транзитивность отношения R означает, что из и

следует Если в матрице транзитивного отношения элементы аii = 1 и аij = 1, то обязательно аij = 1. Квад­рат R2 транзитивного отношения R, вообще говоря, содержится в самом отношении В случае, если отношение R рефлексивно, то R2 = R.

С понятием транзитивного отношения связано понятие опера­ции транзитивного замыкания. Именно, для каждого отношения

R определим отношение как наименьшее транзитивное отноше­ние, содержащее данное. Можно показать, что такое отношение

определяется единственным образом и где п — мощность множества А — области задания отношения R.

Пример 2.9. Проиллюстрируем это свойство. Пусть отношение R оп­ределяется матрицей

Тогда имеем

и транзитивное замыкание отношения R есть матрица

6. Линейность (связность) отношения R означает, что для лю­бых или или В матрице линейного отношения или аij =1, или аji =1 для любых i≠j.

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

6.3. Пространства четких бинарных отношений

Во многих теоретических исследованиях и практических при­ложениях приходится рассматривать не произвольные бинарные отношения предпочтения на данном множестве объектов, а отно­шения предпочтения, на которые наложены некоторые дополни­тельные условия. Другими словами, обычно рассматривают спе­циальные типы отношений предпочтений, обладающие некоторы­ми из перечисленных в разделе 6.2 свойств. Особенности решаемой практической задачи предопределяют тип рассматриваемых отно­шений. Например, в задачах группового выбора обычно исполь­зуют отношение линейного квазипорядка, соответствующее чис­ловому отношению ≥ (не меньше). Реже используются отношения частичного порядка, совершенного строгого порядка, толерантно­сти и т. п.

Множество всех бинарных отношений предпочтения данного типа с геометрической точки зрения, изложенной в разделе 6.1, об­разует пространство — пространство бинарных отношений пред­почтения данного типа.

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

6.3.1. Три класса отношений

Пусть А — конечное множество объектов. Бинарное отноше­ние R называется отношением слабого предпочтения на множе­стве А, если для любых выполняется либо xRy, либо yRx.

Из нашего определения следует, что отношение слабого предпочтения рефлексивно, т. е. xRx для любых Для остальных пар (х, у) могут иметь место два случая: либо мы имеем xRy, и не выполнено yRx, либо одновременно выполняется xRy и yRx. В первом случае мы говорим, что х строго предпочи­тается у и пишем хРу. Тем самым отношение строгого предпоч­тения Р определяется следующим образом: объекты находятся в отношении Р (хРу) тогда и только тогда, когда выпол­нено xRy и не выполнено yRx. Отношение Р, очевидно, антирефлексивно и антисимметрично.

Во втором случае мы говорим, что выбор между х и у для нас безразличен и будем обозначать это xІy. Отношение безразли­чия I тем самым определено следующим образом:тогда и только тогда, когда xRy и yRx. Очевидно, что отношение І реф­лексивно и симметрично.

В качестве примера рассмотрим отношение R с матрицей

Этому отношению R соответствует строгое отношение предпочте­ния Р с матрицей