2. Свойства операций над отношениями

Приведем здесь список основных свойств операций над отношениями и докажем некоторые из них.

1) 2)

3) (R₁ o R₂) ^–1 = R₁ ^–1o R₂ ^–1. 4) (R₁ o R₂ ) o R₃ = R₁ o (R₂ o R₃).

5) (R₁  R₂ ) o R₃ = (R₁ o R₃ )  ( R₂ o R₃ ).

6) (R₁  R₂ ) o R₃  (R₁ o R₃ )  ( R₂ o R₃ ).

7)  а) если R₁  R₂ то R₁ o R₃  R₂ o R₃;

б) если R₁  R₂ то R₃ o R₁  R₃ o R₂;

в) если R₁  R₂ то R₁^–1 R₂^–1.

8. a) (R₁ R₂)^d = R₁^d  R₂^d; б) (R₁ R₂)^d = R₁^d  R₂^d; в) (R^d)^d = R.

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

Свойство 2.

Пусть пара (x, y)( R_k  ^–1. Тогда (y, x) R_k. Это означает, что найдется отношение R_j, что (y, x) R_j. Отсюда, по определению обратного отношения, (x, y)R_j^–1, а значит, (x, y)R_k^–1и (R_k^–1   R_k^–1.

Докажем обратное включение. Пусть (x,y) R_k^–1 Это означает, что найдется такое множество R_j, что (x,y)R_j^–1. Следовательно, (y, x)R_j  и (y, x) R_k , поэтому (x, y)( R_k ^–1. Значит,    R_k^–1  (R_k^–1.

Одновременное выполнение обоих включений означает равенство множеств, что и требовалось доказать.

Свойство 6.

Пусть (x, y)(R₁  R₂) o R₃. По определению композиции это означает, что найдется такое zA, что (x, z)(R₁  R₂) и (z, y)R₃. Первое включение возможно только тогда, когда одновременно выполнено (x, z)R₁ и (x, z)R₂. Это, в свою очередь, означает, с учетом (z, y)R₃, что одновременно (x, y) R₁ o R₃ и (x, y)R₂ o R₃, а, следовательно, (x, y)(R₁ o R₃)  (R₂ o R₃), что и доказывает требуемое соотношение.

Замечание. Покажем, почему неверно обратное включение. Пусть (x, y) (R₁ o R₃)  (R₂ o R₃), тогда (x, y) (R₁ o R₃) и (x, y) (R₂ o R₃). Первое включение означает существование такого элемента z₁ из A, что (x, z₁)R₁ и (z₁, y) R₃; второе – существование такого z₂A, что (x, z₂)R₂ и (z₂, y)R₃, причем необязательно z₁ = z₂. Значит, не всегда существует такой элемент z, что (x, z)R₁ и (x, z)R₂, а, следовательно, не будет принадлежности пересечению R₁ и R₂.

Свойство 7в.

Возьмём любую пару (x, y)R₁, что эквивалентно (y, х)R₁^–1. Пусть теперь R₁  R₂, т.е. из (x, y)R₁ следует (x, y)R₂. Перейдя к обратным отношениям, получим, что из (y, х)R₁^–1 вытекает (y, х)R₂^–1, что и означает требуемое свойство.

Свойство 8а).

Докажем предварительно равенство = .

Пусть (x, y) . Следовательно, (y, x) R или, другими словами, (y, x)R. Отсюда, ( x, y) R^–1, что означает  (x, y) . Если же (x, y)   , то (x, y) R^–1 и (y, x)R. Тогда (y, x)R или, что то же самое, (x,y)(R )^–1.

Для доказательства свойства 8а) воспользуемся доказанным равенством и известными свойствами операций над множествами и отношениями.

(R₁  R₂)^d = = =

= (R₁ R₂)^–1 =R₁^–1  R₂^–1 = R₁^d  R₂^d.

3. Способы задания отношений

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

1. Матричное задание. Оно используется когда А – конечное или счетное множество А = {x_i}. Тогда бинарное отношение R можно задавать с помощью матрицы R = {x_ij}, элементы которой определяются соотношением:

2. Табличное задание. Этим способом можно задавать произвольное n-арное отношение. Он используется, когда А_i – конечные или счетные множества А_i = {x_ij}. Строки таблицы соответствуют различным n-мерным элементам отношения, столбцы – наборам элементов из множеств А_i.

3. Задание с помощью графа. Для конечного или счетного множества А бинарное отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф – фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x_i, а наличие дуги, соединяющей вершины x_i и x_j, означает, что (x_i, x_j)R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.

Основные свойства графа.

1) Г(R^–1) получается из Г(R) изменением направления стрелок на противоположные.

2) Граф Г(АА) содержит дуги, соединяющие любую пару (x_i, x_j). Такой граф называется полным.

4. Задание верхними и нижними срезами. Этот способ может быть использован для любых множеств и бинарных отношений. Пусть на множестве А задано отношение R. Верхний срез G_R(x) отношения R в точке x А – это множество элементов yА таких, что (y, x)R, т.е.

G_R(x) = { yA | (y, x)R }.

Если рассматривать R как отношение предпочтения, то G_R (x) – это множество элементов, лучших, чем х.

Нижний срез H_R(x) отношения R в точке xА – это множество элементов yА, таких, что (x, y)R, т.е.

H_R(x) = { yA | (x, y)R }.

Свойства нижних и верхних срезов. Для любого хA и любого отношения R_i  AA выполняются соотношения.

1. а) G_RR(x) = G_R(x)  G_R(x); б) H_RR(x) = H_R(x)  H_R(x)

2. a) G_R(x) = A \ G_R(x); б) H_R(x) = A \ H_R(x).

3. a) G_R^–1(x) = H_R(x); б) H_R^–1(x) = H_R(x).

4. G_AA(x) = H_AA(x) = A.