Приведем изображение произведения в виде графа. Пусть отношение A изображено пунктирными стрелками, а отношение B — штриховыми. Соединим вершины xi и xk простой
стрелкой, если можно пройти из xi сначала в x j по пунктирной стрелке, а затем из x j в xk по
штриховой. Эти новые стрелки и изображают произведение отношений.
Обратное отношение A−1 в матричной форме выражается так. Если отношение A представляется матрицей 
aik 
, то A−1 изобра-
жается матрицей 
aki 
, т. е. в первой матрице надо поменять местами строки и столбцы. Другими словами, матрица для отношения
A−1 получается из исходной матрицы зеркальным отражением относительно главной диагонали.
|
1 0 1 |
|
|
1 |
0 0 |
|
|||
Пример. Если A → |
0 |
1 |
1 |
, |
то A−1 → |
0 |
1 |
1 |
. |
|
0 |
1 |
0 |
|
|
1 |
1 |
0 |
|
Чтобы из графа, изображающего отношение A, получить граф,
изображающий отношение A−1 , надо все стрелки поменять на противоположно направленные, а все петли оставить на месте.
§ 3. Алгебраические свойства операций
Поскольку операции пересечения и объединения отношений возникли из теоретико-множественных операций пересечения и объединения, то их свойства аналогичны. Рассмотрим алгебраические свойства остальных операций.
Операция обращения A−1 обладает важным свойством
(A−1 )−1 = A.
— 97 —
Действительно, x(A−1 )−1 y равносильно тому, что yA−1x , а это
в свою очередь равносильно xAy.
Операция умножения AB, в отличие от умножения обычных чисел, не перестановочна, т. е. AB ≠BA в общем случае.
Пример.
|
|
1 |
1 |
0 |
|
|
|
|
|
1 |
0 |
1 |
|
|
|
1 |
0 |
1 |
|
|
|||||||
|
|
0 1 0 |
|
|
|
1 0 |
0 |
= |
|
1 0 |
0 |
|
; |
||||||||||||||
|
|
1 |
0 1 |
|
|
|
|
|
1 |
1 |
0 |
|
|
|
1 |
1 1 |
|
|
|||||||||
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
1 0 |
|
|
|
|
|
1 1 1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
1 0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
= |
|
|
|
. |
||||||
|
|
|
|
1 |
1 1 |
|
|
|
|
|
|
|
1 |
0 1 |
|
|
|
|
|
1 1 1 |
|
|
|||||
Результирующие |
|
матрицы |
не |
|
|
одинаковы, значит, здесь |
|||||||||||||||||||||
AB ≠BA. В случае, когда AB = BA, |
|
говорят, что отношения A и B |
|||||||||||||||||||||||||
коммутируют (коммутативны).
Легко показать, что диагональное отношение E играет роль единицы, т. е.
AE = EA = A
для любого отношения A.
Пустое отношение играет роль нуля, т. е.
A=A=
для любого A. В самом деле, x Ay не может выполняться ни для какой пары (x; y), т. к. x z никогда не выполнено.
Для произведения отношений выполняется сочетательный закон, т. е.
(AB)C = A(BC).
Сочетательный закон позволяет отказаться от расстановки скобок в произведениях и писать, например, ABC вместо (AB)C или
A(BC).
— 98 —
Рассмотрим свойства, связывающие различные операции. 1. Правило обращения произведения.
Это свойство означает, что
(AB)−1 =B−1 A−1.
Действительно, x(AB)−1 y значит, что выполнено yABx, т. е. существует такой z, для которого выполнены соотношения yAz и zBx. Но, тогда выполнены xB−1z и zA−1 y , т. е. xB−1 A−1 y .
2. Операции объединения, пересечения и умножения связаны двумя законами. Первый из них
(A B)C =(AC) (BC).
Как видно, он соответствует закону для чисел (a + b)c = ac + bc. Доказательства этого закона мы здесь не приводим.
Второй закон этой «серии» имеет вид:
(A∩B)C (AC)∩(BC).
Докажем его. Пусть выполнено соотношение x(A∩B)Cy . Это
значит, существует такой z, что одновременно выполняются соотношения xAz, xBz и zCy. Тогда одновременно выполнены пары соотношений xAz и zCy, xBz и zCy. Иначе говоря, xACy и xBCy, т. е.
x(AC)∩(BC)y ,
что и требовалось.
Однако заменить знак включения равенством нельзя. Рассмотрим пример. Пусть на множестве
M ={x1, x2 , x3 , x4 }
выполнены только следующие соотношения: x1 Ax2 , x1Bx3 , x2Cx4 ,
x3Cx4 . Ясно, что A∩B = , значит, (A∩B)C = . С другой стороны, x1 ACx4 и x1BCx4 выполнены. Следовательно, выполнено и
— 99 —
соотношение x1 (AC)∩(BC)x4 , т. е. (AC)∩(BC)≠. В этом случае мы имеем строгое включение
(A∩B)C (AC)∩(BC).
Рекомендуем проверить на примерах следующие простые свойства отношений:
1)(A B)−1 = A−1 B−1;
2)(A∩B)−1 = A−1 ∩B−1;
3)если A B, то A B;
4)если A B, то A−1 B−1;
5)если A B, то AC BC;
6)A= A.
§ 4. Свойства отношений
Здесь мы рассмотрим некоторые важные свойства отношений, которые позволяют выделять группы отношений, такие как эквивалентность (одинаковость), толерантность (похожесть), упорядоченность и др.
Определение 1. Отношение A называется рефлексивным, если E A . Иначе говоря, отношение рефлексивно, если для любого x из множества M xAx.
Примеры рефлексивных отношений: «быть равным», «быть похожим на», «быть параллельным», «иметь общий признак с» и др.
С другой стороны, отношения типа «быть братом», «быть старше» не рефлексивны.
Рефлексивные отношения представляются матрицей, у которой по главной диагонали стоят единицы, прочие элементы могут быть любыми. Граф, изображающий рефлексивное отношение, в каждой вершине имеет петлю.
— 100 —
Определение 2. Отношение A называется антирефлексивным, если из xAy следует x ≠ y , т. е. A∩E = .
Антирефлексивное отношение может выполняться лишь для несовпадающих объектов. Отношения «быть братом», «быть старше» — антирефлексивны. Матрица, представляющая антирефлексивное отношение, имеет нули на главной диагонали, а граф не содержит петлей.
Определение 3. Отношение A называется симметричным, если A A−1, т. е. если выполнено xAy, то выполнено и yAx.
Примерами таких отношений служат «быть похожим на», «быть равным», «быть одинаковым с», «быть родственником». В матрице, представляющей симметричное отношение, элементы, симметрично расположенные относительно главной диагонали, равны:
aik =aki .
В соответствующем графе вместе с каждой стрелкой, идущей из xi в xk , существует и противоположно направленная стрелка.
Поэтому в таком графе можно вообще не обозначать стрелки, а рисовать только петли и отрезки, соединяющие разные вершины.
Теорема 1. Отношение A симметрично тогда и только тогда, когда
A= A−1 .
Доказательство: По определению A A−1 , но тогда A−1 (A−1 )−1 = A . Сравнивая A A−1 и A-1 A, приходим к вы-
воду, что A= A−1 .
Определение 4. Отношение A называется асимметричным, если
A∩ A−1 = .
Это значит, что из двух соотношений xAy и yAx, по крайней мере, одно не выполнено.
Элементы матрицы асимметричного отношения, симметричные относительно главной диагонали, либо оба равны нулю, либо равен
— 101 —
нулю один из них, т. е. aik aki =0 . В соответствующем графе нет
двойных стрелок.
Можно показать, что если отношение A асимметрично, то оно и антирефлексивно. Действительно, пусть вопреки утверждению су-
ществует такой x, что xAx. Тогда xA−1x , т. е. xA∩ A−1x. Но, в та-
ком случае, A∩ A−1 не может быть пустым, значит, отношение A не асимметрично.
Последнее доказанное утверждение означает, что граф асимметричного отношения не может иметь петель.
Определение5. Отношение A называется антисимметричным, если
A∩ A−1 E.
Другими словами, соотношения xAy и yAx выполняются только тогда, когда x = y.
Для элементов матрицы это означает, что всегда, когда i ≠k
aik aki =0 .
Определение 6. Отношение A называется транзитивным, если
A2 A .
Раскроем это алгебраическое условие. Получим: если xAz и zAy выполнены, то выполнено и xAy.
Пример. Рассмотрим отношение «быть больше» на множестве действительных чисел. Это отношение транзитивно, т. к. если x > z
и z > y, то x > y, то есть если xA2 y , то xAy. Это согласуется с фор-
мальным определением.
Свойство транзитивности хорошо иллюстрируется с помощью графа. Если точки x и y соединены путем, состоящим из нескольких стрелок, то существует стрелка, непосредственно идущая из точки x к точке y.
Можно показать, что если отношение A транзитивно и рефлек-
сивно, то A2 = A . Действительно, если A транзитивно, то A2 A по определению. Но если A рефлексивно, то xAx верно, но тогда
верно и xA2 x , т. к. xA2 x равносильно xAz и zAx. Но xAx, следовательно, xAx и xAx, откуда вытекает xA2 x .
— 102 —