Отношения порядка. Диаграмма Хассе
Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются «равными». Обобщением обычного отношения Отношение Пример. Отношение R ={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(1,3)} на множестве X ={1,2,3} является предпорядком. Рефлексивное, антисимметричное, транзитивное отношение называется отношением нестрогого порядка и обозначается символом Антирефлексивное, антисимметричное, транзитивное отношение называется отношением строгого порядка и обозначается символом Примеры: 1. Пусть Y – некоторое множество, тогда отношение включения 2. Отношение «х старше у» на некотором множестве людей является отношением строгого порядка. Множество Х с заданным в нем отношением порядка называется упорядоченным этим отношением. Если любые два элемента х и у множества Х находятся между собой в отношении порядка, то множество Х называется линейно упорядоченным или цепью, иначе множество Х называется частично упорядоченным. В частично упорядоченном множестве можно выделить цепь. Цепь с повторяющимися элементами называется мультицепью. Если между элементами х и у установлено отношение порядка, то они называются сравнимыми, иначе – несравнимыми. Антицепью (семейством Шпернера) называется подмножество частично упорядоченного множества, в котором любые два элемента несравнимы. Специальным типом частично упорядоченного множества является интервал |x,y]={z
Двойственным к частично упорядоченному множеству называется частично упорядоченное множество, определенное на том же носителе с помощью обратного отношения. Это понятие лежит в основе принципа двойственности, который часто формулируют в виде: если некоторое утверждение справедливо для частично упорядоченных множеств, то справедливо и двойственное утверждение, то есть утверждение, касающееся двойственных частично упорядоченных множеств. Рассмотрим множество Х с заданным на нем отношением частичного порядка Говорят, что элемент y покрывает элемент x, если х Пример. Отношение включения
Рис. 2.2
Правило чтения диаграмм Хассе состоит в том, что х Пример. Пусть А={1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка ≤ на этом множестве, задаваемое по правилу: x ≤ y
Заметим, что диаграммы Хассе этих двух отношений совпадают Пусть Х и Y два частично упорядоченных множества. Если их диаграммы Хассе совпадают, то эти частично упорядоченные множества имеют одинаковую структуру.
Рис. 2.3 Рис. 2.4
Пусть задано частично упорядоченное множество X. Для элементов х и у из множества Х их верхней гранью называется любой элемент z Пример. На рис. 2.5 а) изображена диаграмма Хассе множества
Рис. 2.5
Задачи и упражнения
1. Даны множества Х 0={1,2,3,4,5,6}, X 1={1,2,3,4}, X 2={2,3,4,5}, X 3={2,3,4}, X 4={3,4,5}, X 5={2,3}, X 6={3,4}, X 7={4,5}, X 8={2,4}. Сформируйте частичный порядок на этих множествах. 2. Пусть Х - множество всех прямых на плоскости. Являются ли эквивалентными отношения а) параллельности прямых и б) перпендикулярности прямых? 3. Приведите пример четырех различных рефлексивных отношений на множестве 4. Приведите пример трех различных отношений на множестве 5. Приведите пример двух различных симметричных отношений и двух различных, не являющихся симметричными, на множестве 6. Приведите пример двух различных транзитивных отношений и двух различных, не являющихся транзитивными, на множестве 7. Приведите пример частичного порядка и пример отношения, не являющегося частичным порядком.
8. Приведите пример множества и двух различных эквивалентностей на нем. 9. Приведите пример множества и двух различных частичных порядков на нем. 10. Определите свойства следующих отношений, заданных на множестве действительных чисел (R) а) R ={(x, y)| x, y Î R и x - y <0}, в) R ={(x, y)| x, y Î R и 2 x ³3 y }, с) R ={(x, y)| x, y Î R и | x | ³| y |}. 11. Найдите а) R ={(x,y) | x,y Î N и x, делит y }, в) R ={(x, y)| x, y Î R и x + y <0}, с) R ={(x, y)| x, y Î R и 2 x ³3 y }. 12. Докажите, что если отношения R 1 и R 2 рефлексивны, то рефлексивны следующие отношения 13. Докажите, что если отношения R 1 и R 2 симметричны, то симметричны следующие отношения 14. Докажите, что если R эквивалентность, то 15. Докажите, что 16. Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить классы эквивалентности.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|