| Предисловие | 3 |
| 1. Логика высказываний | 4 |
| 1.1. Высказывания | 4 |
| 1.2. Логические операции | 5 |
| 1.3. Формулы логики высказываний. Тавтологии | 9 |
| 1.4. Логическое следствие | 12 |
| 1.5. Некоторые применения тавтологий | 14 |
| 2. Функции алгебры логики и k - значной логики | 18 |
| 2.1. Понятие булевой функции. Элементарные функции | 18 |
| 2.2. Формулы, суперпозиции. Свойства элементарных булевых функций | 20 |
| 2.3. Принцип двойственности | 23 |
| 2.4. Разложение булевых функций попеременным | 24 |
| 2.5. Импликативная нормальная форма | 26 |
| 2.6. Полные системы булевых функций | 27 |
| 2.7. Важные замкнутые классы | 28 |
| 2.8. Критерий полноты | 31 |
| 2.9. Представление о теоремах Поста | 32 |
| 2.10. Функции k- значной логики | 33 |
| 2.11. Реализация функций k -значной логики формулами. Основные эквивалентности | 35 |
| 3. Исчисление высказываний | 38 |
| 3.1. Формальные аксиоматические теории | 38 |
| 3.2. Формулы и аксиомы исчисления высказываний. Примеры выводимых формул | 41 |
| 3.3. Дальнейшие свойства выводов | 43 |
| 3.4. Непротиворечие | 47 |
| 3.5. Полнота | 48 |
| 3.6. О независимости аксиом и k -значиых логиках | 52 |
| 4. Логика предикатов | 54 |
| 4.1. Предикаты | 55 |
| 4.2. Операции над предикатами. Формулы логики предикатов | 57 |
| 4.3. Интерпретации. Равносильность формул | 61 |
| 4.4. Основные равносильности | 66 |
| 4.5. Общезначимость. Выполнимость | 70 |
| 4.6. Понятие о теориях первого порядка | 76 |
| 5. Алгоритм | 79 |
| 5.1. Интуитивное понятие алгоритма и необходимость его уточнения | 80 |
| 5.2. Машины Тьюринга | 82 |
| 5.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга | 86 |
| 5.4. Операции над машинами Тьюринга | 89 |
| 5.5. Частично-рекурсивные функции (класс Ч) | 92 |
| 5.6. Классы Ч и Т | 97 |
| 5.7. Алгоритмически неразрешимые проблемы | 99 |
| 5.8. Универсальные машины Тьюринга и функции | 102 |
| 5.9. Некоторые общие теоремы теории алгоритмов | 105 |
| 5.10. k -Ленточные машины Тьюринга, k ≥ 1 (детерминированные и недетерминированные) | 111 |
| 5.11. Классы Р и NP . Проблема P =? NP . NP -полные проблемы | 116 |
| 5.12. О машинно-независимой теории сложности вычислений | 121 |
| 5.13. Перечисление рекурсивно-перечислимых множеств | 125 |
| Список литературы | 127 |