Книга: Дехтярь М. И. «Основы дискретной математики»

Серия: "Основы информационных технологий"

Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ( "законы логики" ), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.

Содержание:

Выходные данные...... 3 Лекция 1. Предварительные сведения...... 4 Лекция 2. Индукция и комбинаторика...... 16 Лекция 3. Булевы функции и их представления...... 31 Лекция 4. Эквивалентность формул и нормальные формы...... 47 Лекция 5. Полные системы функций и теорема Поста...... 68 Лекция 6. Хорновские формулы и задача получения продукции...... 81 Лекция 7. Язык логики предикатов...... 96 Лекция 8. Логика предикатов и базы данных...... 118 Лекция 9. Графы: представления, достижимость и связность...... 132 Лекция 10. Деревья...... 151 Лекция 11. Три алгоритма на графах...... 163 Список литературы...... 183

Издательство: "Национальный Открытый Университет «ИНТУИТ»" (2016)

ISBN: 9785947747140