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

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

Свойства отношений на множестве

Операции над отношениями

Заметим, что операции объединения, пересечения и дополнения бинарных отношений удовлетворяют законам идемпотентности, коммутативности, ассоциативности, поглощение, инволюции и законам де Моргана.

Над отношениями могут также осуществляться другими алгебраические операции:

6) Произведение (композиция) отношений

Для указанных отношений справедливы следующие утверждения:

Отношение R называется отношением эквивалентности, если R рефлексивно, симметрично и транзитивно. Это отношение обозначается символами E и

Отношение эквивалентности характеризует одинаковость объектов. Однако существуют ситуации, в которых требуется оценить сходство объектов. Этой цели служит отношение толерантности. Отношение, удовлетворяющее свойствам рефлексивности и симметричности, называется отношением толерантности.

В ряде случаев требуется указать старшинство, важность, “первичность” и другие подобные свойства объектов. Для этого служат различные виды отношения порядка.

Отношение называется предпорядком или квазипорядком, если R рефлексивно и транзитивно.

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

Отношение строгого порядка (полного или частичного) обозначается символом

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

Источник

Конспект урока математики «Отношение эквивалентности, порядка и толерантности»

Ищем педагогов в команду «Инфоурок»

КОГОАУ СПО «Яранский государственный технологический техникум»

Методическая разработка урока по теме

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

Дисциплина «Дискретная математика»

Специальность 09.02.04 «Информационные системы

Недопёкина Галина Анатольевна

— изучить понятия отношений эквивалентности, порядка, толерантности;

— научить распознавать каждое из отношений;

— способствовать развитию познавательной активности, мышления, творческих способностей.

Оборудование: презентация, ноутбук, телевизор, толковый словарь Ожегова, тест на 2 варианта на каждого обучающегося.

Актуализация опорных знаний (самостоятельная работа с тестом) .

Какое отношение является

а)

б)

в)

г)

отношение R на множестве X называется рефлексивным, если …

отношение R на множестве X называется антисимметричным, если

отношение R на множестве X называется симметричным, если…

отношение R на множестве X называется транзитивнным, если…

б) о любом элементе множества X можно сказать, что он находится в отношении R с самим собой.

в) из того, что элемент x находится в отношении R с элементом y и элемент y находится в отношении R с элементом z следует, что и элемент x находится в отношении R с элементом z.

На множестве Х <1, 2, 4, 8, 12>задано отношение

« x больше y в 2 раза»

Постройте граф. Какими свойствами обладает данное отношение?

Задайте отношение, обладающее свойством

Изучение нового материала.

Что означают слова «эквивалент», «порядок», «толерантность»? (Работа со словарём).

Эквивалент – нечто равносильное, равнозначное, равносильное другому, вполне заменяющее его.

Порядок – правильное, налаженное состояние, расположение чего-нибудь.

Толерантность – терпимость, уважительное отношение к людям.

Каким образом связаны эти понятия с математикой? На этот вопрос мы и постараемся сегодня на уроке ответить.

Тема урока сегодня «Отношение эквивалентности, порядка, толерантности»

Пример: На множестве дробей задано отношение «равно».

Рефлексивно, т.к. любая дробь равна сама себе.

Отношение R на множестве X называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Вернёмся к рассмотренному примеру. Всё множество дробей разбилось на подмножества ; ;

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

Важность разбиения на классы заключается в том, что в каждом классе оказываются эквивалентные элементы, т.е. элементы, неразличимые с точки зрения заданного отношения.

Поэтому считают, что класс эквивалентности (множество) определяется любым (одним) представителем, т.е. произвольным элементом этого класса.

Пример: возьмём любой класс равных дробей, которые мы получили на множестве: . Если мы возьмём дробь , то весь класс будет задан равными ей дробями.

№ 1. На множестве X <213, 37, 21, 87, 82>задано отношение Р – «иметь в записи одинаковые цифры». Является ли отношение Р отношением эквивалентности?

№ 2. Отношение Т – «имеет одно и тоже число делителей» задано на множестве <1, 2, 4, 7, 8, 10, 11>. Покажите, что Т – отношение эквивалентности и запишите все классы эквивалентности.

Наведём порядок в нашей группе с помощью отношения «быть выше». (Ребята выстраиваются по росту). Определите, какими свойствами обладает это отношение? Постройте граф этого отношения.

Множество X с заданным на нём отношением порядка называется упорядоченным множеством.

№ 1. Задано множество X <2, 8, 12, 32>. Упорядочить данное множество отношением а) «кратно»; б) «меньше».

№ 2. На множестве X<3,6, 9, 12, 15>задано отношение « x делится на y ». Покажите, что это отношение упорядочивает множество X. Чем этот порядок отличается от другого, т.е. «больше».

В нашей группе наверняка есть те, кто много лет дружат. (Выходят пары друзей или подруг). У нас получилось множество, заданное отношением «дружить». Какими свойствами обладает это множество?

— симметричность, т.к. если один человек дружит с другим, то и второй дружит с первым.

Отношение R, заданное на множестве X называется отношением толерантности, если оно рефлексивно и симметрично.

В толерантности элементы не разбиваются на классы, как в эквивалентности, но они группируются в подмножества, внутри которых все элементы взаимосвязаны.

№ 1. Составьте множество, состоящее из пяти элементов (ваших знакомых). Зададим отношение «быть знакомыми». Постройте граф этого отношения, определите его свойства. Является ли данное отношение отношением толерантности?

№ 2. Покажите, что отношение «быть синонимами» является толерантностью. Является ли оно эквивалентностью?

№ 1. На рисунке приведены графы отношений P, Q, S, T. Укажите среди них отношение: а) эквивалентности;

б) порядка; в) толерантности

P Q S T

№ 2. Составьте цепочку из сходных слов. (Сходными являются слова, если они состоят из одинакового числа букв, причём либо совпадают, либо отличаются лишь одной буквой. Например, сходны слова «роза» и «коза», равно как и слова «коза» и «коса». Но слова «роза» и «коса» не являются сходными, так как различаются в двух буквах). Какое отношение построено?

5.Первичное осмысление учебного материала с учётом получаемой специальности.

Данные, хранящиеся в компьютере, называются базой данных. Программы, с помощью которых пользователь извлекает информацию из базы данных или вносит в нее изменения, называются системами управления базами данных (СУБД).

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

а) успеваемости в группе;

б) данных каждого студента своей подгруппы (Ф.И. студента, дата рождения, какую школу закончил, место рождения).

в) данных каждого студента своей подгруппы (личный номер, Ф.И. студента, дата рождения, пол, специальность). Определите свойства отношения. К какому виду отношений оно относится?

Составить родословную своей семьи, задать отношение на полученном множестве и определить его свойства.

7.Подведение итогов урока.

-если отношение обладает свойствами рефлексивности и симметричности, то …

— отношение эквивалентности обладает …

— антисимметричность и транзитивность свойства …

На сколько изученный на уроке материал вам будет необходим в вашей будущей профессиональной деятельности?

Ковалёва Л.Ф. Дискретная математика. Московский государственный университет экономики, статистики, информатики. – М. 2001 г. (электронный)

Источник

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

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

Отношение эквивалентности. Отношением эквивалентности b на множестве B называется рефлексивное симметричное транзитивное бинарное отношение.

Отношением эквивалентности являются отношения равенства чисел и множеств. Конгруэнтность треугольников является отношением эквивалентности на множестве треугольников (два треугольника называются конгруэнтными, если они переводятся друг в друга путем смещения и вращения, или, другими словами, если они равны).

Отношение эквивалентности тесно связано с понятием разбиения множества.

Конечную или бесконечную систему непустых подмножеств <B1, B2, ¼> множества B называют разбиением множества B, если

Сами подмножества B1, B2, ¼ при этом называются классами разбиений.

Пусть <B1, B2, ¼> разбиение множества B и r отношение на B такое, что для любой пары элементов (B, C) множества B Выполняется (B, C) Î r только в случае, если пара элементов B, C Принадлежит одному классу разбиения. Тогда отношение r является отношением эквивалентности на множестве B.

Соответствие между отношением эквивалентности r на произвольном множестве B и разбиением этого множества на классы является взаимно-однозначным. Поэтому справедливо следующее утверждение.

Пусть на множестве B задано некоторое отношение эквивалентности r. Сформируем для каждого элемента B Î B подмножество Bb = <C | C Î B & C r B>, то есть подмножество, состоящее только из тех элементов множества B, которые находятся в отношении эквивалентности r с элементом B. Тогда семейство подмножеств <Bb>B Î B множества B является разбиением этого множества.

Пусть r является отношением эквивалентности на множестве B, тогда фактормножеством B | r множества M по эквивалентности r называется множество классов эквивалентности.

Отношение толерантности. Отношение эквивалентности определяет свойство одинаковости объектов. Действительно, рефлексивность выражает неразличимость любого объекта с самим собой, симметричность – указывает на то, что свойство одинаковости двух объектов не зависит от порядка их сопоставления. Наконец, транзитивность указывает на то, что если некоторый объект A одинаков с объектами B и C, то объекты B и C одинаковы между собой.

Есть отношение, в котором при наличии свойств рефлексивности и симметричности свойство транзитивности отсутствует. Поэтому может быть, что объект A схож с объектом B и схож с объектом C, но объекты B и C друг с другом не схожи.

Отношение b на множестве B называется Отношением толерантности (сходства), если оно рефлексивно и симметрично.

Пример 5.1. Рассмотрим в качестве примера отношение толерантности преобразование «мухи» в «слона» известного лингвиста Ю. А. Шрейдера. В этом случае множество B состоит из четырехбуквенных слов – нарицательных существительных русского языка в именительном падеже. Слова называются сходными, если они отличаются не более чем на одну букву. Требуется найти последовательность слов, которая начинается словом «муха» и оканчивается словом «слон» и в которой любые два соседних слова сходны.

Решение имеет вид: муха – мура – тура – тара – кара – каре – кафе – кафр – каюр – каюк – крюк – крок – срок – сток – стон – слон.

Вместо множества четырехбуквенных слов можно рассматривать множество четырехразрядных двоичных чисел. При этом считать, что числа сходны, если отличаются не более чем одним разрядом. Последовательность чисел 0000 – 0001 – 0011 – 0111 – 1111 переводит число «0000» в число «1111» и при этом каждая пара соседних двоичных отличается только одним разрядом.

Отношения порядка. Отношение b на множестве B называется отношением квазипорядка (или квазипорядком, или предпорядком), если оно рефлексивно и транзитивно.

Пример 5.2. Пусть задано множество B, состоящее из Q Объектов, каждый из которых характеризуется N числовыми признаками Ki, . Если отношение b на множестве B вводится следующим образом

» B, C Î B ((B, C) Î b Þ Ki(B) ³ Ki(C), ),

То оно является отношением квазипорядка.

Действительно, для вещественных чисел отношение ³ является рефлексивным и транзитивным, поэтому и рассматриваемое отношение будет рефлексивным и транзитивным.

Отношением порядка (частичного порядка) называется отношение квазипорядка обладающее свойством асимметричности.

Примером упорядоченного множества может служить множество действительных чисел, упорядоченных естественным образом. Граф отношения порядка (частичного порядка) имеет петли, транзитивен (если граф содержит ребра (A, B) и (B, C), то он обязательно содержит и ребро (A, C)), любые две вершины в графе соединены не более чем одним ребром. Пример графа для некоторого отношения порядка приведен на рис. 5.2.

Рис. 5.2. Пример графа, задающего некоторое отношение порядка

Отношением строгого порядка или Строгим порядком B на множестве B называется отношение, обладающее свойствами антирефлексивности и транзитивности.

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

Теорема 5.1. Если отношение b обладает свойствами антирефлексивности и транзитивности, то оно и асимметрично.

Доказательство. Свойство асимметричности предполагает выполнение соотношения b Ç b–1 = Æ. Предположим противное, что это свойство не выполняется, тогда существует по крайней мере одна пара элементов A, B Î B таких, что A B B и B B A. В силу свойства транзитивности отсюда получаем A B A, однако это противоречит свойству антирефлексивности. Следовательно, допущение b Ç b–1 ¹ Æ не является верным и отношение b на множестве B является асимметричным.

Граф отношения строгого порядка не имеет петель, транзитивен и не имеет контуров.

Напомним, что контуром или циклом в ориентированном графе называется последовательность B1 R12 B2 R23 B3, ¼, Bl–1 Rk–1, L, Bl Rlk Bk вершин B1, B2, B3, ¼, Bk–1, Bk и направленных ребер R12, R23, ¼, Rk–1, L, Rl, K, их соединяющих, причем Bk = B1, а все остальные вершины и ребра различны.

Отношением совершенно строгого порядка b на множестве B называется отношение строгого порядка, если для каждой пары не совпадающих элементов Bj, Bi Î B, Bj ¹ Bi выполняется или Bj b Bi или Bi b Bj. Другими словами, если в отношении строгого порядка нет несравнимых элементов, то оно является отношением совершенно строгого порядка.

Отношения >, Bk – 1 > ¼ > B2 > B1) и используется отношение >, то такой граф (рис. 5.3) очень наглядно демонстрирует преимущество (доминирование) элемента Bk над всеми остальными, а также положение любого элемента множества b среди остальных.

Рис. 5.3. Граф отношения совершенно строгого порядка

В этом случае граф фактически превратился в диаграмму, а диаграммы в случае отношений порядка являются более удобным средством графического отображения бинарных отношений, чем графы.

Источник