Дискретная математика. Теория и практикум (Яков Ерусалимский)

Предисловие
Введение
Глава 1. Алгебра высказываний
§ 1.1. Высказывания. Операции над высказываниями
§ 1.2. Формулы алгебры высказываний
§ 1.3. Двойственность в алгебре высказываний. Принцип двойственности. Закон двойственности
§ 1.4. Hормальные формы. СДHФ. СКHФ. Понятие о показателе степени. Показательные уравнения
§ 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. Полнота и замкнутость. Классы Поста Р0 и Р1
§ 5.3. Классы Поста L и S
§ 5.4. Класс Поста M
§ 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. Графы и их матрицы
Предметный указатель
Литература