Специальные бинарные отношения. Упорядочение и безразличие

Для бинарных отношений нет устоявшейся терминологии. В данном пособии использованы названия специальных бинарных отношений из [4].

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

Введем следующие отношения.

P_уп – отношение строгого упорядочения, обладающее свойством асимметричности.

I_уп – отношение безразличия. Это отношение исключает P^d_уп между двумя элементами, т.е.

x I_уп y Û (x`P<sub>уп</sub> у и y`P_уп x). (1)

Так как (x, y) и (y, x) не принадлежат P_уп, то нельзя сказать, что x лучше y, или x лучше y. Если воспользоваться понятием пересечения отношений, то I_уп можно также представить в виде

I_уп =`P_уп ÇP^d_уп. (2)

Покажем, что I_уп рефлексивно и симметрично.

Симметричность. Отношение xI_упy означает, что (x, y)ÏP_уп и (y, x)ÏP_уп. Отношение же yI_упx означает, что (y, x)ÏP_уп и (x, y)ÏP_уп. То есть, xI_упy и yI_упx абсолютно эквивалентны. Значит, I_уп симметрично.

Рефлексивность. Так как P_уп антирефлексивно, то (x, x)ÏP_уп и по определению (x, x)ÎI_уп. Значит, I_уп рефлексивно.

Можно дать другое определение отношения I_уп, как симметричного, рефлексивного отношения.

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

R_уп = P_уп È I_уп, (3)

которое называется нестрогим упорядочением.

Докажем, что R_уп полно.

ДОКАЗАТЕЛЬСТВО. Возьмем любую пару (x, y). Для нее возможны три случая:

а) (x, y)ÎP_уп; б) (y, x)ÎP_уп;

в) (x, y)ÏP_уп и (y, x)ÏP_уп, т.е. (x, y)ÎI_уп.

Если имеют место случаи а) или в), то, по свойству объединения, (x, y)ÎR_уп. Если выполняется б) или в), то (y, х)ÎR_уп. Иными словами, в любом случае либо пара (x, y), либо (y, x) принадлежит R_уп. Значит, R_уп полно.

Свойство полноты можно принять в качестве определение отношения R_уп.

Рассмотрим основные свойства отношений P_уп и R_уп.

1. а) P_уп È P^d_уп = P^d_уп ;

б) P_уп Ç P^d_уп = P_уп ; в) I =`P_уп Ç P^d_уп ._.

ДОКАЗАТЕЛЬСТВО.

Докажем свойства а) и б). Пусть (x, y)ÎP_уп. Тогда, в силу ас-симметричности, (y, x)ÏP_уп, а значит, (x, y)ÎP^d_уп по определению двойственного отношения. Таким образом, из (x, y)ÎP_уп следует (x, y)ÎP^d_уп, а это означает, что P_уп Í P^d_уп. Тогда, по свойствам объединения и пересечения множеств, P_уп È P^d_уп = P^d_уп , a P_уп = = P^d_уп Ç P_уп, что и требовалось доказать.

Докажем свойство в). Пусть (x, y)ÎI_уп. Тогда, по определению I_уп, будем иметь

(x, y) Î`P<sub>уп</sub> и (y, x) Î`P_уп.

Второе соотношение эквивалентно тому, что (x, y)ÎP^d_уп. Следова-

тельно, из (x, y)ÎI_уп вытекает, что (x, y)ÎP^d_уп и (x,y) Î`P<sub>уп</sub> , т.е. (x, y) Î`P_уп Ç P^d_уп и I_уп Í`P Ç P^d_уп.

Докажем обратное включение. Ход рассуждений представим в виде схемы:

,

Что и требовалось доказать.

2. R_уп = P^d_уп; P_уп = R^d_уп , т.е. P_уп и R_уп образуют двойственную пару.

ДОКАЗАТЕЛЬСТВО. По определению R_уп = P_уп È I_уп. Воспользуемся представлением (2) отношения безразличия I_уп. Тогда

R_уп = P_уп È (`P<sub>уп</sub> Ç P<sup>d</sup><sub>уп</sub> ) = (P<sub>уп</sub> È`P_уп) Ç (P_уп È P^d_уп).

Так как (P_уп È`P_уп) = А´А, то R_уп = P_уп È P^d_уп, а по свойству 1а)

R_уп = P^d_уп.

Второе равенство непосредственно вытекает из свойства 8в п.2 для произвольного отношения R. При R = P_уп получим R^d_уп = = (P^d_уп)^d = P_уп.

Слабый порядок

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

ОПРЕДЕЛЕНИЕ. Асимметричное, негатранзитивное отношение P_сл назовем слабым порядком.

Кроме того, по аналогии с I_уп введем отношение I_сл

xI_слy Û ((x, y) Î`P<sub>сл</sub> и (y, x) Î`P_сл)

или

xI_слy Û ((y, x)ÏP_сл и (x, y)ÏP_сл).

Назовем его отношением эквивалентности. Введем также отношение

R_сл = P_сл È I_сл,

называемое нестрогим слабым порядком. Из определения следует, что P_сл Í P_уп . Так как P_уп только асимметрично, а P_сл асимметрично и негатранзитивно, то из (x, y)ÎP_сл всегда следует

(x, y)ÎP_уп.

В качестве примера R_сл можно привести отношение "³".

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

1) R_сл = P^d_сл , R^d_сл = P_сл.

2) I_сл = R^s_сл , P_сл = R^a_сл.

3) Для любых x, yÎA выполняется одно и только одно из соотношений: xP_слy, yP_слx, xI_слy.

4) Отношение P_сл транзитивно.

5) Отношение I_сл рефлексивно, симметрично, транзитивно.

6) Отношение R_сл транзитивно и полно.

Докажем транзитивность P_сл.

Пусть xP_слy и yP_слz, тогда в силу асимметричности P_сл y x и z y. Предположим противное, что x z, тогда в силу негатранзитивности из x z и z y следует x y, что противоречит условию. Следовательно, xP_слz, т.е. P_сл – транзитивно.

Докажем свойство 5).

Ранее, в п.6, было доказано, что I_уп рефлексивно и симметрично. Аналогично доказывается рефлексивность и симметричность I_сл. Поэтому остается доказать транзитивность I_сл.

Пусть x, y, zÎA таковы, что xI_слy и yI_слz, покажем, что (x, z)ÎI_сл. По определению I_сл, отношение xI_слy эквивалентно выполнению условий (x, y)ÏP_сл и (y, x)ÏP_сл, а отношение yI_слz – (y, z)ÏP_сл и (z, y)ÏP_сл. В силу негатранзитивности P_сл получим, что (x, z)ÏP_сл и (z, x)ÏP_сл. Следовательно, (x, z)ÎI_сл по определе-нию I_сл.

ЗАМЕЧАНИЕ. Свойства рефлексивности, симметричности и транзитивности считают определяющими свойствами отношения эквивалентности.

Разбиение и эквивалентность

ОПРЕДЕЛЕНИЕ. Система (конечная или бесконечная) непустых подмножеств А₁, А₂,..., А_n... множества А называется разбиением, если:

1) объединение множеств А_i образуют все A (т.е. ÈА_i=А);

2) множества А_i попарно не пересекаются (т.е. для любых i¹j

справедливо А_i Ç A_j = Æ).

ТЕОРЕМА о разбиении. Отношение I ÌА´А, будет отношением эквивалентности тогда и только тогда, когда существует разбиение А₁, А₂,..., А_n,... множества А, что из xIy следует существование такого А_i, что x, yÎА_i.

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

ДОКАЗАТЕЛЬСТВО. Предположим, что I – отношение эквивалентности, т.е. оно является рефлексивным, симметричным, транзитивным. Наша задача – построить такое разбиение, чтобы между элементами каждого класса выполнялось отношение I. Введем для каждого xÎА множество В_x, состоящее из элементов эквивалентных х, т.е. В_x = {zÎA | xIz }.

Покажем, что два множества B_x и B_y либо совпадают, либо не пересекаются. Пусть zÎB_x Ç B_y. Это означает, что одновременно zIx и zIy. Тогда, в силу симметричности и транзитивности, получаем xIy. Пусть теперь v – произвольный элемент из B_x, т.е. выполнено отношение vIx. Тогда, вследствие транзитивности отношения I и соотношения xIy, получим vIy, т.е. vÎB_y. Точно также можно доказать, что если vÎB_y, то vÎB_x. Это означает, что всякий элемент v из B_x одновременно принадлежит и B_y и наоборот. Следовательно, два множества B_x и B_y, имеющие хотя бы один общий элемент, совпадают между собой.

Наконец, в силу того, что множества B_x построены для всех элементов х из A, и, в силу рефлексивности I, элемент х принадлежит своему множеству B_x, их объединение включает в себя все множество A. Это означает, что система {B_x} образует разбиение A, т.е. в одну сторону теорема доказана.

Докажем обратное. Пусть имеем разбиение множества А на непересекающиеся классы. Определим отношение I следующим образом: элемент x находится с элементом y в отношении I тогда и только тогда, когда они оба принадлежат одному классу. Тогда это отношение обладает свойством рефлексивности, т.к. сам элемент х принадлежит классу, элементом которого является.

Обладает отношение I и свойством симметричности, т.к. если x и y принадлежат какому-то классу, то это же можно сказать и про y и x.

Наконец, если имеют место отношения xIy и yIz, то это значит, что x, yÎB и y, zÎB, где B – какой-то класс. Таким образом, x, zÎB, т.е. между x и z установлено отношение I. Следовательно, I обладает транзитивностью. Значит, I – отношение эквивалент-ности. Теорема доказана и в другую сторону.

Качественный порядок

Дополним отношение строгого упорядочения P_уп свойством транзитивности. Назовем полученное отношение качественным порядком P_кач. Рассмотрим два примера такого отношения.

1) Пусть х, у – вещественные числа. Введем качественный порядок следующим соотношением:

хР_качу Û x > у + 1.

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

х`Р_кач у <=> х £ у + 1

Положим у = 0; х = 0.9; z = – 0.9. Тогда, очевидно, выполняются отношения (х, y) Î`Р<sub>кач</sub> ; (y, z) Î`Р_кач ; (х, z) Ï Р_кач.

Т.е. условие негатранзитивности не выполняется.

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

2) Введем на множестве точек n-мерного евклидова пространства следующее отношение Par, называемое отношением Парето:

х, уÎРаr Û " i: х_i ³ y_i и $ j: х_j > у_j.

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

 

а) x₁ < y₁ б) x₁ > y₁ в) x₁ < y₁

x₂ > y₂ x₂ = y₂ x₂ < y₂

нет отношения Раr; есть отношение Раr, есть отношение Раr,

x лучше y; y лучше x.

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

Также как и для P_уп и P_сл, на основе P_кач можно построить

производные от него отношения:

I_кач - отношение качественного безразличия;

хI_качу Û (x`Р<sub>кач</sub> у) и (у`Р_кач х);

R_кач – нестрогий качественный порядок R_кач = Р^d _кач.

Качественный порядок также называют в литературе частичным порядком. Понятия же нестрого качественного и нестрого частичного порядков различны.

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

Отношение R_част называется нестрогим частичным порядком, если оно рефлексивно, транзитивно и антисимметрично. Нестрогий частичный порядок можно определить по формуле R_част = P_кач È D.

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

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

	Рефл.	Антирефл.	Симм.	Асимм.	Анти-симм.	Транз.	Нега-транз.	Полн.	Ацикл.
Pуп		+		Å
Iуп	Å		Å
Rуп	+							Å
Pсл		+		Å		+	Å		+
Iсл	Å		Å			Å
Rсл	+					Å	+	Å
Pкач		+		Å		Å			+
Rкач	+						Å	Å
Rчаст	Å				Å	Å

В предлагаемой таблице использованы следующие обозначения:

Å – данным свойством отношение обладает по определению;

+ – это свойство вытекает из определения.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Доказать: а) I_уп È P_уп È P^–1 _уп = A´A;

б) I_уп = R^s_уп; P_уп = R^a_уп.

2. Доказать свойства 1), 2), 3), 6) отношения слабого порядка и производных от него отношений.

3. Доказать следующие свойства:

а) R_кач – полное негатранзитивное отношение;

б) отношение, не различающее близко расположенные точки

(т.е. xRy, если х ³ у – 1) является качественным порядком;

в) R_кач не является транзитивным, а, следовательно, R_кач ¹ R_сл ;

г) I_кач – рефлексивно, симметрично, но не всегда транзитивно;

д) I_кач = R^s_кач и R^d_кач = Р_кач.

4. Какие из следующих отношений являются отношениями эквивалентности:

а) равенства двух чисел;

б) подобия двух треугольников;

в) порядка на вещественной прямой;

г) линейной зависимости в пространстве Rⁿ (n > 1);

д) параллельности прямых на плоскости;

е) перпендикулярности прямых на плоскости.

5. Доказать, что если отношение R транзитивно и симметрично и d_R È r_R = A, то R – отношение эквивалентности.

6*. Доказать, что композиция эквивалентностей R₁ и R₂ является отношением эквивалентности тогда и только тогда, когда R₁ o R₂ = R₂ o R₁.

Доказать, что R является отношением эквивалентности (7–11).

7. R = { (a, b) | a, bÎ N ´ N, a₁ + b₂ = b₁ + a₂}.

8. R = { (a, b) | a, bÎ N, a – b делится на m }.

9. R = { (a, b) | a, bÎ N ´ N, a₁b₂ = a₂b₁ , если a₂b₂ ¹ 0,

a₁= b₁, если a₂b₂ = 0 }.

10. R = { (a, b) | a, bÎ R, a – bÎ Q }.

11. R={ (x, y) | x, yÎ R, f(x) = f(y) }, функция f – фиксирована.

12. Доказать, что следующие отношения являются эквивалентностями. Построить для них фактор-множества.

а) R = { (x, y) | x, yÎ R ³, x₁² +x₂² +x₃² = y₁² +y₂² +y₃² };

б) R = { (x, y) | x, yÎ R ², x₁ = y₁ };

в) R = { (x, y) | x, yÎ R ² , x₂ = y₂ };

г) R = { (x, y) | x, yÎ R, x – [x] = y – [y] }.

13. Доказать, что R является отношением эквивалентности тогда и только тогда, когда (R o R^–1) È D = R.

14. Доказать, что если R – отношение эквивалентности, то и обратное отношение также является отношением эквивалентности.

15. Пусть R₁ и R₂ – отношения эквивалентности. Доказать, что

а) R₁ o R₁ = A² Û R₁ = A²;

б) R₁ o R₂ = A² Û R₂ o R₁ = A².

16. Доказать, что объединение R₁ È R₂ эквивалентностей R₁ и R₂ является эквивалентностью тогда и только тогда, когда R₁ È R₂ = R₁ o R₂.

17. Доказать, что отношение R на множестве A является одновременно эквивалентностью и частичным порядком в том и только в том случае, когда`R = D.

18. Показать, что следующие отношения являются частичным порядком:

а) A Ì B в универсальном множестве S;

б) x(t) £ y(t) для любого t в пространстве C[a,b];

в) m делит n на множестве N.

19*. Пусть отображение j: A´A®A обладает свойствами:

а) j(x, y) = j(y, x);

б) j(x, j(y, z)) = j(j(x, y), z);

в) j(x, x) = x.

Доказать, что отношение R={ (x, y) | j(x, y) = x } является частичным порядком.

20. Пусть функции f₁ и f₂ определены на [0,1]. Будем говорить, что f₁Rf₂, если .

Показать, что R – отношение частичного порядка.

21. Пусть множества X, Y – частично упорядочены. Введем на X´Y отношение: (x₁, y₁) ³ (x₂, y₂), если x₁ ³ x₂, y₁ ³ y₂. Доказать, что это отношение является частичным порядком.

22. Доказать, что если R – частичный порядок, то R^-1 также частичный порядок.

23. Доказать, что отношение R на множестве A есть предпорядок тогда и только тогда, когда R = (R o R) È D.

Примеры решения

Задача 6.

1) Пусть R₁, R₂ и R₁ o R₂ - отношения эквивалентности. Докажем, что R₁ o R₂ = R₂ o R₁.

Пусть (x, y)ÎR₁ o R₂, так как R₁ o R₂ – отношение эквивалентности, то (y,x)ÎR₁ o R₂. Последнее означает, что существует такой элемент zÎA, что (y, z)ÎR₁ и (z, x)ÎR₂. Так как R₁ и R₂ – симметричны, то (x, z)ÎR₂ и (z, y)ÎR₁. Следовательно, (x, y)ÎR₂ o R₁. Обратное включение доказывается аналогично.

2) Пусть R₁ o R₂ = R₂ o R₁, покажем, что R₁ o R₂ является отношением эквивалентности.

Пусть x – произвольный элемент множества A. Так как R₁, R₂ рефлексивны, то (x, x)ÎR₁ и (x, x)ÎR₂, следовательно, (x,x)ÎR₁oR₂, т.е. отношение R₁ o R₂ – рефлексивно.

Докажем его симметричность. Пусть (x, y)ÎR₁oR₂, в силу равенства R₁ o R₂ = R₂ o R₁ получим (x, y)ÎR₂ o R₁, т.е. существует такой zÎA, что (x, z)ÎR₂, (z, y)ÎR₁. Из симметричности R₁ и R₂ следует, что (y, z)ÎR₁ и (z, x)ÎR₂. Следовательно, (y, x)ÎR₁ o R₂.

Для доказательства транзитивности достаточно показать, что (R₁ o R₂) o (R₁ o R₂) Í R₁ o R₂. Действительно,

(R₁ o R₂) o (R₁ o R₂) = R₁ o (R₂ o R₁) o R₂ = R₁ o (R₁ o R₂) o R₂ =

= (R₁ o R₁) o (R₂ o R₂) Í R₁ o R₂.

Задача 19.

Проверим выполнение свойств отношения частичного порядка. Так как j(x, x) = x, то (x, x)ÎR и отношение рефлексивно.

Пусть выполнены оба условия (x, y)ÎR и (y, x)ÎR, т.е. j(x,y)=x и j(y, x) = y. Тогда x = y, так как j(x, y) = j(y, x) по определению функции j. Следовательно, отношение антисимметрично.

Докажем его транзитивность. Пусть (x, y)ÎR и (y, z)ÎR, т.е. j(x, y) = x и j(y, z) = y. Тогда

j(x, z) = j(j(x, y), z) = j(x, j(y, z)) = j(x, y) = x.

Следовательно, (x,z)ÎR, что и требовалось доказать.

Нечеткие отношения. Основные понятия

Пусть Е = Е₁´Е₂´...´Е_n – прямое произведение универсальных множеств и М – некоторое множество принадлежностей (например М = [0,1]). Нечеткое n-арное отношение определяется как не-четкое подмножество R на E, принимающее свои значения в М. В случае n = 2 и М = [0, 1], нечетким отношением R между множествами X = Е₁ и Y = Е₂ будет называться функция R: (X,Y) ® [0, 1], которая ставит в соответствие каждой паре элементов (х, y)ÎX´Y величину m_R(x, y)Î[0, 1]. Обозначение: нечеткое отношение на X´Y запишется в виде: xÎX, yÎY: xRy. В случае, когда X = Y, т.е. X и Y совпадают, нечеткое отношение R: X´X ® [0,1] называется нечетким отношением на множестве X.

Примеры:

1. Пусть X = {x₁,x₂,x₃}, Y = {y₁,y₂,y₃,y₄}, М = [0, 1]. Нечеткое отношение R = X R Y может быть задано, к примеру, таблицей:

	y1	y2	y3	y4
x1			0,1	0,3
x2		0,8		0,7
x3		0,5	0,6

2. Пусть X = Y = (–¥, ¥), т.е. множество всех действительных чисел. Отношение x >> y (x много больше y) можно задать функцией принадлежности

3. Отношение R, для которого m_R(x, y) = , при достаточно больших k можно интерпретировать так: "x и y близкие друг к другу числа".

В случае конечных или счетных универсальных множеств очевидна интерпретация нечеткого отношения в виде нечеткого графа, в котором пара вершин (x_i, x_j) в случае X R X соединяется ребром с весом m_R(x_i, x_j), в случае X R Y пара вершин (x_i, y_j) сое-диняется ребром c весом m_R(x_i, y_j).

Примеры:

1. Пусть Х={x₁,x₂,x₃}, и задано нечеткое отношение R: X´X® [0, 1], представимое графом:

2. Пусть X={x₁,x₂} и Y={y₁,y₂,y₃}, тогда нечеткий граф вида:

 

задает нечеткое отношение X R Y.

Носителем нечеткого отношения R называется обычное множество упорядоченных пар (x, y), для которых функция принадлежности положительна:

S(R) = {(x, y): m_R(x, y) > 0}.

Пусть R₁ и R₂ – два нечетких отношения такие, что "(x, y)ÎX´Y: m_R1(x, y) £ m_R2(x, y), тогда говорят, что R₂ содержит R₁ или R₁ содержится в R₂. Обозначение: R₁ÍR₂.

Пример:

Отношения R₁, R₂ – отношения типа y>>x (y много больше x). При k₂ > k₁ отношение R₂ содержит R₁.