Научная библиотека

§ 2. БИНАРНЫЕ ОТНОШЕНИЯ

Прямое произведение множеств.

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

Введем новое исходное понятие — понятие упорядоченной пары. Любым двум объектам а и b поставим в соответствие новый объект — их упорядоченную пару

ОПРЕДЕЛЕНИЕ. Упорядоченные пары называют равными и пишут в том и только в том случае, когда

В частности, в том и только в том случае, когда а — b.

В дальнейшем часто будем говорить «пара вместо «упорядоченная пара Элемент а называется первым элементом пары , а b — вторым элементом пары.

ОПРЕДЕЛЕНИЕ. Прямым произведением множеств А и В называется множество всех упорядоченных пар таких, что и у В. Это множество обозначается .

Таким образом,

Пример. Пусть . Тогда имеем:

Обобщением понятия упорядоченной пары является понятие кортежа (упорядоченного набора) объектов. Кортеж объектов обозначается через

ОПРЕДЕЛЕНИЕ. Два кортежа называют равными и пишут в том и только в том случае, когда

Кортежи трех объектов называют также упорядоченными тройками. Прямым произведением трех множеств А, В и С называется множество всех таких упорядоченных троек , что . Это множество обозначается через ; таким образом,

Пусть А — непустое множество и п — целое положительное число. Через обозначается множество всех кортежей элементов из А, т. е.

При этом будем считать, что . Множество называется ратным прямым произведением множества А или степенью множества А. В частности, .

ОПРЕДЕЛЕНИЕ. Прямым произведением множеств называется множество всех кортежей длины таких, что

Прямое произведение множеств обозначается символом таким образом,

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

Одним из основных является понятие бинарного отношения.

ОПРЕДЕЛЕНИЕ. Бинарным отношением называется любое множество упорядоченных пар.

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

Если R — бинарное отношение и то говорят, что связаны отношением R, или что элемент находится в отношении R к у, или что для и у выполняется отношение R. Вместо записи часто используют более простую

которая также является записью утверждения «элементы и у связаны отношением

ОПРЕДЕЛЕНИЕ. Множество всех первых элементов пар из R называется областью определения отношения R и обозначается

Множество всех вторых элементов пар из R называется областью значений отношения R и обозначается

ОПРЕДЕЛЕНИЕ. Множество называется областью отношения

Легко видеть, что

Если , то говорят, что R есть отношение между элементами множеств А и В или что R определено на паре множеств А и В. Если А а С и то т. е. R есть также отношение между элементами множеств С и D. Если , то . Таким образом, каждое отношение R является отношением между элементами множеств

ОПРЕДЕЛЕНИЕ. Если то говорят, что R есть бинарное отношение на множестве А.

Ясно, что каждое бинарное отношение R является отношением на области отношения

ОПРЕДЕЛЕНИЕ. Бинарные отношения R и S называются равными, если для любых тогда и только тогда, когда т. е. если R и S равны как множества.

ОПРЕДЕЛЕНИЕ. Пусть R и S — бинарные отношения. Множество всех пар таких, что для некоторого называется композицией (или суперпозицией) отношений S и R и обозначается через

По определению, имеем

Пример. Если , то

ОПРЕДЕЛЕНИЕ. Инверсией бинарного отношения R называется множество всех упорядоченных пар таких, что

Инверсия отношения R обозначается через . Таким образом, по определению,

Пример. Если

ПРЕДЛОЖЕНИЕ 2.1. Если R — любое бинарное отношение, то

т. e. если — инверсия R, то — инверсия

Это предложение непосредственно следует из определения инверсии отношения

ОПРЕДЕЛЕНИЕ. Отношение R называется ограничением отношения S, a S — расширением R, если

ОПРЕДЕЛЕНИЕ. Бинарное отношение R называется ограничением отношения S множеством А, если

Если бинарное отношение R является ограничением отношения S множеством А, то — ограничение .

ТЕОРЕМА 2.2. Композиция отношений обладает свойством ассоциативности, т. е. для любых бинарных отношений

Доказательство. Для любых имеем

Следовательно, равенство (1) верно для любых бинарных отношений R, S и Т.

ТЕОРЕМА 2.3. Для любых бинарных отношений R и

Доказательство. Для любых и у имеем

Следовательно, для любых бинарных отношений R и S.

n-местные отношения.

Обобщением понятия бинарного отношения является понятие -местного отношения.

ОПРЕДЕЛЕНИЕ, -местным отношением называется любое множество кортежей длины (т. е. любое множество упорядоченных наборов объектов).

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

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

ОПРЕДЕЛЕНИЕ. Пусть есть степень непустого множества Любое подмножество множества называется -местным отношением на множестве А, а число — рангом отношения.

В частности, одноместным отношением на А является любое подмножество множества А; трехместным (тернарным) отношением на А будет всякое подмножество множества т. е. любое множество упорядоченных троек элементов множества А.

Пусть — произвольный -местный предикат со свободными переменными . С ним можно связать -местное отношение

Отношение R называется графиком предиката

Представление бинарных отношений графами.

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

Существует простой способ представления бинарных отношений на конечных множествах ориентированными графами. Пусть А — непустое конечное множество и R — бинарное отношение на А, т. е. Представим элементы множества А точками на плоскости.

Каждой паре из R при поставим в соответствие ориентированное ребро (рис. 8), идущее от точки а к точке b. Паре из R поставим в соответствие петлю (рис. 9) с фиксированным направлением обхода (например, всегда против часовой стрелки).

Рис. 8

Рис. 9

Таким образом, бинарному отношению R ставится в соответствие следующая геометрическая фигура: точки плоскости, представляющие элементы множества и ориентированные ребра — каждой паре из R ставится в соответствие ориентированное ребро, идущее от точки а к точке b, или петля, если Такая геометрическая фигура называется ориентированным графом отношения R или просто графом отношения

Если в отношение R входит как пара , так и пара , то в графе отношения R есть два ребра, с вершинами а и b, ориентированные в противоположные стороны. В этом случае два ребра заменяются одним ребром с двумя стрелками (рис. 10).

Ребро с двумя стрелками называется неориентированным.

Рис. 10

Рис. 11

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

Пример. На рис. 11 изображен граф отношения