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

УДК 617 ББК 22.176 072 Оглавление Предисловие Глава 1. 1,1 7 7 7 10 13 1,2 16 16 !7 1.3 Глава 2. 2.1 2.2 'УДК 517 ББК 22.176 Глава 3. 3.1 86 86 86 87 91 93 95 95 1ВВН 5-91134-016-Х ?БВН 5-16-002622-3 ?с? В. А. Осипова, 2006 О «ФОРУМ, 2006 3.2 3.2.2. Рекуррентные соотношеаавя и производвщие функции ..

99 д~~~ор техааааческаах наук, г?рог?>ессор Государственного'уииверситета— Высшей школы экономики О. ?7. Кулиса?ав Осипова В. А. О72 Основы дискретной математики: Учебное пособие. — Мл ФОРУМ: ИНФРА-М, 2006.— 160 сл нл. — ЕВысапее обрзлсшание). 1БВг? 6-91134-016-Х 1ФОРУМ) ?ЕВМ 5-16-002622-3 (ИНФ А-М) Излагаютсп основы современной дискретной математика>. Рассматрнвшотси вопросы, сввзавные с комбинаторикой, мателаатической логикой, теорией графов.

Прнводвтгл практические задачи н даются алгоритмы их реп>енин. Учебное пособие предназначено для студентов, обучающихся по спецпельиоствм, свпзаиныч с вкономнкой, логистикой, ба«внес-аанформатикой. Оно может оказатьси полезным н студентам технических специальностей, изучающим курс «Дискретная математикам МНОЖЕСТВА И ОТНОШЕНИЯ Начальные понятия теории множеств 1.1.1.

Понятие а«нов«встав 1.1.2. Операции над множествами. Алгебра множеств . 1.1.3. Упорядочение. Примое произведение множеств Бинарные отношении. Специальные бинарные отношении 1.2,1. Общее поннтие отношения 1.2.2. Специальные бинарные отношения 1.2.3. Отношения предпочтения. Ранжнрование и проблема выбора . Алгебраические операции.................. ЭЛЕМЕНТЫ МАТЕ?а?АТИЧЕСКОЙ ЛОГИКИ Логика высказываний 2.1.1. Высказывании.

Логические операции. Формулы логики высказываний 2.1.2. Равносильность формул...,........... 2.1.3. Булавы алгебры 2.1.4. Тождественно-истинные формулы. Проблема разрешимости 2.1.5. Двойственность. Закс>а двойственности...... 2.1.6. Нормальные 4>ормы Формул,........... Булавы функции .. 2.2.1. Представление булевой функции Формулой логики высказываний 2.2.2, Полные системы булевых Функций 2.2.3.

Минимизации в классе днзьюнктивных нормальных форы Логика предикатов 2.3.1. Предикаты, кванторы. Формулы логики преднкатов . 2.8.2. Равносильность формул, ......., ...... 2.3.3. Выполнимость п общезначимость. Проблема разрешимости 2.3.4. Эффективная вычнслимость............ ОСНОВЕ??>?Е ПОНЯТИЯ КОМБИНАТОРИКИ Комбинаторные схемы 3.1.1. Правила суммы н произведения,.......

3.1.2. Разлаещени» и сочеавнип 3.1.3, Разбиения. Полиномиальная формула 3.1.4. Классифаацааровааааае. Урновые схемы Некоторые методы пересчета. 3.2.1. Формула включений и исключений 30 31 31 37 «И 44 47 57 57 62 65 69 69 7о 77 79 Оглавление ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 103 Ориентированные н иеорнентпрованные графы. Основные понятия. Примеры прилсвкений теории графов 103 Матричное задание графа .................

Ш 4.24. Матрицы смежности и матрицы инцндеиций .. П1 4,2.2. Матряцы связности и расстояний....,.... 113 Пепси путей и графе 118 4.3.1. Алгоритмы нахождения путей и экстремальных путей в графе. Примеры прикладных задач... 118 4,3.2. Специальные цепи в графе. Задача о коммивояжере 125 Устойчнвые подмножества гра4м. Ядра....... 128 4А.1. Внутренне и внешне устойчивые множества... 128 4А.2. Ядра графа.

Уровни графа............, 131 Деревья . 136 4.5.1. Определение н свойства деревьев ...,..... 136 4.5.2. Остовное дерево графа............... 137 Плоские графы . 142 Потоки в сетях 146 4.7.1. Транспортные сети ................. 146 1.7.2. Гйакспмельпый поток в сети........., .. 148 4.7.3. Паросочстанпя в двудольных графах....... 152 О вычислительной сложности алгоритмов........ 154 Литература Предисловие Во взаимоотношениях математики и ес приложений в середине ХХ века произошел существенный перелом. Математические методы, традиционно используемые в таких областях, как физика, механика, инженерные науки, стали вторгаться в самые различные сферы науки и практики — от биологии, экономики, социологии, психологии до компьютерных технологий.

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

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

Уместно напомнить высказывание известного экономпста Дж. М. Кейнса, который говорил, что «экономическая теория является скорее методом., чеы учением, интеллектуальным инструментом, техникой мышления, позволяя тому, кто владеет ею., приходить к правильным заключениям», Форми- Предисловие рование «техники мышления» является важной составля1ощей для любой научной теории, В предлагаемом учебном пособии освещены те вопросы, которые можно отнести к началам изучения дисциплины «Дискретная математика»: оно базируется на лекционном курсе, читаемом в течение ряда лет для экономических специальностей Московского авиационного института. В то же время зто пособие может использоваться студентами, обучшощимися по специальности прикладная математика и информатика, хотя программа этой дисциплины для них 'значительно шире. Автор выражает благодарность С.

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

Приводится пример интерпретации отношения порядка, позволяющий сформировать модель прикладной задачи ранжирования и выбора наилучших объектов. Мы также считаем полезным остановиться в этом разделе на понятии алгебраической операции на множестве. Первоначально ограниченное натуральными числами оно постепенно расширялось и стало применяться к элементам совершенно «нечислового» характера. 1.1. Начальные понятия теории множеств 1.1.1. Понятие множества Под мноаюестеом О будем понимать любое собрание определенных и различимых между собой объектов, мыслимое как единое целое, Эти объекты называются элементами множества Я. В этом интуитивном определении, принадлежащем немецкому математику Г.

Кантору, существенным Являетсл то обстоятельство, что собрание предметов само рассматривается как один предмет, мыслится как единое целое. Что касается самих предметов, которые могут входить в множество, то относительно них существует значительная свобода. Это может быть множество студентов, присутствующих на лекции, множество целых чисел, множество точек плоскости, множество всех людей,. Глава 1. МНО?КЕСТВА И ОТНОШЕНИЯ живущих на Земле.

Заметим., что канторовская формулировка позволяет рассматривать множества, элементы которых по той или нцой причине нельзя точно указать (например, множество простых чисел, множество русских воинов, погибших в битве на Куликовом поле, и т. д.), Символоьт Е обозначается отношение принадлежности. Запись х Е о' означает; что элемент х принадлежит множеству о'. Если элемент х не принадлежит множеству Б, то пишут х Е о'.

Г. Кантором сформулировано несколько интуитивных принципов, которые естественно считать выполняющимися для произвольных множеств, Интуитивный принцип объемности. Множества А и В считпаютпся равными, если они состоят иэ одних и тех же элеметттов. Записывают А = В, если А и В равны, н А ф  — в противном случае. Пример 1.1. Проиллюстрируем принцип объемности. Множество А всех положительных четных чисел равно множеству В положительных целых чисел, представимых в виде суммы двух положительных нечетных чисел. Действительно, если х Е А, то для некоторого целого положительного числа т х = 2ш; тогда х = (2т — 1) + 1, т.