Отношение эквивалентности. Фактормножество множества по отношению. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Отношение эквивалентности. Фактормножество множества по отношению.



Отношение -произвольное подмножество R множества An всех кортежей (упорядоченных наборов) вида (a1,..., an), где a1,..., an -элементы некоторого множества A; в этом случае говорят, что R есть n -мерное отношение на A.

Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Отношение R называется рефлексивным, если для любого элемента имеет место aRa.

Отношение R называется симметричным, если для любой пары из отношения aRb следует bRa.

Отношение R называется транзитивным, если для любых a, b, c из отношений aRb и bRc следует aRc.

Пусть на множестве M задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент и образуем класс C1 (подмножество M), состоящий из элемента a1 и всех элементов, эквивалентных ему в рамках данного отношения. Затем выберем элемент и образуем класс C2, состоящий из a2 и эквивалентных ему элементов. Продолжая эти действия, получим систему классов C1,C2,… (возможно, бесконечную) такую, что любой элемент из множества M входит хотя бы в один класс, то есть . Эта система обладает следующими свойствами: она образует разбиение множества M, то есть классы попарно не пересекаются; любые два элемента из одного класса эквивалентны; любые два элемента из разных классов не эквивалентны.

Построенное разбиение, то есть система классов – подмножеств множества M, называется системой классов эквивалентности по отношению R. Множество классов эквивалентности называется фактормножеством множества A по отношению R.

 

13. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного и полного порядка.

Отношение -произвольное подмножество R множества An всех кортежей (упорядоченных наборов) вида (a1,..., an), где a1,..., an -элементы некоторого множества A; в этом случае говорят, что R есть n -мерное отношение на A.

Бинарное отношение (двухмерное) R в множестве М, обладающее следующими свойствами: рефлексивности: (" aÎ M) ((a, aR); антисимметричности: (" a, bÎ M) (((a, bR) и (b, aR)╚ a=b); транзитивности: (" a, b, cÎ M) (((a, bR) и (b, cR)(r) (a, cR) называется отношением упорядоченности и может быть обозначено: ¸.

Бинарное отношение R в множестве М, обладающее следующими свойствами: антирефлексивности: (" aÎ M) ((a, a) Ï R); антисимметричности: (" a, bÎ M) (((a, bR) и (b, aR)╚ a=b); транзитивности: (" a, b, cÎ M) (((a, bR) и (b, cR)(r) (a, cR) называется отношением строгой упорядоченности и может быть обозначено: <.
Бинарное отношение R в множестве М, обладающее следующими свойствами: рефлексивности: (" aÎ M) ((a, aR); транзитивности: (" a, b, cÎ M) (((a, bR) и (b, cR)(r) (a, cR) называется отношением предпорядка. Отношение r называется отношением полного порядка, если оно транзитивно, антисимметрично и антирефлексивно (либо транзитивно и ассиметрично). Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные. Примеры: а) Отношения “ ” и “ ” являются отношениями нестрогого порядка, отношения “<” и “>” – отношениями строгого порядка (на всех основных числовых множествах). Оба отношения полностью упорядочивают множества и . б) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок. В нём, например, несравнимыми являются сотрудники различных структурных подразделений (отделов и т. п.). в) На системе подмножеств множества отношение включения “ ” задаёт нестрогий частичный порядок, а отношение строгого включения “ ” задаёт строгий частичный порядок. Например, , а и не сравнимы.

 

14. Диаграмма Хассе как способ задания отношения частичного порядка на множестве.

Отношения частичного порядка рефлексивность: (" aÎ M) ((a, aR); транзитивность: (" a, b, cÎ M) (((a, bR) и (b, cR)(r) (a, cR) антисимметричность: (" a, bÎ M) (((a, bR) и (b, aR)╚ a=b);

Отношение «какой элемент более предпочтителен» определено не для каждой пары.

Пусть aRb и a<b (b предпочтительней, чем а) Уровни иерархии: Нижн. уровни: эл-ты, являющиеся наименее предпочтительными. Выше уровнии: эл-ты, которые над ними доминируют. A={a,b,c} Множество булеан (множество всех подмножеств данного множества). Мощность булеана определяется как: . В данном случае она равна 8. Отношение быть подмножеством: транзитивное и антисимметричное (следовательно отношение порядка).

Диаграммы Хассе используют для наглядного представления ЧУМ. На а этих диаграммах изображают элементы ЧУМ, причем если элемент a предшествует элементу b, то a рисуют ниже b, и соединяют отрезком, если a непосредственно предшествует b.

 



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 191; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.204.177.148 (0.131 с.)