Самохин А.В. Математическая логика и теория алгоритмов ОНЛАЙН


В основном тексте содержится более двухсот задач, в основном теоретической направленности, решение которых поможет разобраться в тонкостях теории; некоторые из них могут стать основой для научно-исследовательской работы студентов.
Содержание
Предисловие ………………………………………………………………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



Читать онлайн
скачать бесплатно


Теги:
теория алгоритмов, Математическая логика, Самохин математическая логика

Коментарі до Самохин А.В. Математическая логика и теория алгоритмов ОНЛАЙН