Какими свойствами обладают следующие бинарные отношения

Пусть $A$ и $B$ два конечных множества. Декартовым произведением множеств $A$ и $B$ называют множество $Atimes B,$состоящее из всех упорядоченных пар, где $ ain A, bin B. $

Бинарным отношением между элементами множества $A$ и $B$ называется любое подмножество $R$ множества $Atimes B$, то есть $ Rsubset Atimes B.$

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры $x$ и $y$ связаны бинарным отношением $R$, если пара $langle x,y rangle $ является элементом R, т.е. $langle x,y ranglein R. $

Высказывание: «предметы $x$ и $y$ связаны бинарным отношением $R$» записывают в виде $xRy.$Таким образом, $ xRyleftrightarrowlangle x,yranglein R.$

Если $Rsubset Atimes A $, то говорят, что бинарное отношение определено на множестве $A$.

Примеры бинарных отношений:

• на множестве целых чисел $Z$ отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
• на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
• на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

Областью определения бинарного отношения $R$ называется множество, состоящее из таких $x$, для которых $langle x,y ranglein R $ хотя бы для одного $y$.
Область определения бинарного отношения будем обозначать $ Re R$.
$Re R={ x|exists y(langle x,yranglein R)}$
Областью значений бинарного отношения $R$ называется множество, состоящее из таких $y$, для которых $langle x,y ranglein R $ хотя бы для одного $x$.
Область значений бинарного отношения будем обозначать $Im R$
$Im R={ y|exists x(langle x,yranglein R)}$

Инверсия (обратное отношение) $R$ — это множество ${langle x,yrangle |langle y,xranglein R}$ и обозначается, как ${R}^{-1}.$

Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество ${langle x,yrangle |exists zlangle xSzwedge zRyrangle}$ и обозначается, как $Rcirc S$.

Бинарное отношение $R$ на некотором множестве $M$ может обладать различными свойствами, например:

• Рефлексивность: $forall xin M(xRx)$
• Антирефлексивность (иррефлексивность): $forall xin Mneg (xRx)$
• Корефлексивность: $forall x,yin M(xRyRightarrow x=y)$
• Симметричность: $forall x,yin M(xRyRightarrow yRx)$
• Антисимметричность: $forall x,yin M(xRywedge yRxRightarrow x=y)$
• Асимметричность: $forall x,yin M(xRyRightarrowneg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
• Транзитивность: $forall x,y,zin M(xRywedge yRzRightarrow xRz)$
• Связность: $forall x,yin M(xneq yRightarrow xRylor yRx)$
• Рефлексивное транзитивное отношение называется отношением квазипорядка
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
• Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка

Над бинарными отношениями можно производить некоторые операции, точно так же, как и над множествами. Не ограничивая общности, будем считать, что следующие операции выполняются на множестве $M$.

• Пересечение. Пересечением двух бинарных отношений ($A$и $B$) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение $Acap B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны как первым, так и вторым отношением ($xAy$ и $xBy$).

  Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
  $ xAyLeftrightarrow xgeq y, xByLeftrightarrow xneq y$, тогда $Acap BLeftrightarrow x>y $

• Объединение. Объединением двух бинарных отношений ($A$ и $B$) является отношение, которое определяется объединением соответствующих подмножеств. Отношение $Acup B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны хотя бы одним из двух отношений хотя бы одно из отношений ($xAy$ или $xBy$).

  Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».

• Включение. Обозначается $Asubseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $Asubseteq B$, то $Aneq B$. Если $Asubseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.

Очевидно, для любого отношения $A varnothingsubseteq Asubseteq U$, где $varnothing$ — пустое, а $U$- полное отношение.

Приведём в пример два графических представления бинарных отношений на множстве $X = {a, b, c, d, e}.$
Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей ($Ox$ и $Oy$). На каждой оси нужно отметить точки которые являются элементами множества $X$.
Будем считать, что $a, b, c, d, e$ — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами $(x, y)$. На рисунке изображена совокупность точек, соответствующих следующему отношению: $R={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.$

Следующий способ, который мы рассмотрим, заключается в использовании ориентированных графов. Элементы множества $X$ становятся вершинами графа, а элементы $langle x,yrangle $ отношения $R$ ребрами, которые соединяют первый член $x$ отношения со вторым членом $y$. Граф, соответствующий бинарному отношению $R$, изображен на рисунке.

Задача

Бинарное отношение $R$ задано на множестве $A={1,2,3,4}$, определить его свойства.
$R={(1,1),(1,2),(2,3),(2,2),(2,4)}$

Спойлер

Проверим все свойства отношения:

• Рефлексивность
  $(forall xin A)langle x,xranglein R$ – это ложное высказывание.
  Можно привести контрпример: $x=3$, пара $langle 3,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
• Антирефлексивность
  $(forall xin A)langle x,xranglenotin R$ – это ложное высказывание.
  Можно привести контрпример: $x=1$, пара $langle 1,1rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
• Корефлексивность
  $(forall x,yin A)langle x,yranglenotin R$ – это ложное высказывание.
  Можно привести контрпример: $x=1,y=2$, пара $langle 1,2rangle$ принадлежит множеству $R$, но $xneq y$. Бинарное отношение не является антирефлексивным.
• Симметричность
  $ forall x,yin A (langle x,yranglein R): langle y,xranglein R$ – это ложное высказывание.
  Можно привести контрпример, $x=1,y=2$ пара $langle 1,2rangle$ принадлежит множеству $R$, а пара $langle 2,1rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
• Антисимметричность
  $forall x,yin A(xRywedge yRxRightarrow x=y)$ – это истинное высказывание
  Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
• Асимметричность
  Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
• Транзитивность
  $forall x,y,zin A(xRywedge yRzRightarrow xRz)$– это ложное высказывание.
  Можно привести контр пример, $x=1,y=2,z=3$ пара $langle 1,2rangle$ принадлежит множеству R и пара $langle 2,3rangle$ принадлежит множеству $R$, а пара $langle 1,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
• Связность
  $forall x,yin A(xneq yRightarrow xRylor yRx)$ – это ложное высказывание.
  Можно привести контрпример, $x=3,y=4$, $3neq 4$ пара $langle 3,4rangle$ не принадлежит множеству $R$ и пара $langle 4,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

[свернуть]

Источники:

• Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
• С.В.Федоровский.Конспект лекций по математической логике
• Кострикин А.В. , «Введение в алгебру», 1977, стр.134
• А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19

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

Вопросы для закрепления пройденного материала

Таблица лучших: Бинарные отношения

максимум из 15 баллов

Место	Имя	Записано	Баллы	Результат
Таблица загружается

Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

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

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

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A´B) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S´K можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

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

Определение 3.1. Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество A´B, т. е.

.

В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит: r, t, j, s, w и т. д.

Определение 3.2. Областью определения бинарного отношения r называется множество Dr={a | $ b, что arb} (левая часть). Областью значений бинарного отношения r называется множество Rr={b | $ a, что arb} (правая часть).

Пример 3.1. Пусть даны два множества A={1; 3; 5; 7} и B={2; 4; 6}. Отношение зададим следующим образом t={(x; y)ÎA´B | x+y=9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере Dt={3; 5; 7} и Rt= B={2; 4; 6}.

,

Пример 3.2. Отношение равенства на множестве действительных чисел есть множество r={(x; y) | x и y – действительные числа и x равно y}. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, Dr= Rr.

,

Пример 3.3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x; y)ÎA´B | y – цена x} – отношение множеств A и B.

,

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x; y)ÎA´B | x+y=9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

4) в виде матрицы: пусть A={a1, a2, …, an} и B={b1, b2, …, bm}, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями

.

Кстати, матричное представление является представлением отношения в компьютере.

Пример 3.4. Пусть даны два множества A={1; 3; 5; 7}и B={2; 4; 6}. Отношение задано следующим образом t={(x; y) | x+y=9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} – есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

3) в матричном представлении это отношение имеет вид

. ,

Пример 3.5. Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M:

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении r, если из устройства mi поступает информация в устройство mj.

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

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

. ,

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

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

rÍA1´…´An={(a1, …, an)| a1ÎA1Ù … ÙanÎAn}

Многоместные отношения удобно задавать с помощью реляционных таблиц. Такое задание соответствует перечислению множества n-к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных. Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная» происходит от латинского слова relation, которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».

Определение 3.4. Пусть rÍA´B есть отношение на A´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A´B, которое определяется следующим образом:

r-1={(b, a) | (a, b)Îr}.

Определение 3.5. Пусть r ÍA´B есть отношение на A´B, а s ÍB´C – отношение на B´C. Композицией отношений s и r называется отношение t ÍA´C,которое определяется следующим образом:

t=s◦r= {(a, c)| $ b Î B, что (a, b)Îr и (b, c)Îs}.

Пример 3.6. Пусть , и C={,, !, d, à}. И пусть отношение r на A´B и отношение s на B´C заданы в виде:

r={(1, x), (1, y), (3, x)};

s={(x, ,), (x, !), (y, d), (y, à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x, 1), (y, 1), (x, 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1, ,), (1, !), (1, d), (1, à), (3, ,), (3, !)},

поскольку из (1, x)Îr и (x, ,)Îs следует (1, ,)Îs◦r;

из (1, x)Îr и (x, !)Îs следует (1, !)Îs◦r;

из (1, y)Îr и (y, d)Îs следует (1, d)Îs◦r;

…

из (3, x)Îr и (x, !)Îs следует (3, !)Îs◦r.

3) r◦s=Æ.

,

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

1) ;

2) ;

3) – ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a; b) Î (s◦r)-1 Û (b; a) Î s◦r Û $ c такое, что (b; c) Î r и (c; a) Î s Û $ c такое, что (c; b) Î r-1 и (a; c) Î s-1 Û (a; b) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

■

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

Рассмотрим специальные свойства бинарных отношений на множестве A.

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

1. Отношение r на A´A называется рефлексивным, если (a,a) принадлежит r для всех a из A.

2. Отношение r называется антирефлексивным, если из (a,b)Îr следует a¹b.

3. Отношение r симметрично, если для a и b, принадлежащих A, из (a,b)Îr следует, что (b,a)Îr.

4. Отношение r называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению r следует, что a=b.

5. Отношение r транзитивно, если для a, b и c из A из того, что (a,b)Îr и (b,c)Îr, следует, что (a,c)Îr.

Пример 3.7. Пусть A={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого aÎA, (a; a)Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

,

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

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

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a ~ b.

Пример 3.8. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

,

Пример 3.9. Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

,

Пример 3.10. Пусть ¢ – множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (mÎ¥) и запишем , если равны остатки этих чисел от деления их на m, т. е. разность (x–y) делится на m.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для “x΢ имеем x–x=0, и, следовательно, оно делится на m;

это отношение симметрично, т. к. если (x–y) делится на m, то и (y–x) тоже делится на m;

это отношение транзитивно, т. к. если (x–y) делится на m, то для некоторого целого t1 имеем , а если (y–z) делится на m, то для некоторого целого t2 имеем , отсюда , т. е. (x–z) делится на m.

,

Определение 3.7. Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

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

Пример 3.11. Отношение x£y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3.12. Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.

,

Пример 3.13. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

,

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

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

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