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

Лекция № 11

Т.к. любое отношение R есть подмножество множества пар W², то для отношений можно определить все те операции, которые определены для подмножеств фиксированного множества.

1.Операция вложения отношений:

Отношение R₁ вложено (включено) в отношение R₂ (R₁R₂) если множество пар, для которых выполнено отношение R₁, содержится во множестве пар, для которых выполнено отношение R₂.

2.Отношение называется дополнением отношения R, если оно выполняется для тех и только тех пар, для которых не выполняется отношение R.

= М² \ R

Или в матричной записи ()=1 - (R) для (i , j = )

В графе G() присутствуют только те дуги, которые отсутствуют в графе G(R).

- ⁺(x)= М \ R⁺(x) для любого хМ

- ^-(x)= М \ R^-(x) для любого хМ

Антидиагональное отношение является дополнением диагонального отношения Е.

3. Пересечением отношений R₁ и R₂ (R₁ R₂ )называется отношение, определяемое пересечением соответствующих подмножеств из МxМ.

4. Объединениемотношений R₁ и R₂ называется отношение, определяемое объединением соответствующих подмножеств из М*М.

5.Введем операцию обращения отношений:

Обратным к отношению R называется отношение R^-1, определяемое условием xR^-1yyRx

· (R^-1)= a_ji(R);

· граф G(R^-1) получается из графа G(R) изменением направлений всех дуг;

· (R^-1)⁺(х)= R^-(х) и (R^-1)^-(x) = R (x)

Результат последовательного выполнения операций дополнения и обращения не зависит от порядка, в котором они выполняются:

= ()^-1

Двойственным к R называется отношение R^d, определяемое формулой:

R^d = ;

Т.е. двойственным к R является отношение R^d, дополнительное к обратному к R.

Специальные свойства бинарных отношений

Рассмотрим свойства отношений, позволяющие выделить типы отношений, широко используемых при анализе систем и в процедурах принятия решений.

Свойство 1: отношение R является рефлексивным, если E R; т.е. если оно выполнено между объектом и самим xRx.

Например: “x имеет общий признак с y ”, “х похож на у ” и т.д.

На графе G(R,M) рефлексивного отношения каждая вершина х М имеет петлю.

В МАТРИЦЕ НА ДИАГОНАЛИ СТОЯТ 1.

Свойство 2: отношение R является антирефлексивным, если R E = Ø, т.е. если из соотношения xRy следует, что х у (отношение R может выполняться лишь для несовпадающих объектов).

Например: «х старше у», «операция у не может начаться, пока не закончится операция х и т.д.».

В матрице на диагонали стоят 0.

Свойство 3: отношение Rявляется симметричным, если R=R^-1, т.е. из выполнения соотношения xRy следует, что выполняется соотношение yRx.

Например: «х похож на у», “операция х несовместна с операцией у ” и т.д.

На графе симметричного отношения каждой дуге (х,у). Соответствует ориентированная ей навстречу дуга. Пару встречно ориентированных дуг можно заменить ребром, тогда симметричное отношение можно описывать неориентированным графом.

Свойство 4: отношение R является асимметричным, если Ø, т.е. из двух соотношений xRy и yRx по меньшей мере одно не выполнено.

Например: «х подчиняется у», «операция х выполнена раньше операции у» и т.д.

Если отношение R асимметрично, то оно антирефлексивно.

Доказательство: пусть для выполнено xRx. По определению обратного отношения это значит, что хR^-1x, но тогда что противоречит асимметричности.

Свойство 5: отношение R является антисимметричным, если , т.е. оба соотношения xRy и yRx выполняются одновременно только тогда, когда х=у.

Например: «операция х является частью операции у».

Свойство 6: отношение Rявляется транзитивным, если для любых элементов х, у, z из М из соотношений xRy, yRz следует соотношение xRz.

Через свойства 1 – 6 можно определить основные типы отношений:

Свойство 7: отношение связности (линейности). Отношение R называется линейным (связным) если для любых илиили или оба условия выполняются одновременно. (по крайней мере одно из них обязательно выполнено – в противовес антисимметричным).

В матрице (линейного)связного отношения или a_ij = 1 или a_ij = 1 для любых