Алгебраизация суперинтуиционистских предикатных логик

• Автор: Тишковский, Дмитрий Евгеньевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 101 с.

Содержание
Введение
1. Дедуктивные системы для суперинтуиционистских предикатных логик
1.1. Суперинтуиционистские предикатные логики и теории
1.2. Суперинтуиционистские дедуктивные системы
1.3. Адекватность суперинтуиционистских дедуктивных систем суперинтуиционистским логикам
1.4. Суперинтуиционистские дедуктивные системы как дедуктивные системы полимодальных логик
1.5. Свойства логик и свойства дедуктивных систем
2. Квазицилиндрические алгебры
2.1. Определение и примеры
2.2. Размерность элементов
2.3. Алгебры локально-конечной размерности
2.4. Означивания формул
2.5. Алгебры Расёвой—Сикорского
2.6. Алгебры Линденбаума—Тарского
2.7. Теорема о полноте
3. Алгебраические эквиваленты некоторых свойств логик
3.1. Дизъюнктивное свойство
3.2. Экзистенциальное свойство
3.3. Свойство Бета
3.4. Проективное свойство Бета
3.5. Интерполяционное свойство
3.6. Соотношение свойств дедуктивных систем и свойств логик
Литература

Введение
Одной из важных областей современной логики является теория неклассических логик. Особую роль среди таких логик играют расширения интуиционистской логики, получившие название суперинтуиционистских логик.
Как известно, одной из ключевых теорем теории моделей является теорема Гёделя о полноте классической логики предикатов, связывающая синтаксическое и семантическое понятия истинности формул. Благодаря этой теореме становится возможным изучение свойств классических теорий семантическими методами. Таким образом, наличие для изучаемой логики семантики, связанной с данной логикой при помощи некоторой теоремы о полноте, во многом облегчает исследование свойств логики, так как становится возможным использовать в дополнение к синтаксическому аппарату ещё и аппарат этой семантики. В частности, если логика полна относительно некоторого класса алгебр, то это позволяет исследовать логику при помощи мощного и развитого аппарата универсальной алгебры.
Хорошим подспорьем в изучении свойств решётки однотипных логик является наличие единой семантики для этих логик. Так, например, решётке пропозициональных суперинтуиционистских логик соответствует решётка многообразий псевдобулевых алгебр. К сожалению, в случае предикатных логик такого удачного соответствия нет. Известно [25], что существует континуум суперинтуиционистских предикатных логик, которые неполны относительно семантики шкал Крипке, и существует континуум суперинтуиционистских предикатных логик, которые неполны относительно семантики псевдобулевых моделей Е. Расёвой и Р. Си-корского [8].
В связи с вышесказанным возникает проблема построения такого класса К однотипных структур, чтобы всякая суперинтуи-ционистская предикатная логика была бы полной относительно некоторого подкласса класса К. Естественно требовать, чтобы класс К был классом алгебр. Таким образом, проблема построения единой семантики для суперинтуиционистских предикатных

логик становится проблемой их единой алгебраизации.
Алгебраическая логика берёт начало с работы Тарского [32]. В этой работе Тарский ввёл понятие алгебры пропозициональных формул. Он определил отношение = на множестве формул условием
А = В «=Ф- ЬАзВи - В Э А
и показал, что это отношение является конгруэнцией на алгебре формул. Тарский доказал, что соответствующая фактор-алгебра является булевой алгеброй, а множество всех классических тавтологий совпадает с множеством формул, эквивалентных Т. Фактор-алгебры, полученные факторизацией алгебры формул по конгруэнции указанного выше вида, получили позднее название алгебр Линденбаума—Тарского и играют важную роль в алгебраизации логик.
Позднее метод Тарского был применён к алгебраизации пропозициональных модальных, суперинтуиционистских и многих других логик. Большой вклад в развитие алгебраческих методов исследования неклассических логик был внесён Е. Расёвой и Р. Си-корским [29,8]. Сам Тарский возглавил обширную исследовательскую программу по алгебраизации классической логики 1-го порядка [17]. Позднее эта программа была подхвачена различными школами алгебраической логики, среди которых следует особо отметить венгерскую школу [11,12,18,19,23,24,31].
В 1989 году метод Тарского был обобщён Блоком и Пигоц-ци [13] на случай алгебраизации произвольных пропозициональных логик. В указанной работе использовалось представление логик дедуктивными системами, и было введено понятие алгебраиз-уемости пропозициональной дедуктивной системы. Было доказано, что алгебраизуемой дедуктивной системе соответствует единственная эквивалентная алгебраическая семантика — некоторое квазимногообразие алгебр. В диссертации также используется представление предикатных логик дедуктивными системами.
Как отмечено в [13, Приложение С], алгебраизации предикатных логик является более сложной задачей, чем алгебраизация пропозициональных логик. Поясним это на следующих простых

переменная xt заменится сначала на ж, а затем хд, заменится на Хц. Таким образом, в (2) каждая свободная переменная заменится на Хц, хг — на Хц, а жд( — на хп. Значит и в (1), и в (2) на соответствующих местах будут находиться одни и те же переменные. □
В следующем примере сохранены все обозначения из доказательства леммы 1.17.
Пример 1.18. Пусть АиФ [А] те же, что и в примере 1.16. Пусть А0 Ух5г0(х5, ж0, ж6, жх) и А! Г1(ж0) жх, ж2).
Тогда
Ф[А](Л0, Ах) =Ужз(/ж5го(ж5;жз,жз,Ж1) 3 п(ж2, ж1; ж2))
(Зж2/Ж5Го(ж5,Ж2,Ж2,Ж1) 3 п(ж2, ЖЬ Ж2)).
Формулы Во и В можно выбрать так: Во
/ж8п(ж8, ж0, ж6, хх), В± Ах = г2(ж0, хх, ж2).
Тогда
Ф[А](В0,Вх) =Ужз(/ж8го(ж8,жз,жз,Ж1) 3 гх(ж2,жх,ж2)) 3 (Зж2/ж8г0(ж8,ж2,ж2,жх) 3 Гх(ж2,Ж1,Ж2)).
Формулы Со и Сх можно выбрать следующим образом: Со Уж8г0(ж8, ж0, ж0, жх), Сх Вх = Ах = гх(ж0,жх,ж2).
Формула В может быть, например, следующая:
В /ж3(до(жз,жх,Ж4,ж5) 3 дх(ж2,ж4))
(Зж2до(ж2,жх,Ж4,ж5) 3 щ(ж2, ж4)).
В Со помечаем свободные вхождения переменных Жо, Жх, ж2, Жз, а в Сх — жо, жз. (Вхождения переменных ж2, жз в Со и переменной жз в Сх фиктивны.) Тогда подстановка БфВ даёт:
/ж3(/ж8г0(ж8,ж3, ж3,жх) 3 Гх(ж2,жх,ж2))
(Зж2Уж8г0(ж8,ж2,ж2,жх) 3 Гх(ж2,Жх,Ж2)),
то есть Ф[А](Во, Вх).
СЛЕДСТВИЕ 1.19. Для любой простой формулы А выполнено АеЬ 4=> Ф[А]еП5(Т).