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

§ 1. Понятие отношения

Задать отношение — это значит указать, между какими объектами оно выполняется. Например, отношение «быть братом» на множестве людей полностью определено, если составлен список всех людей таких, что один из них брат второго.

Пример. Пусть Татьяна, Алексей и Михаил — дети одних родителей, перечисленные в порядке старшинства. Тогда на этом множестве отношение ∆ = «быть братом» выполнено для следующих пар:

(1)A ∆ T; (2) A ∆ M; (3) M ∆ T; (4) M ∆ A.

Впервом и третьем высказывании объекты нельзя менять местами. Это означает, что отношение «быть братом», вообще говоря, не симметрично. Если x — брат y, то y — брат x только в том случае, когда y — мужчина. Соотношение A ∆ A не выполняется, т. е.

данное отношение не рефлексивно.

Отношение ∆1 = «быть старше» выполнено на том же множестве для пар:

(1) T ∆1 A; (2) T ∆1M ; (3) A ∆1M .

Отношения можно устанавливать и между объектами разных множеств. Пусть M1 — множество учащихся некоторой школы, а

M2 — множество ее учителей. Тогда естественным образом получается отношение «x — ученик y» ( x M1, y M2 ). Ясно, что для

одного и того же x (ученика) это отношение может выполняться при различных y (и наоборот).

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

— 88 —

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

Хорошим примером трехместных или тернарных отношений являются алгебраические операции. Например, отношение «образовать сумму» имеет смысл для троек чисел (x, y, z): x + y = z.

Пропорциональность чисел x, y, z, u:

xz

y=u

есть отношение, выполненное длянекоторых четверокчисел x, y, z, u. Мы рассмотрим, прежде всего, бинарные отношения, которые

выполняются (или не выполняются) между двумя объектами. Пусть дано некоторое множество M. Рас-

смотрим	множество всех пар вида (x; y),	где
x M и	y M . Эти пары упорядочены,	т. е.

(x; y)≠(y; x). Множество всех таких упорядо-

ченных пар обозначается M M =M 2 и называется декартовым квадратом.

Отношением на множестве M мы будем называть подмножест-

во декартова квадрата A M 2 .

Содержательный смысл такого определения состоит в том, что

выбор подмножества A M 2 определяет, какие пары находятся в отношении A. Обозначение xAy (x находится в отношении A с y).

Множество пар (x; y) A называется графиком отношения. На рисунке изображен график отношения «быть братом».

Пусть теперь M — множество участников шахматного турнира. Введем отношение «быть победителем встречи». Будем считать, что если x победил y, то (x; y) A. Теперь выпишем турнирную таблицу, заменив «половинки» (т. е. очки, даваемые за

— 89 —

ничью) нулями. Не следует путать это отношение с отношением «сыграл лучше, чем». К примеру, γ победил α, но α сыграл лучше.

Мы фактически получили общий способ задания бинарного отношения на конечном множестве, который называется матричным. В общем виде этот способ можно описать так. Пусть M – n — элементное множество и A — отношение на нем. Перенумеруем элементы M натуральными числами от 1 до n. Построим теперь квадратную таблицу размером n n . На пересечении i-й строки и j-го столбца ставится 1, если выполнено отношение xi Ax j , и 0 — в

противном случае. Этот элемент матрицы обозначим aij . Таким образом,

	1, если x Ax		j	верно
a		i
	=			не верно.
ij	0, если x Ax		j
		i

Очевидно, что матрица aij содержит всю информацию о том,

для каких пар элементов из M выполнено отношение A.

Итак, отношение A на конечном множестве M может быть задано матрицей. Произвол состоит только в выборе нумерации на M. Легко видеть, что существует n! различных способов нумерации и, следовательно, n! матриц, описывающих данное отношение. Если задана матрица размером n n из нулей и единиц и выбрана нумерация на множестве M, то тем самым на M задается некоторое отношение A.

Матрица aij : aij ≡0 задает пустое отношение , которое не выполняется ни для какой пары.

Матрица

aij

: aij ≡1

задает полное отношение

M M , вы-

полненное для всех пар.

1, если i = j

Особую

роль

играет

матрица

δ

.

Этой

: δ =

ij

ij

0, если i ≠ j

матрице соответствует так называемое диагональное отношение E,

— 90 —

или отношение равенства xEy, которое выполняется, только если x = y (один и тот же элемент множества M). Полезно ввести также и антидиагональное отношение условием:

aij =1−δij .

Для пустого, полного, диагонального и антидиагонального отношений имеет место свойство — их матрицы не зависят от выбора нумерации элементов множества M.

Существует еще один важный способ задания бинарных отношений на конечных множествах. Изобразим элементы конечного множества M точками на плоскости. Если выполнено отношение xi Ax j , то проведем стрелку от xi к x j . Если xi Ax j , то у точки xi

нарисуем петлю, выходящую из xi и входящую в ту же точку. По-

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

Более общий случай отношений — отношения между элементами разных множеств. Такое отношение определяется как подмножество A множества M L . Здесь M L обозначает множество пар (x; y), где x M и y L. В математике рассматриваются

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

M1 M2 . .. Mn .

§ 2. Операции над отношениями

Исходя из операций над множествами, можно определить ряд полезных операций над отношениями. Будем для простоты считать, что все отношения заданы на одном множестве M.

— 91 —

Пересечением отношений A и B назовем отношение, определяемое пересечением соответствующих подмножеств. Ясно, что отношение xA∩By выполняется тогда и только тогда, когда одно-

временно xAy и xBy.

Пример. Пусть M — множество действительных чисел, A — отношение «быть не меньше», B — отношение «быть не равным», тогда A∩B есть отношение «быть большим». В самом деле

xAy x ≥b, xBy x ≠b, тогда xA∩By x >b.

Объединением отношений A и B называется отношение, определяемое объединением соответствующих подмножеств. Отношение xA By выполнено тогда и только тогда, когда выполнено хо-

тя бы одно из отношений xAy или xBy.

Пример. Пусть M — множество действительных чисел, A — отношение «быть больше», B — отношение «быть равным», тогда A B — это отношение «быть большим, либо равным».

Для отношений можно определить понятие включения. Мы будем писать A B , если множество пар, для которых выполнено первое отношение, содержится во множестве пар, для которых выполнено второе отношение. Соответственно, будем писать A B , если множество пар A является подмножеством пар B, но A≠B . Важно отметить, что если A B , то из xAy следует xBy, и наоборот, если из xAy следует xBy, то A B.

Очевидно, для любого отношения A

A U ,

где — пустое, а U — полное отношения.

Теперь введем некоторые операции над отношениями, не сводящиеся непосредственно к теоретико-множественным. Простейшая из них — обратное отношение. Если A — отношение на мно-

жестве M, то обратное отношение A−1 определяется условием:

xA−1 y yAx.

— 92 —

Примеры. (1) Если A — отношение «быть больше», то A−1 — отношение «быть меньше». В самом деле, запись x < y равносиль-

на записи y >x .

(2) Если A — отношение «быть мужем», то A−1 — отношение «быть женой».

Важную роль играет в теории отношений операция, обозначаемая как AB — произведение отношений. Эта операция определяется следующим образом: отношение xABy равносильно тому, что существует такое z M , для которого выполнены отношения

xAz и zBy.

Пусть A — отношение «быть женой», а B — «быть отцом». Что означает в этом случае отношение xABy? По определению существует такое z M , что «x — жена z» и «z — отец y», откуда следует, что «x — жена отца y», т. е. «x — мать или мачеха y».

Пусть A — отношение «быть братом», а B — «быть родителем». Тогда произведение AB есть отношение «быть братом одного из родителей», т. е. «быть дядей».

Рассмотрим теперь отношение «меньше» (A) и «больше» (B) на множестве целых чисел. Отношение xABy выполнено, если существует такое z, что

x < z и z > y.

Такое z существует всегда. Можно, например, взять z = x + y + 1. Таким образом, AB есть в данном случае полное отношение.

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

Определим еще одну важную операцию, которая называется

транзитивным замыканием отношения A и обозначается A . Если A — некоторое отношение на M, то транзитивное замыкание опре-

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

— 93 —

x =z0 , z1, z2 , ... , zn = y ,

причем между любыми двумя соседними элементами этой цепочки выполняется соотношение A. В частности, эта цепочка может состоять только из двух элементов (n = 1) x и y. Очевидно, что если

выполнено xAy, то выполнено и xAy, поэтому для всякого отноше-

ния A верно включение A A. Если цепочка состоит из трех элементов, то xAz и zAy, то есть xAAy. Продолжая процесс по индук-

ции, мы заключаем, что отношение xAy выполняется в том и

только в том случае, когда выполняется хотя бы одно отношение вида

xAAA...Ay =xAn y .

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

A= A A2 A3 ... An ...

Итак, транзитивное замыкание отношения A есть объединение всех степеней этого отношения.

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

0+0=0 0 0=0 0+1=1 0 1=0 1+0=1 1 0=0 1+1=1 1 1=1.

Эти правила отличаются от правил обычной арифметики тем, что сумма двух единиц дает единицу, но зато, оперируя над числами 0 и 1, мы не получаем никаких других чисел. Такая арифметика называется булевой.

Приступим к определению операций над матрицами и графами, соответствующим операциям над отношениями. Обозначим матри-

— 94 —

цы, соответствующие отношениям A и B, как aij и bij . Посколь-

ку aik bik =1 только когда aik =bik =1, то операция пересечения

отношений A и B задается матрицей C, в которой каждый элемент есть результат перемножения соответствующих элементов (стоящих на тех же местах) матриц A и B, т. е.

															cik =aik bik .
Например, если
A=				1	0	0				, B =				0	1	0				, то C = A∩B =				0	0	0
				1 1 0										0	0 1									0	0	0				.
				0	0 1									0	1	0								0	0	0

В терминах графов пересечение определяется так. Нарисуем множество вершин M и изобразим отношение A пунктирными стрелками, а отношение B — штриховыми стрелками. Теперь соединим направленными отрезками (со стрелкой) те и только те вершины, которым соответствуют оба предыдущих типа стрелок. Этот граф изображает пересечение отношений A и B.

Объединение отношений A и B, представляемых матрицами aik и bik , может быть аналогично выражено с помощью сложения матриц. Именно, обозначим через

cik =aik +bik

матрицу, элементы которой определяются условием

cik =aik +bik .

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

		1	0	1				0	1	1				1	1	1
aik	=	0 0 1			и	bik	=	0	0	1	, то	cik	=	0 0 1			.
		1	1	1				1 0		1				1	1	1

— 95 —

Легко видеть, что cik =1 тогда и только тогда, когда хотя бы одно из чисел aik или bik равно 1, значит, cik =1 равносильно то-

му, что xi A Byi .

Граф объединения отношений строится путем проведения стрелок между всеми вершинами, которые соединены стрелкой хотя бы одного типа.

Произведение отношений AB представляется так называемым произведением матриц, хорошо известным из алгебры. Эта операция определяется следующим правилом:

cik =ai1b1k +ai2b2k +ai3b3k + ... +ainbnk .

(*)

Пример. Если

a

=

1 1

и

b

=

0

0

, то

ik

0 1

ik

0

1

c

=

1 0+1 0

1 0+1 1

=

0

1

.

ik

0 0+1 0

0 0+1 1

0

1

Поясним это правило. Пусть выполнено соотношение xiABxk. Покажем, что величина cik , вычисленная согласно правилу (*), равна 1. Действительно, по определению произведения отношений существует элемент x j M такой, что xi Ax j и x j Bxk . Это значит,

что aij =bjk =1; поэтому aijbjk =1 . Но по правилам булевой арифметики, если одно из слагаемых (*) равно 1, то и вся сумма равна 1,

т. е. cik =1 .

Обратно, пусть cik =1 . Тогда среди слагаемых в (*) хотя бы одно равно 1. Пусть это будет aijbjk . Но произведение aijbjk равно 1 тогда и только тогда, когда одновременно aij =1 и bjk =1. Это означает, что выполняются оба соотношения xi Ax j и x j Bxk , т. е. xi ABxk

— 96 —