2014-02-18
800
Приведем здесь список основных свойств операций над отношениями и докажем некоторые из них.
1) Ç Rk -1=(Ç Rk) -1.k k
2) È Rk -1=(È Rk ) -1. k k
3) (R1 o R2) -1 = R1 -1o R2 -1.
4) (R1 o R2 )oR3 = R1o(R2 o R3).
5) (R1 È R2 )oR3 = (R1 oR3 )È(R2o R3 ).
6) (R1 Ç R2 )oR3 Í (R1 oR3 )Ç(R2o R3 ).
7) а) если R1Í R2 то R1o R3 ÍR2o R3;
б) если R1 Í R2 то R1-1Í R2-1;
в) если R1 Í R2 то R3oR1 Í R3oR2.
8) a) (R1È R2)d = R1d ÇR2d;
б) (R1Ç R2)d = R1d ÈR2d;
в) (R d)d = R.
ДОКАЗАТЕЛЬСТВО.
Свойство 2.
Пусть пара (x, y)Î(È Rk) -1. Тогда (y, x)ÎÈ Rk. Это означает, что найдется отношение Rj, что (y, x)Î Rj. Отсюда, по определению обратного отношения, (x, y)ÎRj-1, а значит, (x, y)ÎÈRk-1и (ÈRk)-1 Í È Rk-1.
Докажем обратное включение. Пусть (x,y)Î Rk-1 Это означает, что найдется такое множество Rj, что (x,y)ÎRj-1. Следовательно, (y, x)ÎRj и (y, x)Î ÈRk, поэтому (x, y)Î(È Rk)-1. Значит, È Rk-1 Í (ÈRk)-1.
Одновременное выполнение обоих включений означает равенство множеств, что и требовалось доказать.
Свойство 6.
Пусть (x, y)Î(R1 ÇR2)oR3. По определению композиции это означает, что найдется такое zÎA, что (x, z)Î(R1ÇR2) и (z, y)ÎR3.
|
|
|
Первое включение возможно только тогда, когда одновременно выполнено (x, z)ÎR1 и (x, z)ÎR2. Это, в свою очередь означает, с учетом (z, y)ÎR3, что одновременно (x, y)ÎR1oR3 и (x, y)ÎR2oR3, а, следовательно, (x, y)Î(R1oR3)Ç(R2oR3), что и доказывает требуемое соотношение.
ЗАМЕЧАНИЕ. Покажем, почему неверно обратное включение. Пусть (x, y)Î(R1oR3)Ç(R2oR3), тогда (x, y) Î(R1oR3) и (x, y) Î(R2oR3). Первое включение означает существование такого элемента z1 из A, что (x, z1)ÎR1 и (z1, y)ÎR3, второе - существование такого z2ÎA, что (x, z2)ÎR2 и (z2, y)ÎR3, причем необязательно z1=z2. Значит, не всегда существует такой элемент z, что (x, z)ÎR1 и (x, z)ÎR2, а, следовательно, не будет принадлежности пересечению R1 и R2.
Свойство 7б.
Возьмём любую пару (x, y)ÎR1, что эквивалентно (y, х)Î ÎR1-1. Пусть теперь R1ÍR2, т.е. из (x, y)ÎR1 следует (x, y)ÎR2. Перейдя к обратным отношениям, получим, что из (y, х)ÎR1-1 вытекает (y, х)ÎR2-1, что и означает требуемое свойство.
Свойство 8а.
Докажем предварительно равенство 
=
Пусть (x, y)Î . Следовательно, (y, x) Î`R или, другими словами, (y, x)ÏR. Отсюда, (x, y)Ï R-1, что означает и (x, y)Î`R-1. Если же (x, y) Î`R-1, то (x, y)ÏR-1 и (y, x)ÏR. Тогда (y, x)Î`R или, что то же самое, (x,y)Î(`R)-1.
Для доказательства свойства 8а воспользуемся доказанным равенством и известными свойствами операций над множествами и отношениями.
(R1ÈR2)d = (R1ÈR2)-1 = R1ÈR2-=(`R1Ç`R2) =`R1-1 Ç R2-1 = R1d Ç R2d.
Способы задания бинарных отношений
Традиционное задание отношений аналогично тому, как это принято в теории множеств, что не всегда удобно. Поэтому, наряду с таким заданием, применяются другие способы.
|
|
|
1. Матричное задание. Оно используется когда А - конечное
множество А={xi}. Тогда отношение R можно задавать с помощью матрицы R={xij}, элементы которой определяются соотношением:
 |
2. Задание с помощью графа.
Для конечного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть xi, а наличие дуги, соединяющей вершины xi и xj, означает, что (xi,xj)ÎR. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.
Основные свойства графа.
1) Г(R-1) получается из Г(R) изменением направления стрелок
на противоположные.
2) Граф Г(А´А) содержит дуги, соединяющие любую пару (xi, xj). Такой граф назывыется полным.
3. Задание верхними и нижними срезами.
Этот способ может быть использован для любых множеств и отношений. Пусть на множестве А задано отношение R. Верхний срез GR (x) отношения R в точке x ÎА - это множество элементов yÎА таких, что (y, x)ÎR, т.е.
GR(x) = { yÎA | (y, x)ÎR }.
Если рассматривать R как отношение предпочтения, то GR (x) – это множество элементов, лучших чем х.
Нижний срез HR(x) отношения R в точке xÎА - это множество элементов yÎА, таких, что (x, y)ÎR, т.е.
HR(x) = { yÎA | (x, y)ÎR }.
Свойства нижних и верхних срезов.
Для любого хÎA и любого отношения Ri ÍA´A выполняются соотношения.
1. а) GRÇR(x)=GR(x)ÇGR(x); б) HRÇR(x)=HR(x)ÇHR(x)
2. a) G`R(x) = A\GR(x); б)H`R(x) = A\HR(x).
3. a) GR-1(x) = HR(x); б) HR-1(x) = HR(x).
4. GA´A(x) = HA´A(x) = A.
