Това е полезен инструмент, който напълно описва свързания частичен ред. Следователно тя се нарича още диаграма на подреждане. Много е лесно да преобразувате ориентирана графика на релация върху множество A в еквивалентна диаграма на Хасе. Следователно, докато чертаете диаграма на Хасе, трябва да запомните следните точки.
- Върховете в диаграмата на Хасе са обозначени с точки, а не с кръгове.
- Тъй като частичният ред е рефлексивен, следователно всеки връх на A трябва да бъде свързан със себе си, така че ръбовете от върха към себе си се изтриват в диаграмата на Хасе.
- Тъй като частичен ред е транзитивен, следователно, когато aRb, bRc, имаме aRc. Елиминирайте всички ръбове, които се подразбират от транзитивното свойство в диаграмата на Хасе, т.е. изтрийте ръба от a до c, но запазете другите два ръба.
- Ако връх 'a' е свързан с връх 'b' чрез ребро, т.е. aRb, тогава връх 'b' се появява над връх 'a'. Следователно стрелката може да бъде пропусната от ръбовете в диаграмата на Хасе.
Диаграмата на Хасе е много по-проста от насочената графика на частичния ред.
Пример: Да разгледаме множеството A = {4, 5, 6, 7}. Нека R е отношението ≦ върху A. Начертайте насочената графика и диаграмата на Хасе на R.
Решение: Отношението ≦ върху множеството A се дава от
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
Насочената графика на отношението R е както е показано на фиг.
За да начертаете диаграмата на Хасе на частичен ред, приложете следните точки:
- Изтрийте всички ръбове, подразбиращи се от рефлексивното свойство, т.е.
(4, 4), (5, 5), (6, 6), (7, 7) - Изтрийте всички ръбове, подразбиращи се от транзитивното свойство, т.е.
(4, 7), (5, 7), (4, 6) - Заменете кръговете, представляващи върховете, с точки.
- Пропуснете стрелките.
Диаграмата на Хасе е както е показано на фиг.
Горна граница: Да разгледаме B като подмножество на частично подредено множество A. Елемент x ∈ A се нарича горна граница на B, ако y ≦ x за всяко y ∈ B.
Долна граница: Да разгледаме B като подмножество на частично подредено множество A. Елемент z ∈ A се нарича долна граница на B, ако z ≦ x за всеки x ∈ B.
Пример: Помислете, че подредбата A = {a, b, c, d, e, f, g} е подредена, показана на фиг. Също така нека B = {c, d, e}. Определете горната и долната граница на B.
Решение: Горната граница на B е e, f и g, защото всеки елемент от B е '≦' e, f и g.
Долните граници на B са a и b, защото a и b са '≦' всеки елемент от B.
Най-малка горна граница (SUPREMUM):
Нека A е подмножество на частично подредено множество S. Елемент M в S се нарича горна граница на A, ако M следва всеки елемент от A, т.е. ако за всяко x в A имаме x<=m< p>
Ако горна граница на A предшества всяка друга горна граница на A, тогава тя се нарича супремум на A и се обозначава със Sup (A)
Най-голяма долна граница (INFIMUM):
Елемент m в частно множество S се нарича долна граница на подмножество A от S, ако m предхожда всеки елемент от A, т.е. ако за всяко y в A имаме m<=y < p>
Ако долна граница на A следва всяка друга долна граница на A, тогава тя се нарича ниска граница на A и се обозначава с Inf (A)
Пример: Определете най-малката горна граница и най-голямата долна граница на B = {a, b, c}, ако съществуват, на честотната група, чиято диаграма на Хасе е показана на фиг.
Решение: Най-малката горна граница е c.
Най-голямата долна граница е k.