Основы дискретной математики В.А. Осипова (552659), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Множество Х с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным. Элемент а частично упорядоченного множества Х называется максимальным (минимальным), если из того, что арх (хра) следует, что х = а, т. е. в Х нет ни одного элемента х ф а такого, что арх (хра). Элемент а частично упорядоченного множества Х называется наибольшим (наименьшим), если хра (арх) для всех х е Х. Очевидно, что для линейно упорядоченных множеств максимальный элемент единственен и совпадает с наибольшим, соответственно, минимальный элемент единственен и совпадает с наименьшим. Для отношений частичного порядка, заданных на конечном множестве, удобной иллюстрацией являются диаграммы Хассе.

Рассмотрим непустое конечное множество Х, на котором задано отношение частичного порядка -~. Запишем х -с у, если х ~ у и х ф у. Говорят, что элемент у покрывает элемент х, если х с у и не существует такого элемента и, что х -с и -~ у. Тогда х 4 у равносильно тому, что существуют такие элементы Х1, Хг, ..., Хп, ЧТО Х = Х1 С Х2 .С -ь Ха = у, Гдв Х«+1 покрывает хь Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если у покрывает х, то точки х и у соединяют отрезком, причем точку, соответствующую х, располагают ниже у. Такие схемы называются диаграммами Хассе. На рис. 1.3, а, б показаны две диаграммы Хассе, причем вторая соответствует линейно упорядоченному множеству.

По диаграмме легко установить, что отношение, изображенное на рис. 1 3, а имеет два максимальных элемента х4 и хз и не 1.2. Бинарные отношения. Специальные бинарные отношения 23 22 Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ х, х, х, Рис. 1.3: имеет наибольшего, а также имеет один минимальный элемент х1, который является и наименьшим. Поскольку отношение, изображенное парис. 1.3, б, есть линейный порядок, то хз— минимальный и наименьший, х4 — максимальный и наибольший. Пример 1.13.

Рассмотрим три отношения частичного порядка и построим для них диаграммы Хассе: 1. Пусть А = (1, 2, 3). На множестве Р(А) рассмотрим отношение «быть подмножеством». Множество Р(А) содержит восемь элементов: (9, (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)). Его диаграмма Хассе изображена на рис. 1.4, ш 2.

Пусть Х = (1, 2, 3, 5, б, 10, 15, 30). На этом восьмиэлементном множестве рассмотрим отношение частичного порядка «х 4 у ~=» у делится на х». Диаграмма Хассе для этого отношения изображена на рис. 1.4, б. 3. На множестве Х = (1, 2, 3, 4, 5, б, 7, 8) рассмотрим отношение линейного порядка <. Его диаграмма Хассе изображена на рис. 1.4, е. Н,г,з1 зо з 7 ~г,зз (1 г7 ~1 зз 15 10 6 5 4 1г1 ГН 151 5 г з г и 1 1 и б в Рис, 1.4. Заметим, что диаграммы Хассе первых двух отношений совпадают.

Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причем отличную от структуры третьего частично упорядоченного множества, хотя оно тоже содержит восемь элементов. 1.2.3. Отношения предпочтения. Ранжирование и проблема выбора Прообразом отношений частичного и линейного порядка является интуитивное понятие отношения предпочтения (предгпествования). Пусть имеется совокупность объектов А и требуется сравнить их по предпочтительности, т.

е. задать отношение предпочтения на множестве А и определить наилучшие объекты. Отношение предпочтения Р, которое можно определить как «аРЬ, а, Ь Е А 4=» объект а не менее предпочтителен, чем объект Ь» является по смыс71у рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект а не хуже Ь и Ь не хуже а, то они одинаковы по предпочтительности). Естественно считать, что отношение Р транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами это свойство может быть нарушено), т. е. Р— отношение частичного порядка.

Определяя в Р наибольшие элементы (а они равноценны по предпочтительности), мы находим «наилучшие» с точки зрения отношения предпочтения элементы. Однако если Р не является отношением линейного порядка, множество наиболыпих элементов может быть пустым. В этом случае для выбора используется более слабое понятие максимального элемента и множество максимальных элементов определяет «неулучшаемые» с точки зрения этого отношения предпочтения элементы.

Один из возможных способов решения задачи сравнения объектов по 71редпочтительности — ранжирование, т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделим «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты. Проблема выбора наилучших объектов — ключевая в теории принятия решений, разделе прикладной математики, нмеюще»1 От слова ртезетепсе — предпочтение. 24 Глава 1, МНО?КЕСТВА И ОТНОШЕНИЯ многочисленные приложения в экономике, социологии, технике.

В качестве иллюстрации такого приложения приведем экономическую модель «стоимость — эффективность». Пусть объекты оцениваются по двум критериям качества — стоимости и эффективности, значения которых рассчитываются по специальным методикам, и пусть, соответственно, Х и У множества значений этих критериев. Как сравнивать объекты, оцениваемые по двум критериям и выбрать наилучшие, т. е., как сформировать отношение предпочтения на множестве ггар Х х У и определить на нем наибольшие или максимальные элементы? В начале ХХ века итальянский экономист Вильфред Парето предложил некоторый естественный подход к решению таких задач. В его основе лежит формирование на множестве Х х У бинарного отношения П, определяемого условиями: < х1, У1 > П < хг, уг >«=;. х1 < хг и У1 < Уг, где х1, хг Е Х у1, уг Е У (мы для простоты считаем, что Х и У вЂ” числовые множества, а значения критериев максимизируются).

Отношение П есть отношение частичного порядка (проверьте!). Оно называется опгноигением Парето, а множество максимальных элементов такого отношения оптимальными по Парето. На рис. 1.5 жирной линией изображено множество максимальных по Парето элементов заштрихованной области значений множества Х х У. Оно является «северо-восточной границей» для этой области. Максимальные элементы А и В этого множества не сравнимы между собой — по первому критерию А лучше В, но по второму хуже, по второму критерию В лучше А, но по первому хуже.

Рис. 1.б, Сравнение элементов оптимальных по Парето требует дополнительной информации о предпочтениях. 1.3. Бинарные отношения. Специальные бинарные отношения 25 Задачи и упражнения 1. Найти П7, Ву, р ', р е р, р 1 о р, р е р 1 отношений х, у — натуральные числа и х делит у); х, у — действительные числа и х+ у < О); а) р=(<х,у> б) р=(<х,у> в) р=(<х,у> х,уЕ [ — —, — ] иу)згпх~. 2. Доказать, что число бинарных отношений на и-элементнг ном множестве равно 2" . 3. Привести примеры отношений: а) не рефлексивного, но симметричного и транзитивного; б) не симметричного, но рефлексивного и транзитивного; в) не транзитивного, но рефлексивного и симметричного.

4. На множестве прямых на плоскости рассмотрим отношения; а) параллельности прямых; б) перпендикулярности прямых. Определить, будут ли эти отношения отношениями эквивалентности на этом множестве. 5. На множестве 1Ч х М, где 1Ч вЂ” множество натуральных чисел (1, 2, 3, ...), определим отношение р: < х, у > р < и, и >~» х + и = у + и. Доказать, что р — отношение эквивалентности на этом множестве. 6.

Доказать, что пересечение отношений эквивалентности на множестве Х есть отношение эквивалентности на этом множестве. 7. Доказать, что объединение р1 0 рг двух отношений эквивалентности р1 и рг, заданных на множестве Х, является отношением эквивалентности тогда и только тогда, когда Р1ОРг Р1ерг 8. Доказать, что если р — частичный порядок, то р 1— также частичный порядок. 9.

Привести пример линейного порядка на множестве М х Ы, где 14 — множество натуральных чисел. 10. Доказать, что всякий частичный порядок на конечном множестве может быть продолжен до линейного порядка. 11. Доказать, что для конечных множеств единственный максимальный (минимальный) элемент является наибольшим (наименьшим). 27 1.3.

Алгебраические операции 2б Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ 1.3. Алгебраические операции Таблица 1>Ь Таблица 1.1. Систематизируем понятие алгебраической операции, с которым мы уже встречались в различных разделах курса математики. Пусть дано множество М. Говорят, что на М определена бинарная алгебраическая операция, если всякой упорядо 1епной паре элементов < а, 6 > множества М по некоторому закону ставится в соответствие вполне определенный элемент с из этого же множества. Примерами бинарных операций на множестве целых чисел являются сложение и умножение. Однако нашему определению не удовлетворяют, например, множество отрицательных целых чисел относительно умножения и множество действительных чисел относительно деления из-за невозможности деления на нуль. Среди известных бинарных операций, производимых не над числами, отметим векторное умножение векторов пространства, умножение квадратных матриц гюрядка и, композицию отображений множества Х в себя, теоретико-множественное объединение и пересечение множеств.

Фактическое задание алгебраической операции на множестве может быть произведено различными методами. Возможно также непосредственное перечисление всех результатов операции для конечных множеств. Его удобно описать с помощью так называемой таблицы Кэли. Слева и сверху квадратной таблицы выписывают все элементы множества. На пересечении строки, соответствующей элементу а, и столбца, соответствующего элементу 6, записывают результат операции над а и 6. Из двух приведенных таблиц Кэпи (табл. 1.1 и 1.2) вторая — таблица для операции конъюнкции на множестве (И, Л), о которой будет говориться в гл.

Характеристики

Список файлов книги