В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах, страница 10

Пусть x – произвольный элемент из A . Покажем, что a0 ≼ x , откуда и будет следовать,что a0 является наименьшим на A . Из утверждения 4.4 следует, чтодля x найдется элемент a1 , являющийся минимальным на A , такой,что a1 ≼ ≼ x . Но по условиям доказываемого утверждения a0  a1 ≼ x .Пример 4.15. Возвращаясь к упражнению 4.2, используя утверждение 4.5, заключаем, что элемент b является наибольшим на A , а, всилу утверждения 4.2, наименьшего на A элемента нет.60Рассмотрим теперь случай, когда конечное множество является линейно упорядоченным.Утверждение 4.6.

Пусть A – конечное линейно упорядоченноемножество, | A | n  2 . Тогда элементы множества A  {a1 ,..., an }можно занумеровать таким образом, что a1 ≺ a 2 ≺…≺ an , при этом a1является наименьшим на A , an – наибольшим, и i  {2,..., n} a i покрывает ai 1 .Доказательство. В силу утверждения 4.4, в A найдутся минимальный и максимальный элементы: a1 , an . Поскольку a1 , an сравнимы со всеми другими элементами, то a1 является наименьшим, а an –наибольшим на A (см.

утверждение 4.1). Заметим, что a1  a n (еслиa1  a n , то a  A a1 ≼ a ≼ an  a1  A  {a1} , а это противоречитусловию n  2 ), a1 ≼ an , а следовательно, a1 ≺ an , откуда, в силу утверждения 4.3, либо a n покрывает a1 , либо k  2, a2 ,..., ak  A : a1 ≺≺ a 2 ≺…≺ a k ≺ an , где an покрывает a k и i  {2,..., k} элемент a iпокрывает элемент ai 1 . Поскольку все элементы a1 , a2 ,..., ak , an попарно различны (см.

упражнение 4.1), то k  n  1 . Покажем, чтоk  n  1 . Предположим противное, т.е. пусть k  n  1 . Тогда в Aнайдется элемент b  {a1 ,..., ak , an } . Поскольку a1 , an являются наименьшим и наибольшим элементами на A, соответственно, тоa1 ≺ b ≺ an .(4.2)Из (4.2) следует, что k  2 , поскольку при k  1 an покрывает a1 ,а это противоречит (4.2).

Поскольку в линейно упорядоченном множестве все элементы сравнимы, то либо b ≺ a k , либо a k ≺ b , а так какan покрывает a k , то, в силу (4.2), b ≺ a k . Совершенно аналогично доказывается, что b ≺ a k 1 , b ≺ a k  2 ,…, b ≺ a 2 , откуда, используя (4.2),получаем a1 ≺ b ≺ a 2 , а это противоречит тому, что a 2 покрывает a1 .61Для решения некоторых практических задач (см. замечание 4.2)нередко возникает необходимость расширения данного частичного порядка ≼ на некотором множестве A до линейного ≼ Л , удовлетворяющего условию ≼  ≼ Л .

В случае, когда A – конечное множество,существует простой практически реализуемый алгоритм такого расширения. Идея алгоритма простая. Выбираем любой максимальный элемент a1 из A и делаем его наибольшим, т.е. включаем в ≼ все парывида x, a1 , x  A . При этом очевидным образом сохраняются рефлексивность, антисимметричность, транзитивность получаемого такимобразом бинарного отношения, т.е. оно снова является частичным порядком на A .

Далее, удаляем из множества A элемент a1 , т.е. переходим к рассмотрению множества A1  A \ {a1} , снова являющегося частично упорядоченным (см. замечание 4.1). Затем выделяем в A1 любоймаксимальный элемент a 2 и делаем его наибольшим в A1 , т.е. включаем в ≼ все пары вида x, a 2 , x  A1 . Далее удаляем из множества A1элемент a 2 и переходим к рассмотрению множества A2  A1 \ {a2 } ит.д. Действуем так до тех пор, пока в текущем множестве Ai имеетсяболее одного элемента.

В случае же, когда в текущем множестве Ai остался один элемент, требуемый линейный порядок ≼ Л построен (докажите сравнимость по ≼ Л двух любых элементов из A ).В случае, когда частичный порядок на конечном множестве A задан диаграммой Хассе, описанный алгоритм реализуется следующимобразом. В силу утверждения 4.6, диаграмма Хассе строящегося линейного порядка ≼ Л представляет собой ломаную линию, «восходящую»от наименьшего элемента к наибольшему (т.е. при движении по это ломаной от наименьшего элемента к наибольшему будем все время подниматься вверх).

Выбираем любой максимальный элемент a1 в A , помещаем его в верхней точке диаграммы Хассе для ≼ Л и удаляем его издиаграммы Хассе для ≼ (например, стираем его вместе со всеми пря62молинейными отрезками, соединяющими его с другими элементами).Далее выбираем любой максимальный элемент в оставшейся диаграммеХассе для ≼, помещаем его в следующую по высоте точку из диаграммы Хассе для ≼ Л и удаляем из текущей диаграммы Хассе для ≼. Действуем так, пока в диаграмме Хассе для ≼ еще остаются элементы.Пример 4.16. Используя описанный алгоритм, построим линейныйпорядок ≼ Л , являющийся расширением частичного порядка ≼, заданного диаграммой Хассе на рис.4.2, т.е.

удовлетворяющий условию:≼  ≼ Л . Очевидно, что линейный порядок ≼ Л может быть построеннесколькими способами. Один из возможных линейных порядков приведен на рис. 4.3.Рис. 4.3Замечание 4.2. Существует немало практических задач, в которыхтребуется осуществить расширение некоторого частичного порядка,заданного на конечном множестве, до линейного. Примером являетсяорганизация производства на конвейере. Пусть A  {a1 ,..., an } – множество операций, необходимых для изготовления некоторого изделияИ. Тогда для любых двух операций ai , a j , где i  j , возможны трислучая: (а) операция a i может быть произведена только после выполнения операции a j ; (б) операция a j может быть произведена только после выполнения операции a i ; (в) возможно выполнение операции a iпосле a j и наоборот.

Рассмотрим бинарное отношение ≼ на A ,включающее в себя все пары вида ai , ai , i  1,2,..., n , а также все пары ai , a j , гдеi  j , такие, что операция a j может быть произведе63на только после выполнения операции a i . Очевидно, что это бинарноеотношение является рефлексивным, антисимметричным и транзитивным, т.е. является частичным порядком на A . Заметим, что при сборкеизделия И на конвейере необходимо расширить указанный частичныйпорядок до линейного ≼ Л , поскольку сборка на конвейере предполагает линейно упорядоченную последовательность выполнения операций.Отметим, что неоднозначность такого расширения дает возможностьставить задачу оптимальной организации конвейера, а именно, выборалинейного порядка, при котором суммарная потеря рабочего времени(при заданных такте C и времени t i выполнения каждой операции a i ,i  1,2,..., n ) достигает минимального значения, что обеспечивает максимальную производительность труда.

Тактом работы конвейера назовем время, в течение которого конвейерная линия является неподвижной , чтобы обеспечить возможность выполнения на каждом рабочемместе необходимой последовательности работ. Например, в случае, еслидля выбранного линейного порядка ≼ Л выполняется a1 ≺ Л a 2 ≺ Л ……≺ Л an , потеря рабочего времени на первом рабочем месте составляетC  t1  ...  t i1 , где i1  max{ i | t1  ...

 t i  C} ; потеря рабочего времени на втором рабочем месте составляет C  t i1 1  ...  t i2 , гдеi2  max{ i | t i1 1  ...  t i  C} , и т.д.ЗадачиЗадача 4.1. Доказать, что если  – частичный порядок на A , то и – частичный порядок на A .1Решение. Рефлексивность и антисимметричность 1очевидны.Докажем транзитивность  . Действительно, x, y, z  A  x, y ,11 y, z   1   y, x ,  z, y    z, x    x, z   .Задача 4.2. Доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента.64Решение.

Пусть A – частично упорядоченное множество, a –наибольший элемент на A (для случая с наименьшим элементом рассуждение аналогично). Предположим, что b – также наибольший элемент. Тогда по определению наибольшего элемента a ≼ b , b ≼ a , откуда, в силу антисимметричности ≼, выполняется a  b .Задача 4.3. В частично упорядоченных множествах, заданных диаграммами Хассе, найти все упорядоченные пары, входящие в данныйчастичный порядок, максимальные, минимальные элементы, наибольший, наименьший элементы (если таковые имеются), определить сегмент [a, b] . Построить любой линейный порядок, являющийся расширением заданного частичного порядка.(а)(б)(в)Задача 4.4. Построить пример частично упорядоченного множества, имеющего один минимальный элемент, но не имеющего наименьшего элемента.Решение.

Пусть Z – множество целых чисел, линейно упорядоченное естественным образом (т.е. отношением  ). Добавим к этомумножеству комплексное число i. Оно не сравнимо с числами из Z, а поэтому является и минимальным и максимальным на множестве Z  {i} . Таким образом, искомым множеством является Z  {i} , частично упорядоченное указанным выше способом.Задача 4.5.

Пусть 1 ,  2 – линейные порядки на множестве A .Доказать, что 1   2 – линейный порядок на A  1   2 .Решение. Пусть 1   2 – линейный порядок. Покажем, что1   2 (рассуждение в обратную сторону очевидно; см. утверждение3.4). Предположим, что 1   2 и, например,  x, y  1 : x, y   2 .65В силу рефлексивности  2 , выполняется x  y . Поскольку  2 – линейный порядок, то y, x   2 . Из рефлексивности 1 ,  2 следует(см. задачу 3.5(в)), что 1   2  1   2 , а следовательно, x, y ,y, x  1   2 , x  y , что противоречит антисимметричности 1   2 .Задача 4.6.

Построить линейный порядок на множествах: (а) N2 ,где N  {1,2,... } – натуральный ряд; (б) N  N2  N3  … .Решение. (а). Обходим точки из N2, например, согласно рис.4.4(число около точки из N2 является ее номером в процессе обхода)Рис.4.4б) Опишем так называемый «лексикографический порядок» (аналогичный порядку расположения слов в словаре; например, слово «аббат» расположено в словаре раньше слова «абзац», слово «абзац» раньше слова «арба», слово «арба» раньше слова «Арбат» и т.д.) .