Теоретический материал к заданию № 3.

Бинарные отношения

 

1. Бинарные отношения и операции над ними

 

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

А₁´А₂´... ´А_n={(а₁, а₂,..., а_n) | a_iÎA_i }.

Если все множества A_i совпадают A=А₁=А₂=... =А_n, то прямое произведение А₁´А₂´... ´А_n=Aⁿ называют прямой n-ой степенью множества А.

Бинарным отношением между элементами множеств А и В называется любое подмножество RÍA´B. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А.

Если (x, y)ÎR, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

Приведем примеры бинарных отношений.

Пусть A=B= R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение

R₁ = { (x, y) | x² + y² £1 }

определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение

R₂ = { (x, y) | x ³ y }

полуплоскость, а отношение

R₃= { (x, y) | |x-y| £ 1 }

полосу.

Диагональ множества A´A, т.е. множество D={(x,x) | xÎA}, называется единичным бинарным отношением или отношением равенства в A.

Областью определения бинарного отношения R называется множество

d_R={ xÎA | yÎB, (x, y) ÎR }.

Областью значений бинарного отношения R называется множество

r_R={ yÎB | xÎA, (x, y)ÎR }.

Образом множества X относительно отношения R называется множество

R(X) = { yÎB | xÎX, (x, y)ÎR };

прообразом X относительно R называется R ^-1(X).

В теории выбора и принятия решений большую роль играют бинарные отношения предпочтения, то есть такие отношения, согласно которым в паре (x, y)ÎR элемент x в каком-то смысле лучше чем y. Например:

- в смысле отношения R₂ "лучше" означает "больше или равно";

- в смысле отношения R₃ понятие "лучше" может означать "отстоит не больше чем на единицу".

Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R₁, R₂,...

1) Объединение двух бинарных отношений R₁ и R₂ - это отношение

R₁ÈR₂ = { (x, y) | (x, y)ÎR₁ или (x, y)ÎR₂ }.

2) Пересечение двух бинарных отношений R₁ и R₂ - это отношение

R₁ÇR₂ = { (x, y) | (x, y)ÎR₁ и (x, y)ÎR₂ }.

3) Обратное отношение R ^–1 = { (x, y) | (y, x)ÎR}.

4) Дополнение к отношению ={ (x, y) | (x, y)Î(A´A)\R}.

5) Двойственное отношение R^d = .

6) Композиция (суперпозиция) отношений R=R₁oR₂ содержит пару (x, y) тогда и только тогда, когда существует такое zÎA, что (x, y)ÎR₁ и (z, y)ÎR₂.

7) R₁ содержится в R₂ (R₁ Í R₂), если любая пара (x, y), которая принадлежит отношению R₁ также принадлежит и отношению R₂.

 

2. Свойства операций над отношениями.

 

Приведем здесь список основных свойств операций над отношениями и докажем некоторые из них.

1) Ç R_k ^-1=(Ç R_k) ^-1.

2) È R_k ^-1=(È R_k) ^-1.

3) (R₁ o R₂) ^-1 = R₁ ^-1o R₂ ^-1.

4) (R₁ o R₂ )oR₃ = R₁o(R₂ o R₃).

5) (R₁ È R₂ )oR₃ = (R₁ oR₃ )È(R₂o R₃ ).

6) (R₁ Ç R₂ )oR₃ Í (R₁ oR₃ )Ç(R₂o R₃ ).

7) а) если R₁Í R₂ то R₁o R₃ ÍR₂o R₃;

б) если R₁ Í R₂ то R₁^-1Í R₂^-1;

в) если R₁ Í R₂ то R₃oR₁ Í R₃oR₂.

8) a) (R₁È R₂)^d = R₁^d ÇR₂^d;

б) (R₁Ç R₂)^d = R₁^d ÈR₂^d;

в) (R ^d)^d = R.

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

Свойство 2.

Пусть пара (x, y)Î(È R_k) ^-1. Тогда (y, x)ÎÈ R_k. Это означает, что найдется отношение R_j, что (y, x)Î R_j. Отсюда, по определению обратного отношения, (x, y)ÎR_j^-1, а значит, (x, y)ÎÈR_k^-1и (ÈR_k)^-1 Í È R_k^-1.

Докажем обратное включение.Пусть (x,y)Î R_k^-1 Это означает, что найдется такое множество R_j, что (x,y)ÎR_j^-1. Следовательно, (y, x)ÎR_j и (y, x)Î ÈR_k,поэтому (x, y)Î(È R_k)^-1. Значит, È R_k^-1 Í (ÈR_k)^-1.

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

Свойство 6.

Пусть (x, y)Î(R₁ ÇR₂)oR₃. По определению композиции это означает, что найдется такое zÎA, что (x, z)Î(R₁ÇR₂) и (z, y)ÎR₃.

Первое включение возможно только тогда, когда одновременно выполнено (x, z)ÎR₁ и (x, z)ÎR₂. Это, в свою очередь означает, с учетом (z, y)ÎR₃, что одновременно (x, y)ÎR₁oR₃ и (x, y)ÎR₂oR₃, а, следовательно, (x, y)Î(R₁oR₃)Ç(R₂oR₃), что и доказывает требуемое соотношение.

ЗАМЕЧАНИЕ. Покажем, почему неверно обратное включение. Пусть (x, y)Î(R₁oR₃)Ç(R₂oR₃), тогда (x, y) Î(R₁oR₃) и (x, y) Î(R₂oR₃). Первое включение означает существование такого элемента z₁ из A, что (x, z₁)ÎR₁ и (z₁, y)ÎR₃, второе - существование такого z₂ÎA, что (x, z₂)ÎR₂ и (z₂, y)ÎR₃, причем необязательно z₁=z₂. Значит, не всегда существует такой элемент z, что (x, z)ÎR₁ и (x, z)ÎR₂, а, следовательно, не будет принадлежности пересечению R₁ и R₂.

Свойство 7б.

Возьмём любую пару (x, y)ÎR₁, что эквивалентно (y, х)Î ÎR₁^-1. Пусть теперь R₁ÍR₂, т.е. из (x, y)ÎR₁ следует (x, y)ÎR₂. Перейдя к обратным отношениям, получим, что из (y, х)ÎR₁^-1 вытекает (y, х)ÎR₂^-1, что и означает требуемое свойство.

Свойство 8а.

Докажем предварительно равенство (`R)<sup>-1</sup>=`R^-1

Пусть (x, y)Î(`R)<sup>-1</sup>. Следовательно, (y, x) Î`R или другими словами (y, x)ÏR. Отсюда, (x, y)Ï R^-1, что означает и (x, y)Î`R<sup>-1</sup>. Если же (x, y) Î`R^-1, то (x, y)ÏR^-1 и (y, x)ÏR. Тогда (y, x)Î`R или, что то же самое, (x,y)Î(`R)^-1.

Для доказательства свойства 8а воспользуемся доказанным равенством и известными свойствами операций над множествами и отношениями.

________­­_ _______

(R₁ÈR₂)^d = (R₁ÈR₂)^-1 = (R₁ÈR₂)^-1 =

 

=(`R<sub>1</sub>Ç`R₂) =`R<sub>1</sub><sup>-1</sup> Ç `R₂^-1 = R₁^d Ç R₂^d.

 

3. Способы задания бинарных отношений

 

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

1. Матричное задание. Оно используется когда А – конечное множество А={x_i}. Тогда отношение R можно задавать с помощью матрицы R={x_ij}, элементы которой определяются соотношением:

 

2. Задание с помощью графа.

Для конечного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x_i, а наличие дуги, соединяющей вершины x_i и x_j, означает, что (x_i,x_j)ÎR. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.

Основные свойства графа.

1) Г(R^-1) получается из Г(R) изменением направления стрелок на противоположные.

2) Граф Г(А´А) содержит дуги, соединяющие любую пару (x_i, x_j). Такой граф назывыется полным.

3. Задание верхними и нижними срезами.

Этот способ может быть использован для любых множеств и отношений. Пусть на множестве А задано отношение R. Верхний срез G_R (x) отношения R в точке x ÎА - это множество элементов yÎА таких, что (y, x)ÎR, т.е.

 

G_R(x) = { yÎA | (y, x)ÎR }.

 

Если рассматривать R как отношение предпочтения, то G_R (x) – это множество элементов, лучших чем х.

Нижний срез H_R(x) отношения R в точке xÎА - это множество элементов yÎА, таких, что (x, y)ÎR, т.е.

 

H_R(x) = { yÎA | (x, y)ÎR }.

 

Свойства нижних и верхних срезов.

Для любого хÎA и любого отношения R_i ÍA´A выполняются соотношения.

 

1. а) G_RÇR(x)=G_R(x)ÇG_R(x); б) H_RÇR(x)=H_R(x)ÇH_R(x)

2. a) G_{`R</sub>(x) = A\G<sub>R</sub>(x); б)H<sub>`R}(x) = A\H_R(x).

 

3. a) G_R^-1(x) = H_R(x); б) H_R^-1(x) = H_R(x).

 

4. G_A´A(x) = H_A´A(x) = A.

 

 

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

1) Рефлексивность.

Отношение R называется рефлексивным, если (х, х)ÎR для любого хÎA.

Примеры рефлексивных отношений: отношения "³", "£" на множестве R.

2) Антирефлексивность.

Отношение R называется антирефлексивным, если (х, х)ÏR для любого хÎA.

Примеры антирефлексивных отношений: отношения "<", ">" на множестве R.

Если R - антирефлексивное отношение, то xÏG_R(x) и хÏH_R(x)

для любого хÎA.

3) Симметричность.

Отношение R называется симметричным, если для любых x,yÎA из того, что (x, y)ÎR следует (y, x)ÎR и обратно.

Примеры симметричных отношений: отношения "=" и "¹".

Если отношение R симметрично, то для любого хÎA

а) G_R(x) = H_R(x); б) R = R^-1.

4) Антисимметричность.

Отношение R называется антисимметричным, если для любых x и y из A из одновременного выполнения условий (x, y)ÎR и (y, x)ÎR следует, что x = y.

Пример антисимметричного отношения. Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным.

Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y)ÎR означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x)ÎR - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоихвключений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y.

Отношение "³" также антисимметрично: если x³y и y³x, то x=y.

5) Асимметричность.

Отношение R асимметрично, если RÇ R^-1= Æ, т.е. пересечение

отношения R с обратным отношением пусто.

Эквивалентное определение асимметричности: из двух отношений (x, y)ÎR и (y, x)ÎR одно не выполняется.

Примеры асимметричных отношений: ">", "<", "быть начальником". Если R - асимметричное отношение, то из xRy следует yRx.

Для любого отношения R вводятся понятия симметричной части отношения R^s =R ÇR^-1 и асимметричной части отношения R^a = R \ R^s. Если отношение R симметрично, то R= R^s, если отношение R асимметрично, то R= R^a.

Примеры. Если R - "³", то R^-1 - "<", R^s - "=", R^a - ">".

6) Транзитивность.

Отношение R транзитивно, если для любыx x, y, zÎA из того, что (x, y)ÎR и (y, z)ÎR следует (x, z)ÎR.

Свойства транзитивного отношения:

а) RoRÍR;

б) для любого хÎA из yÎG_R(x) следует, что G_R(y)ÍG_R(x).

Нетранзитивным является отношение "¹". Пусть x=2, y=3, z=2, тогда справедливо x¹y и y¹z, но x=z, т.е. (x, z)ÏR.

Отношение R₁ называется транзитивным относительно отношения R₂, если:

а) из (x, y)Î R₁ и (y, x)Î R₂ следует, что (x, z)Î R₁;

б) из (x, y)Î R₂ и (y, x)Î R₁ следует, что (x, z)Î R₁.

7) Негатранзитивность.

Отношение R называется негатранзитивным, если`R транзитивно.

Примеры.

Отношения R₁ - ">" и R₂ - " ¹" негатранзитивны, так как отношения`R<sub>1</sub> - "£",`R₂ - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R₁ одновременно транзитивно и негатранзитивно, а R₂ , как известно, транзитивным не является.

8) Полнота.

Отношение R полно, если для любых x,yÎА либо (x, y)ÎR, либо (y, x)ÎR, либо оба отношения выполняются одновременно.

Свойства полных отношений:

а) G_R(x)ÈH_R(x) = А для любого хÎA;

б) полное отношение рефлексивно.

9) Слабая полнота.

Отношение R называется слабо полным, если для любых х¹y из А или (x, y)ÎR, или (y, x)ÎR.

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

10) Ацикличность.

Бинарное отношение R ациклично, если Rⁿ ÇR^-1= Æ для любого nÎ N. Иными словами, если из любой конечной цепочки отношений хRу, уRt,..., vRz следует, что z¹х, то отношение R ациклично.

 

9. Пусть отношения R₁, R₂ - симметричны. Доказать, что для того чтобы R₁oR₂ было симметрично необходимо и достаточно, чтобы выполнялось равенство R₁oR₂ = R₂oR₁.

 

5. Связи между бинарными отношениями.

 

1. Отношение R симметрично тогда и только тогда, когда R = R^-1.

2. Если R рефлексивно, то R^d антирефлексивно, если R антирефлексивно, то R^d рефлексивно.

3. Отношение R слабо полно тогда и только тогда, когда R^d антисимметрично.

ДОКАЗАТЕЛЬСТВО. Пусть R слабо полно и x¹y. Рассмотрим три случая.

1) (x, y)ÎR.Тогда, по определению обратного отношения

(y,x)ÎR^-1, а по определению двойственного отношения - (y,x)ÏR^d.

2) (y,x)ÎR, тогда (x, y)ÎR^-1 и, следовательно, (x,y)Ï`R^-1 = R^d.

3) (x, y)ÎR и одновременно (y, x)ÎR. Отсюда, (y, х)ÏR^d и

(x, y)Ï R^d.

Так как R - слабо полное отношение, то для любых x¹y выполняется либо случай а), либо б), либо в). Ни в одном из этих случаев включения (x, y)ÎR^d и (y, x)ÎR^d не могут выполняться одновременно. Следовательно, отношение R^d антисимметрично.

Докажем, что из антисимметричности R^d следует слабая полнота отношения R. Рассмотрим эквивалентное определение антисимметричности. Если x¹y, то либо (x,y)ÎR^d и (y,x)Ï R^d, либо (x,y)ÏR^d и (y,x)ÎR^d, либо (x,y)ÏR^dи (y,x)ÏR^d. В первом случае получим, что (x,y)ÎR, во втором - (y,x)ÎR, в третьем - (x,y)ÎR и (y,x)ÎR. Это утверждение означает, что отношение R слабо полно.

4. Отношение R асимметрично тогда и только тогда, когда R^d полно.

ДОКАЗАТЕЛЬСТВО. Пусть R - асимметрично. Тогда по определению, RÇR^-1 = Æ. Рассмотрим два случая.

1) (x, y)ÎR. Тогда (х, y)ÏR^-1, значит, (x, y)ÎR^d.

2) (x, y)ÏR. Тогда (x, y)Î`R и (y, x) Î`R^-1 = R^d.

В любом случае либо (x, y)ÎR^d, либо (y, x)ÎR^d, а это означает, что R^d - полно.

Докажем обратное следствие. Пусть R^d полно. Снова рассмотрим два случая:

а) (x, y)ÎR^d, тогда (y, x)ÏR;

б) (y, x)ÎR^d, тогда (x, y)ÏR.

Так как R^d полно, то либо случай а), либо случай б) всегда будет иметь место, а отсюда следует невозможность одновременного выполнения yRx и xRy. Это означает, что R асимметрично.

Примеры решений задания № 3.

Пример 1.

Доказать, что если отношения R₁, R₂ рефлексивны, то справедливо включение R₁ÈR₂ Í R₁oR₂ .

 

Доказательство.

Пусть (x, y)ÎR₁ÈR₂, тогда (x, y)ÎR₁ или (x, y)ÎR₂. В первом случае из рефлексивности R₂ следует (y, y)ÎR₂ и, следовательно, (x, y)Î R₁oR₂. Аналогично для второго случая получим (x, x)ÎR₁ и (x, y)ÎR₁oR₂, что и требовалось доказать.

 

Пример 2.

Доказать, что отношения RÈ(`RÇR<sup>d</sup>)=RÈ(`R)^s полны.

 

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

RÈ(`R Ç R<sup>d</sup> ) = RÈ(`R Ç`R<sup>-1</sup>) = RÈ(`RÇ(`R)<sup>-1</sup>) = =RÈ(`R)^s.

Покажем теперь, что отношение RÈ(`R)^s полно. Для любых x, yÎA возможен один из трех случаев:

1) (x, y)ÎR;

2) (y, x)ÎR;

3) (x, y)ÏR и (y, x)ÏR.

В первых двух случаях принадлежность (x,y) к рассматриваемому отношению очевидна. Рассмотрим третий случай. Так как (x,y)Î`R и (x,y)Î R<sup>-1</sup>, то (x,y)Î(`R)^s. Следовательно, рассматриваемое отношение полно.

 

 

Варианты задания №1. Доказать соотношение.

0. AÇ(BÇC) = (AÇB)ÇC.

1. AÈ(BÈ C) = (AÈB)È C.

2. .

3. .

4. .

5. .

6. .

7. .

8. (AÈB) \ C = (A \ C) È (B \ C).

9. A \ (B Ç C) = (A \ B) È (A \ C).

 

Варианты задания №2.

0.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

1.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

2.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

3.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

4.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

5.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

6.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

7.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

8.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

9.

a). Определить проекции , если

б). Определить проекции множества векторов : , если

.

Определить проекции упорядоченного множества векторов : , если

.

г). Пусть Найти .

д). Сравнить векторные оценки множества

. Найти парето-оптимальные оценки.

 

 

Варианты задания №3.

0. Доказать, что если отношение R транзитивно, то R^-1 также является транзитивным.

1. Доказать, что из асимметричности отношения R следует асимметричность R^-1.

2. Доказать, что из антисимметричности отношения R следует антисимметричность R^-1.

3. Доказать, что из рефлексивности отношения R следует рефлексивность R ^-1.

4. Доказать, что для симметричности отношения R необходимо и достаточно, чтобы R^d было симметрично.

5. Доказать, что если отношения R₁ и R₂ рефлексивны, то рефлексивны отношения R₁ÈR₂ , R₁ÇR₂, R₁^-1.

6. Доказать, что если отношения R₁ и R₂ антирефлексивны, то антирефлексивны и отношения R₁ÈR₂, R₁ÇR₂, R₁^-1.

7. Доказать, что если отношения R₁ и R₂ симметричны, то симметричны отношения R₁ÈR₂, R₁ÇR₂, R₁^-1.

8. Доказать, что если отношения R₁ и R₂ антисимметричны, то антисимметричны также R₁ÇR₂ и R₁^-1.

9. Пусть отношения R₁, R₂ - симметричны. Доказать, что для того чтобы R₁oR₂ было симметрично необходимо и достаточно, чтобы выполнялось равенство R₁oR₂ = R₂oR₁.