RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2022, том 61, номер 4, страницы 401–423 (Mi al2719)

Варианты субэкспоненциала локального сокращения в исчислении Ламбека

М. В. Валинкин

мех.-матем. ф-т, Московский гос. ун-т им. М. В. Ломоносова, г. Москва, РОССИЯ

Аннотация: Исчисление Ламбека было введено как инструмент для исследования лингвистических конструкций. В дальнейшем это исчисление пополнялось как новыми связками, так и структурными правилами, вроде правил сокращения, ослабления и перестановки. Эти структурные правила разрешаются только для формул под знаком особой модальности, называемой экспоненциалом. Само исчисление Ламбека является некоммутативной субструктурной логикой, и для произвольных формул эти структурные правила не допускаются. Следующий шаг — введение системы субэкспоненциалов: под знаком такой модальности могут допускаться лишь некоторые структурные правила.
Возникает следующий вопрос: можно ли сформулировать систему с тем или иным вариантом правила локального сокращения (для формул под субэкспоненциалом), чтобы восстановить свойство устранимости сечения? Рассматриваются два подхода к решению этой задачи: можно как ослабить правило введения ${!}$ в правой части секвенции (LSCLC), так и расширить правило локального сокращения с отдельных формул до их подпоследовательностей (LMCLC). Стоит также отметить, что в коммутативных исчислениях такой проблемы нет в силу возможности перестановки формул в секвенции (т. е. локальное и нелокальное правила сокращения совпадают).
Доказываются следующие результаты:
устранимость сечения в исчислениях LMCLC и LSCLC;
алгоритмическая разрешимость фрагментов этих исчислений, в которых ${!}$ разрешается применять только к переменным;
алгоритмическая неразрешимость LMCLC (для LSCLC разрешимость остаётся открытым вопросом);
корректность и отсутствие сильной полноты LSCLC относительно класса реляционных моделей;
различные результаты об эквивалентности для этих исчислений и исчислений с другими вариантами субэкспоненциала сокращения.

Ключевые слова: исчисление Ламбека, субэкспоненциал локального сокращения.

УДК: 515.125

Поступило: 10.03.2022
Окончательный вариант: 29.03.2023

DOI: 10.33048/alglog.2022.61.402



Реферативные базы данных:


© МИАН, 2024