Новые константы в предтабличных суперинтуиционистских логиках: подход П.C. Новикова

Abstract

П.С. Новиков в конце 50-х годов ХХ века поставил задачу о новых логических связках как экстрапонятиях для языка со стандартными логическими связками $\vee$, $\wedge$, $\rightarrow$, $\neg$. Я.С. Сметанич в своих работах привел точные формулировки подхода Новикова к понятию новых логических связок в суперинтуиционистских логиках (новая логическая связка, полнота по Новикову). В статье рассмотрена проблема П.C. Новикова применительно к новым константам в предтабличных суперинтуиционистских логиках $LC$, $L2$, $L3$: логика конечных цепей, логика корневых шкал глубины 2 (вееров), логика корневых шкал глубины 3 с наибольшим элементом (даймондов). Получено исчерпывающее описание семейства всех полных по Новикову расширений каждой из предтабличных суперинтуиционистских логик в языке с несколькими дополнительными константами: для $LC$ и $L2$ семантическое описание всех полных по Новикову расширений дано в терминах классов конечных цепей с раскраской ($LC$) и конечных вееров с раскраской ($L2$); для $L3$ подобное описание дано для случая одной константы. Установлена алгоритмическая разрешимость каждого пополнения по Новикову указанных трех суперинтуиционистских логик, а также алгоритмическая проблема распознавания консервативности расширений этих логик в языке с одной дополнительной константой.