ББК 22.144 Г62 УДК 519.45 Рецензенты: кафедра «Проектирование и организация систем» Московского физико-технического института (зав. кафедрой акад. Г. С. Поспелов); чл.-кор. АН Каз.ССР, проф. В. М. Амербаев (Московский институт электронной техники) Горбатов В. А. Г62 Основы дискретной математики: Учеб. пособие для студентов вузов.—М.: Высш. шк., 1986.—311 с., ил. В пер.: 1 р. В книге излагаются основы алгебраических систем, математической ло- гики, теории графов и мографов, теории формальных грамматик и автома- тов, прикладной теории алгоритмов и характеризации моделей, которые в совокупности образуют единый методически взаимосвязанный курс «Дискрет- ная математика». В конце каждой главы приведены упражнения и задачи. Для студентов вузов, обучающихся по специальностям «Прикладная математика», «Электронные вычислительные машины», «Автоматизирован- ные системы управления», «Конструирование и производство электронно- вычислительной аппаратуры», «Системы автоматизированного проектиро- вания». 1702070000-073 ^_og 001 (01)-86 ББК 22.144 517.1 © Издательство «Высшая школа», 1986 ПРЕДИСЛОВИЕ В свете решений партии и правительства претворяются в жизнь гран- диозные научно-технические программы по созданию систем автомати- зации проектирования (САПР), гибкого автоматизированного произ- водства (ГАП), автоматизированных систем управления (АСУ), авто- матизированных систем научных исследований (АСНИ) и других комплексных интегрированных автоматизированных систем обработки информации. Выполнение указанных программ немыслимо без ускоренного внед- рения результатов научно-технического прогресса, особенно достигну- тых в области математики. Большой вклад в развитие современной математики внесли советские ученые М. В. Келдыш, А. И. Мальцев, А. А. Марков, Г. И. Марчук, П. С. Новиков, Л. С. Понтрягин, А. А. Самарский, А. Н. Тихонов и др. Для создания и эксплуатации комплексных интегрированных авто- матизированных систем обработки информации и их компонент (мате- матического обеспечения, пакетов прикладных программ, распределен- ных банков данных, встроенных микропроцессорных систем, сетей пере- дачи данных, систем с разделением ресурсов и распределенной обра- боткой информации) необходимо знание дискретной математики, основ- ной особенностью которой является отсутствие предельного перехода и непрерывности, характерных для классической математики. Книга представляет собой единый методически взаимоувязанный курс, который будет полезен для подготовки инженеров-математиков (специальность «Прикладная математика»), инженеров-системотехников (специальности «Электронные вычислительные машины», «Автоматизи- рованные системы управления») и инженеров других специальностей, таких, как «Конструирование и производство электронно-вычислитель- ной аппаратуры», «Робототехнические системы» и «САПР». Она состоит из пяти глав и включает основные разделы со- временной дискретной математики: алгебраические системы, математи- ческую логику, теорию графов и мографов (гиперграфов), теорию автоматов и формальных грамматик, прикладную теорию алгоритмов и характеризационный анализ. В конце каждой главы приведены задачи и упражнения различной трудности; они предназначены для закрепле- ния введенных понятий, рассмотренных алгоритмов и конструкций. Последняя глава посвящена центральному разделу дискретной мате- матики — характеризационному анализу, решение задач которого являет- ся основой разработки оптимальных алгоритмов и эффективных мате- матического, программного, информационного и технического обеспе- чении современных комплексных интегрированных автоматизированных систем обработки информации. Автор выражает искреннюю признательность за критические заме- чания акад. А. А. Самарскому, акад. Г. С. Поспелову, чл.-кор. АН Каз.ССР В. М. Амербаеву, проф. В. А. Мясникову, проф. Д. А. Поспелову, канд. техн. наук В. Л. Торхову. Автор ЛИТЕРАТУРА К введению B.I. Axo А., Хочкрофт Дж., Ульман Дмс. Построение и анализ вы- числительных алгоритмов.—М.: Мир, 1979. 8.2. Горбатов В. А. Синтез логических схем в произвольном базисе.- В кн.: Теория дискретных автоматов. — Рига: Зинатне, 1967. 8.3. Горбатов В. А. Теория частично упорядоченных систем. - М.: Сов. радио, 1976. 8.4. Гудман С., Хидеттеми С. Введение в разработку и анализ алгорит- мов.- М.: Мир, 1981. 8.5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М.: Мир, 1982. 8.6. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. 8.7. Общая теория систем.—М.: Мир, 1966. 8.8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. 8.9. Свами М.. Тхуласираман К. Графы, сети и алгоритмы,— М.: Мир, 1984. К главе 1 1.1. Горбатов В. А. Синтез логических схем в многозначных логиках, основанный на структурных соотношениях. — В кн.: Многозначные элементы и структуры.—М.: Сов. радио, 1967. 1.2. Горбатов В. А., Павлов П. Г.. Четвериков В. Н. Логическое управ- ление информационными процессами.—М.: Энергоатомиздат, 1984. 1.3. Левин Д. Я. Язык сверхвысокого уровня СЕТЛ и его реализация.— Новосибирск: Наука, Сибирское отделение, 1983. 1.4. Мальцев А. И. Алгебраические системы.—М.: Наука, 1970. 1.5. Berge С., las Vergnas M. Sur un theoreme du type Konig pour hipergraphes, Ann. V. Y. Acad. Sci, 1975, № 1, 1970. К главе 2 2.1. Гильберт Д.. Бернайс П. Основания математики. Логические исчисле- ния и формализация арифметики. — М.: Наука, 1979. 2.2. Новиков П. С. Конструктивная математическая логика с точки зрения классической.—М,: Наука, 1977. К главе 3 3.1. Горбатов В. А. О гомеоморфном вложении графов и их дифферен- цировании.—В сб.: Доклады НТК по итогам НИР за 1968—1969 гг. секции автоматики, вычислительной и измерительной техники/Под ред. Ю. М. Ша- маева, В. А. Горбатова. - М.: МЭИ, 1969. 3.2. Горбатова М. В. Быстродействующий алгоритм раскраски вершин графа. — В кн.: Логическое управление в промышленности. — Ижевск: ИМИ, 1984. 304 К главе 4 4.1. Автоматизация проектирования сложных логических структур/Под, ред. В. А. Горбатова. — М.: Энергия, 1978. 4.2. Горбатов В. А. Семантическая теория проектирования автоматов.— М.: Энергия, 1979. 4.3. Горбатов В. А., Кафаров В. В., Павлов П. Г. Логическое управ- ление технологическими процессами. - М.: Энергия, 1978. 4.4. Горбатов В. А., Останков Б. Л., Фролов С. А. Регулярные структуры автоматного управления/Под ред. В. А. Горбатова.— М.: Машиностроение, 1980. 4.5. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов.— М.: Энергия, 1978. 4.6. Поспелов Д. А. Логико-лингвистические модели в системах управле- ния,—М.: Энергия, 1981. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Автомат 167 — асинхронный 169 — конечный 167 — магазинный 166 — Майхилла 166 — микропрограммный 195 — операционный 170 — синхронный 169 — управляющий 170 алгебра 10 — булева 23 — множеств (алгебра Кантора) 12 — отношений 28 — реляционная 30 алгоритм 42, 165 аргумент (переменная) функции 8 Базис — несвязный 219, 220 — связный 220 — топологический 210 — функциональный 210 буква — пропозициональная 73 Вес производной от булевой функции 66 высота элемента упорядоченного мно- жества 18 гиперкуб (и-мерный куб) 37 грамматика 163 — бесконтекстная 166 — контекстная 166 — линейная 167 — металинейная 167 — односторонне линейная 167 — с конечным числом состояний 163 грань — нижняя 17 — — наибольшая 18, 20 — верхняя 17 306 — — наименьшая 18, 20 граф 13 — взвешенный 89 — гомеоморфный 125 — двудольный 28 — зацепления 199 — затирания 202 — изоморфный 91 — квазиполный 148 — кубируемый 129 — переходов 184 — планарный 125 — полный 26 — связный 94 — — сильно 99 — — несильно 99 — связный — — реберно 141 — типа я о 217. — частичный 15 группа 11 — подстановок (группа Галуа) 11 группоид 10 — аддитивный 10 — ассоциативный 11 — идемпотентный 11 — куммутативный (абелев) 11 — мультипликативный 10 Диаграмма — Хассе 16 — Эйлера 7 диаметр графа 96 длина — микролуча 195 — пути 99 — упорядоченного множества 18 — цепи 18 Изоморфные — алгебры 23 — упорядоченные множества 18 интервал — множества — — максимальный 39 — структурный 22 — булевой функции — — единичный 52 — — максимальный 52 — — нулевой 52 исчисление — высказываний 73, 74 — предикатов 79 — — расширенное 81 — — узкое 80 Квазиплотность 148 квантор — всеобщности 79 — существования 79 класс — эквивалентности 19 — булевых функций — — линейных 56 — — монотонных 58 — — самодвойственных 58 — — сохраняющих константу 0 56 — - - I 56 — хроматический 141 коалгебра 216 — графов 216 код — дополнительный 179 — обратный 179 — прямой 177 кодирование — Айкена-Эмери 182, 183 — «в остатках» 183 — внутренних состояний 204 — - соседнее 208 — — частотно-матричное 204, 205 — Штибитца 182 кольцо 12 комплект 228 — пустой 228 компонента — связности 94 — — сильной 99 ко-операция 216 конституента 35 контур 99 Мажоранта подмножества 17 матрица — базисная — — разрезов 105 (коцикломатическая) — — цикломатическая 104 — инцидентности 26 — инциденций 90 — А-клеточная 97 — смежности 91 — — модифицированная 121 — цикломатическая 102 — частотная отношений 107 — — и-мерная 112 местность функции 8 микролуч 195 микрооперация 185 микропрограмма 186 миноранта подмножества 17 мограф 27 модель 28 — подчиненная 247 множество (а) 6 — равные 7 — семейство (булеан) 7 — упорядоченное 16 — — линейно 16 — — частично 16 Неокрестность 116 Область — значений функции 8 — определения функции 8 окрестность — единичного радиуса элемента (сече- ние) 14 отношение 13 — /i-арное 25 — — симметричное (5-отношение) 25 — бинарное 13 — — упорядоченности 16 — — — строгой 16 — предпорядка 16 — рефлексивное 14 — симметричное 15 — транзитивное 15 — эквивалентности 19 307 Предисловие ....................... Введение ........................ Глава 1. Алгебраические системы .............. 1.1. Множество, функция, операция. Способы задания ..... 1.2. Понятие алгебры. Фундаментальные алгебры ...... 1.3. Бинарные отношения, способы их задания и свойства . . . 1.4. Решетка .................... 1.5. Модель. Алгебра отношений ............ 1.6. Аксиоматика теории множеств. Минимизация представления множеств .................... : 1.7. Задачи и упражнения ................ Комментарии .................. Глава 2. Математическая логика .............. 2.1. Логика высказываний ................ 2.2. Минимизация булевых функций в классе ДНФ ...... 2.3. Полнота .................... 2.4. Синтез логических схем .............. 2.5. Исчисление высказываний .............. 2.6. Исчисление предикатов ............... 2.7. Задачи и упражнения ............... Комментарии .................. Глава 3. Теория графов и мографов ............. 3.1. Взвешенный граф и его матричное задание ...... 3.2. Связность и сильная связность графа ......... 3.3. Цикломатика .................. ] 3.4. Дифференцирование графов и мографов ....... ] 3.5. Устойчивость, покрытия, паросочетания ......... ; 3.6. Вложение графов ................. : 3.7. Раскраска вершин и ребер графа. Характеризация реберности : 3.8. Характеризация раскраски графов ........... 3.9. Задачи и упражнения ............... Комментарии .................. Глава 4. Теория формальных грамматик и автоматов ....... 4.1. Формальные грамматики .............. 4.2. Основные этапы проектирования автоматов ....... 4.3. Арифметические основы операционных автоматов ..... 4.4. Алгоритмический этап проектирования ......... 4.5. Абстрактное проектирование автоматов . •». . . . . . . 4.6. Кодирование внутренних состояний .......... 4.7. Структурное проектирование автоматов ......... 4.8. Моделирование автоматных систем сетями Петри ..... 4.9. Задачи и упражнения ............... Комментарии .................. 310 Глава 5. Прикладная теория алгоритмов. Харакгеризаи,и,нный анализ 5.1. Принципы характеризационного анализа. Построение комбина- торных алгоритмов ................ 5.2. Характеризация частичного упорядочения мографа ..... : 5.3. Характеризация выходной связности логических схем. Струк- турная минимизация ................ ; 5.4. Характеризация разложения графа переходов в частичное де- картово произведение ............... ; 5.5. Характеризация и методы оптимального размещения данных в памяти ЭВМ ................. ^ 5.6. Задачи и упражнения ............... Э Комментарии .................. 3 Литература ................... 3 Предметный указатель ............... 3