Понятие композиции отношений. Виды отношений

Пусть - отношение на
, а - отношение на
Композицией отношений

Это множество обозначается

Пример:

Даны, множества
A = {1,2,3}, B = {x,y}, С = {♦,

Тогда

Теорема.
Композиция отношений ассоциативна;
т.е. если А, В, и С – множества

Виды отношений

В зависимости от того, какими
свойствами обладает отношения, они
делятся на три вида;

Бинарное отношение R на множестве
A2 называется отношением
эквивалентности, если оно обладает
свойствами рефлексивности,
симметричности

Эквивалентные элементы
(т.е. находящиеся в отношении
эквивалентности), как правило, обладают
какими-то общими признаками.

Пример

А = {1,2,3,4,5,6},
R = {(1,1), (2,2), (3,3), (4,4),(5,5), (6,6),
(1,2), (1,4), (2,1),

Если на множестве задано отношение эквивалентности, то все его элементы можно

Разбиением множества А называется совокупность попарно непересекающихся непустых подмножеств А1, А2,

Пусть а А, и R отношение эквивалентнос
ти на А А. Пусть

Пример

А = {1,2,3,4,5,6},
R = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6),
(1,2),

Класс эквивалентности по отношению к R
получаются путем определения класса
эквивалентности каждого элемента
множества

Имеется только три различных класса
эквивалентности

Выводы

Любой элемент класса эквивалентности
порождает класс эквивалентности: если
.
На основании этого свойства

Каждый класс эквивалентности
содержит по крайней мере, один элемент,
в силу рефлексивности отношении.
Множество

Отношение эквивалентности разбивает
множество А на попарно непересекающиеся
классы эквивалентных элементов, таким
образом,

1. Всякое разбиение множества А на классы
задает на множестве А отношение
эквивалентности.
2. Всякое отношение

Отношение порядка

Отношение R на множестве A2
называется отношением частичного
порядка, если оно обладает свойствами
рефлексивности,

Множество А вместе с заданным на нем
отношением частичного порядка R
называется частично

Если для двух элементов x и y выполняется x ≤ y,

Однако, если х предшествует у, и не существует таких элементов z,

Элементы а и b частично упорядоченного множества (А, ≤) называется сравнимыми,

Другими словами линейным порядком на множестве А называется отношение частичного порядка,

Пример линейного порядка: «≤» на
множестве вещественных чисел,
лексикографическое упорядочение слов в
словаре.

Если каждые два элемента частично
упорядоченные множества (А, ≤)
сравнимы, то (А, ≤)

Простым примером отношения порядка является отношение, задаваемое обычным неравенством ≤ на

Рассмотрим на множестве A всех
сотрудников некоторого предприятия. Отношение, задается следующим
образом: сотрудник

Назовем такое отношение «быть
начальником».
Отношение «быть начальником»
является отношением порядка.

Поскольку существуют такие пары
сотрудников x и y, для которых не
выполняется ни

Вершины графа изображают элементы
ЧУ-множества А, и если x y., то
вершина х

Пример:

Дано отношение «…делитель…»
определяет частичный порядок на
множестве А = {1,2,3,6,12,18}. Составить таблицу

Диаграмма Хассе