Донской В.И. Дискретная математика. - Симферополь, Сонат, 2000. - 360 с.
Книга представляет собой учебное пособие для студентов университетов, полностью соответствующее программе курса "Дискретная математика" для специальностей "Информатика" и "Прикладная математика". Может быть использовано студентами смежных специальностей и специалистами в области теоретической и прикладной информатики, программистами и разработчиками прикладных систем.
Оглавление
Глава I. Вводные понятия и элементарные основы
1. Элементы теории множеств....................................................7
2. Отношения...................................................17
3. Функции...................................................................28
4. Основные понятия теории алгебраических структур..........................38
5. Частично упорядоченные множества, решетки и булевы алгебры...............48
Глава II. Булевы функции
1. Основные определения ..............................................57
2. Реализация булевых функций формулами и операция суперпозиции.................63
3. Двойственные формулы и функции ........................................66
4. Совершенные нормальные формы.......................................69
5. Полнота подклассов булевых функций .......................................73
6. Функциональное замыкание и замкнутые классы в Р2...........................77
7. Критерий Э. Поста полноты в Р2............................................83
Глава III. Функции к-значной логики
1. Основные определения ........................................................87
2. Полные системы в ...........................................................93
3. Критерии полноты в Pj.......................................................98
Глава IV. Элементы комбинаторики
1. Простейшие комбинаторные формулы, коэффициенты многочленов, разбиения множеств...................102
2. Основные приемы комбинаторного оценивания...............................111
3. Рекуррентные соотношения ..................................................115
4. Производящие функции........................................................127
Глава V. Дизъюнктивные нормальные формы
1. Основные определения .......................................................138
2. Сокращенные ДНФ.............................................................150
3. Тупиковые ДНФ.................................................................162
4. Подходы к решению задач минимизации ДНФ......................................170
5. Понятие о локальных алгоритмах упрощения ДНФ.................................177
Глава VI Графы
1. Основные определения....................................................182
2. Эйлеровы и гамильтоновы графы...........................................193
3. Деревья ................................................................199
4. Планарные графы .......................................................204
5. Задачи раскраски планарных графов......................................207
Глава VII. Конечные автоматы
1. Функции, преобразующие последовательности..............................217
2. Деревья, задающие детерминированные функции............................223
3. Ограниченно-детерминированные функции, диаграммы Мура и канонические уравнения ............................227
4. Операции над ограниченно-детерминированными функциями и полнота в классе ..................................234
5. Определение и свойства абстрактных автоматов...........................239
6. Минимизация абстрактных автоматов ....................................245
7. Представление событий в автоматах ................................252
8. Основы структурного синтеза автоматов................................259
Глава VIII. Введение в математическую логику
1. Метод формальных (аксиоматических) теорий...........................269
2. Определение исчисления высказываний как аксиоматической теории......272
3. Свойства теории L ................................................282
4. Теории первого порядка ...........................................289
5. Исчисление предикатов первого порядка.............................298
Глава IX. Основы теории алгоритмов
1. Интуитивное понятие алгоритма и его уточнение в модели Маркова.........301
2. Алгоритмическая модель Тьюринга.......................................307
3. Частично-рекурсивные функции .........................................316
4. Эквивалентность алгоритмических систем ...............................335
5. Алгоритмически неразрешимые проблемы.................................336
6. Вычислительная сложность проблем .....................................343
Список литературы ...........................................................354
Дискретная математика, мат. логика, теория алгоритмов, численные методы / Математика / Математика для студентов, аспирантов и научных работников