| От авторов | 3 |
| 1. ЯЗЫК ТЕОРИЙ ПЕРВОГО ПОРЯДКА |
| 1.1. Язык логики высказываний | 4 |
| 1.2. Язык логики предикатов первого порядка | 16 |
| 2. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И КОМБИНАТОРИКИ |
| 2.1. Множества, способы их задания. Подмножества | 23 |
| 2.2. Операции над множествами. Основные равенства | 26 |
| 2.3. Упорядоченная пара. Декартово произведение множеств.
Отношения | 29 |
| 2.4. Свойства бинарных отношений. Отношение эквивалентности | 31 |
| 2.5. Функции. Счетные множества | 33 |
| 2.6. Размещения и размещения с повторениями | 37 |
| 2.7. Сочетания и сочетания с повторениями | 38 |
| 2.8. Формула бинома Ньютона | 42 |
| 2.9. Рекуррентные соотношения и их решения | 45 |
| 2.10. Формула включений и исключений | 50 |
| 2.11. Производящие функции | 55 |
| 2.12. Неориентированные графы | 61 |
| 3. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ |
| 3.1. Основные понятия | 73 |
| 3.2. Важные примеры грамматик | 75 |
| 3.3. А-грамматики и автоматы | 77 |
| 3.4. Некоторые свойства грамматик | 79 |
| 3.5. Иерархия языков | 81 |
| 3.6. Грамматический разбор | 82 |
| 3.7. КС-языки и синтез языков программирования | 85 |
| 3.8. Аксиоматические грамматики | 90 |
| 4. АЛГОРИТМЫ | |
| 4.1. Интуитивное понятие алгоритма и необходимость его
уточнения | 93 |
| 4.2. Машины Тьюринга | 95 |
| 4.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга | 98 |
| 4.4. Операции над машинами Тьюринга | 101 |
| 4.5. Частично-рекурсивные функции (класс Ч) | 104 |
| 4.6. Классы Ч и Т | 109 |
| 4.7. Одна просто определяемая невычислимая функция | 111 |
| 4.8. Алгоритмически неразрешимые проблемы | 113 |
| 4.9. Универсальные машины Тьюринга и функции | 117 |
| 4.10. Некоторые общие теоремы теории алгоритмов | 119 |
| 4.11. k -Ленточные машины Тьюринга, k ≥1 (детерминированные
и недетерминированные) | 125 |
| 4.12. Классы Р и NP . Проблема Р =? NP . NP - полные и NP -трудные проблемы | 130 |
| 4.13. 0 машинно-независимой теории сложности вычислений | 134 |
| 4.14. Перечисление рекурсивно-перечислимых множеств | 138 |
| 4.15. Конечные автоматы | 139 |
| 4.16. Приближенные (эвристические) алгоритмы | 146 |
| ЛИТЕРАТУРА | 151 |