Отношения эквивалентности. Частичный порядок на множестве. Линейный порядок на множестве

Содержание

Слайд 2

Отношение эквивалентности

Отношения эквивалентности и отношения частичного порядка – это особые классы отношений,

Отношение эквивалентности Отношения эквивалентности и отношения частичного порядка – это особые классы
обладающих определенным набором свойств
Определение. Если бинарное отношение R на множестве A рефлексивно, симметрично и транзитивно, то отношение R называется отношением эквивалентности (≡).
Элементы, находящиеся в отношении эквивалентности (или просто эквивалентные элементы) обладают какими-либо общими признаками.

Слайд 3

Примеры отношений эквивалентности

Отношение равенства «=» на множестве чисел.
Отношение подобия на множестве фигур

Примеры отношений эквивалентности Отношение равенства «=» на множестве чисел. Отношение подобия на
плоскости. Например, на множестве треугольников подобные треугольники «имеют те же углы, что и …». Отношение подобия на множестве треугольников является отношением эквивалентности, так как: каждый треугольник подобен сам себе (рефлексивность); если один треугольник подобен другому, то и наоборот (симметричность); если один треугольник подобен второму, а второй третьему, то первый подобен третьему (транзитивность).
Отношение «иметь одинаковые остатки при делении на натуральное число m» на множестве целых чисел является отношением эквивалентности. Иными словами это «отношение сравнимости по модулю m».
Отношение «принадлежать одному виду» на множестве животных.
Отношение «быть родственниками» на множестве людей.
Отношение «быть одного роста» на множестве людей.

Слайд 4

Эквивалентность – основа классификаций

Всякое отношение эквивалентности осуществляет разбиение множества, в котором оно

Эквивалентность – основа классификаций Всякое отношение эквивалентности осуществляет разбиение множества, в котором
определено, на классы (т.е. на непересекающиеся подмножества), внутри которых элементы эквивалентны друг другу. Часто отдельные классы воспринимаются нами как новые объекты, понятия.
Применение отношений эквивалентности и разбиение множеств на классы эквивалентности является основой любой классификации.

Слайд 6

«Определить некоторое отношение эквивалентности между элементами множества А» значит разбить множество А

«Определить некоторое отношение эквивалентности между элементами множества А» значит разбить множество А
на непересекающиеся классы и считать эквивалентными только те элементы, которые попали в один и тот же класс.
Любые два элемента одного класса находятся в отношении R, а любые два элемента из различных классов не находятся в отношении R.
Так как пересечение отношений эквивалентности тоже является отношением эквивалентности, то это позволяет сводить классификацию по нескольким признакам к классификации по одному сложному признаку.

Слайд 8

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

Частичный порядок важен в тех ситуациях, когда мы хотим охарактеризовать

Отношения частичного порядка Частичный порядок важен в тех ситуациях, когда мы хотим
старшинство, т.е. когда при каких-то условиях один элемент множества превосходит другой.

Слайд 11

Диаграмма Хассе (Гессе)

Диаграмма Хассе (Гессе)

Слайд 12

Пример*

Пример*

Слайд 14

При построении диаграммы Хассе предшественников рисуем ниже элемента, которому они предшествуют и

При построении диаграммы Хассе предшественников рисуем ниже элемента, которому они предшествуют и
соединяем ребром только непосредственных предшественников

Слайд 15

Линейный порядок на множестве

Определение. Отношение частичного порядка на множестве А, при котором

Линейный порядок на множестве Определение. Отношение частичного порядка на множестве А, при
из любой пары элементов можно выделить предшествующий и последующий, называется линейным порядком на множестве A.
Иными словами то же определение: когда любые два элемента сравнимы между собой либо в одну сторону, либо в другую, т.е. когда верно либо R(a,b) либо R(b,a), то такое отношение называется линейным порядком, а само множество, на котором оно задано, называется линейно-упорядоченным множеством (или вполне упорядоченным множеством) или цепью.
Т.е. если все пары элементов множества А сравнимы относительно порядка R, то порядок R называется линейным.

Слайд 16

В примере (*) множество А частично упорядоченное (ЧУМ), но не линейного порядка

В примере (*) множество А частично упорядоченное (ЧУМ), но не линейного порядка
(т.к. не все пары можно расставить по порядку). Но в нем есть несколько линейно упорядоченных подмножеств относительно отношения «x делит y», каждому из которых соответствует цепочка ребер на диаграмме Хассе: {1,2,6,18}, {1,3,6,12}, {1,2,6,12}, {1,3,6,18}.
Также примером линейного порядка является лексикографическое (алфавитное) упорядочение слов в словаре. А сам порядок слов, удовлетворяющий этому отношению (лексикографическому упорядочению), является цепью.

Слайд 17

Применение частичного порядка

Данный аспект дискретной математики широко используется в сортирующих процедурах. Некоторые

Применение частичного порядка Данный аспект дискретной математики широко используется в сортирующих процедурах.
из сортирующих процедур требуют, чтобы элементы сортируемых множеств были линейно упорядочены. В этом случае они могут выдавать упорядоченный список.
Другие приложения используют частичный порядок, предполагая, что в любом частично упорядоченном множестве найдется минимальный элемент (не имеющий предшественников) и максимальный элемент (не имеющий последующих элементов).
В примере (*) в частично упорядоченном множестве А есть один минимальный элемент – единица, и два максимальных – 12 и 18.
Имя файла: Отношения-эквивалентности.-Частичный-порядок-на-множестве.-Линейный-порядок-на-множестве.pptx
Количество просмотров: 84
Количество скачиваний: 1