Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Замыкания отношений




Если отношение на множестве M не обладает тем или иным свойством, то его можно попытаться продолжить до отношения R*, которое будет им обладать. Для этого необходимо присоединить некоторые упорядоченные пары к подмножеству . Исходное множество R будет подмножеством в R*. В случае, если вновь построенное множество R* будет минимальным среди всех расширений R с выделенным свойством, то оно будет являться замыканием R относительно данного свойства.

Пример 7. Пусть A . Отношение R на A задано упорядоченными парами: R . Отношение не рефлексивно, не симметрично и не транзитивно. Найдите соответствующие замыкания.

Замыкание относительно рефлексивности должно содержать все пары вида (a,a). Поэтому искомое замыкание имеет вид: R* (добавленные пары отделены подчеркиванием).

В отношение R* добавлены пары (3,3) и (5,5); пара (1,1) уже была в отношении R. Теперь имеются все пары вида (a,a): (1,1), (3,3), (5,5). Получено рефлексивное замыкание.

Замыкание по симметричности должно содержать все пары, симметричные исходным. Построение замыкания целесообразно свести в таблицу.

Таблица 2

№ п/п Примечание
  1,3 3,1 нет Добавить пару (3,1) в отношение R
  1,5 5,1 да
  3,5 5,3 нет Добавить пару (5,3) в отношение R

 

Как видно из таблице 2 в отношение R следует добавить две пары (3,1) и (5,3).

Замыкание по симметричности будет иметь вид R* .

Чтобы выполнить замыкание по транзитивности, необходимо выполнить несколько шагов.

На первом этапе составляется таблица 3.

 

Таблица 3

№ п/п Примечание
  5,1 1,3 5,3 нет добавить пару (5,3) в отношение R
  3,5 5,1 3,1 нет добавить пару (3,1) в отношение R
  5,1 1,5 5,5 нет добавить пару (5,5) в отношение R

 

Из анализа таблицы видно, что следует добавить пары (5,3), (3,1), (5,5) в отношение R. Полученное замыкание имеет вид: .

 

Второй этап. Из анализа видно, что возникло сочетание пар (3,1) и (1,3), поэтому отношение R* должно содержать пару (3,3). Следовательно, .

 

Теперь все необходимые пары добавлены. Метод, приведенный выше, достаточно трудоемок и состоит в переборе практически всех пар.

Можно познакомиться с методом построения замыкания по транзитивности по матрице достижимости ориентированного графа. (учебная дисциплина «Теория вероятностей и математическая статистика»).

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

 

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

Например, отношение равенства является отношением эквивалентности. Действительно, пусть M – произвольное множество. Введем бинарное отношение. Т.к. для всякого a, то R рефлексивно. Так как из равенства следует, что для всех a и b, то R симметрично. Так как из того, что и следует, что для любых a, b, c, то R транзитивно.

Без доказательства приводятся еще некоторые примеры отношения эквивалентности: отношение «имеет тот же возраст» на множестве всех людей; «имеет один и тот же остаток при делении на 3» на множестве натуральных чисел. Можно привести и другие примеры. Все они наводят на мысль, что если на множестве задано отношение эквивалентности, то все его элементы можно разбить на непересекающиеся подмножества. Все элементы в любом из таких подмножеств эквивалентны друг другу.

Разбиением множества A называется совокупность непустых подмножеств A1, A2, …, An множества A, удовлетворяющая следующим требованиям:

1)

2)

Таким образом, отношение эквивалентности разбивает множество на непересекающиеся подмножества, которые называются классами эквивалентности.

Диаграмма Венна разбиения множества A на пять блоков (подмножеств) показана на рис.9.

Рис.9

 

Подмножества изображены не заходящими одно на другое, т.к. они не могут иметь общих элементов. Множество классов эквивалентности множества A называется фактор - множеством.

 

 




Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 2628; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.014 сек.