Исследование правил вывода в нестандартных логиках тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВЕДЕНИЕ

1 СИНТАКСИС И СЕМАНТИКА ДОПУСТИМЫХ

ПРАВИЛ ВЫВОДА В НЕСТАНДАРТНЫХ ЛОГИКАХ

1.1 Семантика Крипке: необходимые предварительные сведения.

1.2 Теория допустимых правил вывода.

2 САМОДОПУСТИМОСТЬ КВАЗИХАРАКТЕРИСТИЧЕСКИХ ПРАВИЛ ВЫВОДА ДЛЯ КОНЕЧНЫХ

МОДАЛЬНЫХ АЛГЕБР

2.1 Самодопустимость правил вывода в нестандартных логиках.

2.2 Строение жесткого фрейма.

2.3 Класс жестких Сгг-фреймов глубины 3.

3 ФИНИТНАЯ АППРОКСИМИРУЕМОСТЬ В

СУПЕРИНТУИЦИОНИСТСКИХ ЛОГИКАХ ПО ДОПУСТИМОСТИ

3.1 Финитная аппроксимируемость модальных логик над К А по допустимости.

3.2 Отсутствие финитной аппроксимируемости суперинтуиционистских логик по допустимости.

3.3 Финитная аппроксимируемость суперинтуиционистских логик по допустимости

4 НАСЛЕДОВАНИЕ ДОПУСТИМЫХ ПРАВИЛ

ВЫВОДА ДЛЯ ЛОГИКИ К

4.1 Наследование допустимых правил вывода для ,94.

4.2 Критерий наследования допустимости правил вывода К

4.3 О логиках над КА с отсутствием наследования допустимости К

5 ЯВНЫЙ БАЗИС ДЛЯ ДОПУСТИМЫХ ПРАВИЛ ВЫВОДА В ЛОГИКЕ ОЬ

5.1 Явный базис в интуиционистской логике Н и 8А.

5.2 Описание явного базиса для допустимых правил логики ОЬ.

Разработка теории для допустимых правил восходит к исследованиям Новикова, который рассматривал наряду с понятием производного правила(допустимого правила) понятие сильного производного правила вывода, Новиков [29] в своей работе затронул дедуктивные аспекты производных правил вывода в интуиционистской логике. Общепринятое понятие допустимого правила появилось в работе Лоренцена [95], который высоко оценил значимость введенного понятия. Наблюдение Лоренцена заключалось в том, что допустимым правилом для логики А является правило вывода относительно которого логика А замкнута. По сути допустимость правил вывода позволяет нам получать более эффективный вывод формул в данном языке. Таким образом введение допустимого правила позволило смотреть на дедуктивные свойства логических систем с новой точки зрения. В работах Маслова [22, 23, 24] исследовалась возможность применения производных и допустимых правил вывода в различных сферах деятельности; по его мнению — первый тип правил связан с уже развитой теорией, а второй с теорией, которая находится в процессе конструирования.

В исследованиях польской логической школы [126] была подмечена связь допустимого правила для алгебраической логики А и соответственно квазитождества истинного на свободной алгебре счетного ранга из многообразия логики А. Рассмотрение допустимости на алгебраическом языке стало поворотным моментом в исследовании, поскольку в таком случае появилась возможность применить аппарат универсальной алгебры на очень высоком уровне. Более того установление допустимости в нестандартных логических системах таких как Я, А'4, 54, Огг, СЬ и ЗЪ означает получение серьезных результатов в основаниях математики. Сближение математической логики и универсальной алгебры [5, 8, 9, 15, 38, 39, 48, 76, 81, 85, 92, 93, 94, 96, 97] позволило изучать объекты логики на интуитивном уровне, под интуитивным мы понимаем введение реляционных систем, так называемых фреймов, где элементы множества трактуются как миры, а бинарное отношение между элементами — отношение достижимости между мирами. Введению таких обьектов мы обязаны Крипке. Крипке [90, 91] подробно разработал реляционную семантику для модальной и интуиционистской логики, что позволило применять теоретико-модельную технику в исследованиях допустимых правил вывода.

Как мы выше упомянули, первым, кто подметил связь между допустимыми и выводимыми правилами был Новиков. В работах Харропа [84] и Минца [25, 26] были получены примеры допустимых, но не выводимых правил в интуиционистской логике. Порт [102] исследовал допустимость и выводимость в логике 55. Отметим что из выводимости следует допустимость, поскольку выводимость в алгебраической логике Л подразумевает истинность на любой алгебре из соответствующего многообразия. Но ясно, что в общем случае из допустимости не следует выводимость, поскольку истинность на свободной алгебре квазитождества вообще говоря не влечет его истинность на любой алгебре из многообразия. В классическом случае ситуация довольно проста: понятия допустимого правила и выводимого эквивалентны. Но в интуиционистском ситуация меняется, что как раз и подметили Харроп и Минц. Таким образом обуславливается появление понятия структурной полноты логики, то есть логики в которой допустимость правила влечет его выводимость. В исследовании структурной полноты преуспели Циткин [53], который исследовал структурную полноту суперинтуиционистских логик, а также Рыбаков [112], которому удалось описать все наследственно структурно полные логики над К4.

В списке проблем в математической логике [71] была сформулирована проблема о распознаваемости допустимых правил в ЫЦпроблема 40). А также близкий вопрос поставил Кузнецов(проблема 42,[71]): существует ли конечный базис для допустимых правил интуиционистской логики?

Проблема распознаваемости была решена положительно Рыбаковым [33] с помощью п-характериетических моделей, после чего вопрос о существовании конечного базиса был решен отрицательно так же Рыбаковым [35, 36]. Вышеописанные результаты стали по сути отправными в исследовании критериев, свойств и базисов допустимых правил для нестандартных логик. Остановимся подробнее на этом исследовании. После получения вышеописанных результатов появился довольно большой простор для исследования. Так например были получены результаты о разрешимости для допустимых правил вывода логик Огг, ,94, ОЬ, причем при доказательстве использовался перевод Геделя-Маккпнси-Тарского [78, 101]. При решении проблемы разрешимости по допустимости весомую роль сыграло представление правил вывода в редуцированной форме. Стоить отметить, что указанные результаты были получены для индивидуальных логик.

Изучения свойств интуиционистской логики относительно характеристических формул стали проводиться в работах Янкова [57, 82, 83]. Характеристические формулы выражают свойство конечных подпрямо неразложимых псевдобулевых алгебр не являться подалгеброй гомоморфных образов любой псевдобулевой алгебры. Позднее в работе Циткина [52] появилось понятие квазихарактеристического правила вывода, причем введенное понятие усилило подход Янкова, поскольку выражает свойство порождающей данное правило подпрямо неразложимой алгебры не являться подалгеброй алгебры из Уаг(Н). Исследования Янкова и Циткина были продолжены

Рыбаковым [113], который получил описание для конечных подпрямо неразложимых модальных А'4-алгебр. В связи с которым было введено понятие жесткого фрейма [114]. Таким образом исследование квазихарактеристических правил перешло на новый качественный уровень, поскольку понятно, что реляционный инструментарий более гибкий чем операционный, так как фрейм имеет наглядное представление и позволяет нам изменять его форму в непосредственной геометрической связи. Цель возникновения жесткого фрейма выявляется в характеризации самодопустимого правила вывода. А именно Рыбаковым, Терзилером и Тендером [114] был получен следующий критерий: правило порождающее конечную подпрямо неразложимую АЧ-алгебру является самодопустимым тогда и только тогда, когда фрейм порождающий алгебру не является жестким. В работе Рыбакова и Онера [115] приводится описание всех типов жестких фреймов глубины не более 2, причем существует всего три типа жестких фреймов глубины не более 2.

Исследование понятия финитно аппроксимируемости имеет довольно долгую историю. Так к примеру табличные логики имеют свойство финитной аппроксимируемости (для примера классическая логика) по построению. Буль [62] с помощью методов из универсальной алгебры показал финитную аппроксимируемость всех расширений логики 54.3, введенной в работе Даммета и Леммона [64]. Габбай и Де Йонг [74] показали финитную аппроксимируемость суперинтуиционистских логик характеризующихся классом фреймов с конечным ветвлением с помощью метода селективной фильтрации, разработанного в [72, 73], и более того установили разрешимость таких логик. Сегерберг [121, 122] использовал сходную методику и показал финитную аппроксимируемость ,94.1, ОЬ, Огг. В работах Файна [67, 68, 69] используется метод опускания точек, Раутенбергом [103, 104] и Крахтом [88, 89] применяется метод расщепления логик. Чагров [46] исследовал разрешимость свойства финитной аппроксимируемости в расширениях ОЬ. Финитная аппроксимируемость относительно допустимости правил вывода возникает как естественное обобщение понятия финитной аппроксимируемости. Как было упомянуто выше финитная аппроксимируемость имеет место в большинстве индивидуальных нормальных модальных и суперинтуиционистских логик, но если изучать данное свойство относительно допустимости, то свойство нарушается к примеру в логиках К4, ,94, ОЬ, Огг. Такие примеры были получены в [117], главный результат данного исследования состоит в том, что все нормальные модальные логики над К4 ширины минимум 3 со свойством ко-покрытия не имеют свойства финитной аппроксимируемости по допустимости. Логики расширяющие 34 ширины менее 2 и фрейм специального вида не принадлежит множеству ,9Я(А) обладают свойством финитной аппроксимируемости. В качестве примера из известных нормальных модальных логик можно привести логику .94.3.

Первоначальные результаты о наследовании допустимости правил получены в [110], где установлено достаточное условие для отсутствия наследования допустимых правил интуиционистской логики Я. В [118] установлен критерий наследования допустимости правил вывода для финитно аппроксимирумых расширений логики ,54. Весомую роль в этом критерии играет свойство ко-покрытия, которое в зависимости от типа логики позволяет получать новые адекватные фреймы. Также в упомянутой работе получен критерий наследования допустимости для табличных расширений логики ,94.

Первые результаты о базисах для допустимых правил были получены Питкиным [52] для квазихарактеристических правил в логике Я, базис для допустимых квазихарактеристических правил логики Н состоит из одного обобщенного правила Минца, тем самым было получено решение проблемы 42 [71] в частном случае. Базисы для допустимых правил вывода в нестандартных логиках стали активно изучаться после решения Рыбаковым ряда открытых вопросов: проблема о распознаваемости допустимых правил в Н (проблема 40)[71], вопрос Кузнецова (проблема 42,[71]) о существовании конечного базиса для допустимых правил интуиционистской логики.

Поворотным стал момент о несуществовании конечных базисов для таких логик как Н, 54, Огг, ОЬ, то есть в таких логиках нельзя получить конечное описание для допустимых правил вывода. Бабенышевым в [4] было установлено, что 54.2 и 54.20гг не имеют конечного базиса для допустимых правил вывода.

Алгебраический эквивалент этих результатов означает, что свободная алгебра из многообразия соответствующая логике не имеет конечного базиса квазитождеств. В отличие от указанных логик 54.3 обладает конечным базисом для допустимых правил [32] и более того любое расширение 54.3 обладает конечным базисом, такой базис состоит из одного правила вывода, суперинтуиционистская логика ЬС также обладает конечным базисом. Римацким в [30] исследована конечная базируемость модальных логик ширины 2. Из результатов о несуществовании конечного базиса для допустимых правил вывода вытекает несуществование конечного описания для допустимых правил вывода. Поэтому, чтобы иметь конкретное описание для допустимых правил вывода возникла потребность в получении явного базиса. Так описание явного базиса (бесконечного) для допустимых правил получено в [86], где предложен явный базис для интуиционистской логики, немного позднее в работе Рыбакова [119] с использованием правил вывода в редуцированной форме было получено описание явного базиса для допустимых правил в модальной логине ,54. Цель работы.

1. Получить с точностью до изоморфизма описание класса жестких Сгг-фреймов глубины 3.

2. Исследовать свойство финитной аппроксимируемости по допустимости правил вывода в суперинтуиционистских логиках.

3. Исследовать свойство наследования по допустимости в логиках расширяющих К А.

4. Построить явный базис допустимых правил вывода логики ОЬ.

Методика исследования. В исследовании применяются общие методы теоретико-модельной и алгебраической семантики для пропозициональных модальных и суперинтуиционистских логик.

Научная новизна. Все результаты, полученные в диссертации, являются новыми и снабжены подробными доказательствами. Результаты совместных работ получены в нераздельном соавторстве.

Основные результаты. В диссертации получены следующие основные результаты.

1. Доказано, что класс жестких 6>г-фреймов глубины 3 состоит из семи специальных типов.

2. Найдены достаточные условия для свойства финитной аппроксимируемости по допустимости и его отсутствия в суперинтуиционистских логиках.

3. Найден критерий наследования допустимости для логик расширяющих КА.

4. Построен явный базис допустимых правил вывода логики СЬ.

Теоретическая и практическая ценность. Все полученные результаты носят теоретический характер и могут быть использованы в дальнейших исследованиях нестандартных логик, а также в таких областях как универсальная алгебра, теория моделей, теория графов и computer science. Апробация работы. Результаты диссертации докладывались на

• XXXVII-международной научной студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 1999),

• XXXVIII-международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск,2000),

• XXXIX-международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 2001),

• международной конференции посвященной 60-летию со дня рождения Ю.Л.Ершова (Новосибирск, 2000),

• международной конференции "Дифференциальные уравнения и симметрия" (Красноярск, 2000),

• международной конференции посвященной 70-летию со дня рождения В.П.Шункова и 65-летию В.М.Бусаркина(Красноярск, 2002).

Публикации. По теме диссертации опубликовано 12 работ [129]—[140]. Основные результаты диссертации опубликованы в работах [132], [133], [135]—[137], [139], [140]. Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения и библиографического списка, включающего 128 наименований. Объём работы 96 страниц машинописного текста.

ЗАКЛЮЧЕНИЕ

В данной работе представлен класс жестких фреймов глубины 3 для логики Огг. Если говорить о других логиках например ,94 или К4, в силу Леммы 2Л, классы жестких фреймов для указанных логик будут шире чем для От г, и по вычислительным причинам описания для таких логик не приводятся. Имеет смысл в дальнейшем найти комбинаторные формулы связыващие глубину и ширину жесткого фрейма, а также найти комбинаторные формулы для перечисления всего класса жестких фреймов, также имеет смысл исследовать логики порожденные жесткими фреймами на предмет базируемости по допустимости.

В связи с проведёнными исследованиями возникают следующие задачи, сформулированные в [117]: ослабить свойства ко-накрытия и транзитивности, найти достаточные условия финитной аппроксимируемости по допустимости для всех логик над К4, найти необходимые и достаточные условия для финитно аппроксимируемых логик над ,94 или К4 ширины не более 2 для обладания финитной аппроксимируемостью по допустимости.

Полученный в работе критерий для наследования допустимых правил вывода К4 получит продолжение в дальнейшем изучении наследования свойств нестандартных логик. Отметим, что ряд открытых вопросов о наследовании допустимых правил вывода, сформулированных ранее (см. [118]), остался не решенным. К таким вопросам можно отнести проблемы, связанные с изучением логик, наследующих правила вывода, допустимые для К4 и ,94: нахождение алгоритмических критериев наследования, описание структуры этих логик, выяснение, является ли множество таких логик замкнутым относительно решеточных операций, есть ли среди них логики без свойства финитной аппроксимируемости. Остается нерешенной и общая зада

80 ча получения критерия наследования допустимых правил вывода для произвольной модальной логики.

Исследования базисов для допустимых правил вывода в нестандартных логиках проводились в работах Циткина, Рыбакова, Бабенышева, Римацкого. Большинство из полученных результатов связано с отсутствием конечного базиса для допустимых правил вывода. Наряду с этим ощущалась явная нехватка работ посвященных построениям бесконечных базисов. Поэтому построенный в данной работе базис для GL восполняет этот пробел, поскольку мы имеем в таком случае описание допустимых правил вывода, хотя и бесконечное.

В настоящий момент инструменты неклассических логик интенсивно используются в исследованиях по computer science, поэтому полученные в диссертации результаты помимо чисто математических приложений, могут иметь применение также при разработке теории информатики, искусственного интеллекта и computer science.

1. Артемов С.H. Модальные логики доказуемости// Известия Академии наук СССР. Сер. математическая. — 1985. — № 49. — С. 1123-1154.

2. Бабенышев C.B. Разрешимость проблемы допустимости правил вывода в модальных логиках S4.2 п S4.2Grz и суперинтуиционистской логике КС// Алгебра и логика. — 1992. — Т. 31. — № 4. — С. 341-359.

3. Бабенышев C.B. Базисы допустимых правил вывода модальных логик S4.2 и S4.2Grz// Алгебра и логика. — 1993. — Т. 32. — № 2. — С. 117-130.

4. Безгачева Ю.В. Допустимость правил вывода в логиках ширины 2// Деп. ВИНИТИ — 27.07.98,— № 2377-В98.

5. Биркгофф Г. Теория решёток. — М.:Наука, 1984.

6. Рейтинг А. Интуиционизм. — М.:Мир, 1965.

7. Генцен Г. Исследования логических выводов// Математическая теория логического вывода. — 1967 — С.9-74 — М.:Наука.

8. Горбунов В.А. Алгебраическая теория квазимногообразий. — Н.:Научная книга, 1999.

9. Григолия Р.Ш. Свободные алгебры неклассических логик. — Т.:Мецниереба, 1987.

10. Захарьящев М.В. Синтаксис и семантика суперинтуиционистских логик// Алгебра и логика. — 1989. — Т. 28. — № 4. — С. 402-429.

11. Карпенко A.C. Логики Лукасевича и простые числа. — М.:Наука, 2000.

12. Кон П.М. Универсальная алгебра. — М.:Мир, 1968.

13. Кузнецов A.B., Герчиу В.Я. О суперинтуиционистской логике и конечной аппроксимируемости// Доклады Академии Наук СССР. — 1970 — Т. 195 — № 5 — С. 1029-1032.

14. Леммон Е. Алгебраическая семантика для модальных логик 1,11// Семантика модальных и интенсиональных логик. — М.: Прогресс, 1981. — с.98-105.

15. Мальцев А.И. Алгебраические системы.— М.: Наука, 1970.— 392 с.

16. Максимова JI.JI. Предтабличные суперинтуиционистские логики// Алгебра и логика. — 1972. — Т. 14. — № 2. — С. 558-570.

17. Максимова Л.Л., Рыбаков В.В. О решётке нормальных модальных логик// Алгебра и логика. — 1974. — Т. 13. — № 2. — С. 105-122.

18. Максимова Л.Л. Модальные логики конечных слоев// Алгебра и логика. — 1975. — Т. 14. — № 3. — С:. 304-319.

19. Максимова Л.Л. Предтабличные расширения логики S4 Льюиса// Алгебра и логика. — 1975. — Т. 14. — № 1. — С. 28-56.

20. Мардаев С.И. Наименьшие неподвижные точки в логике Гёделя-Лёба// Алгебра и логика. — 1993. — Т. 32. — № 6. — С. 683-689.

21. Марков A.A. О конструктивной математике// Труды Матем. ин-та АН СССР им. В.А.Стеклова — 1962. — С. 8-14.

22. Маслов С.Ю. О поиске вывода в исчислениях общего типа// Зап. научных семинаров ЛОМИ АН СССР — 1972. — Т. 32. — С. 59-65

23. Маслов С.Ю. Теория поиска вывода и некоторые ее применения// Кибернетика1975.— №4 — С. 134-144.

24. Маслов С.Ю. Теория дедуктивных систем и ее применения. — М.:Радио и связь — 1986.

25. Минц Г.Е. Допустимые и производные правила// Записки научного семинара ЛОМИ АН СССР,— 1968. — № 8. — С. 189-191.

26. Минц Г.Е. Производность допустимых правил// Записки научного семинара ЛОМИ АН СССР,— 1972. — № 32. — С. 85-99.

27. Муравицкий А.Ю. О суперинтуиционистских логиках аппроксимируемых алгебрами с условием убывающих цепей// Математические заметки — 1984.

28. Т. 29. — № 6. — С.907-916.

29. Нагорный Н.М. Реализуемостная семантика раннего периода марковского кон-структивизма(история и проблемы.) — Логические исследования. — Вып.7 — 2000.

30. Новиков П.С. Конструктивная математическая логика с точки зрения классической. — М.: Наука, 1977.

31. Римацкий В.В. О конечной базируемое™ по допустимости модальных логик ширины 2// Алгебра и логика. — 1999. — Т. 38. — № 4. — С.436-455.

32. Рыбаков В.В. Допустимые правила предтабличных модальных логик// Алгебра и логика. — 1981. — Т. 20. — № 4. — С.440-464.

33. Рыбаков В.В. Допустимые правила логик, содержащих 84.3// Сибирский математический журнал. — 1984. — Т. 25. — № 5. — С. 141-145.

34. Рыбаков B.B. Критерий допустимости правил в модальной системе ,94 и интуиционистской логике// Алгебра и логика. — 1984. — Т.23 — № 5. — С.369-384.

35. Рыбаков В.В. Разрешимость проблемы допустимости в конечнослойных модальных логиках// Алгебра и логика. — 1984. — Т. 23. — № 1. — С. 100-116.

36. Рыбаков В.В. Базисы допустимых правил логик SA и Int// Алгебра и логика.1985. — Т. 24. — С. 55-68.

37. Рыбаков В.В. Базисы допустимых правил модальной системы Grz и интуиционистской логики// Математический сборник.— 1985. — Т. 128— № 3.1. С. 321-338.

38. Рыбаков В.В. Универсальные теории свободных А-алгебр при А I) S4.3// Слож-ностные проблемы математической логики. Калинин. — 1985. — С. 72-75.

39. Рыбаков В.В. Алгебраические методы в пропозициональной логике// Семиотика и информатика. — М., — 1986'. — № 28. — С. 102-121.

40. Рыбаков В.В. Уравнения в свободной топобулевой алгебре// Алгебра и логика.1986. — Т. 25. — № 2. — С. 172-204.

41. Рыбаков В.В. Уравнения в свободной топобулевой алгебре и проблема подстановки// Доклады АН СССР. — 1986. — Т. 287. — № 3. — С. 554-557.

42. Рыбаков В.В. Базисы допустимых правил модальных систем Grz и интуиционистской логики// Математический сборник. — 1987. — Т. 56. — № 2. — С. 311-331.

43. Рыбаков B.B. Разрешимость по допустимости модальной системы Grz и интуиционистской логики// Известия АН СССР: Сер. математическая. — 1986.

44. Т. 50. — № 3. — С. 598-616.

45. Рыбаков В.В. Допустимость правил вывода и логические уравнения в модальных логиках, аксиоматизирующих доказуемость// Известия АН СССР.1990. — № 3. — С.357-377.

46. Рыбаков В.В. Критерии допустимости правил вывода с параметрами в интуиционистской пропозициональной логике// Известия АН СССР. Сер. математическая. — 1990. — Т. 54. — № б. — С. 693-703.

47. Сидоренко Е.А. Теорема дедукции для неклассических логик: два подхода// Логические исследования. — 2001. — Вып. 8. — С. 172-187.

48. Чагров A.B. Неразрешимые свойства расширений логики доказуемости// Алгебра и логика — Т. 29 — № 3 — С. 350-367.

49. Шехтман В.Б. Лестницы Ригера-Нишимуры// Доклады АН СССР. — 1978. — Т. 241. — № 6. — С. 1288-1291.

50. Шехтман В.Б. Неразрешимое суперинтуиционистское исчисление высказываний// Доклады АН СССР. — 1978. — Т. 240. — № 3. — С. 549-552.

51. Хомич В.И. О проблеме отделимости для суперинтуиционистстких пропозициональных логик// Докл. АН СССР — 1980. — Т. 254. — № 4. — С. 820-823.

52. Хомич В.И. О свойствах суперинтуиционистстких пропозициональных исчислений// Сибирский математический журнал. — 1990. — Т. 31. — №6. — С. 158-175.

53. Цейтин Г.С. О сложности вывода в исчислении высказываний// Зап. научных семинаров ЛОМИ АН СССР — 1968. — Т. 8. — С. 234-259.

54. Циткин А.И. О допустимых правилах интуиционистсткой логики высказываний// Математический сборник. — 1977. — Т. 102. — № 2. — С. 314-323.

55. Циткин А.И. О структурально полных суперинтуиционистских логиках// Доклады АН СССР. — 1978. — Т. 241. — № 1. — С. 40-43.

56. Эсакия Л.Л. Слабая транзитивность реституция// Логические исследования.2001. — Вып. 8. — С. 244-256.

57. Янков В.А. О некотором суперконструктивном пропозициональном исчислении// Доклады Академии наук СССР — 1963 — Т.151 — № 4. — С. 796-798.

58. Янков В.А. Об исчислении слабого закона исключенного третьего// Известия Академии наук СССР — 1968 — Т.32 — № 5. — С. 1044-1051.

59. Янков В.А. Коньюнктивно неразложимые формулы в пропозизиональных исчислениях// Известия Академии наук СССР. Сер.мат — 1969 — Т.33 — № 1.1. С. 18-38.

60. Artemov. S.N., Dzhaparicize G. Finite Kripke Models and Predicate Logics of Provability// Journal of Symbolic Logic. — 1990. — V. 55. — № 3. — P. 10901098.

61. Beklemishev L.D. Provability logics for natural Turing progressins of arithmetical theories// Studia Logica. — 1991. — V. 50. — P. 107-128.

62. Beklemishev L.D. On bimodal logics of provability// Annals of Pure and Applied Logic. — 1994. — V. 68. — P. 115-159.

63. Blok W.J. On the degree of incompletness of modal logics// Bulletin of the Section of Logic of the Polish Academy of Science— 1978.— V. 7. — № 4 — P. 167-175.

64. Bull R.A. That all extensions of S4.'i have the finite model property// Z. für Mathematical Logic unci Gründl, der Mathematik. — 1966. — V. 12. — P. 341344.

65. Cliagrov A., Zakharyaschev M. Modal logics. — Oxford: Oxford University Press1997. — 589 p.

66. Dummett M.A., Lemmon E.J. Modal logics between S4 and S5// Z. für Mathematical Logic und Gründl, der Mathematik. — 1959. — V. 5. — P. 250264.

67. Esakia L., Meskhi V. The critical modal systems// Theoria. — 1977. — V. 43.1. P. 52-60.

68. 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.

69. Fine K. The logics containing S4.3// Z. für Mathematical Logic und Gründl, der Mathematik. — 1971. — V. 17. — P. 371-376.

70. Fine K. Logics containing K4. Part I// The Journal of Symbolic Logic. — 1974.1. V. 39. — P. 229-237.

71. Fine K. Logics containing K4. Part II// Tlie Journal of Symbolic Logic. — 1985.1. V. 50. — P. 619-651.

72. Fitting M.C.Intuitionistic logic, model theory and forsing— Amsterdam: Elsevier1969.

73. Friedman H. One hundred and two problems in mathematical logic// The Journal of Symbolic Logic. — 1975. — V. 40. — № 3. — P. 113-129.

74. Gabbay D. Selective filtration in modal logics// Theoria. — 1970. — V. 30. — P. 323-330.

75. Gabbay D. A general filtration method for modal logics// .Journal of Phil. Logic.1972. — V. 1. — P. 29-34.

76. Gabbay D., de Jongli D. A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property// Journal of Symbolic Logic.1974. — V. 39. — P. 67-78.

77. Goldblatt R. First-order definability in modal logic// Journal of Symbolic Logic.1975. — № 1 — V. 40. — P. 35-40.

78. Grig'olia R.S. Free »94.3-algebras of finite rank// Investigations in Non-classical Logics and Formal Theories. — 1983. — P. 281-286.

79. Grzegorc.zyk A. Some relational systems and the associated topological spaces// Fundamenta Mathematical. — V.60 — 1967. — P. 223-231.

80. Godel K. Eine Interpretation der Intuitionistisher Aussagenkalculus// Ergebnisse Math. Kolloquiums. — 1933. — V. 4. — P. 39-40.

81. Harrop R. On the existence of finite models and decision problems for propositional calculi// Proceedings of the ( 'ami)ridge Philosophical Society. — 1958. — V.54.1. P. 1-13.

82. 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.

83. Horn A. THe separation theorem of intuitionistic prepositional calculus// The Journal of Symbolic Logic. — 1962. — V.27. — № 4. — P. 391-399.

84. Jankov Y.A. The Relationship between Deducibility in the Intuitionistic Propositional Calculus and the Finite Implicational Structures// Soviet Mathematics Doclady. — 1963 — V.31 — № 2. — P.1203-1204.

85. Jankov V.A. The construction of a sequence of strongly independent superintuitionistic propositional calculi// Soviet Mathematics Doclady. — 1968.1. V.9.

86. Jaskowski S. Investigations into the systems of intuitionistic logic// Polish logic: 1920-1939. Oxford: Clarendon press — 1967. — V.25. — P. 259-263.

87. Jonsson B., Tarski A. Boolean algebras with operators// American journal of mathematics. — 1951. — V.73. — P. 891-939.

88. Iemhoff R. On the admissible rules of Intuitionistic Propositional Logic// Journal of Symbolic logic. — 2001. — V.66. — P. 291-312.

89. Kleene C.S. On the interpretation of intuitionistic number theory// Journal of Symbolic Logic. — 1945. — V.10 — P. 109-124.

90. Kracht M. Internal definability and completeness in modal logics. Ph. D. — Free University of Berlin, 1991. — 110 p.

91. Kracht M. Splittings and the finite model property// Journal of Symbolic Logic.1993. — V. 58. — P. 139-157.

92. Kripke S. Semantic, analysis of modal logic,// Zeitschrift für mathematische Logic und Grundlagen der Mathematik. — 1963. — V.9. — P. 67-96.

93. Kripke S. Semantic analysis of intuitionistic. logic.// Formal systems and recursive functions. — 1965. P. 92-130.

94. Lemmon E. Algebraic semantics for modal logics 1,11// Journal of Symbolic Logic.1966. — Y. 31. — P. 46-65, 191-218.

95. Lindon R.O. Equations in free groups// Trans. Amer. Math. Soc. — 1960. — V. 96. — P. 445-457.

96. Lindon R.C. Equations in free meta-abelian groups// Trans. Amer. Math. Soc. — 1966. — V. 17. — P. 728-730.

97. Lorenzen P. Einfurung in Operativ Logik und Mathematik. — Berlin, Göttingen, Heidelberg: Springer-Verlag — 1955. — 412 p.

98. Makanin G.S. Decidability of universal and positive theories of free groups// Izvestiya Acad, of Sei. USSR. — 1984. — № 4. — P. 735-749.

99. Makanin G.S. Problem of solvability for equations in free semigroup// Mathematical sbornik. — 1977. — V.103. — № 2. — P. 147-236

100. Makinson D. On some completeness theorem in modal logic.// Zeitschrift für mathematische Logic und Grundlagen der Mathematik. — 1966. — V.12. — P. 379-394.

101. Malinowski J. Deduction theorem in quantum logic — some negative results// The Journal of symbolic logic — 1990. — V.55. — № 2 — P. 615-625.

102. McKinsey J. On syntactical construction of systems of modal logic// Journal of symbolic logic. — 1945. — V. 10. — P. 83-94.

103. McKinsey J., Tarski A. Some theorems about the sentential calculi of Lewis and Heyting// Journal of symbolic logic. — 1948. — V. 13. — P. 1-15.

104. Port J. The deducibilities of S5// Journal of Philosophical Logic. — 1981. — V. 10. — P. 409-422.

105. Rautenberg W. Splitting lattices of logics// Archiv Math.Logik. — 1980.— V. 20.1. P. 155-159.

106. Rautenberg W. Applications of Weak Kripke Semantics to Intermediate Consequences// Studia Logica. — 1986. — V. 45. — P. 119-134.

107. Rybakov V.V. Logical Equations and Admissible Rules of Inference with Parameters in Modal Provability Logics// Studia Logica. — 1990. — V. 49.2. — P. 215-239.

108. 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.

109. Rybakov V.V. A modal analog for Glivenko's theorem and its applications// Notre Dame J. of Formal Logic. — 1992. — V. 33. — № 2. — P. 244-248.

110. Rybakov V.V. Rules of inference with parameters for intuitionistic. logic.// Journal of Symbolic Logic. — 1992. — V. 57. — № 3. — P. 912-923.

111. Rybakov V.V. Intermediate Logics Preserving Admissible Inference Rules of Heyting Calculus// Mathematical Logic Quarterly. — 1993. — V.39 — P. 403-415.

112. Rybakov V.V. Criteria for admissibility of inference rules. Modal and intermediate logics with the branching property// Studia Logica. — 1994. — V. 53. — № 2.1. P. 203-225.

113. Rybakov V.V. Hereditary Struc.turaelly Complete Modal Logics// J of Symbolic logic — 1995. — V. 60 — № 1 — P. 266-288.

114. Rybakov V.V. Admissibility of logical inference rules. — Amsterdam, New-York: Elsevier Publishers, — 1997. — 617 p.

115. Rybakov V.V, Terziler M, Gencer C. Self-admissible quasi-characterizing inference rules// Bulletin Section Logic. — 1998. — V. 27. — № 4. — P. 164-171.

116. Rybakov V.V, Oner T. The structure of rigid frames of restricted depth// Bulletin Section Logic. — 1998. — V. 27. — № 4. — P. 172-181.

117. Rybakov V.V, Remazki V., Terziler M. Basis in Semi-reduced form for admissible rules of intuitionistic logic IPC// Mathematical logic quarterly. — 1999. — V. 53.2. — P. 203-215.

118. Rybakov V.V, Kiatkin V.R, Oner T. On Finite model property for admissible rules// Mathematical logic quarterly. — 1999. — V. 45. — № 4. — P. 505-520.

119. Rybakov V.V., Gencer G., Oner T. Description of Modal Logics Inheriting Admissible Rules for 54// Logic Journal of IGPL. — 1999 — V. 7 — № 51. P. 635-663.

120. Rybakov V.V. Construction of an explicit basis for rules admissible in modal system S4// Mathematical logic quarterly. — 2001. — V. 47. — № 4. — P. 441446.

121. Scroggs S.J. Extensions of the Lewis system 55// The Journal of Symbolic Logic1951 — V. 16. — P. 563-566.

122. Segerberg K. Decidability of 54.1// Theoria. — 1968. — V. 34. — P. 7-20.

123. Segerberg K. An essay in classical modal logic// Filosofiska Studier, Mimeograph.1971. — V. 1-3.

124. Solovay R. Provability interpretations of modal logic.// Israel J. Math. — 1976.1. V. 25. — P. 287-304,

125. Troelstra A.S, Van Dalen D. Constructivism in Mathematics// Israel J. Math. North-Holland— V.l — 1988.

126. Williamson T. Some Admissible Rules in Nonnormal Modal Systems// Notre Dame Journal of Formal Logic. — 1993. — V. 34. — № 3. — P. 378-400.

127. Wojcicki R. Theory of Logical Calculi. — Dordrecht: Kliiwer Press, — 1988. — 390 p.

128. Wolter F. The finite model property in tense logic// Journal of Symbolic Logic.1995. — V. 60. — № 2. — P. 757-774.

129. РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

130. Федоришин Б.Р. Описание жестких фреймов глубины 3 адекватных S4+Grz// Материалы XXXVII международной научной студенческой конференции "Студент и научно-технический прогресс", с. 144-145. 1999.

131. Федоришин Б.Р. Описание жестких фреймов глубины 3// Материалы XXXVIII международной научной студенческой конференции "Студент и научно-технический прогресс", с. 13-14. 2000.

132. Иванов В.С, Федоришин Б.Р. Финитная аппроксимируемость по допустимости правил вывода в суперинтуиционистских логиках// Материалы международной конференции "Логика и приложения", Новосибирск, с.53, 2000.

133. Иванов В.С, Федоришин Б.Р. Критерий отсутствия финитно аппроксимируемости суперинтуиционистских логик по допустимости// Абелевы группы и модули. — Томск. — 2000.— Вып. 15. — с. 24-29.

134. Rybakov V.V, Fedorisliin В. Faces of monotonicity and wisdom formulas problem// Bulletin of the Section of Logic — V.29 — No 4 — 2000 — P.181-192.

135. Федоришин Б.P. О строении жесткого фрейма// Материалы XXXIX международной научной студенческой конференции "Студент и научно-технический прогресс", с. 13-14. 2001.

136. Иванов В.С, Федоришин Б.Р. Критерий финитной аппроксимируемости суперинтуиционистских логик по допустимости// Материалы XXXIV научной студенческой конференции. — Красноярск. — 2001.— с. 70-77.

137. Федоришин Б.Р. Описание класса жестких Сг^-фреймов глубины 3. Красноярск, Краен, университет, 2001, 12 е., Деп. в ВИНИТИ 28.11.01 N 2429-2001.

138. Федоришин Б.Р. Достаточное условие наследования допустимых правил логики КА// Материалы II всесибирского конгресса посвященному Софьи Ковалевской — Красноярск. — 2002 — с. 149-153.

139. Федоришин Б.Р. О неполноте многообразия модальных ,94-алгебр относительно класса алгебр с условиями конечности// Материалы международной конференции "Алгебра и ее приложения". — Красноярск. — 2002 — с. 122.

140. Федоришин Б.Р. Явный базис для допустимых правил вывода логики Геделя-Леба GL. Красноярск, Краен, университет, 2002, Деп. в ВИНИТИ 28.10.02 N1850-B2002.

141. Руцкий А.Н., Федоришин Б.Р. Критерий наследования допустимых правил вывода модальной логики КА. Красноярск, Краен, университет, 2002, Деп. в ВИНИТИ 11.11.02 N1938-B2002.

142. Руцкий А.Н., Федоришин Б.Р. Критерий наследования допустимых правил вывода КА/1 Сиб. мат. журнал — 2002 — Т.43 — № 6 (в печати).

143. Ivanov V.S., Fedorishin B.R. Finite model property w.r.t admissibility for superintuitionistic, logics// Sib. Adv. in Math, (принята к печати).