double arrow

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


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

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

1) 2)

3) (R1 o R2) –1 = R1 –1o R2 –1. 4) (R1 o R2 ) o R3 = R1 o (R2 o R3).

5) (R1 È R2 ) o R3 = (R1 o R3 ) È ( R2 o R3 ).

6) (R1 Ç R2 ) o R3 Í (R1 o R3 ) Ç ( R2 o R3 ).

7) а) если R1 Í R2 то R1 o R3 Í R2 o R3;

б) если R1 Í R2 то R3 o R1 Í R3 o R2;

в) если R1 Í R2 то R1–1Í R2–1.

8) a) (R1È R2)d = R1d Ç R2d; б) (R1Ç R2)d = R1d È R2d; в) (Rd)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) o R3. По определению композиции это означает, что найдется такое zÎA, что (x, z)Î(R1 Ç R2) и (z, y)ÎR3. Первое включение возможно только тогда, когда одновременно выполнено (x, z)ÎR1 и (x, z)ÎR2. Это, в свою очередь, означает, с учетом (z, y)ÎR3, что одновременно (x, y)Î R1 o R3 и (x, y)ÎR2 o R3, а, следовательно, (x, y)Î(R1 o R3) Ç (R2 o R3), что и доказывает требуемое соотношение.

Замечание. Покажем, почему неверно обратное включение. Пусть (x, y) Î(R1 o R3) Ç (R2 o R3), тогда (x, y) Î(R1 o R3) и (x, y) Î(R2 o R3). Первое включение означает существование такого элемента 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)Î . Если же (x, y) Î , то (x, y) ÏR–1 и (y, x)ÏR. Тогда (y, x)Î`R или, что то же самое, (x,y)Î(`R )–1.

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

(R1 È R2)d == =

= (`R1 Ç`R2)–1 =`R1–1 Ç R2–1 = R1d Ç R2d.


Сейчас читают про: