 | Я.М.Ерусалимский, 2000 (Rus)
Дискретная математика: теория, задачи, приложения
ПРЕДИСЛОВИЕ
Учебное пособие по дискретной математике. Содержит разделы: алгебра предикатов и множеств, отображения, элементы комбинаторики, отношения, булевы функции, элементы теории графов. Отдельный раздел составляют задачи и упражнения. Предназначено для студентов и преподавателей ВУЗов, инженеров-системотехников, программистов. Для школьников, изучающих математику и информатику углубленно
Оглавление
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 Число сюръективных отображений
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 Изоморфизм графов. Геометрические графы. Плоские и неплоские графы. Пути, цепи, контуры, циклы
7.3 Части графа: подграф, частичный граф
7.4 Эйлеровы графы, критерий эйлеровости
7.5 Деревья и леса
7.6 Помеченные графы. Перечисление помеченных деревьев. Матрицы графов
7.7 Взвешенные графы. Задача о кратчайшем соединении. Кратчайшие пути
8. ЗАДАЧИ И УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
8.1 Алгебра высказываний
8.2 Двойственность в алгебре высказываний
8.3 Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ
8.4 Релейно-контактные схемы и схемы из функциональных элементов
8.5 Предикаты и кванторы, множества, отображения
8.6 Элементы комбинаторики. Отношения
8.7 Функции алгебры логики
8.8 Машина Тьюринга
8.9 Графы и их матрицы
Рекомендуемая литература
|