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

Начнем с примеров. Натуральные числа могут быть полными квадратами, 4, 81, 144, или не быть ими, как 5, 30, 48. Это свойство, или признак числа можно трактовать как принадлежность к определенному подмножеству натуральных чисел - полных квадратов {0, 1, 4, 9, 16, 25, ...}. То же можно сказать про признак "Х > 2" для действительных чисел: число 5 обладает этим свойством, а число 1 - нет. Напротив, неравенство X > Y выражает свойства не одного числа X или Y, а совокупное свойство пары чисел: если
X = 5, Y = 3, то неравенство выполняется, а для пар (5, 10) и (3, 5) не выполняется. Можно выразить это так: условие X > Y выполнено для определенного множества пар чисел.

Некоторые понятия как в математике, так и в обычном языковом Употреблении самими своими названиями предполагают отношения между субъектами или объектами: участник (какого-то мероприятия или коллектива), сосед, знакомый (чей-то), одноименный, сопоставимый (с кем-либо или чем-либо), отличающийся (от чего-то другого), внутри, снаружи, между, обратная функция, обратная терема. В последнем случае, как мы знаем, если А - обратная теорема (по отношению к теореме В), то и В является обратной к А, так что этот термин характеризует не само утверждение А, а его взаимоотношение с другим утверждением. Также не бывает взаимно-однозначного множества - этим термином обозначается соответствие между двумя множествами.

Пусть задано непустое множество М. n-арное (n-местное) отношение на множестве М - подмножество RMn; обозначение - R(m1, m2, .., mn). Говорят, что элементы, составляющие кортеж (m1, m2, .., mn) находятся в отношении R, причем это свойство не отдельных элементов, а именно их совокупности. Полезно рассматривать и одноместное (унарное) отношение - оно называется признаком, или свойством элементов множества М. В более общем смысле n-арное отношение можно определить и для совокупностей элементов различных множеств М1, М2, .., Мn как подмножество RM1M2...Mn. Число n называется арностью, или местностью отношения. Чаще других используется случай n=2.

Бинарное (двуместное) отношение - множество пар (a, b)R M1M2; обозначение - R(a, b) или aRb -элементы a и b находятся в отношении R .

Примеры
  1. Отношение равенства между двумя или несколькими числами, фигурами, множествами.
  2. Бинарное отношение старшинства между людьми по возрасту или воинскому званию.
  3. Бинарные родственные и другие отношения между людьми "быть отцом", "быть внуком", "быть одноклассниками".
  4. Трехместное (тернарное) отношение "между" для тройки точек (А, В, С) на прямой: точка A расположена между точками B и С.
  5. Тернарное отношение для тройки точек на плоскости - "лежать на одной прямой".
  6. Четырехместное отношение для точек пространства -"принадлежать одной плоскости".
  7. Четырехместное отношение для чисел - "быть пропорциональными", т.е. удовлетворять соотношению X / Y = Z / T.
  8. Бинарное отношение между целыми числами - "иметь одинаковые остатки oт деления на 7".
  9. Бинарное отношение {(1, 3), (4, 2), (4, 5), (3, 1), (2, 5), (3, 2)} можно рассматривать просто как 6 пар натуральных чисел (рисунок 12);
Рисунок 12
Рисунок 12

 однако 4 этот пример может иметь и содержательный смысл: например, для 5 авторов 1, 2, 3, 4, 5 пара ( X, Y ) означает, что автор X в своих работах ссылается на автора Y.

 Отношение - понятие очень широкое. Так, можно рассматривать отношение принадлежности элемента a множеству M как бинарное отношение между объектами a и M , выполненное для всех пар (a, M) таких, что a M.

 Поскольку n -арные отношения являются множествами, то к ним применимы все теоретико-множественные операции: объединение, пересечение, дополнение и др. Так, объединение отношений "Х > Y" и "Х = Y" на числовом множестве есть отношение "Х > Y", a дополнение к последнему есть отношение "Х < Y".

 Еще один важный пример - отношение включения для множеств.

 Булеан В(Е) - множество всех подмножеств множества E. Булеан В(Е) обозначается также 2E. Если М ,N - подмножества Е и М есть подмножество множества N , то ( М N ) - бинарное отношение на В(Е).

 Равенство отношений R1 = R2 есть равенство множеств R1 и R2, определяющих эти отношения, хотя бы они были выражены по-разному. Например, отношения между натуральными числами "иметь одинаковые остатки от деления на 2" и "давать при сложении четное число" совпадают. Действительно, остатки от деления двух чисел р и q на 2 равны, если они оба четные (в этом случае остаток - 0) или оба нечетные (остаток 1). То же при сложении чисел р и q : если сумма четная, то оба слагаемых - одной четности, так как сумма четного и нечетного чисел - нечетна.

 Бинарное отношение на конечном множестве можно представить квадратной матрицей, у которой строки и столбцы - это элементы множества, а элемент матрицы, находящийся на пересечении строки Х и столбца Y равен 1, если XRY, и равен 0 в противном случае.

Пример

Пусть M{a,b,c}. Рассмотрим 4 отношения:

R1 = {(a,b), (b,c), (c,a)};
R2 = {(a,a), (a,b), (b,b), (a,c), (b,c), (c,c)};
R3 = {(a,a), (a,b), (b,b), (c,c)};
R4 = {(a,a), (a,b), (b,a), (a,c), (c,a), (b,c), (c,b)}.
R1 = 010
001
100
R2 = 111
011
001
R3 = 110
010
001
R4 = 111
101
110

 Бинарное отношение можно изобразить схемой (рисунок 13), сопоставив элементам множества точки (вершины), а парам (a, b) R -связки (линии со стрелками, идущие из a в b ).

Рисунок 13
Рисунок 13

 Отношение ARB можно рассматривать и как совокупность всех высказываний вида "элемент а А находится в отношении R с элементом bВ. Поэтому для отношений содержательными являются определяемые естественным образом логические операции или связки: дизъюнкция, конъюнкция, отрицание, которые порождают составные отношения; так, например, отрицание бинарного отношения R на множестве М есть бинарное отношение ┐R , в котором находятся все пары элементов из М , кроме находящихся в отношении R. ┐R называют также противоположным отношением для R .

 Инверсией бинарного отношения R называется отношение, обозначаемое R-1 и такое, что aR-1b тогда и только тогда, когда bRa. Понятно, что инверсией отношения R-1 является отношение R , т.е. можно сказать, что отношения R и R-1 взаимно обратны.

Пример

Инверсией для отношения "больше" является отношение "меньше"; то же - для их разновидностей: старше - моложе, дороже -дешевле, выше - ниже и т.п. Инверсия отношения отличается от отрицания: инверсией отношения Х > Y на множестве чисел является отношение Х < Y , тогда как отрицанием - отношение X ≤ Y .

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

Рефлексивное (соответственно, антирефлексивное) отношение - бинарное отношение, обладающее свойством a: aRa (соответственно, а : a┐Ra).

 Симметричное отношение - бинарное отношение, обладающее свойством a, b: aRb bRa (т.е. из aRb следует bRa ).

 Антисимметричное отношение- бинарное отношение такое, что а, b: если а b, то aRb b┐ Ra - т.е. если а и b - в этом порядке! -находятся в отношении R , то b и а - нет. Это же свойство выражают иначе: a, b : если aRb и bRa , то а = b.

Примеры
  1. Отношения равенства рефлексивны и симметричны.
  2. Отношения между парами чисел "больше", "меньше" -антирефлексивны и антисимметричны.
  3. Отношение параллельности прямых рефлексивно и симметрично. Понятие симметрии можно распространить и на отношения большей арности, имея в виду симметрию для отдельных пар в n -кортеже. Так,тернарное отношение R(X, Y, Z) симметрично по паре (Y, Z), если всегда R(a,b,c) выполняется вместе с R(a,c,b) . Например, отношение (X \ Y = Z) симметрично по (Y, Z). Действительно, если Х \ Y = Z , то Х = Y Z и ясно, что перестановка Y и Z не изменяет равенства.

     Транзитивное отношение - бинарное отношение, обладающее свойством a, b, c: (aRb bRc) aRc.

  4. Отношения "больше" и "меньше" транзитивны.
  5. Отношение параллельности прямых транзитивно.
  6. Отношения равенства транзитивны.
  7. Отношения "правее" "левее" между делениями на линейной шкале прибора.
  8. Отношения "севернее", "южнее" между точками земной поверхности.

 Примеры нетранзитивных отношений.

  1. Отношение перпендикулярности прямых.
  2. Известное из истории европейского средневековья отношение между вассалом и сюзереном, выражавшееся формулой: "вассал моего вассала - не мой вассал.
  3. Отношение между игроками или командами в спортивном турнире: "участник Х выиграл у участника Y": возможно, что А выиграл у В , В выиграл у С, но А проиграл С.
  4. Отношения "западнее", "восточнее" между точками земной поверхности: Ярославль (40° восточной долготы) западнее Хабаровска (135° восточной долготы); Хабаровск западнее Торонто (80° западной долготы), но Ярославль восточнее Торонто.

 Пример

Пусть аБb - отношение на множестве островов некоторого архипелага, состоящее в том, что остров b является ближайшим для острова a (если допустить, что среди попарных расстояний могут быть равные, то ближайших для a может оказаться несколько). Отношение Б разумно считать определенным только для пар различных элементов, и, поэтому, нерефлексивным: иначе ближайшим к каждому острову будет он сам и только он. Отношение Б, вообще говоря, несимметрично, поскольку если b - ближайший для а, то для b ближайшим может оказаться как a, так и какой-то третий остров с. Наконец, отношение Б не является транзитивным, что очевидно, например, для трех островов, расположенных на одной прямой или вообще не в вершинах равностороннего треугольника. В таблице 1 сведены характеристики рассмотренных выше отношений R1-R4

Таблица 1
Рeфл.Антирефл.Симм.Антисимм.Транз.
R1-+-++
R2+--++
R3+--+-
R4--+-+

 

Для рефлексивного (соответственно, антирефликсивного) отношения все диагональные элементы матрицы равны 1 (соответственно, 0), а схема в каждой вершине имеет (соответственно, не имеет) петлю. Матрица симметричного (соответственно, антисимметричного) отношения симметрична относительно главной диагонали, т.е. aij = aji (соответственно, aij aji), а схема вместе с каждой стрелкой содержит (соответственно, не содержит) противоположно направленную.

Транзитивное замыкание бинарного отношения R есть бинарное отношение такое, что a b (т.е. элементы а, b находятся в отношении ), если существует цепочка c1, c2, ...,cn , для которой aRc1,
c1Rc2, ...,ckRb. Например, для отношения "быть сыном" транзитивным замыканием является отношение "быть прямым потомком по мужской линии". Для отношения на множестве квартир дома "иметь общую стену" транзитивное замыкание - это отношение "находиться на одном этаже". Отношение , конечно, транзитивно.

 

Вопросы для самоконтроля

  1. Сформулируйте определение бинарного отношения.
    Приведите примеры.
  2. Дайте определение булеана.
  3. Укажите какие типы отношений вы знаете.
  4. Приведите примеры отношений.
  5. Изучите самостоятельно такие понятия, как: композиция отношений, степень отношения, ядро отношения.

Практические задания


Tест для самоконтроля