logo
КЛ

§ 5. Бинарное отношение эквивалентности

Понятия “отношение эквивалентности”, “фактор–множество“, “классы эквивалентности” используются при построении математической модели некоторой реально функционирующей сложной системы. С формальной точки зрения модель есть некоторое фактор – множество элементов моделируемого объекта относительно некоторого отношения эквивалентности, заданного на исходной системе. При исследовании возникает задача выбора существенных свойств, деталей, признаков моделируемого объекта. Отношение эквивалентности, с одной стороны, отождествляет второстепенные, несущественные признаки и свойства, и, с другой – выделяет в качестве представителей классов эквивалентности основные свойства. Если моделируемый объект представлен в виде композиции элементов некоторого базисного множества, то вопрос о соотношении модели и ее прообраза разрешается на основе информации об элементах, на которых вводится отношение эквивалентности – либо это сами элементы базисного множества, либо некоторые подмножества элементов, либо подмножества множества подмножеств элементов.

Бинарное отношение R в множестве М , обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности и обозначается ~ , то есть для имеет место:

1. каждый элемент эквивалентен сам себе: x ~ x ;

2. если х эквивалентен у, то и у эквивалентен х: если х ~ у, то у ~ х;

3. если х эквивалентен у, а у эквивалентен z , то х эквивалентен z: если х ~ у, а у ~ z , то х ~ z .

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

Классом эквивалентности К (т) элемента т называют множество всех элементов mi , каждый из которых находится с этим элементом в отношении эквивалентности, т.е.

K (m) = {mi / mi ~ m}.

Разбиением множества М называется семейство непустых попарно непересекающихся подмножеств (классов), объединение которых совпадает с М .

Проиллюстрируем процедуру построения разбиения множеств.

Пусть на множестве М задано отношение эквивалентности R . Осуществим следующее построение:

- выберем элемент т1 и образуем подмножество (класс эквивалентности), состоящий из элемента т1 и всех элементов, эквивалентных т1 : К (т1) ;

- выберем элемент , и образуем подмножество (класс эквивалентности) элемента т2 : К (т2) , состоящий из элемента т2 и всех элементов, эквивалентных ему , и т.д. В результате такого построения получится система классов эквивалентности К (т1), К (т2), … (возможно бесконечная) такая, что любой элемент из множества М входит хотя бы в один класс, т.е. .

Данная система обладает следующими свойствами:

1. классы эквивалентности попарно не пересекаются:

Ø;

2. любые два элемента из одного класса эквивалентны;

3. любые два элемента из разных классов неэквивалентны.

Построенное разбиение (система классов) называется системой классов эквивалентности по отношению R .

Если бинарное отношение является бинарным отношением эквивалентности, то его матрицу смежности можно привести с помощью перестановок строк (столбцов) к виду

С= .

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