Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Экстремальные элементы в частично упорядоченном множестве




Решение.

= с элементом a не сравнимы элементы b и d. С элементом d не сравнимы элементы a, b, c, e.

 

 

Рис. 2

Пусть М – частично упорядоченное множество. Элемент х М называется минимальным элементом этого множества, если во множестве М не существует элемента a x. Элемент y М называется максимальным элементом этого множества, если в нем не существует элемента a>y. Минимальный и максимальный элементы в упорядоченных множествах могут существовать, а могут и не существовать (в случае бесконечных множеств), их может быть несколько.

Пример 1.

M = {1, 2 ... } = N; порядок – обычное сравнение чисел, минимальный элемент - это 1, максимальные элементы отсутствуют).

Пример 2.

M 1 = [0; 1], M 2 = (0; 1], M 3 = [0; 1], M 4 = (0; 1).

В M 1 минимальный элемент - это 0, максимальный элемент это - 1.

В M 2 минимального элемента нет, максимальный элемент - это 1.

В M 3 минимальный элемент - это 0, максимального элемента нет.

В M 4 минимальный и максимальный элементы отсутствуют (порядок – обычное сравнение чисел).

Пример 3.

М = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

Отношение порядка – это отношение включения. В этом множестве три минимальных элемента, не сравнимых между собой, – множества {1;2}, {1; 3}, {2; 3}. Максимальный элемент один – множество {1, 2, 3}.

Пример 4.

М = {2, 3, 4 ... }, a < b Û a делит b и ab.

Максимального элемента нет, а минимальные элементы - все простые числа.

Пример 6.

Покажем, как на диаграмме выглядят минимальный и максимальный элементы в случае множества: М = {2, 3, 4, 6, 7, 12, 16, 18}, a < b Û a делит b и ab. (рис.3)

Рис. 3

Минимальные элементы – 2, 3, 7. В минимальный элемент не входит ни одна линия со стрелкой.

Максимальные элементы – 7, 12, 16 18. Из максимального элемента не выходит ни одна линия со стрелкой. Один и тот же элемент может быть одновременно и максимальным, и минимальным. В этом случае он не сравним ни с каким другим элементом данного множества.

Утверждение.

Во всяком непустом конечном, частично упорядоченном множестве М существует хотя бы один минимальный (максимальный) элемент.

Доказательство.

Докажем существование минимального элемента.

Допустим, что в М нет минимальных элементов. Пусть |M| = n, выберем произвольный элемент а Î М, обозначим его через х 1. Так как х 1 – не минимальный элемент, то существует b Î М, (обозначим b через x 2), такой, что x 2 < х 1. Далее, существует с Î М, (обозначим с через х 3), такой, что x 3 < x 2 < x 1. Продолжим перебор элементов множества M. Перебрав все, получим цепочку: xn < xn- 1 <... < x 2 < x 1. Так как xn – не минимальный элемент, то (k): xk < xn, k < n. Таким образом, xk < xn < xn- 1 <... < xk <... < < x 1. Но отношение порядка транзитивно, получаем, что xk < xk, - противоречие, строгий порядок антирефлексивен.

Определение. Пусть M – частично упорядоченное множество. Элемент х Î М называется наименьшим элементом множества М, если (" а Î М, a¹x): а > х. Элемент y Î Mнаибольшим элементом множества М, если (" а Î М, a¹y): а < y. По определению наименьший (наибольший) элемент сравним со всеми другими элементами множества М

Утверждение.

Если во множестве М существует наименьший (наибольший) элемент, то он единственен.

Доказательство.

Пусть х 1 ≠ х 2 – два наименьших элемента множества . По определению наименьшего элемента х 1 < х 2, (х 1 – наименьший элемент), а также х 2 < х 1 – (х 2 – наименьший элемент) Þ х 1 = х 2 в силу антисимметричности любого отношения порядка.

Примеры наибольших и наименьших элементов.

1. Æ и М – являются наименьшим и наибольшим элементами булеана 2 М, упорядоченного по включению.

2. В множестве N наименьший элемент - 1, наибольшего элемента нет (порядок – обычное сравнение чисел).

3. Множество R – не имеет ни наибольшего элемента, ни наименьшего элемента (порядок – обычное сравнение чисел).

4. Во множестве В = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, частично упорядоченном по включению, нет наименьшего элемента; множество

{1, 2, 3} - наибольший элемент множества В.




Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 3245; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.