Введение

Г л а в а 1. Основные понятия теории множеств
1. Предварительные сведения из теории множеств
2. Операции на множествах и их специальные свойства

Г л а в а 2. Элементы математической логики
1. Высказывания. Операции над высказываниями
2. Зависимости между операциями
3. Функции алгебры логики
4. Булевы формулы. Логическая оболочка системы булевых функций
5. Разложение функций по переменным
6. Совершенная дизъюнктивная нормальная форма
7. Совершенная конъюнктивная нормальная форма
8. Двойственность
9. Полнота и замкнутость
10. Многочлены Жегалкина
11. Классы Поста. Теорема Поста
12. Импликанты и минимизация ДНФ
13. Предикаты и кванторы
14. Предикатные формулы и операции над множествами
15. Задача выполнимости предиката

Г л а в а 3. Основные определения и задачи теории графов
1. Основные определения
2. Сети, контактные схемы и булевы формулы
3. Задача, с которой началась теория графов
4. Задачи об оптимальных путях
5. Простые циклы в графах. Цикломатическое число графа
6. Эйлерова характеристика плоского графа
7. Потоки в транспортных сетях
8. Теорема о системе различных представителей и её приложение
к теории графов
9. Поток, насыщающий выходные дуги

Г л а в а 4. Элементы теории конечных автоматов
1. Понятие автомата
2. Варианты автоматов
3. Автоматы и графы
4. Минимизация числа состояний автомата
5. Распознавание множеств автоматами
6. Детерминизация источников и синтез автоматов

Список литературы

Приложение: задания для домашних контрольных работ

Список основных обозначений

Предметный указатель