Отношение.

Df1. Отношением называют пару множеств , где

Рассматривают или имеют место отношения на некотором множестве М, а не просто отношение.

Пример:

М – множество элементов числовой оси

Ф: х = у

М² – декартовый квадрат М² = М М

- связывает элементы х и у

х у, через (=, >, < …)

можно обозначить любое взаимное отношение между двумя элементами:

х = у, х || у, х у, х у, х > у, х у, и т.д.

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

1. Полное отношение

2. Пустое отношение

, Ф черпает элементы из множества М.

3. Диагональное отношение

Е_М , где < х, у> Ф, х = у.

Над отношениями имеют место операции как над множествами, поскольку отношения – это множества ()

1) Рассмотрим операцию

, где Ф М²

, где М²

, где

Пример:

хφ у х = у

хψ у х > у

х(φ ψ)у| х(= >)у = х у

2) Рассмотрим операцию

, где Ф М²

, где М²

, где

3) Заданы 2 отношения φ и ψ, нужно найти их разность

, где

4)

5) Дополнение

Имеется некоторое отношение , где Ф М²

- дополнение отношения φ, получается путем изъятия из декартового квадрата множества точек графика

Рассмотрим операции над отношением, как над графиком

1. Инверсия:

^-1 , где Ф^-1 М²

2. Композиция:

, где Ф М²

, где М²

, где М²

x, y, z М

3. Импликация

Если рассматривать 2 отношения, связанные следующим образом

, где Ф М²

, где М²,

то говорят, что φ имплицирует ψ, если задав пару отношением φ находим такую же пару в отношении ψ, т.е. ()

4. Сужение

Если задано отношение φ, то попытаемся сузить на множество А.

φ _А – сужение отношения φ на множество А

Отношение эквивалентности

- задано отношение, оно называется эквивалентностью, если удовлетворяет следующим условиям:

1) Рефлексивность: х х

а) =, х = х

б) >, х> х

2) Симметричность: х у→ у х

а) = х = у→ у = х

б) > х > у у > х

3) Транзитивность:

Если удовлетворяет этим условиям, то говорят, что φ (эквивалентность).

Отношение эквивалентности собирает вокруг себя элементы одного класса.

х~y

…………….

……………

Классы обладают свойством собирать вокруг себя элементы, удовлетворяющие эквивалентности. С другой стороны между классами нельзя взять пару элементов, удовлетворяющих эквивалентности.

Отношение φ разбивает исходное множество М на классы. Легко видеть, что

а) , б)

Берем исходное множество М – фактор-множества: это множество М, разбитое на классы отношением φ.

Пример:

Студенты факультета разбиты на курсы. Внутри курса , но , т.е нельзя приравнять первокурсника к пятикурснику.

Некоторые дополнительные свойства отношений:

Пусть задано отношение , где Ф М²

1) Рефлексивность:

2) Симметричность:

3) Транзитивность:

4) Антисимметричность:

5) Связанность или связность:

Отношения типа порядка простейшие отношения >, <

Квазипорядок – якобы порядок, не отвечает свойству рефлексивности.