Сервер Методического Обеспечения вгуэс

Вид материала

Реферат

Содержание А задано отношение строго частичного порядка

Подобный материал:

• Дипломная работа студента 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.

Из первого и третьего членов этой коньюнкции следует . Осталось доказать, что . Допустим, x=z, тогда получаем , то есть x=y, но по условию . Это противоречие и доказывает, что x

в) Допустим, что выполняется конъюнкция , то есть , но первый и третий член коньюнкции влекут x=y. Противоречие. Значит соотношения x и y не могут выполняться одновременно.

Теорема доказана.

Верно и обратное утверждение.

Любой строгий частичный порядок порождает естественным образом просто частичный порядок.

1. Теорема 4

Пусть на множестве А задано отношение строго частичного порядка <, тогда отношение является отношением частичного порядка.

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

Проверим выполнение всех трех условий, определяющих отношение частичного порядка.

а)  – эта дизъюнкция истинна, так как истинен ее второй член х=х, поэтому .

б) Пусть , это значит,

,

что равносильно

.

Отсюда следует: , то есть , что и означает .

в) Пусть , тогда

.

Это равносильно

.

Первый, второй и третий члены этой дизъюнкции ложны. Первый по свойству в) определения строгого порядка, второй и третий по свойству а). Остается равенство х=у.

Теорема доказана.

1. §8. Линейно упорядоченные множества.
   Лексикографический порядок

Как отмечали мы в предыдущем параграфе, есть частично упорядоченные множества, в которых любые два элемента сравнимы, а есть множества, где существуют несравнимые элементы. Это различие подчеркивается следующим определением.

1. Определение 1

Частично упорядоченное множество называется линейно упорядоченным, если выполняется условие:

г) для любых .

Для строгого порядка это условие принимает вид:

г) для любых .

Основной целью этого параграфа является изучение так называемых лексикографических порядков, которые в последнее время находят приложение в информатике и в различных разделах математического моделирования.

1. Определение 2

Пусть и  – линейно упорядоченные множества. Определим на бинарное отношение следующим образом:

.

Введенное отношение называется отношением лексикографического порядка.

1. Теорема 3

Если и  – линейно упорядоченные множества, тогда множество также линейно упорядочено.

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

Проверим выполнение всех четырех условий линейной упорядоченности.

а) Рефлексивность. Очевидно, что , так как выполняется второе условие дизъюнкции в определении лексикографического порядка: .

б) Транзитивность. Пусть и . Если , то и , если же , то , и снова . Теперь пусть , тогда и , следовательно, и , что и завершает доказательство транзитивности.

в) Антисимметричность. Пусть и . Из определения лексикографического порядка получаем и , то есть . Из второго "слагаемого" дизъюнкции в определении лексикографического порядка теперь получаем и . Следовательно, .

г) Сравнимость любых двух элементов множества . Пусть . Так как  – линейно упорядоченное множество, то для элементов выполнено одно из трех условий:

, тогда ;

, тогда ;

. В этом случае для элементов возможно одно из двух:

, тогда ;

, тогда .

Таким образом, сравнимость, а вместе с ней и вся теорема, доказана.

Таким образом, если  – линейно упорядоченное множество, то на множестве естественным образом также возникает линейный порядок – лексикографический. По индукции лексикографический порядок определяется на множестве и по индукции же доказывается, что этот порядок – линейный.

Проиллюстрируем вышеизложенные конструкции примером.

Пусть .

Расположим в лексикографическом порядке возрастания элементы множества :