Самохин А.В. Математическая логика и теория алгоритмов. - М., 2003. - 237 с.
Главы III и IV имеют отношение к алгоритмическому проектированию электронных схем; главы V и VI — к автоматическому порождению синтаксически правильных текстов, т.е. к специальному программированию; остаток книги посвящен основам теории алгоритмов: здесь обсуждаются, какие задачи вообще являются алгоритмически разрешимыми и какова сложность соответствующих алгоритмов. В главах I и II собран материал по началам теории множеств, необходимый для понимания остального текста (как, впрочем, и почти всей математики).
В основном тексте содержится более двухсот задач, в основном теоретической направленности, решение которых поможет разобраться в тонкостях теории; некоторые из них могут стать основой для научно-исследовательской работы студентов.
Содержание
Предисловие ........................................................................6
Глава I. Множества и мощности ............................................7
§1. Множества ..................................................................7
§2. Число элементов............................................................9
§3. Равномощные множества ................................................12
§4. Счётные множества........................................................14
§5. Теорема Кантора-Бернштейна ........................................19
§6. Теорема Кантора ..........................................................25
§7. Функции ......................................................................30
§8. Операции над мощностями ..............................................35
Глава II. Упорядоченные множества........................................40
§1. Отношения эквивалентности и порядка..............................40
§2. Изоморфизмы................................................................46
§3. Фундированные множества..............................................50
§4. Вполне упорядоченные множества ....................................53
Глава III. Логика высказываний ............................................57
§1. Высказывания и операции................................................57
§2. Полные системы связок ..................................................64
§3. Схемы из функциональных элементов ................................70
Глава IV. Исчисление высказываний ......................................85
§1. Исчисление высказываний ..............................................85
§2. Второе доказательство теоремы о полноте ..........................93
§3. О женской логике ..........................................................96
Глава V. Языки первого порядка ............................................99
§1. Формулы и интерпретации ..............................................99
§2. Определение истинности ................................................103
§3. Выразимые предикаты....................................................106
§4. Выразимость в арифметике..............................................109
§5. Невыразимые предикаты: автоморфизмы............................112
Глава VI. Исчисление предикатов ..........................................116
§1. Общезначимые формулы ................................................116
§2. Аксиомы и правила вывода..............................................118
§3. Корректность исчисления предикатов ................................123
§4. Выводы в исчислении предикатов......................................126
4.1. Примеры выводимых формул ....................................126
4.2. Выводимость из посылок ..........................................128
4.3. Переменные и константы ..........................................131
§5. Полнота исчисления предикатов ......................................132
§6. О выводах и доказательствах ..........................................140
Глава VII. Вычислимые функции, разрешимые и перечислимые множества..........145
§1. Вычислимые функции ....................................................145
§2. Разрешимые множества ..................................................146
§3. Перечислимые множества................................................147
§4. Перечислимые и разрешимые множества............................149
§5. Перечислимость и вычислимость ......................................150
Глава VIII. Универсальные функции и неразрешимость ............153
§1. Универсальные функции..................................................153
§2. Диагональная конструкция ..............................................154
§3. Перечислимое неразрешимое множество ............................156
Глава IX. Нумерации и операции............................................158
§1. Главные универсальные функции......................................158
§2. Вычислимые последовательности вычислимых функций .............161
§3. Главные универсальные множества ..................................162
§4. Множества номеров........................................................164
Глава X. Теорема о неподвижной точке....................................168
§1. Неподвижная точка и отношения эквивалентности................168
§2. Программа, печатающая свой текст ..................................170
§3. Несколько замечаний......................................................171
3.1. Бесконечное множество неподвижных точек ..................171
3.2. Неподвижная точка с параметром ..............................172
3.3. Неподвижная точка для перечислимых множеств ..........173
3.4. Пример использования..............................................174
Глава XI. Машины Тьюринга ................................................175
§1. Зачем нужны простые вычислительные модели? ..................175
§2. Машины Тьюринга: определение ......................................175
§3. Машины Тьюринга: обсуждение ......................................177
Глава XII. Арифметичность вычислимых функций....................180
§1. Программы с конечным числом переменных........................180
§2. Машины Тьюринга и программы......................................182
§3. Арифметичность вычислимых функций..............................184
§4. Теоремы Тарского и Гёделя ............................................187
§5. О непостижимой эффективности математики ......................189
Глава XIII. Рекурсивные функции ..........................................194
§1. Примитивно рекурсивные функции....................................194
§2. Примеры примитивно рекурсивных функций ......................195
§3. Примитивно рекурсивные множества ................................196
§4. Другие виды рекурсии ....................................................198
§5. Машины Тьюринга и примитивно рекурсивные функции . . . 200
§6. Частично рекурсивные функции........................................202
§7. Оценки скорости роста. Функция Аккермана ......................204
Задачи ................................................................................208
§1. Алгебра высказываний....................................................208
1.1. Таблицы истинности ................................................208
1.2. Порядок действий и упрощённая запись формул ............209
1.3. Равносильные преобразования и упрощение формул .... 210
§2. Двойственность в алгебре высказываний ............................213
§3. Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ ..................215
§4. Релейно-контактные схемы и схемы из функциональных элементов ........219
4.1. Задачи синтеза........................................................219
4.2. Анализ схем............................................................220
§5. Предикаты, кванторы, множества и отображения ................224
5.1. Предикаты, кванторы, множества ..............................224
5.2. Отображения ..........................................................227
§6. Функции алгебры логики ................................................231
§7. Машина Тьюринга ........................................................234
Список литературы................................................................237
