Допустимые правила вывода в нестандартных логиках и их базисы тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Римацкий, Виталий Валентинович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Красноярск
МЕСТО ЗАЩИТЫ
|
||||
|
2000
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
На правах рукописи
РИМАЦКИЙ ВИТАЛИЙ ВАЛЕНТИНОВИЧ
УДК 517.11
ДОПУСТИМЫЕ ПРАВИЛА ВЫВОДА В НЕСТАНДАРТНЫХ ЛОГИКАХ И ИХ БАЗИСЫ.
01.01.06 — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Красноярск-2000
Работа выполнена в Красноярском государственном университете
Научный руководитель доктор физико-математических наук,'
профессор РЫБАКОВ В.В. Официальные оппоненты: доктор физико-математических наук,
на заседании диссертационного совета Д 064.61.02 в Красноярском государственном университете по адресу 660041, г. Красноярск, пр. Свободный, 79-.
С диссертацией можно ознакомиться в библиотеке Красноярского государственного университета.
профессор ЯКОВЛЕВ Б.В. . кандидат физико-математических наук, ШРАЙНЕР П.А.
Ведущая организация Иркутский государственный университет,
г. Иркутск
Защита состоится 4? 2000 г. в
часов
Автореферат разослан
Ученый секретарь диссертационного сове"-0 кандидат физико-математических наук
3 03
)
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
Любое логическое исследование связано с некоторой логической дедуктивной системой (логикой) или классом таких систем. Как правило рассматривается конкретная аксиоматизация логики, состоящая из фиксированного набора аксиом и правил вывода, определяющих данную систему. Выбирая язык, набор аксиом и правил вывода можем задать самые различные логики. Особую роль играют широко известные классическая пропозициональная логика PC и исчисление предикатов РРС, развитые в работах Д. Гильберта, К. Гёделя и Г. Генцена в 20 - 40-е годы. Примерно в то же время в трудах А. Гейтинга (интуиционистская 1930), Лукасе-вича (многозначная 1920), К. Льюиса (модальная 1920 - 1930) появились первые логики, отличающиеся от классических - так называемые неклассические или нестандартные логики.
Понятие допустимого правила вывода, введенное Лоренценом в 50-х годах, непосредственно вытекает из понятия формального логического исчисления. Это в точности те правила вывода, добавление которых к списку постулированных правил не расширит исчисления, не изменит множество теорем логики. Ценность допустимых правил формального исчисления заключается в том, что с их помощью можно упростить и сократить процесс вывода и верификации формул в этом исчислении, кроме того понятие допустимого правила не зависит от конкретной аксиоматизации исчисления, то есть является инвариантом. Проблема допустимости правил вывода заключается в следующем: допустимо ли данное правило вывода в заданном формальном исчислении (логике).
Проблематика допустимости естественно переносится на случай ло-
гических исчислений. Если в классическом исчислении высказываний проблема допустимости правил вывода решается тривиально, то уже случай интуиционистской пропозициональной логики потребовал разработки сложной техники. Первые конкретные результаты по проблеме допустимости в интуиционистской логике были получены в 60-ых годах. Так Харропом в 1960 году [22], а после Минцем в 1972 [18] были получены примеры допустимых, но не производных правил вывода. Г.Е. Минцем в [17, 18] был найден ряд достаточных условий допустимости и производ-ности в интуиционистской логике.
Вопрос о существовании алгоритма, распознающего допустимость правил вывода, был поставлен Кузнецовым A.B. Схожая проблема была включена в обзор проблем Фридмана ([21], проблема 40). В 1977 году А.И. Цит-киным были найдены критерии допустимости для правил специального вида в [19]. Им же в [20] были описаны модусно предполные суперинтуиционистские логики. Но сама проблема Кузнецова-Фридмана разрешимости по допустимости в интуиционистском исчислении высказываний оставалась открытой. Аналогичная проблема также актуальна для модальных логик. Допустимость и производность специальных правил в логике Льюиса S5 исследовалась Портом в 1981 году в [23, 24].
Проблема допустимости имеет прямой алгебраический аналог, а именно: правило допустимо в логике, если и только если соответствующее ему квазитождество истинно на свободных алгебрах многообразия, соответствующего этой логике. Разрешимость проблемы допустимости в логике эквивалентна разрешимости квазиэквациональной теории свободных алгебр многообразия, порожденного этой логикой. Это позволило привлечь к решению проблемы допустимости хорошо разработанные алгебраические методы. На основе этого подхода Рыбаковым В.В. была доказана в
1981 году разрешимость проблемы допустимости для "сильных" модальных логик — табличных и предтабличных, там же был поставлен вопрос о проблеме допустимости в "слабых" логиках [2]. Алгоритмический критерий допустимости для логик S4+cTfe был найден Рыбаковым В.В. в 1984 в [3]: В том же году была доказана разрешимость проблемы допустимости для целого класса логик — логик, расширяющих S4.3 [5].
В [2] было замечено, что правило вывода a/ß допустимо в суперинтуиционистской логике Л Э Int, тогда и только тогда, когда правило T(a)/T(ß) допустимо в <т(А) — наибольшем модальном напарнике Л, где Т(а) перевод Гёделя-МакКинси-Тарского интуиционистской формулы а в модальную. Появилась надежда, что проблему допустимости в Int можно решить, доказав разрешимость проблемы допустимости в одной из модальных логик яруса jo~1(Int). В 1984 году Рыбаковым В.В. [4] был найден алгоритмический критерий допустимости правил вывода в модальной системе S4 и интуиционистской логике Int. Одновременно были получены алгебраические аналоги этих результатов — разрешимость универсальных теорий свободной алгебры замыканий и свободной псевдобулевой алгебры. *
Помимо проблемы' распознавания допустимых правил вывода не меньшую важность имеет проблема нахождения конечного числа допустимых правил вывода, называемых базисом допустимых правил вывода, из которых все остальные получаются как следствия (проблема Кузнецова, 1973г.). Проблема конечной базируемости по допустимости также имеет алгебраический аналог: нахождение базиса квазитождеств квазимногообразия, порождаемого свободной алгеброй счетного ранга .^(А) из многообразия, соответствующего логике А. Благодаря этому при изучении вопроса о конечной базируемое™ допустимых правил заданной логики или
класса логик оказалось возможным использовать аппарат универсальной алгебры. На сегодняшний день теория допустимых правил вывода представляет собой результат слияния методов универсальной алгебры (теории квазимногообразий) и теоретико-модельной семантики Крипке. .
Оказалось, что для многих базовых, индивидуальных нестандартных логик не существует базиса от конечного числа переменных для допустимых правил вывода. Например, Рыбаковым В.В. было доказано отсутствие такого базиса для логик S4 и Int в [6], Grz в [7], для логик 54.1, 54.2, S4In, А'4, КАЛ, КАЛ, КС, /„, п 6 N в Главе 4.2 [1]. Однако, некоторые фрагменты множества допустимых правил логики Int имеют конечный базис [19], так же как и любая модальная логика, расширяющая логику 54.3 (CoroIIary 4.3.20 [1]). В тоже время целые классы достаточно "сильных" табличных логик ширины или глубины 2 имеют конечный базис для допустимых правил, что было доказано в [26], [28].
Цель работы
1. получить достаточно эффективный и удобный семантический критерий принадлежности конечной алгебры квазимногообразию свободной алгебры конечного ранга;
2. разработать технику исследования базисов допустимых правил табличных модальных пропозициональных логик, расширяющих логику Льюиса S4, и суперинтуиционистских логик;
3. доказать конечную базируемость по допустимости произвольной табличной логики глубины 2, а также финитно аппроксимируемых логик ширины 2;
4. Описать базис допустимых правил вывода интуиционистской логи-
ки Int;
5. Описать 54.2-логики и родственные им логики, сохраняющие допустимость правил вывода, допустимых в логиках 54.2, Grz.2, КС;
В диссертации получены следующие основные результаты
1. Доказана конечная базируемость по допустимости произвольной табличной логики глубины 2, а также финитно аппроксимируемых логик ширины 2;
2. Как следствие доказана конечная базируемость квазиэквациональ-ной теории квазимногообразий, порожденных свободными алгебрами и где А — логика из описанного выше класса;
3. Описан рекурсивный базис допустимых правил вывода интуиционистской логики Int в полу-редуцированной форме;
4. Описаны 54.2-логики и родственные им логики, сохраняющие допустимость правил вывода, допустимых в логиках 54.2, Grz.2, КС;
Научная новизна. Все результаты, полученные в диссертации, являются новыми и снабжены строгими доказательствами.
Теоретическая и практическая ценность. Полученные результаты имеют теоретическую ценность и могут быть использованы в дальнейших исследованиях по проблемам допустимости правил вывода и их базисов.
Апробация работы.
Результаты диссертации докладывались на Международной конференции по математической логике, посвященной 85-летию со дня рож-
дения А.И. Мальцева (г. Новосибирск, 1994 г.), XXXIV - XXXV Международных научных студенческих конференциях (г. Новосибирск, 1996 и 1997 гг.), I и II Международной конференции "Мальцевские чтения" (г. Новосибирск, 1997 и 1998 гг.), XV Межрегиональной научно - технической конференции (г. Красноярск, 1997г.), а также на заседаниях семинаров "Алгебра и логика" при Новосибирском государственном университете, семинара по неклассическим логикам при Институте математики СО РАН (г. Новосибирск) и на заседаниях Красноярского алгебраического семинара.
Публикации. По теме диссертации опубликовано 10 работ [26] - [35].
Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы из 83 наименований и занимает 98 страниц машинописного текста.
Много раз результаты и ход работы обсуждались с Владимиром Владимировичем Рыбаковым, которому я благодарен за поддержку и терпение. ' Я также благодарен Голованову М.И. за полезные обсуждения на семинарах кафедры алгебры и математической логики Красноярского госуниверситета. .
СОДЕРЖАНИЕ РАБОТЫ
1. В первой главе формулируются общие сведения из области модальных и суперинтуиционистских логик, приводятся основные факты из области алгебраической семантики и семантики Крипке для модальных и суперинтуиционистских логик. В заключительном параграфе вводится понятие допустимого правила вывода и базиса для допустимых правил заданной логики, а также формулируются основные предварительные ре-
зультаты.
Определение 1.41 Правило вывода
Ai{xi ...,хп). ..,Ак(х 1 ...,хп) f — -
В(х 1 ...,ж„)
называется допустимым в логике Л тогда и только тогда, когда для любых формул ßi..., ßn и для любого г, г = L.fc, выполняется
Ai{ßi ...,/?„)€ А J5(/?i.. .,/?„) € А.
Для данного правила вывода можем поставить в соответствие квазитождество
г* = {А^Ж!. ..,х„) = 1& ...&Ак(х i .. ,,х„) = 1 В[х 1.. .,ж„) = 1},
и наоборот. Свойство этого соответствия выражено в
Утверждение 1.42 Пусть логика А Э K(Int) и Kj (А) есть класс свободных алгебр многообразия Var(А). Тогда
1.гбЛ<*(А) Ä)(A)f=r*; 2. Kj(X)\=q r(q) е Ad(А).
Определение 1.45 Множество Ас(* (А) допустимых правил логики А называем базисом допустимых правил, если для любого допустимого правила г найдутся правила ri,.. .,r* € Ad*(А) такие, что г выводимо из гх,..., г/, в логике А.
Базис допустимых правил и соответствующих квазитождеств связывает
Утверждение 1.46 Правила вывода ri,r2,...,rn образуют базис для допустимых правил вывода в логике А тогда и только тогда, когда rj,... ,г* есть базис для квазитождеств в свободной алгебре $W(A).
Утверждение 1.48 Зи(-Х) не имеет базиса квазитождеств от конечного числа переменных тогда и только,когда существует последовательность алгебр £„ б Var(X), где индексы п образуют строго возрастающую последовательность чисел, таких что:
1) для любого п £„ - п + 1 порожденная;
2) А, 0ЫА)«;
3) любая «-порожденная и собственная подалгебра алгебры £„ принадлежит квазимногообразию А)*3.
2. Во второй главе мы исследуем условия принадлежности конечной алгебры квазимногообразию ^(Л)^, порожденному свободной алгеброй счетного ранга Доказана следующая
Теорема 2.5 Пусть Л - табличная логика, расширяющая логику Si или Int. Конечная алгебра £ принадлежит квазимногообразию 3§(А) тогда и только тогда, когда £ есть подалгебра конечного прямого объединения свободных алгебр конечных рангов.
Однако, можно усилить полученный критерий. Для этого дадим два определения. Пусть Л - заданная табличная логика над 54 или Int, и пусть Т - корневой конечный А-фрейм.
Определение 2.6 Говорим, что фрейм М есть ко-накрытийный Л-последователь для Т [обозначение СодС^)], если он получен из Т следующим образом. Пусть Fo := Т и первый слой фрейма Т содержит хотя бы один вырожденный (одноэлементный) сгусток (в суперинтуиционистском случае все сгустки - вырожденные). На каждом шаге построения г > 0 фрейма для каждой нетривиальной антицепи Aj С Ti, не имеющей ко-накрытия в F,-, добавляем к Fi (единственный) элемент e,j как А-ко-накрытие для Aj. В силу табличности логики А через конечное число шагов процесс построения оборвется. Если же все сгустки первого
слоя фрейма Т - собственные (т.е. их мощность строго больше чем 1), то описанный выше процесс проводим для фрейма FUe, где е - вырожденный сгусток. Полученный в результате построения фрейм является ко-накрытийным Л-последователем для фрейма Т.
Пусть Q - произвольный А-фрейм, у € Q-
Определение 2.7 Локальной компонентой элемента у называется открытый подфрейм К(у) := Q П Со\{ун).
Локальная компонента определяется не единственным образом (если в Q существуют дубли ко-накрытий), однако любая локальная компонента элемента конечного фрейма также является конечной. Заметим также, что локальная компонента определена только в тех фреймах, первый слой которых содержит вырожденный сгусток. Однако, для нашего исследования понятие локальной компоненты позволяет получить достаточно удобный и наглядный критерий принадлежности конечных алгебр Ъп из Утверждения 1.48 квазимногообразию Зш(А), что следует из
<0
Лемма 2.7 Пусть алгебра *8п удовлетворяет условиям Утверждения 1.48. Тогда для любого п > 3 и для произвольного элемента у £ 93+ определена локальная компонента К (у), т.е. фрейм 23 J содержит хотя бы один одноэлементный сгусток первого слоя.
Лемма 2.10 Пусть А - табличная логика над 54 или Int, G - произвольный конечный А-фрейм такой, что существует хотя бы один вырожденный сгусток первого слоя фрейма G. Алгебра G+ принадлежит квазимногообразию 5т (-М тогда и только тогда, когда для любого элемента у € G существует р-морфизм из конечного прямого объединения фреймов U,-6/CoA(cf), с,- 6 на каждую локальную компоненту К(у) элемента у, где тп - мощность алгебры, порождающей логику А.
Заметим, что условие существования р-морфизма из Ui^{Co\{cf-) на
каждую локальную компоненту К{у) невозможно ослабить. На стр. 32 приводится пример фрейма, иллюстрирующий данное утверждение.
3. Следующая Глава 3 посвящена доказательству конечной базируемое™ логик ширины или глубины 2. Следствием Леммы 2.10 является
Теорема 3.1 Любая табличная логика А глубины 2, расширяющая логику S4 или Int, имеет конечный базис для допустимых правил вывода.
Аналогичным образом доказывается
Теорема 3.4 Любая финитно аппроксимируемая модальная (суперинтуиционистская) логика над логикой Si{Int) ширины 2 имеет конечный базис для допустимых правил вывода.
Заключительный параграф данной Главы 3 посвящен описанию базиса для допустимых правил вывода в полу-редуцированной форме для интуиционистской логики Int.
4. Следующая Глава 4 посвящена описанию логик, сохраняющие допустимые правила логики 54.2 и родственных ей логик. В [1] был получен семантический критерий допустимости правила в заданной логике. Однако, определить является ли данное правило вывода допустимым в заданной логике само по себе представляет сложную проблему. Поэтому, полезно знать какие логики сохраняют допустимые правила некоторых важных, индивидуальных систем. В работе [1] были предложены критерии, гарантирующие сохранение допустимости правил вывода модальной системы 54. В настоящей главе мы расширяем сферу применений этой техники на более сильные модальные логики-логики, расширяющие 54.2 и 54.3. Прежде, чем сформулировать основные результаты, приведем несколько определений.
Определение 4.1 Логика А2 сохраняет допустимые в Aj (Ai С Аг)
правила вывода, если любое правило вывода, допустимое в А^ также допустимо в Аз.
Определение 4.2 Фрейм М называется ко-накрытийным последователем фрейма если М получен за конечное число шагов следующим образом: пусть /<Ь := Р- На каждом шаге построения г добавляем к фрейму единственный рефлексивный элемент как описано ниже. Выбираем некоторую нетривиальную антицепь сгустков Р^, не имеющую в Р, ко-накрытия (если такая существует) и добавляем к Р,- новый рефлексивный элемент как ко-накрытие выбранной антицепи. Через конечное число шагов процесс построения обрывается и полученный фрейм Рп есть ко-накрытийный последователь М для Р.
Определение 4.3 Логика А, расширяющая логику ,94.2, имеет свойство ко-накрытий, если для любого конечного корневого А-фрейма Р любой его ко-накрытийный последователь есть А-фрейм.
Основной результат сформулирован в
Теорема 4.10 Финитно аппроксимируемая логика А, расширяющая 54.2, сохраняет все допустимые в 54.2 правила вывода если и только если, А имеет свойство ко-накрытий.
Совершенно аналогично из Лемм 4.6 и 4.9 вытекает:
Теорема 4.11 Финитно аппроксимируемая логика А, расширяющая логику Сгг.2, сохраняет все допустимые в 54, 54.1, 54.2 или Сгг.2. правила вывода если и только если, А имеет свойство ко-накрытий.
Для сравнения с допустимыми правилами 54, заметим, что верно
Утверждение 4.11 Логика 54.2 не сохраняет допустимые в 54 правила вывода.
Действительно, правило вывода
-<{Оо[(Ог Л O-i*) A Ooz] V Оп[(Ох Л 0~>а:) Л ОсЬж]}
J» -—---—■—-------------------------------------------
->OD(Oa; A O-ix) не допустимо в 54.2, но допустимо в логике 54. Совершенно аналогичным образом доказывается Теорема 4.13 Финитно аппроксимируемая логика Л, расширяющая логику КС, сохраняет все допустимые в КС правила вывода если и только если, Л имеет свойство ко-накрытий.
Не смотря на то, что логика 54.3 расширяет логику 54.2, результаты предыдущего пункта не применимы к 54.3-логикам напрямую. Действительно, особенность таких логик заключается в том, что дополнительная аксиома логики 54.3 О?) V □(□? Dp) выражает линейный
поток событий, и поэтому 54.3-фреймы должны иметь линейное отношение достижимости. И значит, все такие логики не имеют свойства ко-накрытий, если следовать Определению 4.2: нетривиальные антицепи не могут иметь ко-накрытий. Однако, после незначительных упрощений аналогичным образом получается Теорема 4.19
Финитно аппроксимируемая логика А, расширяющая 54.3, сохраняет все допустимые в 54.3 правила вывода если и только если, А имеет свойство ко-накрытий.
СПИСОК ЛИТЕРАТУРЫ.
[1] Rybakov V.V. Admissibility of logical inference rules. -Book, Studies ill Logic and Foundations of Mathematics., Vol. 136, Elsevier Publ., Amsterdam, New-York, 1997, 617 pp.
[2] Рыбаков B.B. Допустимые правила предтабличных модальных логик // Алгебра и логика. 1981. Т. 20. №4. С. 440-464.
[3] Рыбаков В.В. Разрешимость проблемы допустимости в конечнослой-ных модальных логиках // Алгебра и логика. 1984. Т. 23. №1. С. 100-116.
[4] Рыбаков В.В. Критерий допустимости правил в модальной системе S4 и интуиционистской логике // Алгебра и логика. 1984. Т. 23. №5. С. 546-572.
[5] Рыбаков В.В. Допустимые правила логик, содержащих S4.3 // Сибирский математический журнал. 1984. Т. 25. №5. С. 141-145.
[6] Рыбаков В.В. Базисы допустимых правил логик S4 и Int // Алгебра и логика. 1985. Т. 24. № 1. С. 87-107.
[7] Рыбаков В.В. Базисы допустимых правил модальной системы Grz и интуиционистской логики // Математический сборник. 1985. Т. 128. №3. С. 321-338.
[8] Рыбаков В.В. Универсальные теории свободных А-алгебр при А Э
S4.3 // Сложностные проблемы математической логики. Калинин.
г
1985. С. 72-75.
[9] Рыбаков В.В. Уравнения в свободной топобулевой алгебре и проблема подстановки // Доклады АН СССР. 1986. Т. 287. №3. С. 554-557.
[10] Рыбаков В.В. Алгебраические методы в пропозициональной логике // Семиотика и информатика. — М., 1986. №28. С. 102-121.
[11] Рыбаков В.В. Разрешимость по допустимости модальной системы Grz и интуиционистской логики // Известия АН СССР: Сер. математическая. 1986. Т. 50. №3. С. 598-616.
[12] Рыбаков В.В. Базисы допустимых правил модальных систем Grz и интуиционистской логики // Математический сборник. 1987. Т. 56. №2. С. 311-331.
[13] Рыбаков В.В. Допустимость правил вывода и логические уравнения в Модальных логиках, аксиоматизирующих доказуемость // Известия АН СССР. Сер. математическая. 1990. Т. 54. №2. С. 357-377.
[14] Рыбаков В.В. Критерии допустимости правил вывода с параметрами в интуиционистской пропозициональной логике // Известия АН СССР. Сер. математическая. 1990. Т. 54. №6. С. 693-703.
[15] Rybakov V.V. Logical equations and admissible rules of inference with parameters in modal provability logics // Studia Logica. 1990. V. XLIX. №2. P. 215-239.
[16] Rybakov V.V. Metatheories of first-order theories // Proc. of the IV Asian Logic Conference. CSK Educational Center. — Tokyo. Japan. 1990. P. 16-17.
[17] Минц Г.Е. Допустимые и производные правила // Записки научного семинара ЛОМИ АН СССР. 1968. №8. С. 189-191.
[18] Минц Г.Е. Производность допустимых правил // Записки научного семинара ЛОМИ АН СССР. 1972. №32. С. 85-99.
[19] Циткин А.И. О допустимых правилах интуиционистской логики высказываний // Математический сборник. 1977. Т. 102. №2. С. 314323.
[20] Циткин А.И. О структурально полных суперинтуиционистских логиках // Доклады АН СССР. 1978, Т. 241. №1. С. 40-43.
[21] Friedman Н. One hundred and two problems in mathematical logic // The Journal of Symbolic Logic. 1975. V. 40. №3. P. 113-129. ■
[22] Harrop R. Concerning formulas of the types A —» В V С, A —>■ 3xB(x) in intuitionistic formal systems // The Journal of Symbolic Logic. I960. V. 25. №1. P. 27-32.
[23] Port J. The deducibilities of S5 // Journal of Phylosophical Logic. 1981. V. 10. P. 409-422.
[24] Port J. Axiomatization and independence in S4 and S5 // Reports on Mathematical Logic. 1983. V. 16. P. 23-33.
[25] Rybakov V.V. Problems of substitution and admissibility in the modal system Grz and intuitionistic calculus. // Annals of pure and applied logic. 1990. V. 50. P. 71-106.
Работы автора по теме диссертации.
[26] В.В. Римацкий. Базисы допустимых правил вывода Табличных Модальных Логик глубины 2. Алгебра и логика, т. 35 (1996), N5 с. 612 -623.
[27] V.V. Rimatskiy. Finite Bases of Admissibile inference rules for Modal Logics of Width 2. Bulletin of the Section of Logic; v.26, N.3, Oct. 1997, pp. 126 - 134.
[28] В.В. Римацкий. О конечной базируемое™ допустимых правил вывода модальных логик ширины 2 . Алгебра и логика, т. 38 (1999), N5, с. 436 - 455.
[29] V.V. Rybakov, M. Tetziler, V. Remazki. Bases in semi-reduced form for admissible rules of infcuitionistic logic IPC. Mathematical Logic Quaterly, No. 2, Vol. 46 (2000), 17 pp.
[30] В.В. Римацкий. Расширения конечно базируемых по допустимости табличных логик; Сиб. Мат. Журнал, в печати.
[31] В.В.Рыбаков, В.В.Римацкий. 54.2-логики, сохраняющие допустимые - правила вывода логики 54.2 и родственных ей логик, Сиб. Мат. Журнал, в печати.
[32] В.В. Римацкий. Базисы допустимых правил вывода Табличных Модальных Логик глубины 2. Тезисы Международной конференции по математической логике; г. Новосибирск, 1994; с. 86.
[33] В.В. Римацкий. О базисах квазитождеств модальных алгебр. Тезисы XXXV Международной студенческой научной конференции, секция алгебры и математической логики, г.Новосибирск, 1997; с. 86
[34] В.В. Римацкий. N-характеристические модели некоторых неклассических логик. Тезисы XV Научно-практической конференции, г.Красноярск, апрель 1997; с. 17.
[35] В.В. Римацкий. Конечная базируемость допустимых правил вывода модальных логик ширины 2 . Тезисы XV Научно-практической конференции, г.Красноярск, апрель 1997; с. 17.
ВВЕДЕНИЕ.
1 Предварительные сведения.
1.1 Синтаксис и алгебраическая семантика.
1.2 Теоретико-модельная семантике.
1.3 Правила вывода нестандартных логик.
2 Критерий принадлежности конечных алгебр квазимногообразию з2(А).
3 Базисы допустимых правил.
3.1 Базисы допустимых правил логик глубины 2.
3.2 Базисы допустимых правил логик ширины 2.
3.3 Базис допустимых правил интуиционистской логики Int в полу-редуцированной форме.
4 Логики, сохраняющие допустимость правил вывода.
4.1 Сохранение допустимости правил вывода в логиках, родственных логике £4.2.
4.2 84.3-логики, сохраняющие допустимость правил вывода.
Любое логическое исследование связано с некоторой логической дедуктивной системой (логикой) или классом таких систем. Как правило рассматривается конкретная аксиоматизация логики, состоящая из фиксированного набора аксиом и правил вывода, определяющих данную систему. Выбирая язык, набор аксиом и правил вывода можем задать самые различные логики. Особую роль играют широко известные классическая пропозициональная логика PC и исчисление предикатов РРС, развитые в работах Д. Гильберта, К. Гёделя и Г. Генцена в 20 - 40-е годы. Примерно в то же время в трудах А. Рейтинга (интуиционистская 1930), Лукасевича (многозначная 1920), К. Льюиса (модальная 1920 -1930) появились первые логики, отличающиеся от классических - так называемые неклассические или нестандартные логики.
Примечательно, что эти чисто логические исследования также сформировали область универсальной алгебры. Исторически первым семантическим аппаратом для изучения этих логик были различные алгебраические системы и модели. Фундамент данного направления был заложен в исследованиях А. Тарского и А. И. Мальцева (теория моделей), Лукасевича и Поста (многозначные алгебры), Стоуна и Маккинси (псевдо- и топобулевы алгебры). И только в 60-е годы в работах С. Крипке появилась теоретико-модельная семантика нестандартных логик, развитая впоследствии Леммоном, Дамметтом и другими.
Вполне естественно, что первоначально изучались различные аксиоматизации логик и их теоремы. Однако затем было замечено, что изменя набор постулированных правил вывода, можем также получать различные логики. Или добавляя некоторые правила вывода мы сохраняем множество теорем логики, значительно усиливая при этом ее дедуктивную силу. Стало ясно, что правила вывода играют более важную роль в процессе вывода 2 по сравнению с аксиомами системы. Все это привело к вопросу: когда правило вывода совместимо с заданной логикой и как следствие к понятию допустимого правила вывода.
Понятие допустимого правила вывода, введенное Лоренценом в 50-х годах, непосредственно вытекает из понятия формального логического исчисления. Это в точности те правила вывода, добавление которых к списку постулированных правил не расширит исчисления, не изменит множество теорем логики. Ценность допустимых правил формального исчисления заключается в том, что с их помощью можно упростить и сократить процесс вывода и верификации формул в этом исчислении, кроме того понятие допустимого правила не зависит от конкретной аксиоматизации исчисления, то есть является инвариантом. Проблема допустимости правил вывода заключается в следующем: допустимо ли данное правило вывода в заданном формальном исчислении (логике).
Проблематика допустимости естественно переносится на случай логических исчислений. Если в классическом исчислении высказываний проблема допустимости правил вывода решается тривиально, то уже случай интуиционистской пропозициональной логики потребовал разработки сложной техники. Интерес к интуиционизму был вызван связями с основаниями математики. В 50-ые годы П.С. Новиков отмечал в своих лекциях важность различия допустимых и производных правил вывода в интуиционистской логике. Первые конкретные результаты по проблеме допустимости в интуиционистской логике были получены в 60-ых годах. Так Харропом в 1960 году [54], а после Минцем в 1972 [10] были получены примеры допустимых, но не производных правил вывода. Г.Е. Минцем в [10, 11] был найден ряд достаточных условий допустимости и производности в интуиционистской логике.
Вопрос о существовании алгоритма, распознающего допустимость правил вывода, был поставлен Кузнецовым A.B. Схожая проблема была включена в обзор проблем Фридмана ([45], проблема 40). В 1977 году А.И. Циткиным были найдены критерии допустимости для правил специального вида в [29]. Им же в [30] были описаны модусно предполные суперинтуиционистские логики. Но сама проблема Кузнецова-Фридмана разрешимости по допустимости в интуиционистском исчислении высказываний оставалась открытой. Аналогичная проблема также актуальна для модальных логик. Допустимость и производность специальных правил в логике Льюиса S5 исследовалась Портом в 1981 году в [62, 63].
Проблема допустимости имеет прямой алгебраический аналог, а именно, правило допустимо в логике, если соответствующее ему квазитождество истинно на свободных алгебрах многообразия, соответствующего этой логике. Разрешимость проблемы допустимости в логике эквивалентна разрешимости квазиэквацио-нальной теории свободных алгебр многообразия, порожденного этой логикой. Это позволило привлечь к решению проблемы допустимости хорошо разработанные алгебраические методы. На основе этого подхода Рыбаковым В.В. была доказана в 1981 году разрешимость проблемы допустимости для "сильных" модальных логик — табличных и предтабличных, там же был поставлен вопрос о проблеме допустимости в "слабых" логиках [13]. Алгоритмический критерий допустимости для логик S4 + Ofc был найден Рыбаковым В.В. в 1984 в [15]. В том же году была доказана разрешимость проблемы допустимости для целого класса логик — логик, расширяющих S4.3 [17].
В [13] было замечено, что правило вывода а/ß допустимо в суперинтуиционистской логике Л Э Int, тогда и только тогда, когда правило Т(а) /T(ß) допустимо в сг(А) — наибольшем модальном напарнике Л, где Т(а) перевод Гёделя-МакКинси-Тарского интуиционистской формулы а в модальную (см. например [5]). Появилась надежда, что проблему допустимости в Int можно решить, доказав разрешимость проблемы допустимости в одной из модальных логик яруса /Г1 (Int). В 1984 году Рыбаковым В.В. [16] был найден алгоритмический критерий допустимости правил вывода в модальной системе S4 и интуиционистской логике Int. Одновременно были получены алгебраические аналоги этих результатов — разрешимость универсальных теорий свободной алгебры замыканий и свободной псевдобулевой алгебры. Заметим, что. как показано в [14], элементарные теории этих алгебр неразрешимы.
Использованный Рыбаковым В.В. в [16] метод оказался достаточно мощным и гибким в использовании. Помимо решения основной проблемы допустимости, с помощью этого критерия удалось получить ряд не менее интересных результатов: таких, как уже упоминавшееся доказательство разрешимости универсальных теорий свободной алгебры замыканий и свободной псевдобулевой алгебры, доказательство отсутствия базиса допустимых правил от конечного числа переменных. Данная техника, с несущественными изменениями, использовалась для доказательства разрешимости проблемы допустимости в логиках Grz, S (логика Соловая), GL (логика Гёделя-Лёба), К4 (см. [67, 65]). Причем логики S и Gl представляют особый интерес, как логики, аксиоматизирующие различные варианты понятия доказуемости в арифметике [74, 1, 33, 34]. В настоящее время интенсивно исследуются различные аспекты проблемы допустимости [19]—[27], [70, 64, 40, 75, 76].
Несмотря на успехи метода в решении проблем допустимости в различных логиках, приблизительно в то же время, стали отчетливей видны его ограничения. Первое (очевидное и принципиальное) ограничение заключается в том, что проблему разрешимости по допустимости можно поставить только в разрешимых логиках, из всего многообразия нормальных модальных логик мощности континуум, поскольку допустимость правила вида р V -1 р/а в логике равносильна тому, что а теорема этой логики. Второе принципиальное ограничение основывается на том, что метод применим только к транзитивным финитно аппроксимируемым логикам, поскольку только в этом случае удается эффективно описать «-характеристические модели логики. В то же время, оказалось, что аналогичный подход может быть реализован напрямую и в суперинтуиционистских логиках [69], полимодальных логиках, логиках схем, то есть там, где используется семантика Кринке с транзитивными фреймами.
Помимо проблемы распознавания допустимых правил вывода не меньшую важность имеет проблема нахождения конечного числа допустимых правил вывода, называемых базисом допустимых правил вывода, из которых все остальные получаются как следствия (проблема Кузнецова, 1973г.). Проблема конечной ба-зируемости по допустимости также имеет алгебраический аналог: нахождение базиса квазитождеств квазимногообразия, порождаемого свободной алгеброй счетного ранга из многообразия, соответствующего логике А. Благодаря этому при изучении вопроса о конечной базируемое™ допустимых правил заданной логики или класса логик оказалось возможным использовать аппарат универсальной алгебры. На сегодняшний день теория допустимых правил вывода представляет собой результат слияния методов универсальной алгебры (теории квазимногообразий) и теоретико-модельной семантики Крипке.
Оказалось, что для многих базовых, индивидуальных нестандартных логик не существует базиса от конечного числа переменных для допустимых правил вывода. Например, Рыбаковым В.В. было доказано отсутствие такого базиса для логик 54 и Int в [18], Grz в [19], для логик 54.1, 54.2, 54/„, Х4, КАЛ, К4.2, КС, /п, п е N в Главе 4.2 [28]. Однако, некоторые фрагменты множества допустимых правил логики Int имеют конечный базис [29], так же как и любая модальная логика, расширяющая логику 54.3 (Corollary 4.3.20 [28]). В тоже время целые классы достаточно "'сильных" табличных логик ширины или глубины 2 имеют конечный базис для допустимых правил, что было даказано в [78], [80].
Табличные логики, расположенные в верхней части решетки модальных (суперинтуиционистских) логик, являются наиболее сильными в классе всех данных логик. В частности, многообразие алгебр, соответствующее табличной логике, является локально конечным, т.е. любая конечно порожденная алгебра из данного многообразия - конечна. Этот факт позволил высказать предположение, что любая транзитивная табличная логика конечно базируема по допустимости.
В диссертации получены следующие основные результаты
1. Доказана конечная базируемос.ть по допустимости произвольной табличной логики глубины 2, а также финитно аппроксимируемых логик ширины 2;
2. Как следствие доказана конечная базируемость квазиэква-циональных теорий свободных алгебр А) и зт(А), где А -любая логика, описанного выше класса;
3. Построен рекурсивный базис для допустимых правил выода логики Int в полу-редуцированной форме
4. Описаны 54.2-логики и родственные им логики, сохраняющие допустимость правил вывода, допустимых в логиках 54.2, Grz.2, КС;
Результаты диссертации докладывались на Международной конференции по математической логике, посвященной 85-летию со дня рождения А.И. Мальцева (г. Новосибирск, 1994 г.), XXXIV - XXXV Международных научных студенческих конференциях (г. Новосибирск, 1996 и 1997 гг.), I и II Международной конференции "Мальчевские чтения" (г. Новосибирск, 1997 и 1998 гг.), XV Межрегиональной научно - технической конференции (г. Красноярск, 1997г.), а также на заседаниях семинаров "Алгебра и логика" при Новосибирском государственном университете, семинара по неклассическим логикам при Институте математики СО РАН (г. Новосибирск)
1. Артемов С.Н. Модальные логики доказуемости // Известия Академии наук СССР. Сер. математическая. 1985. №49. С. 1123-1154.
2. Бабенышев С.В. Базисы допустимых правил вывода модальных логик S4.2 и S4.2Grz // Алгебра и логика. 1993. Т. 32. №2. С. 117-130.
3. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. — М.: Наука, 1980.
4. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории // Успехи математических наук. 1965. Т. 20. №. 4. С. 37-108.
5. Захарьящев М.В. Синтаксис и семантика суперинтуиционистских логик // Алгебра и логика. 1989. Т. 28. №4. С. 402-429.
6. Chagrov A., Zakharyaschev М., On the independent axiomatizability of modal and superintuitionistic logics. J. of Logic and Computation, Vol. 5, 1995, 287 - 302.
7. Максимова Л.Л. Модальные логики конечных слоев // Алгебра и логика. 1975. Т. 14. №3. С. 304-319.
8. Максимова Л.Л., Рыбаков В.В. О решетке нормальных модальных логик // Алгебра и логика. 1974. Т. 13. №2. С. 105122.
9. Мальцев А.И. Алгебраические системы. — М.: Наука, 1970.
10. Минц Г.Е. Производность допустимых правил // Записки научного семинара ЛОМИ АН СССР. 1972. №32. С. 85-99.
11. Минц Г.Е. Допустимые и производные правила // Записки научного семинара ЛОМИ АН СССР. 1968. №8. С. 189-191.
12. Расёва Е., Сикорский Р. Математика метаматематики. — М.: Наука, 1972.
13. Рыбаков В.В. Допустимые правила предтабличных модальных логик // Алгебра и логика. 1981. Т. 20. №4. С. 440-464.
14. Рыбаков В.В. Элементарные теории свободных алгебр замыканий // XXVI Всесоюзная алгебраическая конференция: Тез. докл.— Ленинград, 1981. С. 116.
15. Рыбаков В.В. Разрешимость проблемы допустимости в ко-нечнослойных модальных логиках // Алгебра и логика. 1984. Т. 23. №1. С. 100-116.
16. Рыбаков В.В. Критерий допустимости правил в модальной системе S4 и интуиционистской логике // Алгебра и логика. 1984. Т. 23. №5. С. 546-572.
17. Рыбаков В.В. Допустимые правила логик, содержащих S4.3 // Сибирский математический журнал. 1984. Т. 25. №5. С. 141-145.
18. Рыбаков В.В. Базисы допустимых правил логик S4 и Int // Алгебра и логика. 1985. Т. 24. №1. С. 87-107.
19. Рыбаков В.В. Базисы допустимых правил модальной системы Grz и интуиционистской логики // Математический сборник. 1985. Т. 128. №3. С. 321-338.
20. Рыбаков В.В. Универсальные теории свободных Л-алгебр при А Э 84.3 // Сложностные проблемы математической логики. Калинин. 1985. С. 72-75.
21. Рыбаков В.В. Уравнения в свободной топобулевой алгебре и проблема подстановки // Доклады АН СССР. 1986. Т. 287. №3. С. 554-557.
22. Рыбаков В.В. Уравнения в свободных топобулевых алгебрах // Алгебра и логика. 1986. Т. 25. №2. С. 172-204.
23. Рыбаков В.В. Алгебраические методы в пропозициональной логике // Семиотика и информатика. — М., 1986. №28. С. 102-121.
24. Рыбаков В.В. Разрешимость по допустимости модальной системы Сгг и интуиционистской логики // Известия АН СССР: Сер. математическая. 1986. Т. 50. №3. С. 598-616.
25. Рыбаков В.В. Базисы допустимых правил модальных систем Сге и интуиционистской логики // Математический сборник. 1987. Т. 56. №2. С. 311-331.
26. Рыбаков В.В. Допустимость правил вывода и логические уравнения в модальных логиках, аксиоматизирующих доказуемость // Известия АН СССР. Сер. математическая. 1990. Т. 54. №2. С. 357-377.
27. Рыбаков В.В. Критерии допустимости правил вывода с параметрами в интуиционистской пропозициональной логике // Известия АН СССР. Сер. математическая. 1990. Т. 54. №6. С. 693-703.
28. Rybakov V.V. Admissibility of logical inference rules. -Book. Studies in Logic and Foundations of Mathematics., Vol. 136, Elsevier Publ., Amsterdam, New-York, 1997, 617 pp.
29. Циткин А.И. О допустимых правилах интуиционистсткой логики высказываний // Математический сборник. 1977. Т. 102. №2. С. 314-323.
30. Циткин А.И. О структурально полных суперинтуиционистских логиках // Доклады АН СССР. 1978. Т. 241. №1. С. 4043.
31. Фейс Р. Модальная логика. — М.: Наука, 1974.
32. Balcer К. Finite equational basis for finite algebras a congruence-distributive equational class // Advanced Mathematics. 1977. V. 24. № 3. P. 207-243.
33. Beklemishev L.D. Provability logics for natural Turing progressins of arithmetical theories // Studia Logica. 1991. V. 50. P. 107 128.
34. Beklemishev L.D. On bimodal logics of provability // Annals of Pure and Applied Logic. 1994. V. 68. P. 115-159.
35. Bellissima F. Finitely Generated Free Heyting Algebras // The Journal of Symbol с Logic. 1986. V. 51. №1. P. 152-165.
36. Blok W.J. The Free Closure Algebra on Finitely Many Generators // Indogations Mathematicae. 1977. V. 39. №5. P. 362-379.
37. Blok W.J., Pigozzi D. A finite basis theorem for quasivarieties // Algebra Universalies. 1986. V. 22. P. 1-13.
38. Chagrov A., Zakharyaschev M., Modal logics. // Book, Cambridge Press, 1997, 589 pp.
39. Dummctt M.A.E., Lemmon E.J. Modal logics between S4 and S5. // Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 1959. V. 4. P. 250-264.
40. Fagin R., Halpern J.Y., Vardi M.Y. What is an inference rule // The Journal of Symbolic Logic. 1992. V. 57. №3. P. 1018-1045.
41. Fine K. Logics Containing S4.3 // Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 1971. V. 17. P. 371-376.
42. Fine K. An Ascending Chain of S4 Logics. // Theoria. 1974. V. 40. P. 110-116.
43. Fine K. Logics containing K4, Part I // The Journal of Symbolic Logic. 1974. V. 39. №3. P. 229-237.
44. Fine K. Logics containing K4. Part II // Journal of Symbolic Logic. 1985. V. 50. №3. P. 619-651.
45. Friedman H. One hundred and two problems in mathematical logic // The Journal of Symbolic Logic. 1975. V. 40. №3. P. 113-129.
46. Gabbay D.M. Selective Filtration in Modal Logics // Theoria. 1970. V. 30. P. 323-330.
47. Gabbay D.M. A General Filtration Method for Modal Logics // Journal of Philosophical Logics. 1972. №1. P. 29-34.
48. Gabbay D.M., De Jongh D.H.J. A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property // The Journal of Symbolic Logic. 1974. V. 39. №1. P. 67-78.93
49. Gleit Z., Goldfarb W. Characters and fixed points in provability logic // Notre Dame Journal of Formal Logic. 1990. V. 31. №1. P. 26 36.
50. Goldblatt R.I. Metamathematics of modal logics. Part I // Reports on Mathematical Logic. 1976. V. 6. P. 41-78.
51. Goldblatt R.I. Metamathematics of modal logics. Part II // Reports on Mathematical Logic. 1976. V. 7. P. 21-52.
52. Goldblatt R.I. The McKinsev axiom is not canonical // The Journal of Symbolic Logic. 1991. V. 56. №2. P. 554 -562.
53. Gurevich Y., Shelah S. Fixed-point extensions of first-order logic J // Annals of Pure and Applied Logic. 1986. V. 32. P. 265-280.
54. Harrop R. Concerning formulas of the types A —> B V C, A —> 3xB(x) in intuitionistic formal systems // The Journal of Symbolic Logic. 1960. V. 25. № 1. P. 27-32.
55. Jonsson B., Tarski A. Boolean Algebras with operators // American Journal of Mathematics. 1951. V. 73. P. 891-939.
56. Kripke S. Semantic Analysis of Modal Logic // Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 1963. V. 9. P. 67-96.
57. Lemmon E.J. Algebraic semantics for modal logics, II // The Journal of Symbolic Logic. 1966. V. 31. P. 191-218.
58. Makinson D. On some completeness theorems in modal logic // Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 1966. V. 12. P. 379 -394.
59. McKinsey J.C.C. On the syntactical construction of systems of modal logic // The Journal of Symbolic Logic. 1945. V. 10. P. 83-94.
60. McKinsey J., Tarski A. Some theorems about the sentential calculi of Lewis and Heyting // The Journal of Symbolic Logic. 1948. V. 13. P. 1-15.
61. Pigozzi D. Finite basis theorem for relatively congruence-distributive quasivarieties // Transactions of the American Mathematical Society. 1988. V. 310. №2, P. 499-533.
62. Port J. The deducibilities of S5 // Journal of Philosophical Logic. 1981. V. 10. P. 409-422.
63. Port J. Axiomatization and independence in S4 and S5 // Reports on Mathematical Logic. 1983. V. 16. P. 23-33.
64. Rautenberg W. Applications of Weak Kripke Semantics to Intermediate Consequences // Studia Logica. 1986. V. 45. P. 119-134.
65. Rybakov V.V. Logical equations and admissible rules of inference with parameters in modal provability logics // Studia Logica, 1990. V. XLIX. №2. P. 215-239.
66. Rybakov V.V. Metatheories of first-order theories // Proc. of the IV Asian Logic Conference. CSK Educational Center. — Tokyo. Japan. 1990. P. 16-17.
67. Rybakov V.V. Problems of substitution and admissibility in the modal system Grz and intuitionistic calculus. // Annals of pure and applied logic. 1990. V. 50. P. 71-106.
68. Rybakov V.V. Poly-modal logic as metatheory of pure predicate calculus // Abstracts of the 9-th Intern. Congress of Log. Meth. and Phil, of Sci., Section 1-5. Uppsala. Sweden. 1991. P. 158.
69. Rybakov V.V. Rules of inference with parameters for intuitionistic logic // The Journal of Symbolic Logic. 1992. V. 57. №3. P. 912-923.
70. Rybakov V.V. Criteria for admissibility of inference rules modal and intermediate logics with the branching property // Studia Logica. 1994. V. 53. №2. P. 203-22
71. Segerberg K. Decidability of Four Modal Logics // Theoria. 1968. V. 28. P. 21-25.
72. Segerberg K. An essay in classical modal logic // Filosofiska Studier. University of Uppsala.— Uppsala, 1971. V. 1-3. №13.
73. Selman A. Completness of calculi for axiomaticalv defined classes of algebras // Algebra Universalies. 1972. V. 2. .№1. P. 20-32.
74. Solovay R. Provability interpretations of modal logic // Israel J. Math. 1976. V. 25. P. 287-304.
75. Venema Y. Derivation rules as anti-axioms in modal logic // The Journal of Symbolic Logic. 1993. V. 59. №3. P. 1003-1034.
76. Williamson T. Some Admissible Rules in Nonnormal Modal Systems // Notre Dame Journal of Formal Logic. 1993. V. 34. №3. P. 378-400.
77. Wojtvlak P. Independent axiomatizability of Sets of Sentences. Annals of Purer and Applied Logic, V. 44, 1989, 259 - 299.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
78. В.В. Римацкий. Базисы допустимых правил вывода Табличных Модальных Логик глубины 2. Алгебра и логика, т. 35 (1996), N5 с. 612 -623.
79. V.V. Rimatskiy. Finite Bases of Admissibile inference rules for Modal Logics of Width 2. Bulletin of the Section of Logic: v.26, N.3, Oct. 1997, pp. 126 134.
80. B.B. Римацкий. О конечной базируемое™ допустимых правил вывода модальных логик ширины 2 . Алгебра и логика, г. 38 (1999), N5, с. 436 455.
81. V.V. Rybakov, М. Terziler, V. Remazki. Bases in semi-reduced form for admissible rules of intuitionistic logic IPC. Mathematical Logic Quaterly, No. 2, Vol. 46 (2000), 17 pp.
82. B.B. Римацкий. Расширения конечно базируемых по допустимости табличных логик; Сиб. Мат. Журнал, в печати.
83. В.В.Рыбаков, В.В.Римацкий. 54.2-логики, сохраняющие допустимые правила вывода логики 54.2 и родственных ей логик, Сиб. Мат. Журнал, в печати.
84. В.В. Римацкий. Базисы допустимых правил вывода Табличных Модальных Логик глубины 2. Тезисы Международной конференции по математической логике; г. Новосибирск, 1994; с. 86.
85. В.В. Римацкий. О базисах квазитождеств модальных алгебр. Тезисы XXXV Международной студенческой научнойконференции, секция алгебры и математической логики, г.Новосибирск, 1997; с. 86
86. В.В. Римацкий. 1Ч-характеристические модели некоторых неклассических логик. Тезисы XV Научно-практической конференции, г.Красноярск, апрель 1997; с.17.
87. В.В. Римацкий. Конечная базируемость допустимых правил вывода модальных логик ширины 2 . Тезисы XV Научно-практической конференции, г.Красноярск, апрель 1997; с. 17.
