Композиция бинарных отношений

Пусть заданы три множества X , Y , Z и два отношения R Ì X * Y и S Ì Y * Z.

Композицией двух отношений R и S называют такое отношение T Ì X * Z , которое состоит из всех таких параметров <x , z>, для которых существует такой элемент y, что пара <x , y > Î R и < y , z > Î S .

Обращение (симметризация)

Отношение, симметричное (обратное) некоторому отношению R = X *Y обозначается R ^-1 и является подмножеством R ^-1 Ì Y * X, образованное парами <y , x > , что < x , y > Î R .

Кроме того, к отношениям можно принимать все теоретико-множественные операции.

Общие свойства отношений.

Рефлексивность – свойство отношений, когда каждый элемент множества находится в данном отношении к самому себе.

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R рефлексивно, если для любого х Î Х имеет место х R х.

Например, отношения между числами в выражениях а = а или а ³ а обладают свойством рефлексивности, так как для каждого а есть пара (а, а), находящаяся в данном отношении.

Антирефлексивность - свойство отношений, когда ни какой элемент множества не находится в данном отношении к самому себе.

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R антирефлексивно, если для любого х Î Х не имеет место х R х.

Например, отношения между числами в выражениях а > c обладает свойством антирефлексивности, так как нет ни одной пары (а, а), находящейся в этом отношении.

Симметричность – свойство отношений, когда наличие этого отношения между парой элементов x _i и x _j, влечет за собой и наличие этого же отношения между элементами обратной пары ( x _j , x_i).

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R симметрично, если

( x _i , x _j ) Î R « ( x _j , x _i ) Î R .

Например, отношение неравенства на множестве чисел обладает свойством симметричности, так как если а ¹ с, то и с ¹ а.

Асимметричность - свойство отношений, когда наличие этого отношения между парой элементов x _i и x _j, влечет за собой отсутствие этого отношения между элементами обратной пары ( x _j , x _i).

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R асимметрично, если

( x _i , x _j ) Î R « ( x _j , x _i ) Ï R , т.е. R Ç R ^-1 = Æ

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

Например, отношения между числами в выражениях а > c обладает свойством асимметричности, так как если для пары (а, с) справедливо отношение а > c, то для пары (с, а), отношение с > а не имеет места.

Антисимметричность - свойство отношений, когда наличие этого отношения между парой элементов (x _i , x _j) и наличие этого же отношения у обратной парой (x _j , x _i), возможно только в том случае, если x _i ,= x _j_..

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R антисимметрично, если

( x _i , x _j ) Î R & ( x _j , x _i ) Î R « x _i ,= x _j

Например, отношение между числами (а, с) в выражении а ³ с обладает свойством антисимметрии, так как отношение « ³ » справедливо и для обратной пары только в том случае, если а = с.

Транзитивность – свойство отношения, состоящее в том, что если первый элемент находится в данном отношении ко второму элементу, а второй элемент находится в этом же отношении к третьему элементу, то первый элемент находится в этом отношении к третьему элементу.

Пусть R – бинарное отношение на множестве Х, т.е. R = X ´ Х.

Отношение R транзитивно, если

( x _i , x _j ) Î R & ( x _j , x _к ) Î R ® ( x _i , x _к ) Î R .

Например, отношение между числами (а, b) в выражении или а > b обладает свойством транзитивности, так как если отношение « > » справедливо для пары а > b и справедливо для пары b > c, то оно справедливо и для пары а > c.

Сложные отношения

Эквивалентные отношения обладают свойствами рефлексии, симметрии и транзитивности. Действительно, эквивалентность означает неразличимость объектов по принятым показателям. Для обозначения отношения эквивалентности используется символ º.

Отношение строго порядка обладает свойствами антирефлексии и транзитивности. Для обозначения отношения используется символ >.

Отношение квазипорядка обладает свойствами рефлексии и транзитивности. Для обозначения квазипорядка используется символ ³. Например, если Oi ³ Oj, то говорят, что объект Oi не хуже объекта Oj.

Если любые два объекта из множества О сравнимы по отношениям строго порядка или квазипорядка , то добавляют слово “полный” или “линейный”: полный строгий порядок или полный квазипорядок.

Вопросы для самопроверки к главе 3

1. Определение множества.

2. Операции над множествами.

3. Понятие универсума, подмножества, пустого множества, дополнения.

4. Свойства операций над множествами, равносильные преобразования.

5. Декартово произведение множеств.

6. Бинарные отношения.

7. Свойства бинарных отношений.

Упражнения к главе 3

1. Какие из ниже приведенных соотношений не верны и почему?

a) x Î {2, 4, x , y , { x , a }}

b) Î { x , {2, 3}, a }