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

1
Глава 3. Бинарные отношения

3.1. Основные положения
Бинарным отношением R на множестве называется подмножество <R, > множества , < R, > ( 2).

Иными словами бинарное отношение R на множестве представляет собой подмножество упорядоченных пар множества . Множество называется областью задания отношения R. То, что некоторая упорядоченная пара (а,b) принадлежит отношению <R, > записывается (а,b) <R, > или a >b, а читается а находится в отношении R с b. Для упрощения записи, если ясно, на каком множестве задано отношение R, будем записывать (а,b) R или аRb . При необходиьости будем специально оговоривать, на каком множестве задано отношение.

Рассмотрим примеры бинарных отношений. Отношение «быть братом», заданное на множестве жильцов некорогодома может включать следующие пары «Александр брат Петра», «Василий брат Светланы», «Петр брат Александра» (отметим, что мы различаем первую и третью пару, так как в определении бинарного отношения речь идет имено об упорядоченных парах ). Отношение R «а знаком с b», заданное на следующих множествах : 1-множество студентов одной группы, 2-множество студентов курса, 3-множество студентов факультета. Естественно, определяются три различных отношения 1>, 2>, 3>. Очевидно, что второе отношение будет включать все пары, образующие первое отношение и еще некоторые пары из 22, а третье отношение, в свою очередь будет включать все пары из второго отношения и еще некоторые пары из 33.


Чтобы задать отношение R на множестве надо указать каким-либо способом те пары (a,b) , которые содержатся в R . Это можно выполнить следующими способами:

1. задание перечислением.

R= {(a,b), (b,c), (b,d),...}

2. задание матрице.

Пусть состоит из n элементов. Построим квадратную матрицу nn , обозначаемую А(R) = (aij (R)) по следующему правилу:

aij (R) =

3. задание графом.

Поставим во взаимно однозначное соответствие элементам множества вершины графа G. Элемент xi и соответствующую вершину графа будем обозначать одинаково. Граф G(R) отношения R содержит дугу, направленную от xi к xj тогда и только тогда, когда выполняется xi Rxj .

4. задание отношения с помощью общего свойства.

Данным способом мы уже пользовались, рассматривая примеры бинарных отношений. Тогда нами использовались свойства «быть братом», «быть знакомым». Формально задание отношения R свойством записывается следующим образом:

R=(x,y) | x,y  , [задаваемое свойство]}.

Например,

R= (x,y) | x,y N, [x делит y]},

где N-множество натуральных чисел.

5. задание с помощью сечений.

Верхним сечением R+(x) отношения > в точке x называется множество всех элементов y , находящихся с элементом x в отношении R.


R+(x)={ y  | (y,x) R}

Нижним сечением R(x) отношения > в точке x называется множество всех элементов y, с которыми элемент x находится в отношении R.

R(x)={ y  | (x,y) R}.

В общем случае отношение R полностью задано, если для каждого x  задано R+(x), или для каждого x  задано R(x).

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

Введем в рассмотрение бинарные отношения специального вида.

Пустое отношение. Отношение называется пустым, если оно не выполняется ни для одной пары (x,y)  . Как и пустое множество обозначается .

Матрица пустого отношения содержит только нули;

граф G() не имеет дуг;

R+(x) = R(x) = для х .

Полное отношение. Отношение называется полным (обозначается U ), если оно выполняется для всех пар (x,y) .

Матрица А(U)- такая, что аij(U) = 1 i,j ;

граф G(U)- полносвязный граф ;

R+(x) = R(x) = для х .


Диагональное отношение. Отношение называется диагональным (обозначается Е), если оно выполняется для всех пар (x,y) , состоящих из одинаковых элементов, т.е. хЕу, если х = у.

Матрица А(Е) такая, что

аij(Е) =

граф G(E) содержит только дуги-петли во всех вершинах;

R+(x) = R(x) = {x} х .

Антидиагональное отношение. Отношение называется антидиагональным (обозначается), если оно выполняется для всех пар (x,y), состоящих из несовпадающих элементов, т.е. ху, если ху.

Матрица А() такая, что

аij() =

граф G()- все дуги (xi ,xj) и не содержит дуг-петель;

R+(x) = R(x) = \ {x} х .
Операции над бинарными отношениями

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


Включение отношений. Отношение R1 вложено (включено) в отношение R2 (обозначается R1 R2), если множество пар, для которых выполнено отношение R1, содержится во множестве пар, для которых выполняется отношение R2. Выделим строгое включение R1 в R2, обозначив его R1 R2.

R1 R2, если R1 R2 и R1 R2.

Нетрудно убедиться, что для любого R выполняется RU.

Непосредственно из определения следует соотношение:

R1 R2  ( х,у   [x R1y x R2y]).

Если R1 R2, то

1. аij(R1) = аij(R2)

2. граф G(R1) является подграфом G(R2);

3. R1+(x) R2+(x) х ,

R1(x) R2(x) х .

Операция дополнения. Отношение называется дополнением отношения R, если оно выполняется для тех и только для тех пар, для которых не выполняется отношение R


2\R

Легко видеть, что

1. aij() =1- aij(R)

2. в графе G() присутствуют те и только те дуги, которых нет в графе G(R)

3.;

.

Очевидны соотношения: .
Операция пересечения. Пересечением отношений R1 и R2 (обозначается R1 R2) называется отношение, которое выполняется только для тех пар, для которых выполняется R1 и R2 одновременно

x R1  R2 y  xR1 y  x R2 y

Нетрудно убедиться в справедливости следующих соотношений:


  1. ;

  2. .

Операция объедения. Объединением отношений R1 и R2 (обозначается R1R2) называется отношение, которое выполняется только для тех пар, для которых выполняется хотя бы одно из отношений R1 или R2.


.

Справедливо:


  1. ;

  2. .

Операция обращения. Обратным к отношению R называется отношение R–1, определяемое условием :

  1. .

Справедливы следующие соотношения:

  1. ;

  1. граф G(R-1) получается из графа G(R) изменением направления дуг на противоположное;

  1. ;

.

4. ;

  1. .

Операция произведения (композиции). Обозначается R1R2 либо R1 R2 . Произведением отношений R1 и R2 называется отношение, определяемое следующим условием :

.

Справедливы следующие соотношения:
  1. ;


2.;

  1. ;

  2. в графе G(R1R2) присутствуют только те дуги, которыми можно замкнуть путь длиной 2, в котором первая дуга принадлежит G(R1) , а вторая - G(R2).

Частным случаем произведения отношений является квадрат R2 отношения R.

.

По индукции определяется n-я степень отношения R

.

Тот факт, что (x,y)Rn означает, что существует цепочка элементов x=x1,x2,x3,...,xn=y такая, что (xi,xi+1)R i=1,2,...,n-1.

Операция транзитивного замыкания. Обозначается или TC(R).Транзитивным замыканием отношения R называется отношение , определяемое следующим условием:


Таким образом, xy если существует такая цепочка Z из элементов , первым элементом которой является х, а последним - у, что между соседями в этой цепочке выполнено отношение R. В частности цепочка может состоять только из двух элементов: z1=x , z2=y , а значит , т.е. . Если цепочка состоит из трех элементов (n=2), то xRz , zRy , иначе говоря, xRRy. Если цепочка состоит из четырех элементов, то xRRRy. Продолжая это рассуждение, приходим к выводу, что тогда и только тогда, когда выполнено хотя бы одно из соотношений вида xRR...Ry или сокращено xRny , т.е.,




Таким образом, транзитивное замыкание отношения R есть объединение всех степеней этого отношения. Матричная иллюстрация этой операции не наглядна. В графе проводится дуга (xi,xj), если в графе G(R) существует какой-либо путь из вершины xi в xj . Таким образом, для построения на G(R) выделяются все пути и замыкаются непосредственно дугами.

Операция перехода к двойственному отношению
Двойственным к R является отношение Rd определяемое:



Т.е. Rd – отношение дополнительное обратному R (или обратное дополнительному).

Справедливы следующие соотношения:




  1. граф G(Rd) получается из полносвязного графа исключением всех дуг, обратных дугам G(R);








Операция редукции (взятия транзитивного остова). Обозначается Rr


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









Операция сужения. Отношение 1,1> называется сужением отношения > на множестве 1 , если 1 и R1=R21.

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

Граф G(R1) отношения 1,1> – это подграф графа G(R), порожденный множеством вершин 1.

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


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

Рефлексивность. Бинарное отношение R называется рефлексивным, если справедливо ER (напомним, что E – диагональное отношение). Иначе говоря, рефлексивное отношение всегда выполняется для одинаковых объектов, т.е.

В матрице A(R) рефлексивного отношения на главной диагонали всегда единицы, т.е. aij(R)=1 i=j, граф G(R) рефлексивного отношения содержит петли во всех вершинах. Для рефлексивного отношения выполняется:




Антирефлексивность. Отношение R называется антирефлексивным, если справедливо RE=. Антирефлексивное отношение может выполняться только для несовпадающих объектов. Таким образом, .

В матрице A(R) антирефлексивного отношения выполняется .

Граф G(R) не содержит петель. Для антирефлексивного отношения R выполняется .

Симметричность. Отношение R называется симметричным, если справедливо R=R-1, иначе говоря, для симметричного R имеет место xRyyRx.

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

Только при x=y=1 имеет место xRx.

В матрице A(R) симметричного отношения aij(R)=aij(R). Граф G(R) вместе с дугой (xi,xj) всегда содержат и дугу (xj,xi), т.е. симметричное отношение может быть задано неориентированным графом. Для симметричного отношения выполняется


Асимметричность. Отношение R называется асимметричным, если справедливо RR-1=, т.е. из двух выражений xRy и yRx по крайней мере одно не выполняется.


В матрице A(R) асимметричного отношения aij(R)aji(R)=0. Граф G(R) не может одновременно содержать дуг (xi,xj) и (xj,xi). Для асимметричного отношения выполняется:



Антисимметричность. Отношение R называется антисимметричным, если справедливо RR-1=. Таким образом, xRy и yRx могут быть справедливы одновременно лишь для x=y.

В матрице A(R) антисимметричного отношения aij(R)aji(R)=0 ij, граф G(R) не может одновременно содержать дуг (xi,xj) и (xj,xi) при ij. Для антисимметричного отношения выполняется:



Транзитивность. Отношение R называется транзитивным, если справедливо R2R, т.е. xRy,yRzxRz. По индукции получается:



В матрице A(R) транзитивного отношения


в графе G(R) всегда присутствуют дуги, соединяющие начало и конец каждого пути. Для транзитивного отношения выполняется:




Ацикличность. Отношение R называется ацикличным, если справедливо RkR-1= k, т.е.:

.

Граф G(R) не содержит контуров (циклов). Для ацикличного отношения выполняется:



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

Отрицательная транзитивность. Отношение R называется отрицательно транзитивным, если его дополнение , т.е. если справедливо:


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



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

(3.1)

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

(3.2)

Пусть вопреки (3.2) имеет место ситуация . В силу нашего исходного предположения , что противоречит предыдущему предположению.


Кроме приведенных свойств в теории принятия решений используются еще такие свойства как связность и слабая связность. Отношение R будем называть связным (совершенным, линейным), если x,y выполняется по крайней мере одно из соотношений xRy либо yRx, и слабосвязным, если x,y, xy выполняется xRy либо yRx. Заданное на множестве натуральных чисел отношение «» – связное, а отношение «>» – слабо связное.

Рассмотрим взаимное влияние приведенных свойств отношений.

Утверждение 3.2. Асимметрия отношения влечет его антирефлексивность. Докажем утверждение. Доказательство проведем от противного. Пусть x и xRx, значит имеет место xR-1x. Тогда xRR-1x, т.е. RR-1 не пусто, что противоречит асимметричности R.

Утверждение 3.3. Ацикличность влечет асимметрию. Утверждение доказывается от противного. Пусть R – ациклично и одновременно не асимметрично, тогда существуют x,y такие, что xRy и yRx, что противоречит ацикличности.

Утверждение 3.4. Асимметрия и отрицательная транзитивность влекут транзитивность. Докажем утверждение. Пусть R асимметрично и отрицательно транзитивно и имеет место xRy, yRz. Покажем, что в этом случае xRz.

В силу отрицательной транзитивности R справедливо

. (3.3)

В силу асимметричности R и нашего исходного предположения (yRz) ситуация zRy иметь место не может, т.е. (3.3) преобразуется: xRyxRz. И окончательно: xRy,yRzxRz, т.е. R–транзитивно.

Утверждение 3.5. Ацикличность и слабая связность влекут отрицательную транзитивность. Утверждение докажем от противного. Пусть R ациклично, слабо связно и вопреки отрицательной транзитивности имеет место ситуация для некоторых (3.4)


Из (3.4) следует, что (т.к. не может быть одновременно ). В силу слабой связности: .

И, окончательно, с учетом (3.4) имеем: , что противоречит ацикличности R.

Утверждение 3.6. Антирефлексивность и транзитивность влекут асимметричность. Докажем утверждение от противного.

Пусть R антирефлексивно, транзитивно и, вопреки утверждению , т.е. существуют x,y, такие, что xRyyRx. В силу транзитивности , что противоречит антирефлексивности.

Утверждение 3.7. Антирефлексивность и транзитивность влекут ацикличность. Докажем утверждение от противного. Пусть R антирефлексивно, транзитивно и вопреки утверждению существует цепочка Z={z1,...,zk} элементов множества такая, что xRz1, z1Rz2, ..., zkRx. Тогда в силу транзитивности R имеет место xRx, что противоречит антирефлексивности.

Утверждение 3.8. Антирефлексивность, транзитивность и слабая связность влекут отрицательную транзитивность. Докажем утверждение. Пусть R антирефлексивно, транзитивно, слабо связно. В силу утверждения 3.7. R ациклично; ацикличное слабосвязное отношение, в силу утверждения 3.4 отрицательно транзитивно.

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


Утверждение 3.9. Если отношения R1 и R2 рефлексивны, то рефлексивны и следующие отношения:



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

Утверждение 3.10. Если отношения R1 и R2 антирефлексивны, то антирефлексивны и следующие отношения:



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

Утверждение 3.11. Объединения рефлексивного отношения R1 с любым отношением R – рефлексивное отношение. Доказательство непосредственно вытекает из соответствующих определений.

Утверждение 3.12. Если отношения R1 и R2 симметричны, то симметричны и следующие отношения:


Докажем утверждение. Для любого R справедливо . С учетом того, что для симметричного R1 справедливо , имеем , т.е. отношение также симметрично.


Справедливо . В силу симметрии R1 и R2 . Тогда , т.е. отношение симметрично.

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

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

Утверждение 3.13. Транзитивное замыкание симметричного отношения R есть симметричное отношение.

Утверждение 3.14. Транзитивное замыкание рефлексивного отношения R есть рефлексивное отношение.

Утверждение 3.15. Если отношение R1 асимметрично, то:

а). асимметрично отношение ;

б). асимметрично пересечение R1R при любом R.

Утверждение 3.16. Если отношения R1 и R2 антисимметричны, то антисимметричны также и следующие отношения:


Утверждение 3.17. Если отношения R1 и R2 транзитивны, то транзитивны также и следующие отношения:

.

Заметим, что такие свойства как асимметричность, антисимметричность, транзитивность не инвариантны относительно операции объединения. Для всех введенных свойств имеет место инвариантность относительно операции сужения R на любое подмножество множества .

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