Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное - М., 2003. - 484 с.
Книга является введением в дискретную математику. Она написана на основе курса лекций, который читал автор в течении ряда лет на факультете вычислительной математики и кибернетики Московского государственного университета.Третье издание вышло в 2001 г. Содержит разделы: функциональные системы с операциями (алгебра логики, к-значная логика, вычислимые функции), комбинаторный анализ, графы и сети, теория кодирования, некоторые приложения в кибернетике.
ОГЛАВЛЕНИЕ
Об авторе..................................
Предисловие............................
ЧАСТЬ I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Глава 1. Алгебра логики....................9
§ 1. Функции алгебры логики................9
§ 2. Формулы. Реализация функций формулами ... 14
§ 3. Эквивалентность формул. Свойства элементарных
функций. Принцип двойственности.....20
§ 4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма ..... 25
§ 5. Полнота и замкнутость........30
§ 6. Важнейшие замкнутые классы. Теорема о полноте 33
§ 7. Представление о результатах Поста.....42
Глава 2. k -значная логика.........43
§ 1. Функции k-значной логики. Формулы и реализация
функций формулами ..................43
§ 2. Примеры полных систем........48
§ 3. Распознавание полноты. Теорема о полноте . . 51
§ 4. Некоторые свойства существенных функций. Критерий полноты...........56
§ 5. Особенности k-значных логик......65
Глава 3. Огравиченно-детерминированные (автоматные)
функции с операциями..........73
§ 1. Детерминированные функции......73
§ 2. Задание детерминированных функций при помощи
деревьев. Вес дерева.........78
§ 3. Ограниченно-детерминированные функции и способы их задания...........86
§ 4. Операции над о.-д. функциями......91
§ 5. Примеры полных систем........105
§ 6. О соотношении операций С и О......110
Глава 4. Вычислимые функции........113
§ 1. Машипы Тьюринга.........ИЗ
§ 2. Один метод построения машин Тьюринга ... 121
§ 3. Машинные коды и их преобразования .... 129
§ 4. Вычислимые функции........143
§ 5. Операции С, Пр и мю.........146
§ 6. Вычислимые функции и операции С, Пр, мю ....151
§ 7. Формула Клини. Частичная рекурсивность вычислимых функций. Примеры полных систем .... 162
ЧАСТЬ II. КОМБИНАТОРНЫЙ АНАЛИЗ
§ 1. Комбинаторные объекты и комбинаторные числа . 171
§ 2. Простейшие свойства комбинаторных объектов и
чисел.............173
§ 3. Методы изучения комбинаторных объектов и чисел 188
§ 4. Оценки и асимптотики для комбинаторных чисел 202
ЧАСТЬ III ГРАФЫ И СЕТИ
Глава 1. Графы............222
§ 1. Реализация в евклидовом пространстве. Изоморфизм 222
§ 2. Оценка числа графов.........226
Глава 2. Сети.............227
§ 1. Сети и их свойства..........227
§ 2. Оценка числа сетей..........232
§ 3. Двухполюсные сети из двухобъектных наборов ....... 237
§ 4. n-сети.............253
ЧАСТЬ IV
ТЕОРИЯ КОДИРОВАНИЯ
§ 1. Критерий однозначности декодирования ...... 260
§ 2. Алгоритм распознавания однозначности декодиро- 268
вания .............
§ 3. Об одном свойстве взаимно однозначных кодов ...... 272
§ 4. Коды с минимальной избыточностью .... 276
§ 5. Самокорректирующиеся коды......288
ЧАСТЬ V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Глава 1. Дизъюнктивные нормальные формы .... 297
§ 1. Понятие д. и. ф. Проблема минимизации булевых
функций............297
§ 2. Упрощение д. н. ф. и тупиковые д. п. ф. (относительно упрощения).........300
§ 3. Постановка задачи в геометрической форме . . 307
§ 4. Сокращенная д. н. ф..........312
§ 5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. н. ф. . . 316
§ 6. Некоторые однозначно получаемые д. н. ф. . . 324
§ 7. Понятие локального алгоритма......331
Глава 2. Синтез схем из функциональных элементов . . 336
§ 1. Понятие схе.мы из функциональных элементов . 336
§ 2. Проблема синтеза схем из Ф. Э......345
§ 3. Элементарные методы синтеза......351
§ 4. Нижняя оценка для L(n)........355
§ 5. Оптимальный по порядку метод синтеза схем из
Ф. Э. (метод Шеннона)........357
§ 6. Асимптотически наилучший метод синтеза схем из
Ф. Э. (метод Лупанова)........361
§ 7. Синтез сумматора..........364
§ 8. Синтез схем из Ф. Э., реализующих симметрические
функции............366
Список литературы.............370
Предметный указатель...........373
Указатель обозначений ..........381
