Сервер Методического Обеспечения вгуэс
| Вид материала | Реферат |
СодержаниеА рассмотреть естественный порядок, то получим схему: . Мы проводим стрелку от a А. Доказательство а) Высказывание ложно, так как ложно второе утверждение конъюнкции , значит, ложно x |
- Дипломная работа студента 545 группы, 334.18kb.
- Т. Н. Коржавина Принципы организации службы научного и методического обеспечения колледжа, 47.35kb.
- «sql*net», 239.02kb.
- Генезис развития теории и методики программно-методического обеспечения обучения, 145.89kb.
- Прозрачный прокси сервер на базе squid, ipfw и Freebsd, 8.5kb.
- Доклад «Три кита школьного образования: стандарты, учебники, егэ», 116.02kb.
- Справка по результатам самоаттестации методического объединения учителей русского языка, 447.26kb.
- Большой Сервер Недвижимости 31. 05. 2008: программа, 1328.13kb.
- Т. Г. Римская научный редактор, к и. н., доцент, директор филиала вгуэс в г. Находке, 2476.8kb.
- Владивосток: Изд-во вгуэс, 2005., 1071.2kb.
§7. Отношение порядка
Определение 1
Отношение называется отношением порядка на множестве , если выполнены следующие условия:
а) для любого (рефлексивность);
б) для любых , если и , то (транзитивность);
в) для любых , если и , то (антисимметричность).
Если – отношение частичного порядка, то вместо принято писать . Тогда условия а), б), в) примут вид:
а) ;
б) и влечет ;
в) и влечет .
Если на множестве задано отношение частичного порядка, то оно называется частично упорядоченным множеством и обозначается .
Примеры
1. На множестве задан естественный порядок, который вы изучали еще в школе. Мы его так и будем называть – естественный порядок – и обозначать, как обычно, .
2. Пусть – произвольное множество и – множество всех подмножеств множества . На определено отношение порядка следующим условием: тогда и только тогда, когда . Очевидным образом выполняются следующие условия:
а) ;
б) ;
в) .
То есть отношение включения подмножеств есть отношение частичного порядка. Этот пример имеет принципиальное отличие от естественных порядков, рассмотренных в первом примере. В первом примере любые два числа сравнимы по величине, то есть имеет место: для любых .
В примере 2 ситуация иная. Пусть . Мы не можем утверждать, что , но не можем также утверждать, что , то есть и являются несравнимыми. Наличие в некоторых упорядоченных множествах несравнимых элементов и дало основание внести термин частично упорядоченного множества.
3. Пусть
.
Определим: тогда и только тогда, когда .
Проверьте самостоятельно, что это отношение есть отношение частичного порядка, и что в этом упорядоченном множестве есть попарно несравнимые элементы (наборы).
4. На одном и том же множестве можно задать разные отношения порядка. Например, на множестве кроме естественного порядка можно задать следующее отношение:
в том и только в том случае, когда делится на , то есть существует , такое, что . Докажем, что введенное отношение на есть отношение частичного порядка.
а) , так как делится на ;
б) Пусть и , тогда и , где , следовательно, , то есть делится на и ;
в) Пусть и , тогда и . Отсюда следует, что , поэтому , а произведение двух натуральных чисел равно 1 только в том случае, когда , отсюда , то есть . Итак все три свойства – рефлексивность, транзитивность, антисимметричность – частичного порядка выполняются. Значит, отношение делимости на является отношением частичного порядка. Это отношение отличается от естественного порядка. Например, , но неверно, что , так как 5 не делится на 3.
5. Конечные упорядоченные множества удобно изображать с помощью схем. Проиллюстрируем это двумя примерами.
Пусть .
Если на А рассмотреть естественный порядок, то получим схему:
.
Мы проводим стрелку от a к b, если . Стрелку же от 2 к 4 мы не проводим потому, что существование ее гарантируется стрелками от 2 к 3, от 3 к 4 и транзитивностью.
Теперь на том же множестве А рассмотрим отношение делимости, тогда получим схему:
Получим совершенно различные схемы на одном и том же множестве А.
Наряду с обычным частичным порядком изучаются строгие частично упорядоченные множества.
Определение 2
Множество называется строго частично упорядоченным, если выполняются условия:
а) для любого неверно, что (антирефлексивность);
б) для любых влечет x
в) для любых не могут одновременно выполняться соотношения x
Всякое отношение частичного порядка естественным образом порождает отношение строгого порядка.
Теорема 3
Если есть отношение частичного порядка, то отношение является отношением строгого порядка на А.
Доказательство
а) Высказывание ложно, так как ложно второе утверждение конъюнкции , значит, ложно x
б) Пусть x