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

Начнем с примеров. Натуральные числа могут быть полными

квадратами, как 4, 81, 144, или не быть ими, как 5, 30, 48. Это свойство,

или признак числа можно трактовать как принадлежность к

определенному подмножеству натуральных чисел - полных квадратов

{О, 1, 4, 9, 16, 25,...}. То же можно сказать про признак "Х>2" для

действителы-.ых чисел: число 5 обладает этим свойством, а число 1 -

. нет. Напротив, неравенство X > Y выражает свойство не одного числа

•• X или Y , а совокупное свойство пары чисел: если X — 5, Y - 3 , то

неравенство выполняется, а для пар (5, 10) и (3, 5) не выполняется.

Можно выразить это так: условие X > Y выполнено для определенного Множества пар чисел.

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

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

Пусть задано непустое множество М п -арное (/7-местное) отношение на множествеЛ/ - подмножество Бинарные отношения - student2.ru ; обозначение

Бинарные отношения - student2.ru Говорят, что элементы, составляющие кортеж

Бинарные отношения - student2.ru находятся в отношении R , причем это свойство не

отдельных элементов, а именно их совокупности. Полезно рассматривать и одноместное (унарное) отношение - оно называется признаком, или

свойством элементов множества М . В более общем смысле п -арное отношение можно определить и для совокупностей элементов различных

множеств Бинарные отношения - student2.ru как подмножество Бинарные отношения - student2.ru

Число п называется арностью,или местностьюотношения. Чаще других используется случай п = 2.

Бинарное (двуместное) отношение- множество пар

Бинарные отношения - student2.ru ; обозначение - R(a,b) или aRb - элементы а и

b находятся в отношении R .

Примеры.1) Отношение равенства между двумя или несколькими числами, фигурами, множествами

2) Бинарное отношение старшинства между людьми по возрасту или воинскому званию.

3) Бинарные родственные и другие отношения между людьми "быть отцом", "быть внуком", "быть одноклассниками".

4) Трехместное (тернарное)отношение "между" для тройки точек

(А,В,С) на прямой: точка А расположена между точками В и С-

5) Тернарное отношение для тройки точек на плоскости - "лежать на одной прямой".

6) Четырехместное отношение для точек пространства -"принадлежать одной плоскости".

7) Четырехместное отношение для чисел - "быть

пропорциональными", т е. удовлетворять соотношению XIY - Z / Т .

8) Бинарное отношение между целыми числами - "иметь

одинаковые остатки от деления на 7"

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

Отношение - понятие очень широкое. Так, можно рассматривать отношение принадлежности

элемента а множеству Л/ как Бинарные отношения - student2.ru

бинарное отношение между объектами а и М , выполненное для всех пар (а,М) таких, что Бинарные отношения - student2.ru

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

дополнение к последнему есть отношение " X < Y". Бинарные отношения - student2.ru

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

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

на В(Е).

Равенство отношений Бинарные отношения - student2.ru есть равенство множеств Бинарные отношения - student2.ru ,

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

слагаемых - одной четности, так как сумма четного и нечетного чисел - нечетна.

Бинарное отношение на конечном множестве можно представить квадратной матрицей, у которой строки и столбцы - это элементы

множества, а элемент матрицы, находящийся на пересечении строки X и столбца У равен 1, если XRY , и равен 0 в противном случае. Пример. Пусть М {а, Ь, с]. Рассмотрим 4 отношения:

V Бинарные отношения - student2.ru j

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

Отношение ARB можно рассматривать и как совокупность всех высказываний вида "элемент Бинарные отношения - student2.ru находится в отношении R с

элементом. Поэтому для отношений содержательными являются

определяемые Бинарные отношения - student2.ru естественным образом логические операции или связки' дизъюнкция, конъюнкция, отрицание, которые порождают составные отношения; так, например, отрицание бинарного отношения R на множестве М есть бинарное отношение Бинарные отношения - student2.ru , в котором

находятся все пары элементов из М , кроме находящихся в отношении

Бинарные отношения - student2.ru называют также противоположным отношением для R . Упражнение.Сформулируйте самостоятельно, что называется

конъюнкцией и дизъюнкцией отношений. Рассмотрите конъюнкцию, дизъюнкцию и отрицание отношения Бинарные отношения - student2.ru

Инверсиейбинарного отношения R называется отношение, обозначаемое Бинарные отношения - student2.ru и такое, что Бинарные отношения - student2.ru тогда и только тогда, когда bRa .

Понятно, что инверсией отношения Бинарные отношения - student2.ru является отношение R , т.е.

можно сказать, что отношения Бинарные отношения - student2.ru взаимно обратны.

Пример.Инверсией для отношения "больше" является отношение "меньше"; то же - для их разновидностей: старше - моложе, дороже -дешевле, выше - ниже и т.п.

Инверсия отношения отличается от отрицания: инверсией

отношения X > Y на множестве чисел является отношение X < Y , тогда как отрицанием - отношение Бинарные отношения - student2.ru

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

Рефлексивное(соответственно, антирефлексивное)

отношение-бинарное отношение, обладающее свойством a'.aRa

(соответственно, Бинарные отношения - student2.ru

Симметричное отношение- бинарное отношение, обладающее свойством Бинарные отношения - student2.ru

Антисимметричное отношение- бинарное отношение такое, что Бинарные отношения - student2.ru если Бинарные отношения - student2.ru - т.е. если а и b - в этом порядке! -

находятся в отношении R , то b и а - нет. Это же свойство выражают иначе: Бинарные отношения - student2.ru : если aRb и bRa , то а - b .

Примеры.1) Отношения равенства рефлексивны и симметричны.

2) Отношения между парами чисел "больше", "меньше" -антирефлексивны и антисимметричны.

3) Отношение параллельности прямых рефлексивно и симметрично.

Понятие симметрии можно распространить и на отношения большей

арности, имея в виду симметрию для отдельных пар в п -кортеже. Так,

|тернарное отношение R(X,Y,Z) симметрично по паре (F,Z), если

всегда R(a,b,c) выполняется вместе с R(a,c,b). Например, отношение

(X - Y - Z) симметрично по (F,Z). Действительно, если X - Y = Z , то

X = Y + Z и ясно, что перестановка К и Z не изменяет равенства. Транзитивное отношение- бинарное отношение, обладающее

свойством Бинарные отношения - student2.ru

Примеры.1) Отношения "больше" и "меньше" транзитивны. 2} Отношение параллельности прямых транзитивно.

3) Отношения равенства транзитивны.

4) Отношения "правее", "левее" между делениями на линейной шкале прибора

5) Отношения "севернее", "южнее" между точками земной

поверхности

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

1) Отношение перпендикулярности прямых.

2) Известное из истории европейского средневековья отношение между вассалом и сюзереном, выражавшееся формулой: "вассал моего вассала - не мой вассал".

3) Отношение между игроками или командами в спортивном

турнире: "участник X выиграл у участника Y ": возможно, что А выиграл

у В , В выиграл у С, но А проиграл С-

4) Отношения "западнее", "восточнее" между точками земной поверхности- Ярославль (40° восточной долготы) западнее Хабаровска (135° восточной долготы); Хабаровск западнее Торонто (80° западной долготы), но Ярославль восточнее Торонто.

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

несколько). Отношение Б разумно считать определенным только для пар различных элементов, и, поэтому, нерефлексивным: иначе

ближайшим к каждому острову будет он сам и только он. Отношение Б , вообще говоря, несимметрично, поскольку если b - ближайший для а , то для b ближайшим может оказаться как а , так и какой-то третий остров

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

В табл 1 сведены характеристики рассмотренных выше отношений

Я,-Л4-

Бинарные отношения - student2.ru

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

каждой стрелкой содержит (соответственно, не содержит) противоположно направленную.

Транзитивное замыканиебинарного отношения R есть бинарное отношение Бинарные отношения - student2.ru такое, что Бинарные отношения - student2.ru (т е. элементы a,b находятся в

отношении Бинарные отношения - student2.ru ), если существует цепочка Бинарные отношения - student2.ru , для которой

Бинарные отношения - student2.ru . Например, для отношения "быть сыном" транзитивным замыканием является отношение "быть прямым потомком по мужской линии". Для отношения на множестве квартир дома "иметь общую стену" транзитивное замыкание - это отношение "находиться на

^ одном этаже". Отношение Бинарные отношения - student2.ru , конечно, транзитивно. )

§4. Отношения эквивалентности "

Отношение эквивалентности- бинарное отношение, являющееся рефлексивным, симметричным и транзитивным.

Примеры.1) Рассмотренные выше отношения равенства, параллельности прямых.

2) Отношение подобия треугольников.

3) Отношение между элементами множества всех многоугольников: "иметь одинаковое число сторон".

4) Бинарное отношение пропорциональности Р между парами чисел (X,У) и (Z,Т): (X, Y)P(Z,Т) , если XIY = ZIT .

5) Упоминавшееся выше отношение между целыми числами -"иметь одинаковые остатки от деления на 7".

Пусть на множестве М введено некоторое отношение эквивалентности R . Для каждого элемента Бинарные отношения - student2.ru рассмотрим

множество Бинарные отношения - student2.ru элементов Бинарные отношения - student2.ru , эквивалентных Бинарные отношения - student2.ru . В силу

симметричности и транзитивности отношения R , если Бинарные отношения - student2.ru , то

Бинарные отношения - student2.ru . Если же Бинарные отношения - student2.ru ; иначе, если бы существовал

элемент Бинарные отношения - student2.ru , то выполнялось бы Бинарные отношения - student2.ru и, в силу

транзитивности Бинарные отношения - student2.ru

Таким образом, система различных множеств Бинарные отношения - student2.ru - разбиение

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

бинарного отношения R на множествеМ - систему подмножеств

множества М такую, что

1) любые два элемента из одного класса эквивалентны;

2) любые два элемента из разных классов не эквивалентны.

Верно и обратное. Любое разбиение множества М можно рассматривать как отношение эквивалентности, в котором находятся пары элементов, отнесенные к одному и тому же классу разбиения, и не находятся элементы из разных классов.

Группировку объектов, применяемую в статистике, законодательстве (например, разделение предприятий на малые, средние и крупные для установления нормативов, единых для всех элементов группы) и в других областях, можно рассматривать как установление эквивалентности.

Классы эквивалентности для примеров 2-5.

(2) - множества подобных друг другу треугольников; в разных классах - треугольники разной формы.

(3) - счетное множество классов: в л -и класс входят все п -угольники.

(4) - пары чисел (X, Y), имеющих одинаковое значение частного X/Y.

(5) - 7 классов чисел Бинарные отношения - student2.ru имеющих остаток / при

делении на 7. Класс Nt содержит числа вида Бинарные отношения - student2.ru

Например, для / =4 класс Бинарные отношения - student2.ru -этомножество(...-10, -3, 4, 11, 18, 25, ..). Рассмотрим еще один важный пример.Определим отношение Э между множествами следующим образом: Бинарные отношения - student2.ru , или короче -

Бинарные отношения - student2.ru , если существует взаимно однозначное соответствие между множествами L и М . Можно показать, что Э является отношением эквивалентности. Действительно, если для трех множеств L,M,K выполнено L Э М и М Э К, то элементу Бинарные отношения - student2.ru соответствует некоторый

элемент Бинарные отношения - student2.ru , а элементу т соответствует элемент Бинарные отношения - student2.ru ; тогда

Бинарные отношения - student2.ru , поскольку можно сопоставить элементу / элемент k . Классы эквивалентности состоят при этом из множеств, имеющих одинаковую мощность (для конечных множеств - одинаковое число элементов).

Наши рекомендации