Введение в дискретную математику. Яблонский С. В.— М.: Наука. Главная редакция физико-математической литературы, 1979.
Книга является введением в дискретную математику — раздел прикладной математики, бурно развивающийся в последние годы и являющийся базой для математической кибернетики. Она написана на основе курса лекций, читавшегося автором в течение ряда лет на факультете вычислительной математики и кибернетики Московского государственного университета.
Книга предназначается студентам факультетов прикладной математики, аспирантам, а также инженерам и специалистам, работающим в области прикладной математики.
ОГЛАВЛЕНИЕ
Предисловие.......................... 5
ЧАСТЬ I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Глава 1. Алгебра логики................... 7
§ 1. Функции алгебры логики............... 7
§ 2. Формулы. Реализация функций формулами....... 10
§ 3. Эквивалентность формул. Свойства элементарных функции.
Принцип двойственности............... 15
§ 4. Разложения булевых функций по переменным. Совершенная
дизъюнктивная нормальная форма ............ 10
§ 5. Полнота и замкнутость................. 23
§ 6. Важнейшие замкнутые классы. Теорема о полноте .... 27
§ 7. Представление о результатах Песта........... 34
Глава 2. Л'-значная логика.................. 35
§ 1. Функции /с-зиачпой логики. Формулы и реализация функций формулами..................... 35
§ 2. Примеры полных систем................ 39
§ 3. Распознавание полноты. Теорема о полноте......... 42
§ 4. Некоторые свойства существенных функций. Критерий полноты .......................... 47
§ 5. Особенности й-значных логик.............. 55
Глава 3. Ограниченно-детерминированные (автоматные) функции
с операциями.................... 62
§ 1. Детерминированные функции............. 62
§ 2. Задание детерминированных функций при помощи деревь
ев. Вес дерева...................... 67
§ 3. Ограниченно-детерминированные функции и способы их
задания........................ 73
§ 4. Операции над о.-д. функциями............. 78
§ 5. Примеры полных систем................. 88
§ 0. О соотношении операций С и О............ 91
Глава 4. Вычислимые функции................ 95
S 1. Машины Тьюринга................... 95
§ 2. Один метод построения машин Тьюринга....... 102
§ 3. Машинные коды и их преобразования......... 108
§ 4. Вычислимые функции................. 120
§ 5. Операции С, Пр и ц,................. 123
§ 6. Вычислимые функции и операции С, Пр, |,i....... 127
§ 7. Формула Клини. Частичная рекурсивпость вычислимых
функций. Примеры полных систем........... 136
4 ОГЛАВЛЕНИЕ
ЧАСТЬ П. ГРАФЫ И СЕТИ
Глава 1 . Графы . ...................... 143
§ 1. Реализация в евклидовом пространстве. Изоморфизм . . 143
§ 2. Оценка числа графов ................. 146
Глава 2. Сети ........................ 150
§ 1. Сети и их свойства ................... 150
§ 2. Оценка числа сетей ................... 154
§ 3. Двухполюсные сети из двухобъектных наборов ..... 158
§ 4. л-сети ......................... 171
ЧАСТЬ III. ТЕОРИЯ КОДИРОВАНИЯ
§ 1. Критерий однозначности декодирования ......... 177
§ 2. Алгоритмы распознавания однозначности декодирования 184
§ 3. Об одном свойстве взаимно однозначных кодов ...... 187
§ 4. Коды с минимальной избыточностью ........... 191
§ 5. Самокорректирующиеся коды .............. 199
ЧАСТЬ IV. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Глава 1. Дизъюнктивные нормальные формы ......... 206
§ 1. Понятие д.н.ф. Проблема минимизации булевых функций 206 § 2. Упрощение д.н.ф. и тупиковые д.н.ф. (относительно упро-
щения) ........................ 209
§ 3. Постановка задачи в геометрической форме ........ 215
§ 4. Сокращенная д.н.ф ................... 220
§ 5. Тупиковость на основе геометрических представлений. Ме-
тоды построения тупиковых д.н.ф ............. 222
§ 6. Некоторые однозначно получаемые д.н.ф ........ 229
§ 7. Понятие локального алгоритма ............. 235
Глава 2. Синтез схем из функциональных элементов ...... 2 10
§ 1. Понятие схемы из функциональных элементов ..... 240
§ 2. Проблема синтеза схем из Ф. Э ............. 248
§ 3. Элементарные методы синтеза .............. 252
§ 4. Нижняя оценка для L (п) ................ 256
§ 5. Оптимальный по порядку метод синтеза схем из Ф. Э. (ме-
тод Шеннона) ...................... 258
§ С. Синтез сумматора ................... 261
§ 7. Синтез схем из Ф. Э., реализующих симметрические функ-
263
Литература ........................... 266
Предметный указатель ...................... 268
ПРЕДИСЛОВИЕ
Дискретная математика — часть математики, которая ааро-дилась в глубокой древности. Как говорит само заглавие, главной ее спецификой является дискретность, т. е. антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине этого века в связи с научно-техническим прогрессом, поставившим изучение сложных управляющих систем, в связи с внедрением ЭВМ. 13 узком смысле дискретная математика ограничивается только этими новыми разделами. Именно так это понимается и в данной книге. К упомянутым новым разделам мы относим: теорию функциональных систем; теорию графов и сетей; теорию кодирования; комбинаторный анализ; целочисленное программирование и т. п.
Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Книга содержит материал, соответствующий двум типам программ курса «Дискретная математика»: стандартной программе для факультетов прикладной математики и кибернетики большинства университетов и программе соответствующего курса, читаемого в МГУ. Эти программы не ставят целью дать большое количество материала фактического и имеющего спрос в данное время. Чрезмерная детализация и привязывание программы к специальным фактам опасно тем, что лет через 10—15 (а это как раз время активной деятельности обучаемых сейчас студентов) появятся новые факты, а старые частично утратят свою значимость. Ввиду этого главная задача курса — это обучение методам и мышлению, характерным для дискретной математики. Материал, вошедший в эту книгу, знакомит читателя с узловыми задачами из нескольких разделов дискретной математики и ее приложений. Он подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10—15) серьезных теорем с непохожими доказательствами, а также познакомить с приме-
Цена: 150руб.
