русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Частково впорядковані множини


Дата додавання: 2014-05-29; переглядів: 1014.


 

Відношення R на А є відношеннячасткового порядку, якщовоно рефлексивно, симетрично й транзитивно.

Якщовідношення R на А є відношеннямчасткового порядку, то (A,R) називаютьчасткововпорядкованоюмножиною, або ЧУ-множиною з порядком R. Якщовідношення порядку R передбачається за замовчуванням, то (A,R) можнапозначити просто А

Нехай С={1,2,3}, а X—безлічвсіхпідмножинбезлічіС:

 

X=Р(С)={0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Определим отношение Rна Xпосредством (Т, V)ÎR, еслиТÍV. Такимобразом, ({2},{1,2}) ÎR, поскольку {2} Í{1,2} и ({2,3},{3}) ÎR, поскольку{2,3} Î{3}. Можно легко проверить, что R — отношение частичного порядка, а(А, R)_ ЧУ-множество

Частковевпорядкованеприйнятопозначати через ,а часткововпорядковану множину через (S, ), де -частковий порядок на множині S якщо(a,b)Î ,товідповідно до уведеногоранішепозначенням для відношень, a b

Два елементи а й b частково впорядкованої мнодини (S, ≤) порівнянні, якщо а ≤ bабо b ≤ а. Якщо кожні два елементи частково впорядкованої множини (S, ≤) порівнянні, то (S, ≤) називається цілком упорядкованою множиною або ланцюгом.

Для зображення частково впорядкованих безлічей є графічний апарат, відомий як діаграми Гессе. Для заданоїЧу-множини (А, ≤) діаграма Гессе складається із сукупності крапок і ліній, у якій крапки представляють елементи А, і якщо а ≤ с для елементів а й смножини А, тоді а поміщено нижче с, і вони з'єднані лінією, якщо не існує таке b ≤ а,с, що а ≤ b ≤ с. Якщо розгляд відносин обмежений відносинами часткового порядку, для них діаграми Гессе являють собою просто орієнтований граф, у якому петлі не зазначені; і якщо а ≤ b ≤с, тоді лінія від а до с не зазначена.

 

ПобудуйтедіаграмиГессе для наступнихЧУ-множеств (А, ≤), где

а) А= {a, b, с, d} и

≤= {(а,а), (b, b),(с, с), (d, d), (а, с), (b, с), (с, d), (a, d), (b, d)}

 

б) A = {а, b, с, d} и ≤= {(а, а), (b,b), (с, с), (d, d), (a, с), (b, с)};

 

в) A = {a,b,c,d} и≤ = {(a,a),(b,b),(c,c),(d,d)};

 

г) A= {а, b, с, d} и≤= {(а,а). (b,b), (c,с).(d, d),(а, b). (b,с),(а,с), (с, d), (а, d),(b,d)

 

Перелічитеелементибезлічі А и виразите≤ як безлічупорядкованих пар для кожної з наведенихнижчедіаграм Гессе

:


<== попередня лекція | наступна лекція ==>
Властивості відношень | ІНСТРУМЕНТАЛЬНІ ЗАСОБИ ВІЗУАЛЬНОГО ПРОГРАМУВАННЯ


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн