Введение
1. Предварительные сведения 7
1.1. Сведения из логики 7
1.1.1. Основные определения 7
1.1.2. Логика слабого закона исключённого третьего 11
1.1.3. Свойства позитивных формул 15
1.2. Алгоритмы и количество информации 28
1.2.1. Алгоритмы 28
1.2.2. Количество информации 30
2. Алгоритмические задачи 33
2.1. Определение и основные свойства 33
2.1.1. Операции над множествами 33
2.1.2. Интерпретация классической логики 34
2.1.3. Интуиционистская логика и реализуемость . 35
2.1.4. Сложность алгоритмических задач 36
2.1.5. Простейшие логические свойства 39
2.2. Оценки на сложность задач 42
2.2.1. Нижняя оценка для критических импликаций 42
2.2.2. Классификация формул по сложности порождаемых алгоритмических задач 46
2.2.3. Верхние оценки для критических импликаций 49
2.2.4. О мощности множеств, на которых достигается нижняя оценка сложности 59
3. Финитные задачи 62
3.1. Основные свойства финитных задач 63
3.1.1. Определение 63
3.1.2. Утверждения о корректности 64
3.1.3. Финитные задачи и логика 69
3.2. Достаточное множество решений 71
3.2.1. Определение и простейшие свойства 71
3.2.2. Нижняя оценка для критических импликаций 76
3.2.3. Классификация формул по мощности достаточного множества решений 79
3.2.4. Об оптимальности оценки для критических импликаций 82
3.3. Колмогоровская сложность финитных задач 85
3.3.1. Определение и простейшие свойства 85
3.3.2. Классификация формул по сложности порождаемых финитных задач 88
Литература 91
