Дискретная математика. Теория и практикум. Учебник

Предисловие
Введение
Глава 1. Алгебра высказываний
§ 1.1. Высказывания. Операции над
высказываниями
§ 1.2. Формулы алгебры высказываний
§ 1.3. Двойственность в алгебре высказываний.
Принцип двойственности. Закон двойственности
§ 1.4. Нормальные формы. СДНФ. СКНФ. Понятие о
показателе степени. Показательные уравнения
§ 1.5. Основные проблемы алгебры высказываний.
Критерии тождественной истинности и
тождественной ложности
§ 1.6. Релейно-контактные схемы и схемы из
функциональных элементов
Глава 2. Алгебры предикатов и множеств.
Отображения
§ 2.1. Предикаты. Логические операции над
предикатами. Кванторы
§ 2.2. Кванторы, их свойства и применение
§ 2.3. Алгебра множеств
§ 2.4. Отображения. Образ и прообраз множества
при отображении. Свойства образов и прообразов
§ 2.5. Типы отображений. Обратимость и
односторонняя обратимость
§ 2.6. Семейства множеств и операции над
семействами
Глава 3. Элементы комбинаторики
§ 3.1. Что такое комбинаторика? Число элементов
во множестве. Правило суммы
§ 3.2. Декартово произведение множеств,
множество степень
§ 3.3. Множества инъективных и биективных
отображений. Размещения, перестановки
§ 3.4. Бином Ньютона. Сочетания. Сочетания с
повторениями
§ 3.5. Количество сюръективных отображений
§ 3.6. Пути на решетке
§ 3.7. Генерация комбинаторных объектов
Глава 4. Отношения
§ 4.1. n-местные отношения. Булевы алгебры
отношений и матриц
§ 4.2. Бинарные отношения на множестве.
Свойства
бинарных отношений
§ 4.3. Отношение порядка и доминирование
§ 4.4. Отношение эквивалентности
Глава 5. Булевы функции
§ 5.1. Функции алгебры логики. Многочлены
Жегалкина
§ 5.2. Полнота и замкнутость. Классы Поста P0 и Р1
§ 5.3. Классы Поста L и S
§ 5.4. Класс Поста М
§ 5.5. Критерий полноты (теорема Поста)
§ 5.6. Предполные классы и их свойства
Глава 6. Элементы теории алгоритмов
§ 6.1. Что такое алгоритм? Вводные понятия
§ 6.2. Машина Тьюринга. Описание. Примеры машин
§ 6.3. Сочетания машин Тьюринга: композиция и
объединение. Машины с полулентами,
разветвление и итерация машин
§ 6.4. Тьюрингов подход к понятию "алгоритм".
Алгоритмически разрешимые и неразрешимые
проблемы
§ 6.5. Универсальная машина Тьюринга
Глава 7. Элементы теории графов
§ 7.1. Введение, общее определение графа.
Локальные характеристики
§ 7.2. Изоморфизм графов. Геометрические графы.
Плоские и неплоские графы. Реализуемость в R3.
Пути, цепи, контуры, циклы
§ 7.3. Части графа: подграф, частичный граф.
Связность и сильная связность, компоненты.
Мосты
графа
§ 7.4. Эйлеровы графы, критерий эйлеровости
§ 7.5. Деревья и леса
§ 7.6. Помеченные графы. Перечисление
помеченных деревьев. Матрицы графов
§ 7.7. Взвешенные графы. Задача о кратчайшем
соединении. Кратчайшие пути
§ 7.8. Пространства циклов и разрезов. Потоки в
сетях
Глава 8. Практикум по решению упражнений и
задач
§ 8.1. Таблицы истинности формул алгебры
высказываний
§ 8.2. Равносильные преобразования и упрощение
формул
§ 8.3. Двойственность в алгебре высказываний
§ 8.4. Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ
§ 8.5. Релейно-контактные схемы и схемы из
функциональных элементов
§ 8.6. Алгебра предикатов. Кванторы
§ 8.7. Алгебра множеств
§ 8.8. Отображения
§ 8.9. Комбинаторика
§ 8.10. Отношения
§ 8.11. Функции алгебры логики
§ 8.12. Машина Тьюринга
§ 8.13. Графы и их матрицы
Предметный указатель
Литература