Пример 2.10. Бинарные операции над множествами – это отображение B(U) £ B(U) 7!B(U); унарная операция дополнения – это отображение из B(U) в само себя (B(U) 7!B(U)).

Таким образом, бинарные операции – это тернарные отношения, унарные операции – это бинарные отношения. J

2.2Операции над отношениями

Вэтом разделе будем считать, что все отношения заданы на одном и том же множестве M. Пусть заданы отношения A µ M £M и B µ M £M. Так как отношения – это множества, то все операции над множествами применимы к отношениям.

Объединение отношений: A [ B.

Соотношение xA [ By выполняется тогда и только тогда, когда выполнено хотя бы одно из соотношений xAy или xBy:

xA [ By , xAy _ xBy.

Пересечение отношений: A \ B.

Соотношение xA \ By выполняется тогда и только тогда, когда одновременно выполнены xAy и xBy:

xA \ By , xAy ^ xBy.

Примеры 2.11.

1.Пусть M – множество вещественных чисел. A – отношение “быть не меньше”: x > y;

B – отношение “быть не равным”: x 6= y;

A \ B – отношение “быть строго больше": x > y.

2.A – отношение “быть больше": x > y;

B – отношение “быть равным": x = y;

A [ B – отношение “больше или равно": x > y.

3. Отношение A “быть севернее”, B – "быть западнее"; A \ B – быть “северо-западнее”. J

На отношения переносится и понятие включения µ и строгого включения ½. Например, < ½ 6 (отношение < является собственным подмножеством отношения 6). Из определения включения (или подмножества) следуют такие его свойства:

если A µ B, то из xAy логически следует xBy

(A µ B , xAy ) xBy) ,

и, обратно, если из xAy следует xBy, то A µ B

( xAy ) xBy , A µ B).

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

? µ R µ U,

где ? – пустое отношение, U = M £ M – полное (универсальное) отношение.

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

Определение. Отношение hA¡1; Mi, обратное к данному отношению hA; Mi, определяется условием:

xA¡1y , yAx (xA¡1y равносильно yAx).

Примеры 2.12.

1.Если A – отношение >, то A¡1 – отношение <.

2.Если A – отношение “быть родителем то A¡1 – отношение “быть ребенком". J

Определение. Произведение отношений AB определяется следующим образом:

xABy , 9z 2 M[xAz ^ zBy]

(соотношение xABy выполняется тогда и только тогда, когда существует такой z 2 M, что одновременно выполняются соотношения xAz и zBy).

Примеры 2.13.

1.Если A – отношение <, а B – отношение >, то xABy выполнено, если существует z такой, что x < z и z > y. Если M – множество целых чисел, то такой z существует всегда: можно взять для примера z = x + y + 1. Таким образом, AB есть, в данном случае, полное отношение.

2.Если отношение A есть “быть отцом”, то отношение AA есть отношение “быть дедом”. J

Степень отношения. В последнем примере была задана

степень отношения: A2 = AA. В общем случае Ak = AA ¢ ¢ ¢ A.

| {z }

k раз

Соотношение xAky выполнено тогда и только тогда, когда

54 Глава 2. Бинарные отношения

2.2.1 Выполнение операций над отношениями

Продемонстрируем на примере операции над отношения-

Для краткости здесь пары hx; yi представлены в виде xy. Операция умножения выполняется в точности по определению: соотношение xABy выполнено, если существует такой z, что xAz ^ zBy. Например, aABd, так как есть элемент

b, такой, что aAb ^ bBd, и так далее.

По существу, операция умножения отношений AB, представленных массивами, выполняется так: из отношения A выбирается очередная пара hx; zi, а из отношения B выбираются все пары вида hz; yi, и пары вида hx; yi включается в AB (без повторений).

Операция объединения выполняется еще проще: в A [ B включаются все пары из A и из B, за исключением повторяющихся.

В пересечение A \ B выбираются пары, общие для обоих отношений. Для нашего примера

пар hx; yi на пары hy; xi. Для нашего примера

Дополнение. Пусть задано отношение hA; Mi, то есть A µ M £ M; M £ M = U – универсальное (полное) отношение.

Дополнение отношения определяется как для обычного множества:

A = U n A = M £ M n A.

над множеством M.

M2 = fha; ai, ha; bi, ha; ci, ha; di, hb; ai, hb; bi, hb; ci, hb; di, hc; ai, hc; bi, hc; ci, hc; di, hd; ai, hd; bi, hd; ci, hd; dig.

A = fha; ai, ha; ci, ha; di, hb; ai, hb; bi, hc; ai, hc; ci, hc; di, hd; ai, hd; bi, hd; ci, hd; dig. J

Далее предполагается, что нумерация на множестве M уже выбрана, и что матрицы, соответствующие (при данной нумерации) отношениям A и B, обозначены kaijk и kbijk. Элементы матриц можно рассматривать как высказывания о

массив отношения A, матрица отношения A и граф отношения A, соответственно.

Д о к а з а т е л ь с т в о .

1. °) Из определения произведения следует, что выполнение соотношения xA(BC)y означает, что существует такой z, что выполняются xAz и z(BC)y. Из этого, в свою очередь следует, что существует такой w, что выполняются соотношения xAz и zBw и wCy. Из xAz и zBw следует xABw, а из xABw и wCy следует x(AB)Cy.

Такого рода цепочку рассуждений будем для краткости представлять в следующем виде:

8x; y[xA(BC)y] ) 9z[xAz ^ z(BC)y] ) ) xAz ^ 9w[zBw ^ wCy] )

) (xAz ^ zBw) ^ wCy ) x(AB)w ^ wCy ) x(AB)Cy,

где символ ) означает следует (логическое следствие); 9x[¢ ¢ ¢ ] – существует такой x, что высказывание в скобках [¢ ¢ ¢ ] истинно; ^ – логическая связка “и".

2. °( Аналогично,

x(AB)Cy ) 9z[x(AB)z ^ zCy] )

) 9w[xAw ^ wBz ^ zCy] ) xAw ^ w(BC)y ) xA(BC)y.

Из двух доказанных утверждений следует справедливость теоремы. £

Из ассоциативности произведения следует, что порядок выполнения операций произволен и в расстановке скобок нет необходимости: вместо A(BC) или (AB)C можно писать просто ABC.

Следующие две теоремы определяют "дистрибутивные" свойства произведения относительно объединения и пересечения.

Теорема 2.3 (A [ B)C = (AC) [ (BC)

(умножение распределяется относительно объединения).

Как показано на рисунке, может оказаться, что соотношения xAz^zCy, xBz^zCy и соотношения xAv^vCy, xBv^vCy не выполняются одновременно, т.е. A \ B = ?. £

Теорема 2.5 ¢A = A¢ = A; A? = ?A = ?.

Д о к а з а т е л ь с т в о . Докажем лишь первое утверждение:

¢A ) 8x; y[x¢Ay] ) 9z[x¢z ^ zAy] )

(из определения ¢ : z = x) x¢x ^ xAy ) xAy ) A.

A¢ ) 8x; y[xA¢y] ) 9z[xAz^z¢y] ) xAy ^y¢y ) xAy ) A. £

Несколько следующих теорем отражают свойства обра-

) y(A [ B)x ) x(A [ B)¡1y ) (A [ B)¡1 £

)yA¡1x ) xAy ) A.

2.°( A ) 8x; y[xAy] ) yA¡1x )

) x(A¡1)¡1y ) (A¡1)¡1. £

Отметим некоторые свойства отношения включения.

Теорема 2.10 Если A µ B, то A¡1 µ B¡1.

xAy влечет xBy, т.е. xAy ) xBy (см.стр. 51). Для обратного отношения yA¡1x ) yB¡1x. Это значит A¡1 µ B¡1 (свойство

включения).

2. °( A¡1 µ B¡1 ) 8x; y[yAx ) yBx] ) A µ B. £

Теорема 2.11 Если A µ B, то AC µ BC и CA µ CB.

Д о к а з а т е л ь с т в о . Из свойства отношения (стр. 51) A µ B следует 8x; z[xAz ) xBz]. Далее,

xACy ) [xAz ^ zCy ) xBz ^ zCy] ) AC µ BC.

Второе утверждение доказывается совершенно аналогично. £

b

Теорема 2.12 A µ A.

Д о к а з а т е л ь с т в о . Следует непосредственно из определения транзитивного замыкания: