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

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

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

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

.

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

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

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

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

Пример 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}.

,

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

,

Пример 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₁, a₂, …, a_n} и B={b₁, b₂, …, b_m}, r – отношение на A´B. Матричным представлением r называется матрица M=[m_ij] размера n´m, определенная соотношениями

.

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

Пример 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. n-местное(n-арное) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей)

rÍA₁´…´A_n={(a₁, …, a_n)| a₁ÎA₁Ù … Ùa_nÎA_n}

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

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

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

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

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

Определение 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}.

Пример 5. Пусть , и 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=Æ.

,

Теорема 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.