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

Бинарные отношения в теории принятия решений

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

Основными свойствами отношений являются: рефлексивность, антирефлексивность, симметричность, асимметричность, антисимметричность, транзитивность, ацикличность.

Рефлексивным называется такое отношение P, для которого справедливо утверждение EÍP, где Е – диагональное отношение. Это означает что для всех xÎA, где А – носитель P, xPx. В матрице рефлексивного отношения на главной диагонали всегда стоят единицы, а в соответствующем графе при каждой вершине находится петля.

Антирефлексивным называется отношение P, для которого . Это означает, что для всех xÎA:(x,x)ÏP, то есть в матрице отношения на главной диагонали всегда стоят нули, а в графе отсутствуют петли.

Симметричным называется отношение Р, для которого . Это значит что для всех x, yÎA, которые находятся в отношении Р, то есть xPy, справедливо утверждение yPx. В матрице симметричного отношения элементы bij и bji, размещены симметрично относительно главной диагонали, равные между собой. В графе G(P) наличие дуги (xi,xj) означает наличие дуги (xj,xi).

Асиметричным называется отношение Р, для которого , то есть если (x,y) ÎP то (y,x)ÏP. В матрице ассиметричного отношения для всех i и j, а на главной диагонали находятся нулевые элементы. В графе G(P) нет одновременно дуг (xi, xj) и (xj, xi) и отсутствуют петли.

Антисимметричным называется отношение Р, если , где Е- диагональное отношение. Таким образом выражения xPy и yPx справедливы одновременно лишь тогда, когда x=y. В матрице B(P) условие выполняется для всех i,j кроме i=j. В графе G(P) не существует одновременно дуг (xi, xj) и (xj, xi), но возможны петли.

Транзитивным называется отношение, для которого , то есть если xPz и zPy, то xPy. По индукции как следствие получаем: если xPz₁,z₁Pz₂…,z_nPy, то xPy. В матрице B(P) транзитивного отношения для произвольных значений i, k справедливо соотношение:

.

В графе G(P) существует дуга (x,y) если существует путь из x в y.

С понятием транзитивного отношения тесно связанно понятие операция транзитивного замыкания. Для каждого отношения Р определим отношение , как минимальное транзитивное отношение, в состав которого входит Р. Такое отношение определяется однозначно, как , где n=card(A), A – носитель Р, card(A) – мощность множества А.

Ацикличным называется отношение Р, для которого для произвольного k. Для ацикличного отношения , то есть если в графе G(P) ацикличного отношения вершины x и y соединены путем, то в нем нет дуги (y,x).

Ацикличность и транзитивность – это важные свойства с точки зрения теории принятия решений, так как отображают определенные природные связи между объектами. Если x лучше в определенном смысле чем y, а y лучше z, то в этом случае естественно полагать, что x лучше z (транзитивность), и минимум z не лучше x (ацикличность).

Связным отношением называется отношение Р, для которого , где - обратное отношение, U – полное отношение, Е – диагональное отношение. Это означает, что для произвольных x, yÎ А, x¹y где А – носитель Р или (x,y) Î P или (y,x) Î P. В матрице В(Р) хотя бы один из элементов b_ij, b_ji равен единице, а граф G(P) – связанный.

Утверждения:

- Отношение Р симметрично лишь тогда, когда ;

- Если отношение Р асимметрично, то оно антирефлексивно;

- Если отношения Р и Q симметричны, то симметричны и отношения Р Q P Q;

- Композиция симметричных отношений Р и Q является симметричной, если выполняется необходимое и достаточное условие коммутативности ;

- Обратное к транзитивному отношению Р отношение является транзитивным;

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

- Если два отношения транзитивны и одно транзитивно относительного другого, то объединение этих отношений является транзитивным;

- Пусть Р – транзитивное отношение. Тогда его симметричная составляющая Р_S- транзитивна; его асимметричная составляющая Р_А транзитивна; Р_А транзитивна относительно Р_S;

- Симметричная составляющая отношения квазипорядка является отношением эквивалентности;

- Отношение Р является ацикличным только тогда, когда его отношение достижимости антисимметрично, то есть когда - отношение порядка;

- Если граф линейного отношения не имеет контуров, то оно транзитивно.

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

Толерантностью (I) (равнодушием) называется отношение Р которое одновременно является рефлексивным и симметричным.

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

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

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

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

Линейным (полным) порядком является отношение Р, которое одновременно рефлексивно, антисимметрично, транзитивно и связное.

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

Другими словами, достижимость

где Е- диагональное отношение, А – носитель отношения. Матрица достижимости имеет единицы на главной диагонали, а граф соответственно – петли при каждой вершине, потому что каждая вершина графа достижима сама из себя, то есть достижимость всегда рефлексивна в отличии от транзитивного замыкания. Отношение достижимости Р отображает существование пути в графе G(P), то есть a b (где a,bÎА) только тогда, когда существует путь из вершины а в вершину b в графе G(P) отношения Р.

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

Таким образом a b лишь тогда, когда найдется путь в графе G(P) отношения Р как с вершины а в вершину b, так и из b в а, то есть а и b входят в состав контура в графе G(P).

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

Элементы множества носителя агрегированного отношения А_D в этом случае можно рассматривать как подмножество (или классы) множества носителя А первоначального отношения, которые создают ее разбиение. Таким образом, если

и для любых i, j, i¹j, A_i A_j = Æ.

Отношение Р_D с носителем А_D определенное через первоначальное отношение Р с носителем А следующим образом

,

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

Таким образом А_i и А_j находятся в отношении Р_D лишь тогда , когда найдется хотя бы одна пара элементов, которая принадлежит к каждому из этих подмножеств (или к каждому из этих классов), которые находятся в отношении Р.

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

Согласно определения эквивалентности существует однозначное соответствие между определенными отношениями эквивалентности D и разбитием А на классы- подмножества .

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

- Свойство рефлексивности сохраняется при факторизации;

- Свойство симметричности сохраняется при факторизации;

- (Достаточное условие сохранения транзитивности фактор отношения) Свойства транзитивности сохраняется при факторизации транзитивного отношения по имеющимся первоначальному отношению отношения эквивалентности;

- Необходимым и достаточным условием транзитивности отношения Р_D при факторизации произвольного бинарного отношения Р по произвольной эквивалентности D, которые имеют общего носителя А, является выполнение условия

;

- Свойство линейности сохраняется при факторизации;

- Факторизация отношения квазипорядка по его симметричной составляющей является отношением порядка;

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

- Если Р – линейное отношение с носителем А, то фактор отношение , полученное из Р путем факторизации его по отношениям взаимной достижимости, является линейным отношением порядка с носителем .

Таким образом факторизация произвольного отношения по отношению его взаимной достижимости приводит к фактор отношению, в котором контуры отсутствуют, то есть в процессе такой факторизации происходит «стягивание» контуров первоначального бинарного отношения. Факторизация по сути соответствует процедуре агрегирования системы преимуществ ЛПР, что позволяет исследовать общие свойства системы преимуществ и откорректировать полученное отношение.