Предисловие
Часть 1. Курс лекций по математической логике
Введение
Глава I. Алгебра логики
§ 1. Понятие высказывания
§ 2. Логические операции над высказываниями
§ 3. Формулы алгебры логики
§ 4. Равносильные формулы алгебры логики
§ 5. Равносильные преобразования формул
§ 6. Алгебра Буля
§ 7. Функции алгебры логики
§ 8. Представление произвольной функции алгебры логики
в виде формулы алгебры лотки
§ 9. Закон двойственности
§ 10. Дизъюнктивная нормальная форма и совершенная
дизъюнктивная нормальная форма (ДНФ и СДНФ)
§ 11. Конъюнктивная нормальная форма и совершенная
конъюнктивная нормальная форма (КНФ и СКНФ)
§ 12. Проблема разрешимости
§ 13. Некоторые приложения алгебры логики
Глава II. Исчисление высказываний
§ 1. Понятие формулы исчисления высказываний
§ 2. Определение доказуемой формулы
§ 3. Производные правила вывода
§ 4. Понятие выводимости формулы из совокупности формул
§ 5. Понятие вывода
§ 6. Правила выводимости
§ 7. Доказательство некоторых законов логики
§ 8. Связь между алгеброй высказываний и исчислением высказываний
§ 9. Проблемы аксиоматического исчисления высказываний
Глава III. Логика предикатов
§ 1. Понятие предиката
§ 2. Логические операции над предикатами
§ 3. Кванторные операции
§ 4. Понятие формулы логики предикатов
§ 5. Значение формулы логики предикатов
§ 6. Равносильные формулы логики предикатов
§ 7. Предваренная нормальная форма
§ 8. Общезначимость и выполнимость формул
§ 9. Пример формулы, выполнимой в бесконечной области
и невыполнимой ни в какой конечной области
§ 10. Проблема разрешимости для общезначимости и выполнимости,
неразрешимость ее в общем случае (без доказательства)
§ 11. Алгоритмы распознавания общезначимости формул
в частных случаях
§ 12. Применение языка логики предикатов для записи
математических предложений, определений,
построения отрицания предложений
§ 13. Замечание об аксиоматическом исчислении предикатов
Глава IV. Математические теории
§ 1. Язык первого порядка
§ 2. Термы и формулы
§ 3. Логические и специальные аксиомы. Правила вывода
§ 4. Примеры математических теорий из алгебры, анализа, геометрии
§ 5. Доказательство в теории
§ 6. Доказуемость частных случаев тавтологий
§ 7. Теорема дедукции
§ 8. Интерпретация языка теории
§ 9. Истинностные значения формул в интерпретации. Модель теории
§ 10. Изоморфизм интерпретаций. Категоричность теории
§ 11. Проблемы непротиворечивости, полноты, разрешимости теории
§ 12. Непротиворечивость исчисления предикатов
(теории без специальных аксиом)
§ 13. Теория натуральных чисел
§ 14. Теорема Геделя о неполноте
Глава V. Алгоритмы
§ 1. Понятие алгоритма и его характерные черты
§ 2. Разрешимые и перечислимые множества
§ 3. Уточнение понятия алгоритма.
§ 4. Вычислимые функции. Частично рекурсивные и
общерекурсивные функции
§ 5. Машины Тьюринга
§ 6. Нормальные алгоритмы Маркова.
§ 7. Неразрешимые алгоритмические проблемы (обзор)
Часть II. Задачник-практикум по математической логике
Глава I. Алгебра логики
§ 1. Высказывания и логические операции над ними
Формулы алгебры логики
§ 2. Равносильные формулы алгебры логики
§ 3. Функции алгебры логики. Совершенные нормальные формы
§ 4. Приложения алгебры логики
Глава II. Исчисление высказываний
Исчисление высказываний
Глава III. Логика предикатов
§ 1. Понятие предиката. Логические и кванторные операции
над предикатами
§ 2. Понятие формулы логики предикатов. Равносильные формулы
логики предикатов
§ 3. Общезначимость и выполнимость формул
Предваренная нормальная форма (п.н.ф.)
§ 4. Применение логики предикатов в математике
Глава IV. Алгоритмы
§ 1. Частично рекурсивные и общерекурсивные функции
§ 2. Машина Тьюринга
Ответы, указания, решения
Глава I
Глава II
Глава III
Глава IV
Литература