О некоторых вариантах понятия реализуемости

• Автор: Чернов, Алексей Вячеславович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 93 с.

Оглавление
Введение

1. Предварительные сведения

1.1. Сведения из логики

1.1.1. Основные определения

1.1.2. Логика слабого закона исключённого третьего

1.1.3. Свойства позитивных формул

« 1.2. Алгоритмы и количество информации

1.2.1. Алгоритмы

1.2.2. Количество информации

2. Алгоритмические задачи

2.1. Определение и основные свойства
2.1.1. Операции над множествами
2.1.2. Интерпретация классической логики
2.1.3. Интуиционистская логика и реализуемость .
2.1.4. Сложность алгоритмических задач
2.1.5. Простейшие логические свойства
2.2. Оценки на сложность задач
2.2.1. Нижняя оценка для критических импликаций
2.2.2. Классификация формул по сложности порождаемых алгоритмических задач
2.2.3. Верхние оценки для критических импликаций

ОГЛАВЛЕНИЕ ^
2.2.4. О мощности множеств, на которых достигается нижняя оценка сложности
3. Финитные задачи
3.1. Основные свойства финитных задач
3.1.1. Определение
3.1.2. Утверждения о корректности
3.1.3. Финитные задачи и логика
3.2. Достаточное множество решений
3.2.1. Определение и простейшие свойства
3.2.2. Нижняя оценка для критических импликаций
3.2.3. Классификация формул по мощности достаточного множества решений
3.2.4. Об оптимальности оценки для критических
импликаций
• 3.3. Колмогоровская сложность финитных задач
3.3.1. Определение и простейшие свойства
3.3.2. Классификация формул по сложности порождаемых финитных задач
Литература
Введение
Введение

Классическая логика изучает истинность и ложность высказываний, полученных из некоторых исходных элементарных высказываний при помощи логических операций V, Л, —>, называемых
также логическими связками.
А. Н. Колмогоров в своей статье [16], написанной в 1932 году, предложил рассматривать аналогичные операции не над высказываниями, а над задачами. Логические связки в этом случае используются для построения составной задачи из нескольких исходных элементарных задач. Например, для задач А и В их конъюнкция А А В есть задача „решить обе задачи А и Б“, а импликация А —> В — „указать общий метод, позволяющий из решения задачи А получить решение задачи Б“.
В некоторых случаях решение составной задачи можно указать, даже не зная использованных элементарных задач, а зная лишь структуру составной задачи, то есть задающую её формулу. Такова, например, задача вида А —> А. Колмогоров в статье [16] указывал, что множество формул, для которых можно указать заранее некоторое решение составной задачи, естественно назвать конструктивной логикой. Так определённое „исчисление задач“ он рассматривал как новый подход к построению интуиционистской логики, отличный от философских рассмотрений Брауэра.
Колмогоров ограничился лишь несколькими примерами элементарных задач и неформальным описанием операций, но не сформулировал математически строгой семантики, подобной той, которую булевы функции предоставляют для классической логики. Впоследствии было предложено несколько вариантов семантики, следующей этим идеям. Первым было понятие реализуемости, предложенное С.К.Клини (1945). На несколько других принципах
ГЛАВА 2. АЛГОРИТМИЧЕСКИЕ ЗАДАЧИ

деляются следующим образом.
ХУУ = {(0,х) |хеХ}и{(1,у) уе¥},
ХЛУ = {(х,у)хеХ,уе¥},
X —> У = {р | Ух (т е X =4» р](х) определено и [р](х) 6 У)} ,
1 = 0И -X = X —> _1_ = X —у 0.
Для каждой пропозициональной формулы Ф(^1,... ,£*) по индукции определяется составная задача Ф(Х1,... ,Хк), получающаяся при подстановке задач Х^... ,Хк вместо переменных Дк-Таким образом, каждая формула Ф может рассматриваться как операция, сопоставляющая множество Ф(Х,... ,Хк) множествам
хи...,хк.
2.1.2. Интерпретация классической логики
Сначала отметим почти тривиальное свойство введённых операций, которое, однако, позволяет описать в терминах задач классическую логику и технически полезно в дальнейшем.
Сопоставим пустому множеству истинностное значение „ложь“, а всем непустым множествам — истинностное значение „истина“. Тривиально проверяется, что введённые операции над множествами V, А, при таком сопоставлении переходят в соответствующие булевские операции над истинностными значениями.
Формула, рассматриваемая как операция над множествами, превращается при этом в соответствующую той же формуле булеву функцию. Отсюда получается следующее простое утверждение (впервые этот факт отметил Плиско в [12]).