Математическая логика и теория алгоритмов

В современной логике логические процессы изучаются путем их отображения в формализованных языках или логических исчислениях. Построение исчисления отличается особой тщательностью, с которой формулируются его синтаксические и семантические правила, отсутствием исключений, характерных для естественного языка. Исследованием формального строения логических исчислений, правил образования и преобразования занимается логический синтаксис. Отношения между исчислениями и содержательными областями, служащими их интерпретациями или моделями, исследуются логической семантикой. Современная логика слагается из большого числа логических систем, описывающих отдельные фрагменты, или типы содержательных рассуждений. В данном курсе будут рассмотрены классические исчисление высказываний и исчисление предикатов первого порядка.

ВВЕДЕНИЕ 2
1. ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ 3
1.1 Логика высказываний 3
1.2 Понятие формальной теории 7
1.3 Исчисление высказываний (ИВ) 8
1.4 Теорема дедукции 10
1.5 Непротиворечивость и полнота исчисления высказываний 11
1.6 Методы проверки выводимости формул ИВ 12
1.7 Понятие предиката 17
1.8 Логические эквивалентности с кванторами 21
1.9 Термы и формулы в исчислении предикатов 22
1.10 Аксиомы и правила вывода в исчислении предикатов 23
1.11 Теоремы об исчислении предикатов первого порядка 24
1.12 Метод резолюций для исчисления предикатов 25
2. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ И РЕКУРСИВНЫХ ФУНКЦИЙ 29
2.1 Понятие алгоритма 29
2.2 Машина Тьюринга 30
2.3 Вычисление функций на машине Тьюринга 35
2.4 Алгоритмически неразрешимые задачи 39
2.5 Примитивно рекурсивные функции 42
2.6 Частично рекурсивные функции 46
2.7 Характеристики сложности алгоритмов 50
2.8 Классы сложности и 54
ЛИТЕРАТУРА 56