Математическая логика: [Учеб. пособие для мат. спец. пед. ин-тов

Предисловие ......Page 4 Введение ......Page 6 Указатель обозначений ......Page 9 1.1.2. Высказывание ......Page 10 1.1.3. Алфавит и формулы алгебры высказываний ......Page 11 1.1.4. Эффективность определения формулы. Соглашение об опускании скобок ......Page 12 1.1.5. Семантика букв алфавита алгебры высказываний ......Page 13 1.1.6. Истинностные значения и истинностные таблицы формул алгебры высказываний ......Page 15 1.1.7. Отношение равносильности формул ......Page 16 1.1.8. Истинностные функции ......Page 17 1.1.9. Совершенные нормальные формы истинностных функций ......Page 18 1.1.10. Полные системы истинностных функций ......Page 20 1.1.11. Виды формул алгебры высказываний и их классификации ......Page 21 1.1.12. Важнейшие свойства общезначимых формул ......Page 22 1.1.13. Важнейшие общезначимые формулы ......Page 23 1.1.14. Методы установления общезначимости формул. Равносильные преобразования формул ......Page 25 1.1.15. Отношение логического следования и его связь с общезначимостью ......Page 27 1.1.16. Важнейшие правила следования ......Page 30 1.1.17. Применения языка алгебры высказываний ......Page 33 1.2.1. Алфавит, формулы, система аксиомных схем и правило вывода теории L ......Page 40 1.2.2. Формальное доказательство и формальный вывод ......Page 41 1.2.3. Свойства отношения выводимости ......Page 43 1.2.4. Непротиворечивость теории L ......Page 51 1.2.5. Правила введения и удаления логических операторов ......Page 52 1.2.6. Полнота теории L ......Page 58 1.2.8. Разрешимость теории L ......Page 63 1.2.9. Использование правил введения и удаления и МТ1 при установлении существования доказательств и выводов в теории L ......Page 65 1.2.10. Независимость аксиом теории L ......Page 71 2.1.2. Предикат, логическая функция. Область определения, область значений и область истинности логической функции ......Page 75 2.1.3. Ионы и переменные ......Page 77 2.1.4. Формулы алгебры предикатов ......Page 78 2.1.5. Семантика букв алфавита алгебры предикатов ......Page 80 2.1.6. Свободные и связанные вхождения переменных. Замкнутая и открытая формулы ......Page 85 2.1.7. Интерпретации формул. Предметные интерпретации формул ......Page 87 2.1.8. Истинностные таблицы формул алгебры предикатов ......Page 90 2.1.9. Отношение равносильности формул алгебры предикатов ......Page 93 2.1.10. Виды формул алгебры предикатов. Важнейшие общезначимые формулы алгебры предикатов ......Page 95 2.1.11. Важнейшие свойства общезначимых формул ......Page 98 2.1.12. Отношение логического следования в алгебре предикатов ......Page 103 2.1.13. Применение языка алгебры предикатов ......Page 106 2.2.1. Алфавит и формулы теории PL. Системы аксиомных схем. Правила вывода. Формальное доказательство. Формальный вывод ......Page 111 2.2.2. Непротиворечивость теории PL ......Page 112 2.2.3. Правила введения и удаления кванторов ......Page 113 2.2.4. Применения теории PL ......Page 115 3.1.1. Аксиоматический метод: три стадии развития ......Page 119 3.1.2. Формализованные языки ......Page 121 3.1.3. Синтактика формализованного языка: термы и формулы ......Page 122 3.2.1. Язык теории Аr ......Page 123 3.2.3. Логика теории Аr ......Page 124 3.2.4. Естественная (стандартная) интерпретация теории Аr ......Page 125 3.2.5. Теоремы теории Аr ......Page 127 4.1.1. Проблема разрешения и разрешающий алгоритм ......Page 130 4.1.2. Проблема вычисления и вычислительный (вычисляющий) алгоритм ......Page 131 4.1.3. Интуитивное понятие алгоритма ......Page 132 4.1.4. Потребность в математическом уточнении интуитивного понятия алгоритма ......Page 137 4.2.1. Определение класса рекурсивных функций ......Page 139 4.2.2. Примеры рекурсивных функций ......Page 141 4.3.1. Алгоритмы над словами (интуитивное понятие) ......Page 144 4.3.2. Нормальный алгоритм Маркова ......Page 150 4.3.3. Тезис Чёрча — Маркова ......Page 151 4.4.1. Интуитивные понятия ......Page 152 4.4.2. Машина Тьюринга — математическое понятие алгоритма ......Page 155 4.4.3. Вычислимость по Тьюрингу. Тезис Чёрча — Тьюринга ......Page 156 4.4.4. Существование невычислимых функций ......Page 159 4.4.5. Применения к формальной арифметике (формальная система Аг) ......Page 163 1.1. Алгебра высказываний ......Page 167 1.2. Исчисление высказываний (теория L) ......Page 194 2.1. Алгебра предикатов ......Page 204 2.2. Исчисление предикатов (теория PL) ......Page 238 3.1. Классы разрешимых вопросов и вычислимых функций ......Page 246 3.2. Машина Тьюринга ......Page 251 Ответы. Указания. Решения ......Page 258 Литература ......Page 261 Терминологический указатель ......Page 262