Отношения и их свойства. Бинарные отношения и их свойства

Бинарным отношением Т(М) на множестве М называется подмножество М 2 = М х М, Т(М) с М 2 . Формальная запись бинарного отношения выглядит шкТ(М) = {(х, у) / (х, у) е Т с М х М}. Обратите внимание: далее мы будем рассматривать только не пустые множества Ми заданные на них непустые бинарные отношения Т(М)

Понятие «бинарное отношение» является более общим понятием, чем функция. Каждая функция представляет собой бинарное отношение, но не каждое бинарное отношение есть функция.

Например, множество пар Р = {(а, Ь), (а, с), (а, б)} является бинарным отношением на множестве {а, Ъ, с, (1), но функцией не является. И наоборот, функция Р= {(а, Ь),(Ь, с), (с1, а)} является бинарным отношением, заданным на множестве {а, Ь, с, с!}.

Мы уже сталкивались с понятием отношения при рассмотрении с (включение) и = (равенство) между множествами. Также неоднократно вами использовались отношения =, Ф, , заданные на множестве чисел - как натуральных, так и целых, рациональных, вещественных и т.д.

Определим несколько понятий относительно бинарного отношения, заданного на множестве М[ 2, 11].

Обратное отношение

Я-"= {(х, у) / (у, х) € Я). (1.14)

Дополнительное отношение

Л = {(*, У) / (х, у) й /?}. (1.15)

Тождественное отношение

и = {(х, х) / X Е М). (1.16)

Универсальное отношение

I ={(х,у)/хеМ,уеМ}. (1.17)

Рассмотрим несколько задач.

Задача 1.8

На множестве М= {а, Ь, с, с1 , е} задано бинарное отношение Т(М ) = = {{а, а ), (а , Ь ), (Ь , с), (с, ?/), (^/, б), {б, е)}. Построить отношения : обратное к Т , дополнительное к Т, тождественное бинарное отношение и и универсальное бинарное отношение /.

Решение.

Для решения этих задач нам нужны только определения.

По определению на множестве М= {а , Ь , с, б, е} обратное к ДЛ/) бинарное отношение должно содержать все обратные пары тождественное бинарное отношение Т~ = {(а , а ), (/?, я), (с, 6), (б, с), (^/, ?/), (с, б)}.

По определению на множестве М= {а, Ь, с , б, е} дополнительное к Т(М ) бинарное отношение должно содержать все пары из декартова произведения М 2 , которые не принадлежат Т(М), т.е. {(а , с), {а, Л), (а, е), (Ь, а), (Ь, Ь), (Ь, б), (Ь, е), (с, а), (с, Ь), (с, с), (с, е), {б, а), (б, Ь), (б, с), (е, а), (е, Ь), (е, с), (е, б), (е, е)}.

По определению на множестве М = {а, Ь, с, б , е} тождественное бинарное отношение и = {(а, а ), (Ь , /?), (с, с), (^/, ^/), (е, е)}.

По определению на множестве М = {а , 6, с, б, е} универсальное бинарное отношение содержит все пары из декартова произведения М 2 , т.е. / = {(а, а), (а , А), (о, с), (а,), (я, е), (Ь, а), (Ь, Ь), (Ь, с), (Ь, б), (Ь, е), (с, а), (с, Л), (с, с), (с, йО, (с, е), (б, а), (б , А), (, с), (,), (^,

Задача 1.9

На множестве М натуральных чисел от 1 до 5 построить бинарное отношение R = {(а , d) / mod(? r , Z>) = 0}, где mod - остаток от деления а на Ь.

Решение.

В соответствии с заданием на множестве натуральных чисел М строим такие пары (а , Ь), где а делится на b без остатка, т.е. mod(?, Ъ ) = = 0. Получаем R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (4, 1), (5, 1), (4, 2)}.

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

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

При графическом представлении каждый элемент х и у множества М представляется вершиной, а пара (х, у) представляется дугой изх в у.

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

Матрица смежности S представляет собой квадратную матрицу тх/й, где т - мощность множества М, и каждый ее элемент 5(х, у) равен единице, если пара (х, у) принадлежит Т(М), и равен нулю в противном случае.

На рис. 1.3 представлено графическое и матричное представление для Т(М) = {(а , а), (а, Ъ), (b , с), (с, d), (d , d), (d, e)}.

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

Бинарное отношение Т(М) называется рефлексивным тогда и только тогда, когда для каждого элемента х е М пара (х, х) принадлежит этому бинарному отношению Т(М), т.е. Vx е М, 3(х, х) е Т(М).

Рис. 1.3. Графическое (а) и матричное (б) представление множества

Классическим определением этого свойства является следующее утверждение: из того, что элемент х принадлежит множеству М, следует, что пара (х, х) принадлежит бинарному отношению Т(М), заданному на этом множестве, т.е. /хєМ-) (х, х) є Т(М).

Прямо противоположное свойство бинарных отношений называется иррефлексивностью. Бинарное отношение Т(М) называется иррефлексивным тогда и только тогда, когда для каждого элемента х из множества М пара (х, х) не принадлежит этому бинарному отношению, т.е. /х є М -> (х, х) ё Т(М).

Если бинарное отношение Т(М) не обладает ни свойством рефлексивности, ни свойством иррефлексивности, то оно является нерефлексивным.

Например, для множества М - {а, Ь, с , ^/, е} бинарное отношение Т Х (М) = {(а , а), (а, Ь), (Ь, Ь), (Ь, с), (с, с), (с, сі), (сі, сі), (сі , с), (е, е )} является рефлексивным, Т 2 (М) = {(а , Ь), (Ь , с), (с, сі), (сі, с), (сі, е )} является иррефлексивным, а Т 3 (М) = {(а , а ), (а, Ь), (Ь , с), (с, сі), (сі , ?/), (?/, с)} является нерефлексивным.

Если во множестве М содержится хотя бы один элемент х, то правильная классификация не представляет сложности. Обратите внимание: для однозначности решения задачи классификации свойство рефлексивности следует определять только для непустых множеств!

В соответствии с этим бинарное отношение на пустом множестве является нерефлексивным, так же как нерефлексивным будет пустое бинарное отношение.

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

Классическим определением свойства симметричности является следующее утверждение: из того, что пара (х, у) принадлежит Т(М), следует, что обратная пара (у, х) также принадлежит Т(М), т.е. /(х, у) є Т(М) -> (у, х) є Т(М). В этом случае еслих = у, то свойство симметричности плавно переходит в рефлексивность.

Прямо противоположное свойство бинарных отношений называется антисимметричностью. Бинарное отношение Т(М) называется антисимметричным тогда и только тогда, когда для каждой пары различных элементов х и у пара (у, х) не принадлежит этому бинарному отношению, т.е. /(х, у) є Т(М), (у, х) і Т(М).

Классическим определением антисимметричности можно считать следующее . Из того, что в антисимметричном бинарном отношении Т(М) для любой пары (х, у) обратная пара (у, х) также принадлежит Т(М), следует, что х = у, т.е. ((х, у) е Т(М), (у , х) е Т(М )) -> -> х = у.

Если бинарное отношение Т(М ) не обладает ни свойством симметричности, ни свойством антисимметричности, то оно является несимметричным.

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

М - {а, Ь, с, ^/, е}. Бинарное отношение Г, = {(а , а), (а, Ь ), (Ь , а ), (с, с1), (с /, с), (е , с), (с, е)} является симметричным, Т 2 = {(а, а), (а, Ь), (с, с1), (е , с), (с, Ь ), (Ь , е )} является антисимметричным, Т 3 = {(а, а ), (а , Ь ), (6, я), (с, с1), (е , с), (с, я)} - несимметричным. Обратите внимание: петля (а , я) никак не влияет на симметричность и антисимметричность.

Свойство транзитивности определяется на трех различных элементах х, у и I множества М. Бинарное отношение Т(М) называется транзитивным тогда и только тогда, когда для каждых двух пар различных элементов (х, у) и (у, О, принадлежащих бинарному отношению Т(М), пара (х, ?) также принадлежит этому бинарному отношению, т.е. (/(х, у) е Т(М), /(у, I) е Т(М)), 3(х, I) е Т(М). Таким образом, между элементами х и ^ существует транзитивное замыкание («транзит»), которое «спрямляет» путь длины два (х, у) и (у, z)?

Классическое определение свойства транзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) также принадлежит этому бинарному отношению, т.е. ((х, у) е Т(М ), (у, I) е Т(М)) -э (х, I) е Т(М ).

Бинарное отношение Т(М) называется интранзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у, ?), принадлежащих бинарному отношению Т(М), пара (х, не принадлежит этому бинарному отношению, т.е. (/(х, у) е Т(М), /(у, I) е Т{М)), (х, I) ? Т(М). Таким образом, в интранзитивном бинарном отношении ни один имеющийся путь длины два не обладает транзитивным замыканием!

Классическое определение свойства интранзитивности формулируется следующим образом: из того, что в транзитивном бинарном отношении Т(М) существует пара (х, у) и пара (у, I), следует, что пара (х, I) не принадлежит этому бинарному отношению, т.е. ((*, у) е Т(М), (у, I) е Т(М)) -э (х, I) ? Т(М).

Если бинарное отношение Т(М) не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным.

Например, рассмотрим множество М - {а , Ь, с, б, е}. Бинарное отношение Т х = {(а , а), (а , Ь ), (а , с), (Ь , с), (с, с), (е , с)} является транзитивным, Т 2 = {(я, я), (я, 6), (6, с), (с, 1), (?, 0} является интранзитив-ным, Т 3 = {(а , я), (я, 6), (6, с), (^/, с), (я, с), (е , ?/)} - нетранзитивным.

Задача 1.10

На множестве М х - {а, Ь, с, б, е} построить бинарное отношение Я с заданными свойствами : нерефлексивности , антисимметричности и нетранзитивности.

Решение.

Правильных решений этой задачи целое множество! Построим одно из них. В нашем бинарном отношении на некоторых вершинах, но не на всех, должны быть петли; не должно быть ни одной обратной дуги; должны быть хотя бы два пути длины 2, из них хотя бы один не иметь транзитивного замыкания. Таким образом, получаем Я = {(а, а), (Ь , Ь ), (а , Ь ), (Ь , с), (с, б), (б, е), (а, с), (с, е)}.

Задача 1.11

Определить свойства бинарного отношения Т, заданного на множестве М 2 = {а, Ь, с, б, е}, представленного ранее на рис. 1.3.

Решение.

В данном бинарном отношении на двух вершинах есть петли, на трех петель нет, следовательно, бинарное отношении нерефлексивно. Нет ни одной обратной дуги, следовательно, бинарное отношение антисимметрично. Бинарное отношение обладает несколькими путями длины два, но ни один из них не обладает транзитивным замыканием - Т интранзитивно.

Лекция 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ÍA 2), то говорят, что r есть отношение на множестве A.

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

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

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

Пример 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)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

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

Пример 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 ={a 1, a 2, …, an } и B ={b 1, b 2, …, 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) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

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

,

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

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

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

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

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

. ,

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

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

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

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ù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.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ÍA 2, которое имеет вид: 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 является симметричным:

	(a , b )Îr	(b , a )	(b , a )Îr?

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

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

	(a , b )Îr	(b , c )Îr	(a , c )	(a , c )Îr?

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

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

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

.

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

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

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

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

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

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

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

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

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

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

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

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

2. Слабая рефлексивность:

3. Сильная рефлексивность:

4. Антирефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

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

8. Антисимметричность:

9. Асимметричность:

10. Сильная линейность:

11. Слабая линейность:

12. Транзитивность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

Глава 1. Элементы теории множеств

1.1 Множества

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

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

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

Множества обычно обозначаются заглавными латинскими буквами. Если элемент

принадлежит множеству , то это обозначается:

Если каждый элемент множества

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

Подмножество

множества называется собственным подмножеством , если

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение , пересечение и разность .

Определение 1 . Объединением

Определение 2 . Пересечением двух множеств называется новое множество

Определение 3 . Разностью двух множеств называется новое множество

Если класс объектов, на которых определяются различные множества обозначить

(Универсум ), то дополнением множества называют разность упорядоченную n-ку , называют мощностью отношения .

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

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

Лекция 21. Свойства отношений

1. Свойство рефлексивености

2. Свойство симметричности

3. Свойство транзитивности

Мы установили, что бинарное отношение на множестве X пред­ставляет собой множество упорядоченных пар элементов, принад­лежащих декартову произведению X х Х. Это математическая сущ­ность всякого отношения. Но, как и любые другие понятия, отноше­ния обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые.

Рассмотрим на множестве отрезков, представ­ленных на рис. 98, отношения перпендикулярно­сти, равенства и «длиннее». Построим графы этих отношений (рис. 99) и будем их сравнивать. Ви­дим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отно­шение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлек­сивности или просто, что оно рефлексивно.

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

R рефлексивно на Х ↔ х R х для любого х € X.

опр.

Если отношение R рефлексивно на множестве X, то в каждой вер­шине графа данного отношения имеется петля. Справедливо и обрат­ное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

Отношение подобия треугольников (каждый треугольник подо­бен самому себе).

Существуют отношения, которые свойством рефлексивности не обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно ска­зать, что он перпендикулярен самому себе. Поэтому на графе отноше­ния перпендикулярности (рис. 99) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

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

Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

Если один отрезок равен другому отрезку, то этот «другой» равен первому.

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

Определение. Отношение R на множестве X называется симмет­ричным, если выполняется условие: из того, что элемент х находит­ся в отношении R с элементом у, следует, что и элементу находит­ся в отношении R с элементом х.

Используя символы, это отношение можно записать в таком виде:

R симметрично на Х ↔ (х R y →yRx).

опр.

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к x . Справедливо и обратноеутверждение. Граф, содержащий вместе с каждой стрелкой, идущей от x к у, и стрелку, идущую от у к x , является графом симметричного отношения.

В дополнение к рассмотренным двум примерам симметричных от­ношений присоединим еще такие:

Отношениепараллельности на множестве прямых (если прямая x параллельна прямой у, то и прямая у параллельна прямой х)

Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

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

Определение. Отношение R на множестве X называется анти­симметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится.

R симметрично на Х ↔ (х R y ^ x≠y →yRx).

опр.

Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого со­единены только одной стрелкой, есть граф антисимметричного отношения.

Кроме отношения «длиннее» на множестве отрезков свойством ан­тисимметричности, например, обладают:

Отношение «больше» для чисел (если х больше у, то у не может
быть больше х);

Отношение «больше на 2» для чисел (если х боль­ше у на 2, то у не может быть больше на 2 числа х),

Существуют отношения, не обладающие ни свой­ством симметричности, ни свойством антисиммет­ричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 100. Он показывает, что данное отношение не обладает ни свой­ством симметричности, ни свойством антисимметричности.

Обратим внимание еще раз на одну особенность графа отноше­ния «длиннее» (рис. 99). На нем можно заметить: если стрелки про­ведены от е к а и от а к с, то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с, то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

Определение. Отношение R на множестве X называется транзи­тивным, если выполняется условие; из того, что элемент х нахо­дится в отношении R с элементом у и элемент у находится в от­ношении R с элементом z, следует, что элемент х находится в от­ношении К с элементом z .

Используя символы, это определение можно записать в таком виде:

R транзитивно на X ↔ (х R y ^ yRz → xRz).

опр.

Граф транзитивного отношения с каждой парой стрелок, идущих от x к у и у к z , содержит стрелку, идущую от х к z. Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z, то отрезок х равен отрезку z, Это свойство отражено и на графе отношения равенства (рис. 99)

Существуют отношения, которые свойством транзитивности не об­ладают. Таким отношением является, например, отношение перпенди­кулярности: если отрезок а перпендикулярен отрезку d , а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!

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

Определение. Отношение R на множестве X называется связан­ным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находит­ся в отношении R с элементом у, либо элемент у находится в от­ношении R с элементом х.

Используя символы, это определение можно записать в таком виде:

R связано на множестве X ↔ (х ≠ у => хRу v уRх).

опр.

Например, свойством связанности обладают отношения «больше» длянатуральных чисел: для любых различных чисел х и у можно ут­верждать, что либо х > у, либо у > х.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

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

Выделенные свойства позволяют анализировать различные отно­шения с общих позиций - наличия (или отсутствия) у них тех или иных свойств.

Так, если суммировать все сказанное об отношении равенства, за­данном на множестве отрезков (рис. 99), то получается, что оно реф­лексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности - симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве отрезков связанными не являются.

Задача 1. Сформулировать свойства отноше­ния R, заданного при помощи графа (рис. 101).

Решение. Отношение R -антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с, на графе есть стрелка, идущая от b к с.

Отношение R - связанно, так как любые две вер­шины соединены стрелкой.

Отношение R свойством рефлексивности не обла­дает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число y не больше числа x 2 раза.

Данное отношение не обладает свойством рефлексивности, пото­му что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.

Заданное отношение не транзитивно, так как из того, что число x больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связан­ности не обладает, так как существуют пары таких чисел х и у, что ни число х не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3, 5 и 8 и др.

Отношение, заданное на множестве, может обладать рядом свойств, а именно:

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

Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.

Используя символы, это отношение можно записать в таком виде:

R рефлексивно на Х Û("х Î Х ) х R х

Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.

Граф рефлексивного отношения во всех вершинах имеет петли.

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

Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.

R антирефлексивно на Х Û("х Î Х )

Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.

Граф антирефлексивного отношения не содержит ни одной петли.

Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.

Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.

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

Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .

R симметричнона Х Û("х , у Î Х ) х R у Þ у R х

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

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

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

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

R асимметричнона Х Û("х , у Î Х ) х R у Þ

Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .

Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.

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

Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.

R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у

Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.

Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.

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

Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.

R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z

Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.

Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.

7. Связность

Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у

Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.

На графе связного отношения все вершины соединены между собой стрелками.

Пример. Проверить, какими свойствами обладает

отношение «х – делитель у », заданное на множестве

Х = {2; 3; 4; 6; 8}.

1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;

2) свойством антирефлексивности данное отношение не обладает;

3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;

4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;

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

6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.

Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.

§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы

Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:

1) рефлексивности, т.к. каждый студент является однокурсником самому себе;

2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;

3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .

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

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

Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?

Построим граф данного отношения:

Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.

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

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