Свойства отношений и их интерпретация с помощью теории графов.

Бинарное отношение R на множестве X называется рефлексивным, если для любого элемента a X выполняется условие a R a:

( a X) a R a

Если отношение представлено с помощью графа, то рефлексивность этого отношения означает, что в каждой вершине графа обязательно имеется петля.

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

Бинарное отношение R на множестве X называется симметричным, если из a R b следует b R a:

( a, b X)(a R b b R a)

В графе симметричного отношения для каждой дуги из вершины x в вершину y имеется дуга из y в x. Матрица симметричного отношения симметрична относительно главной диагонали.

Объединение и пересечение любого семейства симметричных отношений снова являются симметричными отношениями.

Бинарное отношение R на множестве X называется транзитивным, если для любых трех элементов a, b, c X из aRb и bRc следует aRc:

( a, b, c X) (aRb & bRc aRc).

Определение отношения эквивалентности.

Бинарное отношение называется отношением эквивалентности, если отвечает условиям:

1. Рефлексивность: , ;

2. Симметричность: , то , ;

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

Если связан с , будем писать и говорить, что эквивалентен .