Логика на рубеже тысячелетия

А.С.Карпенко

Abstract. Development of logic at the end of 20th century generated such questions as “What is logic?” or “What is logical system?”. The aim of this paper is to find out and analyze the phenomena that led to such unexpected questions. Firstly, that is a continual variety of logical systems; secondly, an extension of logical system as a result of its restriction; thirdly, an embedding (translation) of richer logical systems into weaker systems; fourthly, a tendency to the investigation of classes of logical systems in the fashion of certain constructions; fifthly, a completion of algebraization of logic; sixtly, the demands of computer revolution, etc. The result of logical concretization of two mathematical constructions – a closure operator introduced at the beginning of this century and a concept of category appeared at the middle of the century – was the beginning of investigations of different arrays of logical systems in a form of some lattice or category construction. Logic apparently loses the quality of science concerned with correctness of reasoning (and this is the phenomenon which expresses a crisis of modeling of truly human logic) and becomes the science about constructions that have an extremely abstract logical nature. In this sense logic is transformed just in metalogic with its new role. And the main point is that Logic comes out of limits of what is properly logical.

Content of the paper: 1) Introduction; 2) Closure operator and deductive systems; 3) Logical comprehension of continuum; 4) An extension of classical logic as a consequence of its restriction (translations and embeddings); 5) Lattices of theories and logics; 6) Lattices of calculi and other constructions; 7) Constructions called as “category” and “topos”; 8) Closure operator and category together; 9) Algebraization of logic; 10) In a search of logical system. Bibliogr.: 50-60 pp.

1. Введение

Работа над логическими статьями для “Новой философской энциклопедии”, а также над статьей “Логика в России. Вторая половина ХХ века” [Карпенко 1999], к удивлению автора, заставила его задуматься не столько об итогах развития логики, сколько о некоторых необычных феноменах и фактах, которые к концу двух с половиной тысячелетнего периода развития логики со всей остротой поставили вопрос о том, что такое логика или, более конкретно, что такое логическая система?

Конечно, два традиционных направления развития логики остаются пока непоколебимыми. Это, с одной стороны, синтаксическое направление, проявившееся в наибольшей степени в фундаментальной работе Д.Габбая [Gabbay 1996] и получившее название “labelled” дедуктивные системы, а также непрекращающиеся попытки максимально обобщить генценовские исчисления (см. [Wansing 1998]). И в первом и во втором случае ставится цель единообразного охвата наибольшего числа различных логических систем и даже различных направлений в логике. С другой стороны, остается неизменной тенденция в выработке единого семантического основания для возможно большего разнообразия логических систем [Epstein 1990, Epstein 1994]. При обоих подходах логическая техника становится всё более утонченной и формально разработанной и не оставляет места философским спекуляциям. На IX Международном конгрессе по логике, методологии и философии науки (Упсала, Швеция, 1991) Г. фон Вригт констатировал: “С логикой случилось то, что она расплавилась в разнообразных исследованиях математики…” [Вригт 1992, с. 89].

На самом деле - это титанические усилия строгой науки представить в совершенно точных терминах понятие “логической системы” и удовлетворить требования компьютерных наук в вопросе о том, что такое дедуцирование? То, что с применением аппарата универсальной алгебры, с развитием теории категорий и с возрастающими потребностями в вычислениях и обработке информации представления о логических системах и о самой логике принимают всё более абстрактный характер, как раз говорит о непостижимой глубине данной науки, а может быть даже о некоторой тайне, скрываемой в недрах логического универсума. И эта тайна периодически нежданно-негаданно проявляется в побочных эффектах, указывающих на нечто принципиально новое и требующих переосмысления статуса самой логики. На два таких примера неожиданного появления нового понятия логической системы (дедуктивная система в смысле Тарского и дедуктивная система как категория) мы обратим специальное внимание в нашей статье.

Эти примеры имеют немаловажное методологическое значение, поскольку указывают на то, что Логика имеет непосредственное отношение к базисным, фундаментальным конструкциям, которые зарождаются в недрах математического знания, создавая этим новый концептуальный аппарат. Такими конструкциями являются теория множеств, оператор замыкания с определенными свойствами, топологические пространства, решетка как определенным образом упорядоченное множество, моноиды, семейство базисных комбинаторов, алгебра Линденбаума, понятие категории, и т. д. Сразу отметим, что первая и последняя из указанных конструкций стали парадигмами нового мышления, а некоторые их конкретизации дали необычайной силы импульс развитию самой логики.

Но открытым остается главный вопрос: представляет ли собой логика как таковая некоторую единую конструкцию или это даже невозможно для систем искусственного интеллекта? Один из основных итогов современного развития логики как раз заключается в постановке этого вопроса, на который мы попытаемя ответить, используя большой фактический материал.

2. Оператор замыкания и дедуктивные системы

В 1909 г. Ф. Рисс, как указывает К. Куратовский [1966], а затем и он сам в 1922 г. вводят оператор замыкания на множестве. Оператором замыкания на множестве A называется отображение C множества всех подмножеств (s )A (множество всех подмножеств A иногда обозначают как 2A) в себя, обладающее следующими свойствами [Кон 1968, с. 56]:

(1) Если X Н Y, то C(X) Н C(Y) (монотонность)

(2) X Н C(X) (рефлексивность)

(3) CC(X) = C(X) (идемпотентность)

для всех X, Y О (s )A.

Подмножество X из A называется замкнутым подмножеством, если C(X) = X.

Важную роль в математике играют операторы замыкания на множестве всех подмножеств (s )A, обладающие следующим дополнительным свойством: замыкание объединения двух подмножеств множества (s )A равно объединению замыканий этих подмножеств. Такой оператор замыкания называется топологией в множестве (s )A.

Отсюда понятно значение оператора замыкания в топологии, и не в меньшей мере его роль в универсальной алгебре (см. кроме указанной книги П. Кона монографию [Stanley & Sankappanavar, 1981].

Оператор замыкания C на множестве A является финитарным, если для каждого X Н A

(4) C(X) = И {C(Y): Y Н X и Y является финитным}.

Заметим, что (4) влечет (3).

Одна из самых неожиданных конкретизаций конструкции под названием “оператор замыкания” была дана А. Тарским [Tarski 1930] в виде операции присоединения следствий (consequence operation). Эта конкретизация носит чисто логический характер.

Теория есть произвольное множество предложений некоторого установленного языка o . Множество всех формул, построенных из пропозициональных переменных и логических связок языка o , обозначим посредством Fm. Если X замкнуто относительно операции присоединения следствий (оператора замыкания), т.е. X = C(X), тогда X называется теорией C. C(X) есть наименьшая теория C, содержащая X, и С(Ж ) есть система всех логически доказуемых или общезначимых предложений C. В терминологии Тарского C(X) называется дедуктивной системой.

Оператор присоединения следствий C называется структурным, если для всех подстановок e (эндоморфизмов) языка o выполняется условие

(5) e(C(X)) Н Ce(X).

Открытие того, что подстановки являются эндоморфизмами, и введение условия (5) появилось в работе [Łoś & Suszko 1958].

Операция присоединения следствий C, выполняющая условия (1) - (5), называется стандартной [Wόjcicki 1984, p. 20].

Под логикой (пропозициональной) понимается пара или сама С, где операция присоединения следствий С не обязательно финитарная, но структурная [Wόjcicki 1984, p. 18]. Изучению логических свойств операции присоединения следствий посвящена фундаментальная монография Р. Вуйцицкого [Wόjcicki 1988]; логико-алгебраические свойства операции С исследуются Я. Челаковским [Czelakowski 1992].

Связь между операцией С и обычным отношением следования „ очевидна: A1, A2, ..., An „ B тогда и только тогда, когда В О С({A1, A2, ..., An}). Тогда, эквивалентно, дедуктивная система L (в языке o ) есть пара L = , где „ есть отношение следования между множествами формул и отдельными формулами, выполняющее следующие три условия для всех Г, ¦ Н Fm и A, B О Fm:


A О Г Ю Г „ A,


Г „ A и Г Н ¦ Ю ¦ „ A,

(3) Г „ A и ¦ „ B для каждого B О Г Ю ¦ „ A,

Дополнительно, „ является финитарным, если

(4) Г „ A Ю Г' „ A для некоторого конечного Г' Н Г,

и называется структурным, если

(5) Г „ A Ю e(Г) „ eA

для каждой подстановки e.

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

3. Логическое осмысление континуума

Самое удивительное, что одновременно с оформлением классической логики [Frege 1879], с построением на её основе грандиозного здания “Principia Mathematica” [Whitehead & Russel 1910-1913] и с появлением первых метатеорем для двузначной пропозициональной логики (непротиворечивость, дедуктивная полнота, функциональная полнота) [Post 1921], - наряду со всем этим проявляется тенденция к критике самих оснований классической логики. Это критика закона исключенного третьего p Ъ Ш p Л. Брауэром [Brouwer 1908] и критика закона непротиворечия Ш (p Щ Ш p), начатая в 1910 г. Я. Лукасевичем (см. [Łukasiewicz 1971]) и Н. А. Васильевым (см. [Васильев 1989]). В 1912 г. К. И. Льюис строит новую теорию логического следования взамен теории материальной (классической) импликации, изложенной в Principia Mathematica. Исходным мотивом Льюиса было избавиться от так называемых парадоксов материальной импликации: p Й (q Й p), p Й (Ш p Й q) и др. В результате вводится новая импликация, названная им “строгой” [Lewis 1912]. Особо обратим внимание на серьезную критику Лукасевичем в начале 20-х годов принципа двузначности (бивалентности) в знаменитой статье “О детерминизме” (см. [Лукасевич 1993]). В итоге, соответственно, появляются интуиционистская логика Гейтинга [Heyting 1930], паранепротиворечивые логики (подробно об этом в фундаментальном труде [Priest, Routley, Norman (eds.), 1989], модальные логики Льюиса [Lewis & Langford 1932], трехзначная логика Лукасевича Ł3 [Łukasiewicz 1920] č её конечнозначные обобщения [Łukasiewicz 1922/23]. Заметим, что в знаменитой Ł3 (как и во всех её обобщениях) не имеют места закон исключенного третьего, закон непротиворечия и закон сокращения (p ® (p ® q)) ® (p ® q) (первая в мире логика без сокращения).

То, что эпоха бурного развития классической логики вплоть до великих ограничительных теорем К. Гёделя начала 30-х годов (см. [Gцdel 1986]) совпала с появлением и развитием различных неклассических направлений в логике, факт сам по себе примечательный. Но долгое время ему не придавали особого значения, поскольку классическая первопорядковая логика считалась и в основном считается и сейчас образцом математических рассуждений, а всё остальное от лукавого (и даже интуиционистская и конструктивная логики, представители которой бросили наиболее серьезный вызов классикам), пока У. Куайн [Quine 1970] не ввел термин “девиантная” (deviant) логика, т.е. логика альтернативная к классической, ставший названием для монографий С. Хаак [Haack 1974, 1996].

Имеются весьма веские основания для предпочтения классической двузначной логики высказываний C2 (о логике предикатов мы скажем позже) всем остальным. В первую очередь - это исключительно простая интерпретация её логических связок посредством двузначных таблиц истинности. Сейчас это кажется и правда до смешного простым, но сто лет назад это не было даже очевидным для Фреге, Рассела и Уайтхеда. Но еще более поразительной (и редкой удачей в науке) оказалась возможность интерпретации функций алгебры логики C2 посредством контактно-релейных схем, предложенная независимо друг от друга В. И. Шестаковым в 1935 г. (опубликовано в [Шестаков 1941]), К. Шенноном [Shannon 1938] и в этом же году в целой серии работ А. Накасимой.

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

Во-первых, это множественность логик. Сначала появление различных классов конечнозначных логик ([Post 1921] и [Łukasiewicz 1922/23]) и пяти льюисовских модальных систем S1 - S5 [Lewis & Langford 1932] не навело на особые размышления. Но тогда же К.Гёдель [Gцdel 1932] заметил, что существует счётное число логик между интуиционистской логикой H и классической C2, которые впоследствии получили название суперинтуиционистских логик (si-логики). А это уже было событием в логическом мире. Исходя из этого факта Т. Умезава в 1955 г. (см. [Umezava 1959]) начинает изучение целых классов логик. Параллельно С. Скрогс [Scroggs 1951] описывает нормальные расширения модальной логики Льюиса S5, а М. Дамметт и Е. Леммон [Dummett & Lemmon 1959] рассмотрели логики между S4 и S5 и перевод si-логик в них.

Появляются всё новые логики, каждая из которых представляет особый интерес, например, цепная логика Дамметта LC [Dummett 1959] или модальная логика Гжегорчика Grz [Grzegorczyk 1967]. В середине 60-х годов в результате критики “парадоксов” строгой импликации Льюиса p ® (q ® q), (p Щ Ш p) ® q (т. е. истина следует из чего угодно и из лжи следует всё, что угодно) оформляется релевантное направление в логике во главе с системой R; добавление к R “безобидной” аксиомы p Й (p Й p) приводит к логике RM с весьма необычными свойствами (о релевантных логиках см. монографию [Anderson & Belnap 1975]. Можно подумать, что идёт “игра в бисер” - конструирование всё более экзотических логик, но с хорошими металогическими свойствами. В то же время, поскольку считается, что существует счетное число логик, то их все можно будет описать и изучить.

Постепенно сложилось понимание логики в гильбертовском духе. Под логикой (пропозициональной) в языке o понимается произвольное множество L Н Fm, которое замкнуто относительно правил вывода MP и Subst. Если L конечное множество, то L называется исчислением. Анализируя объекты (логики) той же самой природы, например из класса si-логик, мы надеемся изучить и понять саму природу данного феномена и подняться на новый уровень знания. Поэтому открываются различные способы конструирования новых логик из данного класса с заданными свойствами. Так, Т.Хосои [Hosoi 1967] вводит понятие “слоя” (slice) для классификации si-логик. В течение долгого времени оставалась надежда найти полное описание решетки (см. ниже раздел 5) модальных и si-логик - тогда можно было бы “обозреть” любую логику и даже, может быть, представить их в виде исчисления.

Все эти надежды были разрушены открытием В.А.Янковым [Янков 1968] континуального класса si-логик (напомним, суперинтуиционистских логик, по-другому, промежуточных) и обнаружением способов конструирования модальных и si-логик с весьма “нежелательными” свойствами (неразрешимость, неаксиоматизируемость и т. д.). Более того, А.В.Кузнецов доказывает теорему о континуальности всякого интервала между H и её собственным расширением [Кузнецов 1971]. Имея в виду исходный гёделевский перевод H в S4 [Gцdel 1933b], можно распространить его и на весь класс si-логик. В результате был установлен изоморфизм всех si-логик в нормальные расширения S4, которых, следовательно, тоже континуум [Максимова и Рыбаков 1974]. Более того, имеет место континуальность для всякого интервала между модальной логикой K4 и её собственным расширением. Впоследствии были обнаружены континуальные классы релевантных логик, например, В. Дзёбяк [Dziobiak 1983] показал это для промежутка между R и RM. Оказалось, что даже одних импликативных si-логик тоже континуум (см. [Chagrov & Zakharyaschev 1997, p. 382]). Существует континуум предикатных si-логик с равенством, имеющих интерполяционное свойство [Максимова 1997] и т. д. Наверное, не одному человеку приходила в голову мысль, что если логик даже одного класса континуум, а людей (разумных существ) всего конечное число и пусть каждый рассуждает по-своему, то что же тогда представляет собой Логика как таковая?

С другой стороны, логическая континуальность проявилась уж совершенно неожиданно. В начале 50-х годов для изучения функциональных свойств многозначных логик А.В.Кузнецовым был введен следующий терминологический аппарат, основанный на свойствах оператора замыкания (см. предыдущий раздел). Пусть Pn обозначает множество всех n-значных функций; Pn есть множество всех функций, соответствующее n-значным логикам Поста (n і 2, n О N) [Post 1921], и пусть В Н Pn. Определим на множествах функций, содержащихся в Pn, операцию замыкания [ ] такую, что [В ] означает множество всех суперпозиций функций из В . Тогда множество всех функций, которые могут быть получены из функций системы В с помощью операции суперпозиции, называется замыканием В . Очевидно, что операция [ ] обладает следующими свойствами:

(i) Если Б Н В , то [Б ] Н [В ]

(ii) В Н [В ]

(iii) [[В ]] = [В ].

Множество функций В называется замкнутым, если [В ] = В .

Таким образом, условия (i) - (iii) есть не что иное, как ещё один пример конкретизации оператора замыкания C.

Заметим, что множество функций В называется функционально полным, если [В ] = Pn. Оказалось, что n-значная (n > 2) функционально полная логика образует континуум замкнутых классов функций [Янов & Мучник 1959], в то время как в C2 таких классов счетное множество. Таким образом, посредством добавления только одного нового истинностного значения к классической логике C2 совершается переход от дискретности к непрерывности (!), и это является еще одним феноменом логического универсума. Вообще-то говоря, точная природа такого различия между двузначной и трехзначной логиками неясна.

Обратим внимание, что, как и в случае с конкретизацией Тарского, имеем ещё одно понимание логической системы, правда, совсем отличное от . Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы [Кудрявцев 1981], обозначаемой (Рn, C), где Рn есть множество всех функций n-значной логики (или множество всех функций счетнозначной логики Рw ) с заданной на нем операцией суперпозиции С. Тогда функциональная система (Рn, C) зачастую отождествляется с самой многозначной логикой и предстает в виде алгебры функций.

Стоит отметить, что уровень конкретизации Кузнецова на порядок выше предыдущего, что ничуть не умаляет значимости введения оператора присоединения следствий Тарским, с чем нам еще придется не раз столкнуться, и непосредственно в следующем разделе.

В итоге, критика “основных” законов и принципов классической логики привела к феномену логической континуальности, выраженному как в континуальности самих классов логических систем, так и в наличии континуальности замкнутых классов логических функций. Отсюда возникает вопрос, является ли логическое мышление человека дискретным или континуальным? Ответ на этот вопрос также зависит от того, что мы понимаем под логикой или логической системой. И в рамках одной ли логической системы мыслит человек?

4. Расширение классической логики
как следствие её ограничения (переводы и погружения)

Если изучение функциональных свойств (замкнутые классы, полнота, предполнота, базисы и т.д.) является прерогативой специалистов в области дискретной математики, инженеров, программистов, физиков, то изучение логики как объекта в виде исчисления относится к сфере “чистой” логики. Именно здесь самым удивительным образом проявился феномен, обозначенный в заглавии этого раздела.

Указанная в предыдущем разделе критика законов и основ классической логики носила бескомпромиссный характер в своей тенденции ограничить сферу последней, но никто из перечисленных авторов не мог даже предположить, что на самом деле неявным образом происходит процесс расширения средств и аппарата классической логики C2. Из результата В. Гливенко [Glivenko 1929] о погружении C2 в H следует, что интуиционистская логика даже “богаче” C2. Более того, Гёдель показал [Gцdel 1933a], что классические законы, включающие только отрицание, конъюнкцию и квантор всеобщности, являются интуиционистскими законами. Поскольку импликация, дизъюнкция и квантор существования определяются через указанные “интуиционистские” логические связки, то можно строго утверждать, что классическая логика предикатов есть подсистема интуиционистской, а значит, вторая есть расширение первой. Гёделем был также предложен метод аксиоматизации льюисовских модальных систем как расширение C2 [Gцdel 1933b]. Оказалось, что n-значные логики (в том числе и предикатные) аксиоматизируются подобным образом [Аншаков & Рычков 1982, 1984.], [Anshakov & Rychkov 1994]. Одним из самых первых примеров в этой области является аксиоматизация в 1971 г. трехзначной логики бессмысленности Д. А. Бочвара B3 (см. [Финн 1974]), которая, заметим, по своим функциональным свойствам слабее Ł3, в то время как Ł3 не является функционально полной. Уже в 1938 г. Д. А. Бочвар при построении B3 выделяет её трехзначный фрагмент, изоморфный C2, т. е. этот фрагмент верифицирует всю классическую пропозициональную логику [Бочвар 1938]. Уже отсюда следует, что B3 можно строить на основе C2. Отметим также, что и релевантная логика R может быть построена на основе C2 [Meyer 1974] (отрицание де Моргана заменяется на булево отрицание).

Феномен этот, конечно, несколько неожидан и требует своего философского, логического и алгебраического (на самом деле категорного) осмысления. Как и в предыдущем случае, мы имеем дело с расширением логического универсума. Расширение классической логики за счет введения не-булевых операций в первую очередь означает нарушение истинностно-функционального характера последней. Необычайный прогресс в хранении и, главное, в обработке информации на основе булевой (классической) логики имеет не только свои естественные физические пределы. Homo-логический универсум не явлется счётным, а процессы, в нем происходящие, не являются истинностно-функциональными. Всё, что можно извлечь из предельного огрубления человеческой логики, впервые представленного работами Шеннона, Шестакова и Накасимы (а это было не что иное, как одна из конкретизаций булевого универсума), как раз извлекает происходящая сейчас компьютерная революция. Но в конечном итоге эта конкретизация тупиковая для создания искусственного интеллекта хоть мало-мальски соответствующего человеческому. Обозначилась явная тенденция к разработке новой логики, которая по своим выразительным средствам намного богаче классической. Этим объясняется пристальное внимание специалистов к многозначным (бесконечнозначным) и нечеткозначным логикам (которые континуальны) в работах по искусственному интеллекту (см. в трудах International Symposium on Multiple-Valued Logic) и в других работах. То, что вначале это выразилось различными внешними ограничениями C2, было только сигналом (непонятым) того, что потребуется более глубокая ревизия логики и, главное, её характера и статуса. Но для этого, как сейчас выяснилось, нужно все-таки определиться в понимании того, что такое логическая система? В последующих разделах мы рассмотрим этот вопрос.

Погружение или перевод (embedding или translation) одной логической системы в другую (первым примером которого является теорема Гливенко) к концу нашего века становится темой тщательного исследования. Самое общее понятие перевода состоит в следующем: cистема S переводима в S', если существует функция (возможно, но не необходимо отображение) между двумя универсумами рассуждений, которая сохраняет (по крайней мере, в одну сторону) отношение дедуцируемости. Первая работа, в которой дано общее определение перевода, принадлежит Д.Правицу и П. Мамносу [Prawitz & Malmnдs 1968]. Отдельные главы, посвященные этой проблеме, появляются в книгах В.А.Смирнова [Смирнов 1987], Р.Вуйцицкого [Wуjcicki 1988] и Р.Эпштейна [Epstein 1990]. О том, что мы имеем дело с важнейшей тенденцией в развитии современной логики, свидетельствует манифест: “Переводы между логическими системами” [Carnielli & D'Ottaviano 1997].

Здесь под логической системой понимается уже хорошо известная нам дедуктивная система в смысле Тарского (берутся первые три пункта определения; см. выше раздел 1). В общем случае под логикой d понимается пара , где А есть множество, назывемое областью (domain) или универсумом A, и CA есть оператор (замыкания) присоединения следствий. Тогда переводы между логическими системами характеризуются как отображения, которые сохраняют операцию присоединения следствий, т. е. как непрерывные функции между множествами:

Переводом (из) логики d = в логику e = является отображение f: A ® B такое, что для любого X Н A

f (СA(X)) Н А(СB(X)).

f называется также непрерывным отображением.

Если f есть перевод, то очевидно, что для любой формулы пропозиционального языка a О СA(X) следует, что f(a ) О СB(f(X)), но обратное не имеет места. В частности, если „ A и „ B являются синтаксическим отношением следования в логиках d и e , соответственно, то f является переводом тогда и только тогда, когда

X „ A j Ю f(X) „ B f(j ).

Конечно, могут рассматриваться различные ограничения, как на само понятие логики, так и на отображение f. Обычно в литературе при определении перевода между логиками требуется также, чтобы имело место и обратное, т.е.

X „ A j Ы f(X) „ B f(j ).

В этом случае перевод называется консервативным переводом [Carnielli & D'Ottaviano 1997, p.72].

Исследование переводов логических систем обеспечивает: новые семантики для неклассических логик, сводит метаматематические и металогические свойства одной системы к другой, чтобы получить нужные результаты, позволяет точно выявить смысл дуальности между логиками (в первую очередь это относится к интуиционистской логике), проясняет и выявляет взаимоотношения между совершенно различными логическими системами.

5. Решетки теорий и логик

Имеется два стандартных (эквивалентных) определения понятия решетки. В первом случае выделяется специальный класс частично-упорядоченного множества , и преимущество здесь чисто геометрическое (см. ниже); во втором случае решетка < L; Ј > характеризуется как алгебра < L; Ъ , Щ >, т. е. как множество с заданными на нем операциями. В этом случае частичный порядок Ј вводится так: x Ј y означает х Щ у = х.

Непустое множество L с двумя бинарными операциями Ъ (дизъюнкция) и Щ (конъюнкция) на L называется решеткой, если L удовлетворяет следующим тождествам [Гретцер 1982]:

I. (a) xЪ x = x

(b) xЩ x = x (идемпотентность)

II. (a) xЪ y = yЪ x

(b) xЩ y = yЩ x (коммутативность)

III. (a) xЪ (yЪ z) = (xЪ y)Ъ z

(b) xЩ (yЩ z) = (xЩ y)Щ z (ассоциативность)

IV. (a) xЪ (xЩ y) = x

(b) xЩ (xЪ y) = x (поглощение).

Решетка L называется дистрибутивной, если выполняются законы дистрибутивности:

V. (a) xЪ (yЩ z) = (xЪ y)Щ (xЪ z)

(b) xЩ (yЪ z) = (xЩ y)Ъ (xЩ z).

Решетка L c двумя нульарными операциями 0 и 1 называется ограниченной, если:

VI. (a) x Ъ 0 = x

(b) x Щ 1 = x

VII. (a) x Ъ 1 = 1

(b) x Щ 0 = 0.

Ограниченные решетки обычно называются алгебрами.

В ограниченной решетке L элемент у называется дополнением х, если х Щ у = 0 и х Ъ у = 1. В этом случае элемент у обозначают ~ х. Булевой алгеброй называется дистрибутивная решетка с дополнениями. Имеется большое число различных (эквивалентных) систем тождеств, определяющих класс булевых алгебр.

Например, алгебра называется булевой алгеброй, если есть ограниченная дистрибутивная решетка и выполняются следующие два тождества:

(В1). x Ъ ~ x = 1

(В2). x Щ ~ x = 0.

Особое место в исследовании различных логик занимают алгебры (решетки) Гейтинга . Пусть х, у О L. Элемент z О L называется псевдодополнением элемента х относительно у, если z - наибольший элемент со свойством х З z Ј y. Тогда есть алгебра Гейтинга, если < L, Ъ , Щ , 0, 1 > есть ограниченная дистрибутивная решетка и для бинарной операции Ю выполняются следующие три тождества [Эсакиа 1985, с. 23]:

(Н1). xЩ (xЮ y) = xЩ y

(Н2). xЩ (yЮ z) = xЩ (xЩ y Ю xЩ z).

(Н3). (xЩ yЮ x) Щ z = z.

Сразу отметим, что рассмотрение различных множеств логических систем в виде определенной структуры (решеточной, псевдобулевой, булевой и т. д.) будет занимать все более значительное место в логических исследованиях и явится одним из главных феноменов развития логики во второй половине ХХ века.

Пусть S есть множество всех предложений языка o и пусть Th(C) есть семейство теорий C (см. раздел 2). Уже Тарский заметил [Tarski 1930а], что Th(C) относительно теоретико-множественного включения образует брауэрову алгебру, т.е. алгебру дуальную к алгебре Гейтинга, с S в качестве её наибольшего элемента и с C(Ж ) в качестве её наименьшего элемента.

Итак, впервые было установлено, что само множество логических систем (в данном случае, дедуктивных систем в смысле Тарского) образует некоторую конструкцию.

В свою очередь, класс конечно-аксиоматизируемых теорий образует булеву решетку [Смирнов 1987, с. 34].

Интересное развитие результатов Тарского в этой области принадлежит В. Дзику [Dzik 1982], который, в частности, показал, что содержание решетки всех теорий классической пропозициональной логики равно множеству интуиционистских теорем.

Обратим внимание на тот факт, что свойства оператора замыкания C индуцируют решетку замкнутых множеств с соответствующими свойствами, которую будем обозначать посредством Lc. Тогда, если оператор замыкания финитарный, т.е. выполняются условия (1) - (С), то получаем алгебраическую решетку замкнутых множеств. Понятие алгебраической решетки используется ниже в этом разделе.

В последнее время особое внимание привлекает проблема интерпретируемости теорий в смысле Дж. Мак-Кинси и А. Тарского [McKinsey & McKinsey 1948], доказавших, что система интуиционистских теорем интерпретируема в модальной системе Льюиса S4. Понятие интерпретируемости часто используется в современной логике. Классическими применениями являются доказательство относительной непротиворичевости, результаты разрешимости и неразрешимости теорий. Вопрос об интерпретируемости теорий рассмотрен в обстоятельной работе [Mycielski, Pudlбk, Stern 1990]. Под теорией (математической) здесь понимается то, что может быть формализовано средствами первопорядковой логики. При этом желательно было бы выделить классы теорий, которые совместно интерпретируемы одна в другой, поскольку понятно, что теории зависят от выбора языка и исходных понятий. Последнее приводит к конструкции весьма абстрактных объектов, а именно классов эквивалентности первопорядковых теорий. Имеются различные отношения эквивалентности на множестве теорий (см., например, понятие дефинициальной эквивалентности [Смирнов 1987, с. 56]). Мыцельский и др. изучают одно из наиболее абстрактных отношений эквивалентности, названное локальной интерпретируемостью, а сами классы эквивалентности названы главами (chapters) математики.

Чтобы избежать тривиальных исключений, рассматриваются только непротиворечивые теории T, с моделями, имеющими более одного элемента. T1 является локально интерпретируемой в теории T2 если для каждой теоремы d О T1 существует интерпретация I такая, что d I О T2. Интерпретация может иметь параметры, переменные могут переводиться как n-ки переменных (в этом случае говорят о n-мерной интерпретации). Будем говорить, что теории T1 и T2 имеют одну и ту же главу (т.е. попадают в один и тот же класс эквивалентности), если T1 является локально интерпретируемой в теории T2, и наоборот.

Собрание всех глав не является собственным классом и имеет мощность континуума . Локальная интерпретируемость индуцирует частичный порядок на множестве глав. Этот порядок таков, что образует дистрибутивную алгебраическую решетку, названную авторами LC (the lattice of chapters).

Обратим внимание, что на самом деле локальную интерпретируемость эквивалентным образом можно задать в терминах алгебраического оператора замыкания [Mycielski, Pudlбk, Stern 1990, p. 11-12].

Большой интерес представляет изучение алгебраических свойств решетки LC, в особенности, если иметь в виду инвариантность глав теории T относительно языка, в котором T выражена. Отметим некоторые свойства: конечно-аксиоматизируемые теории соответствуют компактным элементам в LC; множество компактных глав и множество глав, содержащих рекурсивно перечислимые теории, являются подрешетками LC; эквациональные главы образуют алгебраическую решетку мощности , но она недистрибутивна и даже немодулярна, и т. д.

Кроме теорий, понимаемых как множества предложений, т.е. формул без вхождений свободных переменных, и замкнутых относительно тех или иных операций, особый интерес представляет изучение классов логик, замкнутых относительно соответствующих правил вывода, в первую очередь modus ponens (MP) и подстановки (Subst), и каждый из которых является непротиворечивым расширением какой-либо исходной (базисной) логики. При этом желательно представить такие классы логик в виде хорошо известной конструкции.

Первым подобным примером явилось изучение множества всех суперинтуиционистских логик (si-логик), мощность которого (см. выше раздел 3). Был получен следующий результат: множество всех si-логик, упорядоченное отношением включения, образует алгебру Гейтинга [Hosoi 1969]. Поскольку континуум описать нельзя, то представляет интерес изучение различных подклассов si-логик (см. [Кузнецов 1975], [Rautenberg 1979], [Gabbay 1981], [Chagrov & Zakharyaschev 1997]). Одной из наиболее популярных тем является исследование классов семантик, для которых различные si-логики полны.

Изучение решетки одного класса логик может оказаться полезным для другого класса логик. В связи с этим обратим внимание на поразительный результат, полученный одновременно и независимо друг от друга в 1976 г. В. Блоком [Blok 1976] и Л. Эсакиа (см. [Эсакиа 1979]), установившими изоморфизм между решеткой всех si-логик и всех нормальных расширений логики Гжегорчика Grz. Решетки модальных логик изучались также в [Максимова & Рыбаков 1974], [Blok 1980] и т.д.

Еще А. Роуз [Rose 1953] показал, что мощность множества всех собственных расширений бесконечнозначной логики Лукасевича Łw , т.е. мощность множества всех логик между Łw и C2, является счетной. Элементы этого множества будем называть sł-логиками. Р. Григолия [Григолия 1976] установил, что множество всех sł-логик образует алгебру Гейтинга. См. также [Komori 1981] и [Beavers 1993].

Конечно, возникает вопрос, почему решетка теорий является брауэровой? Природа этого феномена скорее всего заключается в природе операции присоединения следствий (замыкания), используемой Тарским при определении логики. Эта операция является топологическим замыканием, а логики - замкнутые множества, в том числе si-логики и sł-логики. Остается вспомнить связь топобулевых алгебр, псевдобулевых алгебр (алгебр Гейтинга) и брауэровых алгебр: так, всякая псевдобулева (брауэрова) алгебра является алгеброй открытых (замкнутых) элементов подходящей топобулевой алгебры; во всякой топобулевой алгебре совокупность открытых (замкнутых) элементов образует псевдобулеву (брауэрову) алгебру.

6. Решетки исчислений и другие конструкции

Выше рассматривались решетки однотипных логик, например класс логик без закона исключенного третьего (si-логики), или класс логик без закона сокращения (sł-логики), или определенный класс нормальных модальных логик. А нельзя ли построить такую конструкцию, в которой по крайней мере основные логические системы являются “равноправными” элементами? С другой стороны, если исходить из каких-то естественных предпосылок при построении искомой конструкции, то она и должна определить эти основные логические системы.

Пусть мир наполнен объектами, которые обозначим терминами x, y, z, ... Всё, что можно с ними делать, это переставлять местами, брать в скобки, сокращать и/или воспроизводить термины, т.е. выполнять следующие операции:

I x = x. W xy = xyy,

B xyz = x(yz), K xy = x,

C xyz = xzy, S xyz = xz(yz)

для произвольных терминов x, y, z. Наши обозначения для операций есть не что иное, как базисные комбинаторы I, B, C, W, K и S, впервые введенные М. Шёнфинкелем [Schц nfinkel 1924], а затем Х. Карри (см. [Curry & Feys 1958]). Из исходных комбинаторов получают другие комбинаторы, например Bґ xyz = x(zy) (=CB). Следующие исходные множества комбинаторов {B, C, W, K}, {Bґ , W, K}, и {S, K} являются эквивалентными и для последнего (а значит и для остальных) доказана теорема о комбинаторной полноте, т.е. все другие возможные комбинаторы можно построить из исходных [там же, p.189; см. также: Энгелер 1987, с. 96-97]. Обратим внимание, что множество базисных комбинаторов с операцией аппликации образует структуру моноида. Открытие принадлежит Х. Карри, а первая работа А. Чёрчу [Church 1937; см. также: Bцhm & Dezani-Ciancaglini 1989]. Такие моноиды еще называют C-моноидами.

Оказалось, что между комбинаторами и импликативными формулами существует однозначное соответствие [там же, ch.9E]. Главным результатом этого соответствия является следующий важный факт: полное множество исходных комбинаторов определяет собой импликативный фрагмент H® интуиционистской пропозициональной логики H [там же, p.315].

В силу указанного соответствия (оно еще называется изоморфизмом Карри-Ховарда) теперь в качестве элементарных (логических) объектов, из которых будет строиться логическая конструкция, возьмем следующие импликативные формулы:

I. (p ® p) (тождественность)

B. (q ® r) ® ((p ® q) ® (p ® r)) (слабая

транзитивность)

C. (p ® (q ® r)) ® (q ® (p ® r)) (перестановка)

W. (р® (p ® q)) ® (p ® q) (сокращение)

K. p ® (q ® p) (ослабление).

А в качестве операций над нашими объектами будут следующие два логические правила вывода: modus ponens (MP) и подстановка (Subst).

Основным требованием к нашим элементарным объектам, т.е. к импликативным формулам, будет требование их независимости друг от друга [Чёрч 1960, § 19]. Легко показать, что формула I не является независимой в приведенном выше исходном множестве объектов, поскольку она доказуема из C, K или W, K. Поэтому ослабим формулу K посредством K1:

K1. (p ® q) ® ((r ® (p ® q).

Утверждение 1. Множество формул I, B, C, W, K1 является независимой аксиоматизацией H® [Карпенко 1997а, с. 112].

Теперь, в силу доказательства независимости элементов множества {I, B, C, W, K1}, мы можем перейти к построению того, что будем называть логической конструкцией. Рассмотрим семейство всех подмножеств этого множества. Как известно, семейство всех подмножеств некоторого множества образует булеву решетку, упорядоченную отношением включения. В нашем случае булева решетка имеет 32 (=25) элементов с H® в качестве единицы. Остальные вершины решетки представляют собой подлогики H® . Построенную конструкцию обозначим посредством L(H® ).

Пусть TV® обозначает импликативный фрагмент классической пропозициональной логики C2. Тогда возникает следующая нетривиальная проблема, впервые поставленная автором этой статьи в 1992 г.: существует ли независимая аксиоматизация TV® формулами I, B, C, W, K1 и Х? Поскольку для формулы Х в силу изоморфизма Карри–Ховарда не существует соответствующего комбинатора, то мы с необходимостью должны выйти за пределы “интуиционистского универсума” объектов, обозначенных терминами x, y, z, ... Как оказалось, существуют различные кандидаты на место мета-формулы Х (в отличие от объектных формулах I, B, C, W, K1), например,

Х4. (p® p)® ((((p® q)® q)® p)® r)® (((((q® p)® p)® q)® r)® r).

Утверждение 2. Множество формул I, B, C, W, K1, X4 является независимой аксиоматизацией TV® [Карпенко 1997а, с. 120].

В результате получаем конструкцию L(TV® ):


TV®









H®
RM®
Łw ®








R®
BCK
BCIX4









BCI



Две импликативные логики из этой конструкции заслуживают особого разъяснения. RM® есть импликативный фрагмент логики RM, которая получается за счёт добавления к релевантной логике R формулы p ® (p ® p) (см. [Anderson & Belnap 1975]). Łw ® есть импликативный фрагмент бесконечнозначной логики Лукасевича Łw [Łukasiewicz 1929]. Â нашей аксиоматизации Łw ® есть IBCK1X4 = BCKX3 [Karpenko & Popov 1997], где X3 есть X4 без антецедента (p ® p).

Обратим внимание, что конструкция L(TV® ) является максимальной в том смысле, что между RM® и TV® нет промежуточных логик [Avron 1984]. В силу этого можно считать что данная конструкция L(TV® ) содержит фундаментальные (базисные) импликативные логики.

Теперь рассмотрим конструкцию полной (full) классической пропозициональной логики L(TV).

Из работы М. Вайсберга [Wajsberg 1937, § 5] следует, что добавление формулы 0 ® р (где 0 является константой, интерпретируемой как ложь) к произвольной TV® дает TV. Обозначим формулу 0 ® р посредством N.

Утверждение 3. Множество формул I, B, C, W, K, X4, N является независимой аксиоматизацией TV.

Обратим внимание, что BCKX4N есть полная (full) Łw (см. [Turqette 1963]). Таким образом, в максимальной конструкции L(TV® ) только две импликативные логики с 0 имеют решеточную структуру, определяемую естественным путем. Это является следствием того, что в импликативных фрагментах данных логик имеет место полином

p Ъ q = (p ® q) ® q.

Из построения нашей конструкции следует, что две логики занимают особое положение: это классическая пропозициональная логика и бесконечнозначная логика Лукасевича Łw (о последней см. в [Карпенко 1997, гл.6]). Заметим, что изучение алгебраических свойств последней стало отдельным направлением в алгебраической логике (см. [Mundici 1986]; о самой логике Łw см. в [Карпенко 1997, гл.6]).

Наконец, выделим два основных принципа порождения новых пропозициональных логик и целых их классов:

1. В каждом случае нахождение нового Xi определяет различные подлогики из множества {I, B, C, W, K1, Xi, N};

2. Применение операции подстановки порождает целые классы (бесконечные) подлогик в TV® (и других) конструкциях.

В сущности мы имеем дело с классификацией логических исчислений посредством построения различных конструкций в виде конечных булевых решеток [Карпенко 1997a; Karpenko 2000].

Подводя итог, можно сказать, что рассмотренные конструкции в виде решеток пропозициональных логик хорошо показывают взаимоотношения между различными логиками, пути их расширения и то, какое место они занимают по отношению к классической двузначной логике TV. Но и сама конструкция L(TV) есть модель для TV, причем довольно-таки сложной природы, которая содержит в себе, например, специальным образом упорядоченные топологические пространства, соответствующие алгебрам для Łw [Martinez 1990]. Булева решетка различных подлогик подводит к мысли о том, что логическое пространство является весьма неоднородным. Вопрос о какой-то выделенной логике, свойственной человеческому разуму, вообще нельзя ставить. В каком-то смысле в одном из приближений конструкция L(TV) и есть логика.

Конечно, остается проблема построения такой конструкции L(TV), элементами которой являются полные (full) логики, как это получилось для Łw . Оказывается, “подобные” конструкции имеются, но не в виде конечной булевой решетки, а в виде обыкновенного куба с вершиной TV. Разница в том, что вопрос о независимости исчисления, являющегося одной из вершин куба, вообще не ставится. По-видимому, первая такая конструкция была представлена в [Ono 1990], где в качестве исходного исчисления берется так называемое полное исчисление Ламбека FL (грубо говоря, это интуиционистская логика без структурных правил). Кроме комбинирования FL со структурными правилами, соответствующих формулам C, W и K, к некоторым логикам добавляется еще закон снятия двойного отрицания Ш Ш p ® p. В чистом виде куб логических исчислений с вершиной TV представлен [Battilotti & Sambin 2000], где строится секвенциальное исчисление базисной (basic) логики B. Комбинирование последней осуществляется с тремя независимыми свойствами C, D и S, где C есть аксиомы (правила) для двойного отрицания, D состоит из обычных свойств импликации, удовлетворяющих теореме дедукции, и S есть структурные правила, соответствующие формулам W и K, плюс идентификация двух констант, выражающих ложь. Заметим, что логика B подобрана таким образом, что BD есть интуиционистская линейная логика (без экспоненциалов), а BCS является ортологикой.

Поскольку построение данного куба выглядит довольно-таки искусственно, то о едином “логическом пространстве” не может быть и речи. Это является следствием того, что независимость аксиом и независимость свойств - совершенно разные принципы для построения логических конструкций. Отметим, что в первом случае неожиданно проявились преимущества гильбертовских исчислений.

Имеются и другие конструкции логик в виде кубов. Весьма примечательным (учитывая связь l -абстракции, введенной А. Чёрчем, с комбинаторами) является l -куб, который состоит из 8 типовых систем лямбда исчислений. При этом каждое ребро куба представляет отношения включения [Howard 1980].

Таким образом, логика из науки о правильных рассуждениях постепенно превращается в науку о классах логических систем, а на самом деле в науку о логических конструкциях. О том, что это так, - в следующих разделах.

7. Конструкции под названием “категория” и “топос”

Более 50 лет назад усилиями С. Мак-Лэйна и С. Эйленберга была создана теория категорий, одна из наиболее важных математических теорий нашего века [Eilenberg & Maclane 1945]. Новая теория позволила обнаружить совсем неожиданные и удивительные взаимоотношения внутри различных разделов математики и, самое главное, под влиянием идей В. Ловера выступила мощным средством для разработки новых оснований математики (см. его последнюю работу с весьма примечательным названием “Концептуальная математика” [Lawvere & Schanuel 1997]).

Во всем этом наблюдается некоторая негативная реакция на теорию множеств (“основу всех основ”). Теперь в явном виде постулируется, что наши исходные элементы “структурализованы”, а сама конструкция теории множеств должна быть более гибкой.

Итак, “мир” наполнен не элементами, по некоторым свойствам которых образуются множества этих элементов, а категориями с образующими их свойствами, которые, конечно, могут быть различными.

Стандартное определение категории f [Lawvere & Schanuel 1997] включает в себя:

(1) Объекты A,B,C,…

(2) Отображения (морфизмы, стрелки и т.д.): f, g, h,…

(3) Чтобы указать, что f есть отображение, мы пишем (или f: A ® B) и говорим, что “f есть отображение из A в B”.

(4) Для каждого объекта A имеет место тождественное отображение, которое обозначаем тождеством 1A, так что есть одно из отображений из A в A.

(5) Для каждой пары отображений



композиция отображения

(мы обозначаем это отображение

посредством g 1 f)

удовлетворяет следующим правилам

(i) ЗАКОНЫ ИДЕНТИЧНОСТИ: если ,

то 1B 1 f = f и f 1 1A = f.

(ii) ЗАКОН АССОЦИАТИВНОСТИ:

если ,

то (h 1 g) 1 f) = h 1 (g 1 f).

Закон ассоциативности позволяет нам не обращать внимания на расстановку скобок.

Очень многие и хорошо известные нам конструкции обладают свойством быть категорией.

Например,

Категория Объекты Стрелки

Set все множества все функции между

множествами

Top все топологии непрерывные функции

между топологическими

пространствами

Mon моноиды гомоморфизмы моноидов

Pos частично упорядочен-

ные множества монотонные функции

Последняя категория играет центральную роль в построении топосов.

Как подчеркивает П. Т. Джонстон, одной из принципиальных особенностей теории категорий является то, что она принимает “морфизм” как первичное понятие на одном уровне с понятием “объект” [Джонстон 1986, с. 16].

Как и в случае с операцией замыкания определение понятия категория слишком общее, поэтому накладываются различные ограничения. Важным понятием в теории категорий является произведение объектов. Произведением двух объектов a и b в категории f есть объект c из f вместе с двумя морфизмами (отображениями), которые называются проекциями p: c ® a и q: c ® b такими, что для всех объектов d c морфизмами f: d ® a и g: d ® b есть единственный морфизм h: d ® c, такой, что p 1 h = f и q 1 h = g. Как и другие свойства категорий произведение объектов является универсальным свойством. В действительности, с категорной точки зрения, теоретико-множественное произведение, прямое произведение групп, произведение топологических пространств и конъюнкция высказываний в дедуктивной системе - всё это примеры категорного понятия: произведения объектов.

Говорят, что категория f допускает экспоненцирование, если в ней существует произведение любых двух объектов и если для любых двух объектов a и b существует отображающий объект ba (отображение объекта a в объект b), называемый экспоненциалом, и отображение (стрелка) ev: ba ґ a ® b, называемое отображением значения. Например, если A и B - конечные множества с m и n элементами соответственно, то множество BA (множество всех функций из A в B; поэтому отображающие объекты также называются пространствами функций) также конечно и имеет nm элементов. В выражении nm чило m называется экспонентой. Это объясняет выбранную выше терминологию.

Многие категории обладают произведениями (и суммами), но только некоторые имеют отображающие объекты. Категории с произведениями, в которых каждая пара объектов имеет отображающий объект, называются декартово замкнутыми категориями. Почему декартово - понятно, а замкнутость (как обычно) обозначает, что отображение от одного объекта в другой не образует ничего вне категории.

Только в 1960 г. А. Гротендик (A. Grothendieck) пришел к открытию класса категорий, который впоследствии назвал топосами и которые являются исключительно сложными теоретико-множественными конструкциями. Ф. Ловер к концу 60-х годов заметил, что каждый топос Гротендика имеет объект истинностных значений, а само двухэлементное множество {истина, ложь} можно рассматривать как “объект истинностных значений” в категории множеств. Этим фундаментальным открытием была значительно продвинута разработка теории топосов. В результате появилось понятие классификатора подобъекта, которое в свою очередь вводит в обиход понятие “подобъекта”, являющегося категорным аналогом понятия подмножества. Классификатор подобъектов обозначается посредством W и следствием существования такого объекта является всё то, что мы можем сказать о подобъектах X и что может быть переведено в разговор об отображениях X в W . Заметим, что категория подобъектов может содержательно интерпретироваться как “множество истинностных значений”. В итоге элементарный топос (т. е. его свойства могут быть описаны в первопорядковом языке) может быть определен как декартово замкнутая категория с классификатором подобъектов [Голдблатт 1983, с. 97]. Заметим, что категория подобъектов данного объекта в любой категории является категорией Pos, играющей такую важную роль в логике. Как отмечается в [Lawvere & Schanuel 1997, p. 344], логика в узком смысле слова является преимущественно логикой о подобъектах: главное то, как они соотносятся, и то, что их наиболее основные взаимоотношения даны посредством отображений в любой категории.

Самым простым примером топоса, который служит обоснованием введения такового, является категория Set. Таким образом, теория топосов подводит к новому способу понимания множеств. Образно говоря, топос есть категория, которая также обладает достаточно богатой логической структурой. С философской точки зрения интересен тот факт, что все топосы есть модели для интуиционистской логики H. Это является следствием того, что алгебра подобъектов любого элементарного топоса является алгеброй Гейтинга. Отметим также, что поиски категорных вариантов логики первого порядка привели к понятию логической категории (см. [Кок & Рейес 1982]). Использование же аппарата теории категорий для изучения самой логики привело к появлению понятия категорной логики.

Применение теории категорий к логике получило новый и весьма эффективный импульс, когда сама дедуктивная система была представлена в виде категории [Lambek 1968], а на самом деле в категорных терминах можно дать определение дедуктивной системы.

Пусть под объектами дедуктивной системы, как обычно, понимаются формулы A, B, … с индексами или без них, а под стрелками - доказательства f : A ® B или f : A „ B. Дедуктивная система должна иметь следующие операции над стрелками: для каждого объекта A нульарную операцию, называемую идентичной стрелкой 1A: A „ A, и бинарную операцию, композицию, которая является сингулярной формой правила сечения

f: A ├ B g: B ├ C

gf: A ├ C

Дедуктивная система является категорией тогда и только тогда, когда следующие уравнения между стрелками (доказательствами) имеют место [Dožen 1996, p. 250]

f 1 = f, 1 f = f

(hg) f = h (gf).

Большим достижением оказалась формулировка доказательства Ламбеком теоремы о функциональной полноте [Lambek 1974] (см. также [Lambek & Scott 1986, Part I]), которая явилась категорным аналогом и обобщением теоремы дедукции, приведшей к усилению генценовской характеризации интуиционистской импликации, и одновременно явилась категорным обобщением теоремы о комбинаторной полноте. К. Дошен переформулирует и упрощает доказательство этой теоремы и дает ей название теоремы о дедуктивной полноте, извлекая из нее новые следствия. В работе Дошена разрабатываются также важные виды категорий, соответствующие фрагментам различных пропозициональных логик. Специально для импликативных логик, являющихся подлогиками H® (см. выше раздел 6), категорный подход разрабатывается В. Л. Васюковым [Васюков 2000].

Однако вернемся к исходной работе Ламбека [Lambek 1968]. Здесь впервые в литературе изучается понятие эквивалентности доказательств. Это понятие оказывается довольно-таки громоздким, поскольку Ламбек использует системы генценовского типа (логистического) с правилами введения связок слева и справа от стрелок. В связи с этим обратим внимание на работу Г. Минца [Минц 1977], сумевшего значительно упростить аппарат за счет перехода от выводов к соответствующим им термам. Это позволило сочетать преимущества натуральных и логистических выводов. Минц строит дедуктивную систему HCC гильбертовского типа, в которой определяет отношение эквивалентности для выводов. Это превращает HCC в замкнутую категорию: объектами являются формулы, а морфизмами - классы эквивалентности выводов. Особо отметим приведенный перевод с языка теории категорий в язык теории доказательств, например, такого сложного понятия, как “естественное преобразование”.

8. Оператор замыкания и категория - вместе

С построением теории категорий появилась возможность создания логического универсума гораздо более богатого, чем конструкция под названием “решетка”, элементами которой являются логики в том или ином смысле.

В самом общем случае объектами являются логики вида d = , где А есть множество (предложений) и CA есть оператор (замыкания) присоединения следствий, выполняющий условия (1) - (3). Такие дедуктивные системы Вуйцицкий назвал пропозициональными исчислениями [Wуjcicki 1984, p. 18]. Тогда морфизмы между объектами есть не что иное, как переводы (см. выше раздел 3). В результате мы получаем конструкцию, которая является категорией. В [Inouй 1996, p. 312] такая категория обозначается посредством Emb (погружение), а в [Carnielli & D'Ottaviano 1997, p. 74] - Tr (перевод). В последней работе отмечается, что логики вместе с переводами образуют биполную категорию, т. е. категорию, для которой определены произведения и суммы.

Уже отмечалось, что топологические пространства можно определить как множества с оператором замыкания, более строго это выглядит следующим образом. К свойствам монотонности (i), рефлексивности (ii) и идемпотентности (iii) добавляются еще два:

(iv) C(Ж ) = Ж ,

(v) C(X И Y) = C(X) И C(Y).

Тогда категория топологических пространств с непрерывными функциями (в качестве морфизмов) является полной подкатегорией Tr, т. е. переводы между топологическими пространствами есть непрерывные функции в топологическом смысле. Таким образом, некоторые топологические результаты представляют также и логический интерес.

Подчеркнем, что элементами решетки теорий, обнаруженной Тарским, являются теории, сформулированные в одном и том же языке. В алгебраической решетке LC элементами являются теории, сформулированные в разных языках, т. е. с разными словарями нелогических терминов. Остается еще одна возможность: рассмотреть класс разноязыких теорий, основанных на различных логиках. Тогда возникает следующий вопрос: образует ли совокупность таких теорий какую-либо конструкцию? [Васюков 1995, с. 279]. В этой работе показывается, что в общем случае не образуется даже решетка теорий. Чтобы обойти эту трудность, В.Л.Васюков прибегает к теоретико-категорному подходу. В этом случае класс разноязыких теорий рассматривается как некоторая категория Th, объекты которой есть элементарные теории (удовлетворяющие первым трем условиям для оператора замыкания), сформулированные в различных языках и основанные на различных логических исчислениях, а морфизмами являются сформулированные определенным образом переводы одной теории в другую. Полученная категория является дуально-замкнутой категорией, где вместо произведения берется сумма, а вместо импликации - дуальная ей операция. В итоге построенная конструкция Th названа “котопосом” [Васюков 1995, c.291]. Подобный результат Васюков рассматривает как категорное обобщение результата Тарского: там исчисление систем образует алгебру Брауэра одноязычных теорий, а здесь получен топос Брауэра разноязычных теорий.

Отметим также, что с категорной точки зрения может быть рассмотрена и интерпретируемость теорий [Gaifman 1976]: I называется точной (faithful) интерпретацией теории T1 в теорию T2, если

T1 „ d тогда и только тогда, когда T2 „ d I.

Точная интерпретируемость T1 в T2 и наоборот влечет категорную эквивалентность T1- и T2- пополнений предтопоса. Для обычной интерпретируемости это не имеет места.

В начале данного раздела мы видели, что в качестве объектов могут выступать сами дедуктивные системы, а морфизмами между такими объектами считаются переводы одной дедуктивной системы в другую. Теперь можно выйти на уровень еще большего обобщения. Представление дедуктивных систем в виде категории наводит на мысль использовать понятие функтора, являющегося одним из основных понятий в исходной работе родоначальников теории категорий [Eilenberg & Mac Lane 1945] в качестве погружающей операции. Функтор - это отображение из одной категории в другую, сохраняющее категорную структуру. На категорном языке это выглядит следующим образом.

Функтором F из категории f в категорию g называется функция, ставящая в соответствие каждому объекту A из f объект F(A) из g , и еще одна функция, ставящая в соответствие каждой стрелке f : A „ B из f стрелку F(f): F(A) „ F(B) такую, что

F(1A) = 1F(A), F(gf) = F(g) F(f).

В общем случае такие функторы можно рассматривать как переводы одной дедуктивной системы в другую.

9. Алгебраизация логики

Одновременно с традицией развития логики как дедуктивной системы, идущей от Фреге, Уайтхеда и Рассела, развивался совершенно другой подход к логике, наиболее полно выраженный Э. Шрёдером в его трехтомных “Лекциях по алгебре логики” (1890-1905). В третьем томе развивается исчисление отношений и вводятся кванторы, но нигде нет понятия формального доказательства. Предшественники Шрёдера Дж. Буль, В. Джевонс и Ч. С. Пирс, впервые применили алгебраические методы к логике. Отсюда и сам термин “алгебра логики”.

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

Постепенно были выделены основные свойства (классических) логических операций в виде некоторого количества тождеств (равносильностей). В совокупности эти тождества образовали конструкцию под названием “булева алгебра”. Изящной аксиоматизацией класса булевых алгебр являются пары тождеств из раздела 5: (II), (III), (IV), (V) и (B1), (B2). Одно из тождеств (V) выводимо (см. Биркгоф [1952, с. 191]). Таким образом, булева алгебра есть результат алгебраической формализации классической логики высказываний.

Несмотря на простоту формулировки булевы алгебры исключительно богаты по своему содержанию и давно превратились в самостоятельный раздел абстрактной алгебры. Они нашли самое широкое применение в логико-математических исследованиях, в области инженерии контактно-релейных схем, компьютерных наук, аксиоматической теории множеств, теории моделей и в других областях науки и математики (см. трехтомный справочник по булевым алгебрам [Monk (ed.) 1989]).

Результатом алгебраической формализации логики предикатов явились “цилиндрические алгебры”, введенные в 1961 г. Л. Хенкиным и А. Тарским (см. фундаментальный труд [Henkin & Monk & Tarski 1971]).

В алгебраизации логики особую роль сыграла оригинальная идея А. Линденбаума (1926/27), который предложил рассматривать формализованный пропозициональный язык как универсальную алгебру с операциями, соответствующими логическим связкам этого же языка. Но самое главное, затем строится логическая матрица из формул и логических связок, которые составляют само логическое исчисление. Полное признание этот метод получил в 40-е годы в терминологии “алгебры Линденбаума”, или “алгебры Линденбаума–Тарского” (см. историю вопроса в [Surma 1982]). Кратко этот метод можно описать следующим образом.

Рассмотрим бинарное отношение » на множестве формул For пропозиционального языка o : А » В т.т.т., когда A є B есть тавтология. Легко убедиться, что » есть отношение эквивалентности на множестве формул For. Для произвольных классов эквивалентности п Ап и п Вп из For/» пусть п Ап И п Вп = п А Ъ Вп , п Ап З п Вп = п А Щ Вп и - п Ап = п Ш Ап . Тогда алгебра L* = < For/» , И , З , - , 0, 1> называется алгеброй Линденбаума (классической логики) и есть не что иное, как булева алгебра. Нулевым элементом 0 здесь является класс всех противоречий п А Щ Ш Aп , а единицей 1 - класс эквивалентности, состоящий из всех тавтологий п А Ъ Ш Aп .

Легко видеть, что между эквивалентностями классической логики высказываний C2 и тождествами булевой алгебры существует соответствие. Например, между формулой (А Ъ В) є (А Ъ В) и первым тождеством в (II). Более того, „ A в C2 т.т.т., когда A* = 1 в L*, где A* есть аналог А на языке алгебры L*. Таким образом, возникают средства для алгебраического доказательства дедуктивной полноты логических исчислений.

Постепенно алгебраизация логики привела к появлению нового термина “алгебраическая логика”, который стал названием монографии П. Халмоша [Halmos 1962], где методы и аппарат универсальной алгебры стали систематически применяться к изучению логики. В следующем году выходит “Математика метаматематики” (см. [Расёва & Сикорский 1972]), а затем книга Расёвой, ставшая классической [Rasiowa 1974], в которой алгебраические методы применяются к неклассическим логикам. Имеется обзор результатов по алгебраической логике [Эсакиа 1983].

Однако не всякая логика может быть алгебраизуема подобным образом. Например, в релевантной логике R и логике следования E (см. [Anderson & Belnap 1975] существуют теоремы A и B, для которых импликация A ® B не есть теорема. Следовательно, множество всех теорем не совпадает с классом эквивалентности, определенным отношением » . Поэтому встал вопрос об обобщении метода Линденбаума. Обобщение было предложено в обстоятельной работе [Blok & Pigozzi 1989], где вводится лейбницевское отношение эквивалентности между формулами p и q:

p » q «" P(P(p) « P(q)),

где P есть переменная, пробегающая по множеству унарных предикатов.

Что очень важно, берется строгое определение дедуктивной системы (логики), относительно которой и ставится вопрос об алгебраизации. Таковой взята стандартная дедуктивная система, выполняющая условия (1)- (5) для операции присоединения следствий (см. выше раздел 2). В итоге мы имеем алгебраическую семантику для исключительно широкого класса логических систем. См. также [Font & Jansana 1996].

Однако, как и ранее, неалгебраизуемы льюисовские модальные логики S1, S2 и S3, но теперь они обладают более слабым свойством протоалгебраизуемости. Зато релевантная логика R является алгебраизуемой, но не E. Неалгебраизуемыми оказываются импликативные фрагменты этих логик, в то время как H® и TV® алгебраизуемы (см. выше решетку импликативных логик в разделе 6). Недавно было доказано, что известная паранепротиворечивая логика да Косты C1 неалгебраизуема [Lewin, Mikenberg, Schwarze 1991], а следовательно все логики из класса Cn.

Современное бурное развитие алгебраической логики представляет собой систематическое применение методов и, главное, аппарата универсальной алгебры к символической логике. Именно на это как на тенденцию возможного дальнейшего развития алгебры логики указывал А. В. Кузнецов, когда говорил о возможности “охватить алгебраическими методами значительную часть современной математической логики” [Кузнецов 1960]. На самом деле вопрос сейчас стоит об охвате всей символической логики, и результаты здесь весьма впечатляющи (см. [Andrйka, Monk, Nйmeti 1991] и [Andrйka et al. 1994]). Приведем некоторые примеры.

Пусть Alg(L) обозначает класс алгебр, который соотносится с некоторой логикой L. Например, если L есть классическая логика высказываний, то Alg(L) есть класс булевых алгебр. Теперь можно формулировать теоремы, утверждающие, что L имеет определенное логическое свойство т.т.т., когда Alg(L) имеет определенное алгебраическое свойство. Это позволяет дать алгебраическую характеризацию таких логических свойств, как полнота, наличие теоремы дедукции, компактность, разрешимость, интерполяционность Крейга, истинность формул в модели и т. д. Например, первые два свойства принимают следующий вид: L допускает строго полную гильбертовскую аксиоматизацию (Г | - А т.т.т., когда Г | = А) т.т.т., когда Alg(L) есть финитно аксиоматизируемое квази-многообразие; L допускает теорему дедукции т.т.т., когда Alg(L) имеет эквационально определимые главные конгруэнции.

Заметим, что алгебраическая логика является хорошим инструментом для выяснения такого сложного вопроса, как взаимоотношение между различными логическими системами, и вообще для уточнения статуса логики. О последнем говорит название книги П. Халмоша и С. Гиванта “Логика как алгебра” [Halmos & Givant 1998], где показывается, что стандартные результаты в логике хорошо соотносятся с известными алгебраическими теоремами. С другой стороны, такой единый подход к логике представляет также философский интерес. Поэтому статья по алгебраической логике помещается в новое издание “Справочника по философской логике” [Andrйka, Nйmeti, Sain 1999].

Наконец, в силу появления новой парадигмы – теории категорий, представляет интерес работа Дж.Ламбека [Lambek 1988], где аргументируется, что с категорной точки зрения алгебра и логика представляют собой одно и то же: и логика и алгебра имеют дело со стрелками A1 A2 … An ® An+1. В первом случае Ai называются формулами и стрелка рассматривается как дедукция. Во втором случае Ai называются сортами и стрелка осознается как операция.

Если утверждение Ламбека имеет силу, то это наводит на некоторые серьезные размышления, поскольку тогда аппарат теории категорий становится универсальным не только для всей математики (или почти всей) [Mac Lane 1971], но и для логики. Введение в теории категорий конструкции под названием функтор естественным образом привело к образованию конструкции под названием категория категорий [Lawvere 1966]. Не случайно, что с объяснения, что такое категория категорий, по существу начинается монография Мак-Ларти [McLarty 1992].

Каждая категория A имеет тождественный функтор 1A: A ® A, который оставляет объекты и стрелки из A неизменными, и для заданных функторов F: A ® B и G: B ® C имеется композиция G 1 F: A ® C. Поэтому естественно говорить о категории всех категорий, которую назовём CAT, объекты которой есть все категории и стрелки которой есть все функторы. Тогда возникает настоящая проблема: является ли CAT сама по себе категорией? Ответ Мак-Ларти состоит в том, чтобы рассматривать CAT как регулятивную идею, т.е. как неизбежный способ мышления о категориях и функторах, но не как строго легитимную сущность. Такими регулятивными идеями являются, например, собственная личность, универсум и Бог у Канта (1781).

Подобным образом и логика приближается к статусу регулятивной идеи, симптомами чего является поиск всё более строгого и и по возможности универсального объекта (конструкции) с заданными логическими свойствами. В предыдущем разделе таким объектом выступила категория пропозициональных исчислений в смысле Вуйцицкого, которая оказалась биполной. Другим подобным объектом, в одном из приближений, может выступить категория алгебраизуемых логических систем, где под последними понимаются “алгебраизуемые дедуктивные системы” из рассмотренной здесь работы [Blok & Pigozzi 1989], или “строго компактное следование в хороших (nice) общих логиках” [Andrйka et al. 1994]. В [Jбnossy, Kurucz, Eiben 1996] доказано, что категория алгебраизуемых логических систем изоморфна категории соответствующих первопорядковых теорий. Показано также, что эти категории кополны. Более того, ставится вопрос о том, чтобы при построении подобных конструкций вместе с отношением следования рассматривать также семантики данных систем. Алгебраизация таких видов логик дана, например, в [Andrйka & Nйmeti 1994]. Понятно, что различные вариации на понятие операции присоединения следствий, или на отношение следования, или на семантические свойства будут приводить к разным категорным объектам логической природы. И тогда, рано или поздно, встанет подлинный вопрос о регулятивной идее логики всех логик.

Однако завершим данный раздел ностальгией о простой и удобной логической системе, поиск которой к самому концу тысячелетия со всей силой поставил вопрос “Что есть логическая система?” и даже “Что есть логика?”

10. В поисках логической системы

Ровно через сто лет после выхода в свет знаменитой работы Г. Фреге [Frege 1879], в которой вводятся предикаты, отрицание, условная связь (the conditional) и кванторы как основа логики, а также введена идея формальной системы, в которой демонстрации должны осуществляться посредством явно сформулированных синтаксических правил, - после ста лет триумфального развития логики как самостоятельной науки, вызывающей поклонение, удивление, а порой горькое отрешение и даже мщение у её бывших адептов и мистический страх у большинства остальных, вдруг появляется статья Я. Хэккинга под названием “Что есть логика?” [Hacking 1979]. Хэккинг высоко оценивает введение Г. Генценом структурных правил, работа с которыми позволяет выражать те аспекты логических систем, которые не имеют непосредственного отношения к логическим константам. Статья Хэккинга переиздается и открывает собой большой сборник работ под названием “Что есть логическая система?” [Gabbay (ed.) 1994], который издается в Англии и Америке. В этом же году и с тем же названием, что и статья Хэккинга, публикуется философская работа логика с мировым именем Хао Вана [Wang 1994], которая открывается определениями логики, начиная от Канта и вплоть до Гёделя, и заканчивается характеризацией логики, данной Л. Витгенштейном в 1921 г. в его “Трактате…” (см. [Витгенштейн 1958]):

2.0121 “Логика трактует каждую возможность, и все возможности суть её факты”.

Но самое удивительное, что в этом же году под названием “Что есть истинная элементарная логика?” появляется статья выдающегося логика и философа Яакко Хинтикки [Hintikka 1994], в которой развивается новая концепция первопорядковой логики.

Приходится констатировать, что конец века и конец второго тысячелетия, а именно 1994 г. стал той критической точкой, когда под неимоверным давлением окончательно рухнула конструкция под названием “классическая логика”, тем самым ещё раз подтвердив неправоту Канта, который в предисловии ко второму изданию “Критики чистого разума” в 1787 г. писал, что “судя по всему, она (логика. - А.С.) кажется наукой вполне законченной и завершенной” (см. [Кант 1994, с. 14]).

Дедуктивная полнота логики предикатов ещё более укрепила убеждение Гильберта, что вся классическая математика в конечном счете выразима в первопорядковой логике. К этому времени были уже выявлены два важнейших теоретико-модельных свойства теорий в первопорядковом языке:

Теорема Лёвенгейма-Скулема. Если Т имеет бесконечную модель, то Т имеет модель любой бесконечной мощности t , большей или равной мощности теории Т.

Теорема компактности. Пусть Т - произвольное множество аксиом логики. Если для каждого конечного подмножества Т0 множества Т существует модель для всех аксиом из Т0, то существует модель для всех аксиом из Т.

Обе эти теоремы используются для доказательства неаксиоматизируемости теорий (см. [Барвайс 1982]).

Вышеприведенный тезис Гильберта разделялся и разделяется многими логиками, отдающими предпочтение классической логике предикатов перед всеми другими логическими системами. К тому же в 1969 г. была выявлена уникальность первопорядковой логики, заключающейся в том, что классическая логика предикатов является наиболее сильной логикой, обладющей свойством Лёвенгейма-Скулема и свойством компактности [Lindstrцm 1969].

Теорема Линдстрёма. Логика первого порядка является единственной логикой, замкнутой относительно Щ , Ш , $ и удовлетворяющей теоремам компактности и Лёвенгейма-Скулема.

По существу теорема Линдстрёма даёт определение первопорядковой логики в терминах её глобальных свойств. Интересно, что первоначально результат Линдстрёма не привлёк к себе особого внимания, о чём говорит издание в 1973 г. знаменитой книги Г. Кейслера и Ч. Ч. Чэна (см. русский перевод [Кейслер & Чэн 1977], где эта теорема вообще не обсуждается. Только в третьем издании [Chang & Keisler 1990] уже в предисловии говорится, что этот результат является отправной точкой для развития абстрактной теории моделей и вводится новый раздел (2.5), где дается определение “абстрактной логики” как пары классов (l, л ), где l есть класс предложений и л l есть отношение выполнимости (satisfaction), удовлетворяющее определенным условиям. Наиболее известным примером абстрактной логики как раз и является обычная первопорядковая логика, которая обозначается посредством lw ,w .

Абстрактная теория моделей претендует на обозрение всего спектра логик, связей между ними и их сравнение. С начала 70-х годов эта теория бурно развивается, а Дж. Барвайс назвал результат Линдстрёма “одним из первых и до сих пор наиболее поразительных результатов в абстрактной теории моделей” [Барвайс 1982, с. 54].

Имеется много интересных логик, которые богаче первопорядковой логики, такие, как слабая логика второго порядка, которая пытается построить понятие конечного в логике некоторым естественным образом; логики с формулами бесконечной длины; логики с различными экстра-кванторами типа “существует конечно много”, “существует бесконечно много”, “большинство” и т. д.; логики высших порядков. Однако не имеет значения, как мы будем расширять первопорядковую логику - в любом случае теряется или свойство компактности, или свойство Лёвенгейма-Скулема, или оба вместе. Уже второпорядковая логика, допускающая квантификацию по подмножествам, отношениям и функциям, кроме указанных свойств теряет также свойство полноты, и на самом деле является не столько логикой, сколько теорией множеств. Отсюда вся теоретико-множественная проблематика может быть сформулирована во второпорядковых терминах. Это является основным возражением против второпорядковой логики в недавно вышедшей монографии, посвященной расширениям первопорядковой логики [Manzano 1996], и поэтому автор отдает предпочтение многосортной первопорядковой логике, которая является переинтерпретацией второпорядковой логики или даже логики высших порядков в первопорядковую с различными видами объектов. Редукция к первопорядковой логике настолько сильна, что мы приходим к рекурсивно-аксиоматизируемому множеству истин. Еще ранее А. Мальцев, Хао Ван и С. Феферман, среди прочих, подчеркивали удобство работы с такой логикой, хотя, заметим, она только внешне выглядит более богатой. Хорошее введение можно найти у Фефермана [Feferman 1974].

Первой работой, поставившей вопрос о введении новых кванторов, является статья А. Мостовского [Mostowski 1957], где на самом деле обсуждаются лингвистические операторы нового вида, представляющие “естественное обобщение логических кванторов”. Идея Мостовского заключается в том, что любое второпорядковое свойство рассматривается как логический квантор, если оно инвариантно относительно биективных преобразований (перестановок). Построение логики с обобщенными кванторами в последние десителетия привлекло к себе большое внимание лингвистов, математиков, философов, когнитологов. Некоторым итогом развития этого направления является фундаментальный труд “Модельно-теоретические логики” [Barwise & Feferman (eds.) 1985], где Дж. Барвайс приходит к следующему выводу: “Нет обратной дороги к точке зрения, что логика является первопорядковой”. А в монографии Г. Шер [Sher 1991] в связи с данной проблематикой ставится вопрос “Что есть логика?”, обсуждаются границы логики и делается вывод, что логика шире, чем традиционное мышление.

Отметим, что появляются всё новые попытки расширения и изменения первопорядковой логики и построения искомой логической системы. Видимо, одной из наиболее интересных здесь работ является уже упоминавшаяся статья Хинтикки [Hintikka 1994], а также статья с вызывающим названием “Революция в логике?” [Hintikka & Sandu 1996], и вообще целый комплекс работ Хинтикки, связанный с применением созданной им IF-логики (Independence Friendly - дружественной к независимости).

Основная идея Хинтикки состоит в осознании того, что кванторы обычной первопорядковой логики являются зависимыми. Последнее означает, что если мы имеем дело с выражениями типа “для всех x имеются некоторые y, такие, что R(x,y)”, то выбор подобных y не независим, а детерминирован выбором x-ов, иначе говоря, между x и y существует некоторая функциональная зависимость. Понимание этого факта уже отмечалось в литературе (см. [Goldfarb 1979, p. 364]), но главная заслуга Хинтикки состоит в восприятии идеи независимости кванторов, т.е. следует указывать, какие квантификационные переменные зависят от каких. Так, если мы имеем дело с выражением “для всех x, для всех z имеются некоторые y, имеются некоторые w, такие, что S(x,y,z,w)”, то в случае, когда нам требуется независимость x от y, z от w, следует преобразовать искомую фразу в следующую: “для всех x, для всех z имеются некоторые y (не зависящие от z), имеются некоторые w (не зависящие от x), такие, что S(x,y,z,w)”.

Оказалось, что в языке первопорядковой логики не существует средств, позволяющих соответствующим образом записывать последнюю фразу. Хинтикка предлагает осуществить это в виде “(" x)(" z)($ y/" z)($ w/" x)S(x,y,z,w)”, где косая черта (/) означает независимость квантификации одной переменной от другой. То же самое предлагается и в случае дизъюнкции и конъюнкции.

Особенностью IF-логики является её неполнота, что означает невозможность дать список аксиом, из которых все значимые формулы первопорядковой IF-логики могут быть выведены по чисто формальным правилам. Но в то же время она удовлетворяет свойствам компактности и Лёвенгейма-Скулема. Поэтому мы бы предположили, что IF-логика является подсистемой классической логики предикатов или, по крайней мере, последняя погружается в IF-логику. Революционный характер IF-логики, считают Хинтикка и Санду, нельзя изложить в одном томе; особенно важной чертой является её неполнота с далеко идущими последствиями для оснований математики [Hintikka & Sandu 1996, p. 177]. Фактически Хинтикка пытается свести всю обычную математику к расширенной первопорядковой IF-логике [Hintikka 1996].

Однако тематика абстрактной логики и общетеоретические проблемы обоснования математики несколько отступают перед новыми тенденциями в развитии логики конца ХХ века. Логика становится всё более насущной в компьютерных науках, искусственном интеллекте и программировании. Подобное приложение логики порождает большое число новых логических систем, но уже нацеленных непосредственно на их практическое применение. Именно этим и обусловлен выход сборника статей под названием “Что есть логическая система?” [Gabbay (ed.) 1994].

Вообще-то говоря, вопрос стоит так: существует ли одна “истинная” логика (среди бесконечных классов логик), а если нет, то как ограничить наше понимание логики или, более конкретно, логической системы? Возникают и другие вопросы: существует ли реальное различие между синтаксисом и семантикой с точки зрения приложений? И, конечно, стоит вопрос о традиционных свойствах логических систем: полноте, устранении сечения, интерполяционном свойстве и др. Например, Г. Булос [Boolos 1975], защищая второпорядковую логику, спрашивает: почему логика обязательно должна обладать свойством компактности? Интересно, что всё в том же сакраментальном 1994 году на страницах “The New Encyclopedia Britannica” спрашивается, почему свойство Лёвенгейма-Скулема должно соответствовать внутренней природе логики? (Vol. 23, p. 250).

Еще больше возникает вопросов в связи с развитием и применением альтернативных (неклассических) логик (см. выше раздел 3). В статье Жана Безъё с примечательным названием “Универсальная логика” [Bйziau 1994] (обратите внимание на год публикации) спрашивается, почему логика обязательно должна быть монотонной? Заметим, что только такие логики являются элементами указанных выше решеток. Хотя на самом деле исследования в области немонотонных логик давно превратились в отдельное направление в силу их применения [Gabbay 1985], [Nerode & Shore 1993]. К этой области принадлежит целая серия работ Д. Батенса и его учеников, где разработана логика, способная моделировать рассуждения, в ходе которых смысл логических терминов может измениться. В итоге возникло новое направление исследований, названное “адаптивными логиками” [Batens 1994].

Универсальная логика, предложенная Безъё, является логикой со свойством сокращения (комбинатор W). Но опять же давно возникло целое направление, получившее название “логики без сокращения” [Ono & Komori 1985]. Одним из наиболее интересных примеров логик без сокращения являются многозначные логики Лукасевича, как конечные, так и бесконечные. Свойства их столь необычны, что изучение этих логик к концу века стало исключительно интенсивным, что объясняется, в первом случае, их связью с теорией простых чисел [Карпенко & Шалак 2000] и, во втором случае, их связью с фундаментальными алгебраическими структурами совершенно различной природы [Mundici & Cignoli 1997]. Обратим внимание, что многозначные логики Лукасевича как логические исчисления строились по образцу и подобию классической логики. Возникает нетривиальный вопрос, как возможна логика, которая, с одной строны, имеет чисто арифметическую интерпретацию [Карпенко 1999] а с другой стороны, появляются такие конструкции, как решеточно-упорядоченные абелевы группы, бесконечномерные пространства и т.д.? И если это логика, то что всё это значит?

В 1987 г. появилась логическая система под названием “линейная логика” [Girard 1987], импликативный фрагмент которой представляет собой BCI-логику, т.е. логику без утончения и сокращения. Кроме обычных операций линейная логика снабжена различными другими операциями и нашла широкое применение в компьютерных науках. За удивительно короткое время образовалось новое направление [Troelstra 1992]. Категорное рассмотрение линейной логики представлено в [Dožen & Petrić 1999].

Логика без утончения, сокращения и перестановки (комбинатор C) есть ассоциативное исчисление Ламбека для грамматических категорий или синтаксических типов [Lambek 1958]. Логики проявили огромный лингвистический интерес к этой работе (см. литературу в [Buszkowski et al. (eds.) 1988] и [Van Benthem 1991]). Хотя первоначально исчисление Ламбека не было представлено как новая логика, но получила развитие в чисто логических работах, итогом чего явились полные (full) секвенциальные и гильбертовские исчисления без указанных выше трех структурных правил (или аксиом). См., например [Mac Caull 1998], где строится по существу интуиционистское исчисление без структурных правил, которое автор рассматривает как наиболее фундаментальное из всех субструктурных логик и играющее важную роль в теоретических приложениях компьютерной науки. На самом деле построение подобных логик можно считать результатом развития направления, названного “субструктурные логики”, где исчисления получаются за счёт элиминации, ограничения и комбинирования различных структурных правил [Dožen & Schroeder-Heister (eds.) 1993].

В итоге, с одной стороны, в силу невозможности объять необъятное намечена тенденция к выявлению минимальной логики. К. Дошен предлагает считать таковой неассоциативное исчисление Ламбека с единственной бинарной связкой “мультипликации” [Dožen 1993, p. 20]. Вопрос о минимальной логике впервые был поставлен А. Чёрчем [Church 1951], где в качестве примера предложена “слабая позитивная импликация” - IBCW (импликативный фрагмент релевантной логики R), для которой Чёрчем была доказана ослабленная теорема дедукции. Идея о минимальной логике оказалась очень близкой релевантистам и в [Anderson & Belnap, jr. 1975, § 8.11] таковой объявлена логика IB'B. Тема получила дальнейшее развитие в [Anderson & Belnap, jr. & Dunn 1992, p.149], где таковой объявляется логика IB с правилами 1) MP и 2) из A следует (A ® B) ® B. Эту логику авторы обозначали посредством M® . Для неё строится модель такая, что S есть ассоциативный моноид, и множество всех формул, истинных во всех -моделях, аксиоматизируется посредством логики M® .

Поскольку понятие моноида удовлетворяет условиям быть категорией, то данное понятие минимальной логики также обладает данными свойствами. Другими словами, дедуктивная система, отношение следования (дедуцируемости) которой рефлексивно и транзитивно, является категорией. Поэтому с полным основанием логику M® можно было бы считать минимальной логической системой. Но в том-то и дело, что стали появляться совсем “экзотические” логические системы, в которых, например, закон идентичности A ® A не проходит, поскольку, согласно Э. Шрёдингеру, этот закон в общем случае не имеет места для микрообъектов. Такие логики получили название “логики Шрёдингера” [da Costa & Krause 1994].

С другой стороны, проявилась тенденция к объявлению какой-либо достаточно богатой системы металогикой, как это делает К. Дошен [Dožen 1992], снабжая субструктурные логики различными модальными операторами, или Д. Миллер [Miller 1997], разрабатывающий язык программирования, названный Forum, который основан на линейной логике высшего порядка.

Между двумя этими крайностями пробивает себе дорогу тенденция, которую мы обозначили бы как выбор (или конструирование) базисной логики. С одной стороны, она должна быть достаточно богата, чтобы обладать некоторыми хорошими логическими свойствами, а с другой стороны, достаточна бедна, чтобы её можно было положить в основание иерархии (или конструкции) интересных и важных логических систем. Так, например, в классе модальных логик таковой выбрана логика K (см. выше примеч. 1). В связи с этим представляет интерес базисная “специальная промежуточная” логика BPC [Ruitenburg 1995], которая соотносится с модальной логикой K4 в таком же смысле, как интуиционистская логика H с модальной логикой S4. В качестве базисной логики выступает также полное исчисление Ламбека FL или специально построенная для этой цели базисная логика B (см. раздел 6). Недавно было заявлено базисное исчисление предикатов BQC [Ruitenburg 1998], представляющее собой собственную подсистему интуиционистской логики предикатов IQC, использующее семантику Крипке с транзитивным, но не обязательно рефлексивным отношением достижимости. Понятно, что выбор базисной логики - дело довольно-таки произвольное. Однако одним из строгих критериев мог бы служить тот минимальный фрагмент классической (интуиционистской) логики предикатов, в которую погружается сама классическая логика предикатов. Например, в докладе В. М. Попова (см. сноску 7) таким фрагментом выступает импликативно-экзистенциальный фрагмент IQC.

Видимо, стоит согласиться с Дж. ван Бентемом и К. Дэтсом [Van Benthem & Doets 1983, p. 326], что “никакая специфическая теория не является священной в современной логике”. Но что-то ведь должно остаться! В. Карниэлли в рецензии на [Gabbay (ed.) 1994] выдвигает основное предположение: “Нет доказательств, нет логики” [Carnielli 1996, p. 6417]. Но и здесь не так всё просто. Ламбек в статье под названием “Что есть дедуктивная система” [Lambek 1994] выделяет пять стилей дедуктивных систем: (1) гильбертовский стиль (дедукция вида f : ® B, для формулы B; (2) стиль Ловера (f : A ® B, для формул A и B); (3) генценовский интуиционистский стиль (f : A1 … Am® B); (4) генценовский классический стиль (f : A1 … Am ® B1 … Bn), и (5) стиль Шютте (Schьtte) (f : ® B1 … Bn). Ламбек уделяет особое внимание равенствам между выводами. Последнее стало особенно актуальным под влиянием теории категорий и компьютерных наук. Заметим, что Ламбек отдает предпочтение генценовскому стилю в силу введения структурных правил.

Мы начали эту статью с указания различных конструкций, являющихся важными для понимания логики в той или иной форме и степени. Кроме того, нами была предложена конструкция в виде конечной булевой решетки, элементами которой являются сами логические системы, и эта совокупность базисных логических систем может образовать своего рода металогику. На самом деле вопросы, обсуждаемые в этой статье, относятся именно к металогике, но не в её традиционном понимании как исследовании металогических свойств (непротиворечивость, полнота, разрешимость, независимость и т. д.) какой-то конкретной логической системы или даже класса однотипных систем, а именно к металогике как глобальному подходу в исследовании различных совокупностей логик, выявлении структуры не отдельных логических систем, а их целого класса; взаимоотношения между различными логиками, множествами логик и структурами этих множеств; переводу и погружению одних логических систем в другие; построению какой-либо по возможности богатой конструкции, объединяющей как можно больше логических систем, и изучению уже её свойств. Всё это и есть современная металогика.

В связи с этим возникает фундаментальный вопрос о существовании конструкции под названием ЛОГИКА. Написание всего этого раздела, да и всей статьи, свидетельствует, что такой конструкции нет и не может быть. Но это дискурсивный вывод и слишком аналитический. Поэтому закончим мы эту работу впечатляющим рассуждением Я. Лукасевича, взятым из его статьи “В защиту логистики”, написанной в 1937 г., где выявляется сущность той основы, на которой возникает логика.

“Итак, сколько бы я ни занимался даже мельчайшей логической проблемой, ища, например, самую короткую аксиому импликативного исчисления, всякий раз меня не покидает чувство, что я нахожусь рядом с какой-то мощной, неслыханно плотной и неизмеримо устойчивой конструкцией. Эта конструкция действует на меня как некий конкретный осязаемый предмет, сделанный из самого твердого материала, стократ более крепкого, чем бетон и сталь. Ничего в ней я изменить не могу, ничего сам произвольно не создаю, но изнурительным трудом открываю в ней все новые подробности, достигая непоколебимых и вечных истин. Где и чем является эта идеальная конструкция? Верующий философ сказал бы, что она в Боге и является Его мыслью” [Лукасевич 1999, с. 232].

ЛИТЕРАТУРА

[Анисов А.М. 2000] Темпоральный универсум и его познание. М.: ИФРАН (в печати).

[Антимиров и др. 1991] Математическая логика в программировании // [Захарьящев М.В. & Янов Ю.И. (ред.) 1991]. C. 331-407.

[Аншаков О.М. 2000] Логико-математические основания ДСМ-метода автоматического порождения гипотез (докторская диссертация).

[Аншаков О.М. & Рычков С.В. 1982] О многозначных логических исчислениях // Семиотика и информатика. Вып. 19. C. 90-117.

[Аншаков О.М. & Рычков С.В. 1984] Об одном способе формализации и классификации многозначных логик // Семиотика и информатика. Вып. 23. С. 78-106.

[Аншаков О.М., Скворцов Д.П., Финн В.К. 1993] О дедуктивной имитации некоторых вариантов ДСМ-метода автоматического порождения гипотез // Семиотика и информация. Вып 33. C. 164-233.

[Барвайс Д. (ред.) 1982] Справочная книга по математической логике: В 4-х частях. М.: Наука. C. 13-54. (Перевод с английского: Barwise J. (ed.) Handbook of Mathematical Logic. Amsterdam: North-Holland Publ. Co., 1977).

[Барвайс Д 1982] Введение в логику первого порядка // [Барвайс Д. (ред.) 1982] Часть I. Теория моделей. С. 13-54.

[Биркгоф Г. 1952] Теория структур. М.: ИЛ. (Перевод с английского: Birkhoff G. Lattice theory (revised edition). N.Y., 1948).

[Бочвар Д.А. 1938] Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления//Математический сборник. Т. 4. № 2. C. 287-308. (Английский перевод в: History and Philosophy of Logic. 1981. Vol. 2).

[Бочвар Д.А. & Финн В.К. 1972] О многозначных логиках, допускающих формализацию анализа антиномий. 1 // Исследования по математической лингвистике, математической логике и информационным языкам. М. C. 238-295.

[Васильев Н.А.1989] Воображаемая логика. Избранные труды. Отв. ред. В.А.Смирнов. М.: Наука.

[Васюков В.Л. 1995] Развивая Тарского: котопос теорий // Логические исследования. Вып. 3. М.: Наука. C. 276-291.

[Васюков В.Л. 2000] Импликативные логики, дедуктивные импликативные системы и экспоненциальные мультикатегории // Логические исследования. Вып. 7. М.: Наука.

[Витгенштейн 1958] Логико-философский трактат. М.: ИЛ.

[Вригт Г.Х., фон 1992] Логика и философия в ХХ веке // Вопросы философии. № 8. C. 80-91.

[Генцен Г. 1967] Исследование логических выводов // А.В.Идельсон & Г.Е.Минц (ред.) Математическая теория логического вывода. М.: Наука.

[Гильберт Д. & Аккерман В. 1947] Основы теоретической логики. М.: ИЛ.

[Гиндикин С.Г. 1972]. Алгебра логики в задачах. М.: Наука.

[Голдблатт Р. 1983] Топосы. Категорный анализ логики. М.: Мир. (Перевод с английского: Goldblatt R. TOPOI. The categorical analysis of logic. Amsterdam: North-Holland, 1979).

[Гретцер Г. 1982] Общая теория решеток. М.: Мир. (Пер. с англ.: Grдtzer G. General lattice theory. Berlin: Springer-Verlag, 1978.)

[Григолия Р.Ш. 1976] Решетка всех финитно-аппроксимируемых расширений счетнозначной логики Лукасевича // Исследования по теории множеств и неклассическим логикам. М. C. 221-246.

[Джонстон П.Т. 1986] Теория топосов. М.: Наука. (Перевод с английского: Johnstone P.T. Topos theory. London: Academic Press, 1977).

[Захарьящев М.В. & Янов Ю.И. (ред.) 1991] Математическая логика в программировании. М.: Мир.

[Кант 1994] Критика чистого разума. М.: Мысль.

[Карпенко А.С. 1997] Многозначные логики (монография). Логика и компьютер. Вып. 4. М.: Наука.

[Карпенко А.С. 1997а] Классификация пропозициональных логик // Логические исследования. Вып. 4. М.: Наука. C. 107-133.

[Карпенко А.С. 1999] Логика в России. Вторая половина ХХ века // Вопросы философии, № 9. C. 148-158.

[Карпенко А.С. 1999a] Импликации следования, строгая, релевантная, интуиционистская и классическая и их взаимоотношения // Логические исследования. Вып. 6. М.: Наука. C. 76-80.

[Карпенко А.С. 1999b] Характеризация классов натуральных чисел посредством логических матриц // Труды научно-исследовательского семинара логического центра Института философии РАН. М. C. 217-225.

[Карпенко А.С. & Шалак В.И. 2000] Логики Лукасевича и простые числа. М.: Наука (в печати).

[Кейслер Г. & Чэн Ч. Ч. 1977] Теория моделей. М. (Пер. с англ.: Chang C. C. & Keisler H.J. Model theory. Amsterdam: North-Holland, 1973).

[Кок А. & Рейес Г. Э. 1982] Доктрины в категорной логике // [Барвайс Д. (ред.) 1982] Часть I. Теория моделей. C. 289-319.

[Комендантский В. Е. 2000] N-значные изоморфы классической логики (дипломная работа).

[Кон П. 1968] Универсальная алгебра. М.: Мир. (Пер. с английского: Cohn P. M. Universal algebra. N.Y.: Harper & Row, 1965).

[Кудрявцев В. Б. 1981] О функциональных системах. М.

[Кузнецов А.В. 1960] Алгебра логики. Философская Энциклопедия. Т. 1. М. С. 33-38.

[Кузнецов А. В. 1971] Некоторые свойства структуры многообразий псевдобулевых алгебр // XI Всесоюзный алгебраический коллоквиум. Кишинев. - С. 225-256.

[Кузнецов А. В. 1975] О суперинтуиционистских логиках // Математические исследования. Т. 10. Вып. 2.

[Куратовский К. 1966] Топология. Т. 1. М.: Мир. (Перевод с английского: Kuratowski K. Topology. Vol. 1. Warszawa: PWN, 1966).

[Лукасевич Я. 1993] О детерминизме // Логические исследования. Вып. 2. М.: Наука. C. 190-205. (Переизд.: Вопросы философии, 1995, № 5. C. 60-71; Философия и логика Львовско-Варшавской школы. М., 1999. C. 179-198).

[Лукасевич Я. 1999] В защиту логистики // Философия и логика Львовско-Варшавской школы. М.: РОССПЭН. C. 219-232.

[Максимова Л. Л 1997] Интерполяция в суперинтуиционистских логиках предикатов с равенством // Алгебра и логика. Т. 26, № 6. C. 318-357.

[Максимова Л. Л. & Рыбаков В. В. 1974]. Решетки модальных логик // Алгебра и логика. Т. 13. C. 105-122.

[Минц Г.Е. 1977] Замкнутые категории и теория доказательств // Г. Е.Минц & В. П.Оревков (ред.) Теоретическое применение методов математической логики. II. Ленинград: Наука. С. 83-114. (Англ. пер.: Closed categories and the theory of proofs // Mints G. Selected Papers in Proof Theory. Bibliopolis and North-Holland. 1992. P. 183-212).

[Расёва Е. & Сикорский Р. 1972] Математика метаматематики. М.: Наука. (Перев. с англ.: Rasiowa H. & Sikorski R. The Mathematics of Metamathematics. Warszawa: PWN, 1963).

[Смирнов В.А. 1972] Формальный вывод и логические исчисления. М.: Наука. (Переиздано с комментариями: Смирнов В. А. Теория логического вывода. М.: РОССПЭН, 1999. С. 16-233).

[Смирнов В.А. 1987] Логические методы анализа научного знания. М.: Наука.

[Тей А. и др. 1990] Логический подход к искусственному интеллекту. М.: Мир.

[Финн В. К. 1974] Аксиоматизация некоторых трехзначных исчислений высказываний и их алгебр // Философия в современном мире: Философия и логика. М.: Наука. С. 398-438.

[Финн В.К. 1976] О возможностях формализации правдоподобных рассуждений средствами многозначных логик // VII Всесоюзный симпозиум по логике и методологии науки. Киев: Наук. думка. C. 82-83.

[Финн В. К. 1988] Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 28. М.: ВИНИТИ. C. 3-84.

[Хао Ван 1962] На пути к механической математике // Кибернетический сборник. Вып. 5. C. 114-165. (Пер. с англ.: Wang Hao. Toward mechanical mathematics. IBM J. Res. Devel. 1960. Vol. 4. N 1. P. 2-22).

[Чл рч А. 1960] Введение в математическую логику. M.: ИИЛ. (Пер. с англ.: Church A. Introduction to Mathematical Logic. Princeton Univ. Press, 1956).

[Шестаков В. И. 1941] Алгебра двухполюсных схем, построенных исключительно из двухполюсников // Журнал физической техники. Т. 11. Вып. 6. - C. 532-549.

[Энгелер Э. 1987] Метаматематика элементарной математики. М.

[Эсакиа Л. Л. 1979] О многообразиях алгебр Гжегорчика // Исследования по неклассическим логикам и теории множеств. М.: Наука, 1979. C. 257-287.

[Эсакиа Л. Л. 1983] Алгебры логики // Упорядоченные множества и решетки. Саратов: СГУ. C. 115-126.

[Эсакиа Л. Л 1985] Алгебры Гейтинга I. Теория двойственности. Тбилиси: Мецниереба.

[Янков В. А. 1968] Построение последовательности сильно независимых суперинтуиционистских пропозициональных исчислений // Доклады Академии Наук СССР. Т. 181. № 1. C. 33-34.

[Янов Ю. И. & Мучник А. А. 1959] О существовании k-значных замкнутых классов, не имеющих конечного базиса//Там же. Т. 127. C. 44-46.

[Abramsky S., Gabbay D. M., Maibaum T. S. E. (eds.) 1995]. Handbook of Logic in Computer Science. Vol. IV. Semantic modelling. Oxford Science Publications.

[Anderson A.R. & Belnap N.D., jr. 1975] Entailment: The logic of relevance and necessity. Vol. 1. Princeton Univ. Press.

[Anderson A. R., Belnap N. D., jr., Dunn J. M. 1992] Entailment: The logic of relevance and necessity. Vol. 2. Princeton Univ. Press.

[Andrйka H., Monk J. D., Nйmeti I. (eds.) 1991] Algebraic Logic. Dordrecht: North-Holland Publ. Co.

[Andrйka H., Nйmeti I., Sain I. 1999] Algebraic logic. Handbook of Philosophical Logic (second edition). Dordrecht.

[Andrйka H. et al. 1994] Applying algebraic logic; a general methodology. Technical Report, Mathematical Institute. Budapest.

[Anshakov O.M., Finn V.K., Skvortsov D.P. 1989] On axiomatization of many-valued logics associated with formalization of plausible reasoning // Studia Logica. Vol. 48, N 4. P. 423-447.

[Anshakov O. & Rychkov S. 1994] On finite-valued propositional logical calculi // Notre Dame Journal of Formal Logic. Vol. 36, N 4. P. 606-629.

[Avron A. 1984] Relevant entailment - semantics and formal systems // The Journal of Symbolic Logic. Vol. 49. N 2. P. 334-342.

[Barwise J.K. & Feferman S. (eds.) 1985] Model-Theoretic Logics. Berlin: Springer-Verlag.

[Batens D. 1994] Inconsistency-adaptive logics and the foundation of non-monotonic logic // Logique et Analyse. N 145. P. 57-94.

[Battilotti G. & Sambin G. 2000] Basic logic and the cube of its extension Proceedings of LMPS. Florence, 1995 (to appear).

[Beavers G. 1993] Extensions of the А 0-valued Łukasiewicz propositional logic // Notre Dame Journal of Formal Logic. Vol. 34, N. 2. P. 251-262.

[Bйziau J.-Y. 1994] Universal logic // Childers T. & Majer O. (eds.) Logica' 94 Proceedings of the 8th International Symposium. Prague. P. 73-93.

[Blok W.J. 1976] Varieties of interior algebras. PhD thesis, University of Amsterdam.

[Blok W.J. 1980] The lattice of modal logics: an algebraic investigation // The Journal of Symboloc Lgic. Vol. 45. P.221-236.

[Blok W.J. & Pigozzi D. 1989] Algebraizable logics (monograph). Memoirs of the American Mathematical Society. N 396.

[Bolc L. & Borowik P. 1992] Many-valued logics: Theoretical foundations. Vol. 1. Berlin: Springer-Verlag.

[Bolc L. & Borowik P. 1998] Many-valued logics 2. Automated reasonong and practical applications. Berlin: Springer-Verlag.

[Boolos G.1975] On second-order logic // The Journal of Philosophy. Vol. 72. P. 509-526.

[Bцhm C. & Dezani-Ciancaglini M. 1989] Combinatory logic as monoids. Fundamenta Infomaticae. Vol. 12. N 4. P. 525-539.

[Brouwer L.E.J. 1908] De onbetrouwbaarheid der logische principes. Tijdschrift voor wijsbegeerte. Vol. 2, p. 152-158. (Англ. пер.: The unreliability of the logical principles // Brouwer L. E. J. The collected works. Dordrecht, 1975)

[Burris S. & Sankappanavar H. P 1981]. A course in universal algebra. Berlin: Springer-Verlag.

[Buszkowski W. et al. (eds.) 1988] Categorial Grammar. Amsterdam: Benjamins.

[Butler S. W. & Butler J. T. 1992] Profiles of topics and authors of the International Symposium on Multiple-Valued Logic for 1971-1991. International Symposium on Multiple-Valued Logic. 22th. Sendai. P. 372-379.

[Carnielli W.A. 1996] Review of [Gabbay D. M. (ed.) 1994] // Mathematical Review. 96k: 03008.

[Carnielli W. A. & D'Ottaviano M. L. 1997] Translations between logical systems: A MANIFESTO // Logique et Analyse. N 157. P. 67-81.

[Chagrov A. & Zakharyaschev M. 1997] Modal logic. Oxford: Clarendon Press.

[Chang C.C. & Keisler H.J. 1990] Model Theory. Amsterdam: Elsevier Science Publ.

[Chelakowski J. 1992] Consequences operations: Foundational studies. Warszawa. Prepublication.

[Cignoli R., D'Ottaviano I.M.L., Mundici D. 2000] Algebraic Foundations of Many-valued Reasoning. Trends in Logic. Vol. 7. Dordrecht: Kluwer.

[Church A. 1937] Combinatory logic as a semigroup (abstract) // Bull. Amer. Math. Soc. Vol. 43. P. 233.

[Church 1951] Minimal logic (abstract) // The Journal of Symbolic Logic. Vol. 16. P. 239.

[da Costa N. C. A. & Krause D. 1994] Schrцdinger logics // Studia Logica. Vol. 53. P. 533-550.

[Curry H. B. 1954] Generalisation of the deduction theorem. Proceedings of the International Congress of Mathematicans. Vol. 2. Amsterdam. P. 399-400.

[Curry H. B. & Feys R. 1958] Combinatory Logic. Vol. 1. Amsterdam.

[Dožen K. 1992] Modal logic as metalogic // Journal of Logic, Language and Information, Vol. 1, N 3. P. 173-201.

[Dožen K. 1993] A historical introduction to substructural logics // [Dožen K. & Schroeder-Heister P. (eds.) 1993]. P. 1-30.

[Dožen K. 1996] Deductive completeness // The Bulletin of Symbolic Logic. Vol. 2. N 3. P. 243-283.

[Dožen K. & Schroeder-Heister P. (eds.) 1993] Substructural logics. Oxford: Clarendon Press.

[Dožen K. & Petrić Z. 1999] Cartesian isomorphism are symmetric monoidal: A justification of linear logic // The Journal of Symbolic Logic. Vol. 64, N 1. P. 227-242.

[Dummett M. 1959] A propositional calculus with denumerable matrix. // The Journal of Symboloc Lgic. Vol. 24. P. 97-106.

[Dummet M. & Lemmon E. 1959] Modal logics between S4 and S5 // Zeitschrift fь r mathematische Logic und Grundlagen der Mathematik. Bd. 5. S. 250-264.

[Dzik W. 1982] On the content of lattices of logics. Part II // Report on Mathematical Logic. N 14. P. 29-47.

[Dziobiak W. 1983] There are logics with the relevance principle between R and RM // Studia Logica. Vol. XLII, N 1.

[Eilenberg S. & Mac Lane S. 1945] General theory of natural equivalences // Transactions of the American Mathematical Society. Vol. 58. P. 231-294. (Переиздано: Eilenberg-Mac Lane: Collected Works. Academic Press, 1986).

[Epstein G. 1993] Multiple-valued logic design: an introduction. Bristol.

[Epstein R.L 1990]. The semantic foundations of logic. - Vol. 1: Propositional logic. - Dordrecht: Kluwer. (2nd ed., 1995).

[Epstein R.L 1994]. The semantic foundations of logic. Vol. 2: First-order logic. Dordrecht: Kluwer.

[Feferman S. 1974] Application of manysorted interpolation theorems // Proccedings of the Tarski Symposium. Providence. P. 205-224.

[Font J.M. & Jansana R. 1996] A General Algebraic Semantics for Sentential Logics. Berlin: Springer-Verlag.

[Frege G. 1879] Begriffsschrift, eine der arithmetischen nachgebildete Formalsprache des reinen Denkens. Hale (Hebert). (Англ. пер.: Begriffsschrift, a formula language, modelled upon that of arithmetic, for pure thought // [Van Heijenoort J (ed.) 1967]. P. 1-82).

[Gabbay D. M. 1981] Semantical investigations in Heyting's intuitionistic logic. Dordrecht: Reidel.

[Gabbay D. M. 1985] Theoretical foundations for non-monotonic reasoning in expert systems // Apt K.R. (ed.) Logics and models of concurrent systems. Berlin: Springer. P. 439-457.

[Gabbay D. M. (ed.) 1994] What is a logical system? Oxford: Clarendon Press (and New York 1995).

[Gabbay D.M. 1996] Labelled deductive systems. Vol. 1. Oxford: Clarendon Press.

[Gabbay D. M., Hogger C. J., Robinson J. A. (eds.) 1998] Handbook of Logics in Artificial Intelligence and Logic Programming. Vol. V. Logic programming. Oxford Science Publications.

[Gaifman H. 1976] Operations on relational structures functors and classes. I // Proceedings of the Tarski Symposium. Amer. Math. Society. Vol. 25. P. 21-39.

[Girard J. Y. 1987] Linear logic // Theoretical Computer Science. Vol. 50. P. 1-102.

[Glivenko М. 1929] Sur quelques points de la logique de M.Brouwer. Acadйmie Royale de Belgique, Bulletins de la classe des sciences, ser. 5. Vol. 15. P. 183-188. (Русский перевод: Гливенко В. О некоторых аспектах логики Брауэра // Труды научно-исследовательского семинара Логического центра Института философии РАН. М., 1999. C. 19-23).

[Goldfarb W. D. 1979] Logic in the twenties: the nature of the quantifier // The Journal of Symbolic Logic. Vol. 44, N 3. P. 351-368.

[Gц del K. 1932] Zum intuitionistischen Aussgenkalkul // Anzeiger der Akademie der Wissenschaften Wien, mathematisch, natur-wissenschaftliche Klasse. Bd. 69. S. 65-66. (Английский перевод: On the intuitionistic propositional calculus // [Gц del 1986]. P. 222-225).

[Gц del K. 1933a] Zur intuitionistischen Arithmetik und Zahlentheorie // Ergebnisse eines mathematischen Kolloquiums. Vol. 4 (1931-32). P. 34-38. (Англ. пер.: On intuitionistic arithmetic and number theory // [Gц del 1986]. P. 287-295).

[Gц del K. 1933b] Eine Interpretation des intuitionistischen Aussgenkalkь ls // Ergebnisse eines mathematischen Kolloquims. Bd. 4. S. 39-40. (Англ. пер.: On the intuitionistic propositional calculus // [Gц del 1986].

[Gц del K. 1986] Collected works / Ed. in chief S.Feferman. N.Y.: Oxford Univ. Press. Vol. 1.

[Grzegorczyk A. 1967] Some relational systems and the associated topological spaces // Fundamenta Mathematicae. Vol. 60. P. 223-231.

[Haack S. 1974] Deviant logic: Some philosophical issues. L.: Cambridge Univ. Press.

[Haack S. 1996] Deviant logic, fuzzy logic: Beyond the formalism. Univerity of Chicago Press, 1996.

[Hacking I. 1979] What is logic? // The Journal of Philosophy. Vol. 76. N 6. (Переиздано // [Gabbay D. M. (ed.) 1994]. P. 1-33).

[Halmos P. 1962] Algebraic Logic. New York: Chelsea Publishing Co.

[Halmos P. & Givant S. 1998] Logic as Algebra. Washington.

[Hartonas C. 1997] An algebraic theory of structured objects // Notre Dome Journal of Formal Logic. Vol. 38, N 1. P. 65-80.

[Henkin L., Monk J. D., Tarski A. 1971] Cylindric Algebras. Parts I. Amsterdam: North-Holland Publ. Co. (Reprinted in 1985).

[Henkin L., Monk J. D., Tarski A. 1985] Cylindric Algebras. P. I, P. II. Pergamon Press.

[Heyting A 1930] Die Formalen Regeln der intuitionistischen Logik // Sitzungsberichte der Preussischen (Berlin) Academie der Wissenschaften zu Berlin. Phys.-Math. Klasse. P. 42-56.

[Hintikka J. 1994] What is true elementary logic? // Gavroglu K., Stachel J., Wartofsky M. (eds.), Physics, philosophy and the scientific community. Dordrecht: Kluwer. P. 301-326.

[Hintikka 1996] The principles of mathematics revisited. Cambridge: Cambridge Univ. Press.

[Hintikka J. & Sandu G. 1996] A revolution in logic? // Nordic Journal of Philosophical Logic. Vol. 1. N 2. P. 169-183.

[Hosoi T. 1967] On intermediate logics // Journal of the Faculty of Science, University of Tokyo. Vol. 14. P. 293-312.

[Hosoi T. 1969] On intermediate logics II // Journal of the Faculty of Science, University of Tokyo. Vol. 16. P. 1-12.

[Howard W. A. 1980] The formulae-as-types notion of construction // J.R.Hindley & J.P.Seden (eds.) To H.B.Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. London: Academy Press. P. 479-490.

[Inouй T. 1996] Corrections and additions to my paper “A note on unprovability-preserving sound translations”, More general constractions // Logique et Analyse. N 155-156. P. 335-367.

[Jбnossy A., Kurucz Б., Eiben Б. E. 1996] Combining algebraizable logics // Notre Dame Jornal of Formal Logic. Vol. 37. N 2. P. 366-380.

[Karpenko A.S. 1989] Characterization of prime numbers in Łukasiewicz's logical matrix // Studia Logica. Vol. 48. N 4. P. 465-478.

[Karpenko A.S. 2000] Classification of propositional calculi // Studia Logica (to appear).

[Karpenko A.S. & Popov V.M. 1997] BCKX is the axiomatization of implicational fragment of Łukasiewicz's infinite-valued logic Łw // Bulletin of the Section of Logic. Vol. 26, N 3. P. 112-117.

[Kiriyama E. & Ono H. 1991] The contraction rule and decision problems for logics without structural rules // Studia Logica. Vol. 50, N 2. P. 299-319.

[Komori Y. 1981] Super-Łukasiewicz propositional logics // Nagoya Mathematical Journal. Vol. 84. P. 119-133.

[Lambek J. 1958] The mathematics of sentence structure // Americam Mathematical Monthly. Vol. 65. P. 154-170. (Рус. Пер.: Ламбек Дж. Математическое исследование структуры предложений // Математическая лингвистика. М., 1964. C. 47-68).

[Lambek J. 1968] Deductive systems and categories I // Math. Systems Theory. Vol. 2, N 4. P. 278-318.

[Lambek J. 1974] Functional completeness of cartesian categories // Annals of Mathematical Logic. Vol. 6. P. 259-292.

[Lambek J. 1988] On the unity of algebra and logic // F.Borceux (ed.) Categorial Algebra and its Applications. Berlin: Springer-Verlag,.

[Lambek J. 1994] What is a deductive system? // [Gabbay D.M. (ed.) 1994]. P. 141-159.

[Lambek J. & Scott P.I. 1986] Introduction to higher-order categorical logic. Cambridge Univ. Press.

[Lawvere F.W. 1966] The category of categories as a foundation for Mathematics // S.Eilenberg & D. K.Harrison et al. (eds.) // Proceedings of the Conference on Categorial Algebra in La Jolla. 1965. Sprenger Verlag. P. 1-21.

[Lawvere F.W. & Schanuel S.H. 1997] Conceptual Mathematics. A first introduction to categories. Cambridge Univ. Press.

[Lewin R. A., Mikenberg I. F., Schwarze M. G. 1991] C1 is not algebraizable // Notre Dame Journal of Formal Logic. Vol. 32. N 4. P. 609-611.

[Lewis C.I. 1912] Implication and the algebra of logic // Mind. Vol. 21. P. 522-531.

[Lewis C. I. & Langford C. H. 1932] Symbolic logic. N. Y.: The Century Company (2nd ed. with corrections, Dover, 1959).

[Lindstrцm P. 1969] On extensions of elementary logic // Theoria. Vol. 35. P. 1-11.

[Łoś J. & Suszko R. 1958] Remarks on sentential logics // Indagationes mathematicae. Vol. 20. P. 177-183.

[Łukasiewicz J. 1920] O logice tró jwartos ciowey //Ruch Filozoficzny. T. 5. S.170-171. (Англ. пер.: On three-valued logic // [Łukasiewicz J. 1970]. P. 87-88).

[Łukasiewicz 1922/1923] Interpretacja liczbowa teorii zdan // Ruch Filozoficzny. T. 7. S. 92-93. (Англ. пер.: A numerical interpretation of theory propositions // [Łukasiewicz J. 1970]. P. 129-130]).

[Łukasiewicz J. 1929] Elementy logiki matematycznej. Warsawa. (Ŕнгл. пер.: Elements of mathematical logic. N.Y., 1963).

[Łukasiewicz J. 1970] Selected works. Warszawa: PWN.

[Łukasiewicz J. 1971] On the principle of contradiction in Aristotle // Review of Metaphysics. Vol. 24. P. 15-38.

[MacCaull W. 1998] Relational semantics and a relational prove system for full Lambek calculus // The Journal of Symbolic Logic. Vol. 63. N 2. P. 623-637.

[Mac Lane S. 1971] Categories for the Working Mathematician. Springer Verlag.

[Malinowski G. 1993] Many-valued logics. Oxford: Clarendon Press.

[Manzano M. 1996] Extensions of first order logic. Cambridge: Cambridge Univ. Press.

[Martinez N.G. 1990] The Priestly duality for Wajsberg algebras // Studia Logica. Vol. 49. N 1. P. 31-46.

[McKinsey J.C.C. & Tarski A. 1948] Some theorems about the sentential calculi of Lewis and Heyting // The Journal of Symboloc Logic. Vol. 13. P. 1-15.

[McLarty C. 1990] The uses and the abuses of the history of topos theory // British Journal for Philosophy of Science. Vol. 41. P.351-375.

[McLarty C. 1992] Elementary Categories, Elementary Toposes. Oxford: Clarendon Press.

[Meyer R. K. 1974] New axiomatics for relevant logics - I // Journal of Philosophical Logic. Vol. 3. P. 53-58.

[Miller D. 1997] Logic programming and metalogic // H.Sckwichtenberg (ed.) Logic of Computation. Berlin. P.265-308.

[Monk J.D. (ed.) 1989] Handbook of Boolean Algebras. Vols. I-III. Amsterdam: North-Holland Co.

[Mostowski A. 1957] On a generalization of quantifiers // Fundamenta Mathematicae. Vol. 44. P. 12-36.

[Mundici D. 1986] Interpretation of AF C*-algebras in Łukasiewicz sentential calculus // Journal of Functional Analysis. Vol. 65. P. 15-63.

[Mundici D. & Cignoli R. 1997] An invitation to Chang's MV-algebras // M. Droste & R. Gцbel (eds.) Advances in Algebra and Model Theory. Reading, UK: Gordon and Breach Publishing Group.

[Mycielski J. 1977] A lattice of interpretability types of theories // The Journal of Symboloc Lgic. Vol. 42. P. 297-305.

[Mycielski J., Pudlбk P., Stern A. S. 1990] A lattice of chapters of mathematics (interpretations between theorems) // Memoirs of the American Mathematical Society. Vol. 84. N. 426.

[Nйmeti I. & Andrйka H. 1994] General algebraic logic: a perspective on 'what is logic' // [Gabbay D. M. (ed.) 1994]. P. 393-443.

[Nerode A & Shore R.A. 1993] Logics for applications. Berlin: Springer.

[Ono H.1990] Structural rules and a logical hierarchy // Mathematical logic. New York: Plenum Press. P. 95-104.

[Ono H. & Komori Y. 1985] Logics without the contraction rule // The Journal of Symbolic Logic. Vol. 50. P. 169-201.

[Post E. L. 1921] Introduction to a general theory of elementary propositions. American Journal of Mathematics. Vol. 43, N 3. P. 163-185. (Переиздано: [Van Heijenoort J (ed.) 1967]. P. 264-283).

[Prawitz D. & Malmnдs P. E. 1968] A survey of some connections between classical, intuitionistic and minimal logic // Schmidt H. et al. (eds). Contributions to mathematical logic. Amsterdam: North-Holland. P. 215-229.

[Priest G. & Routley R. &. Norman J. (eds.) 1989] Paraconsistent logic: Essays on the inconsistent. Mьnchen: Philosopia Verlag.

[Quine W.V. 1970] Philosophy of logic. N.Y.: Englewood Cliffs.

[Rasiowa H. 1974] An Algebraic Approach to Non-classical Logics. Warszawa: PWN.

[Rautenberg W. 1979] Klassische und nichtklassische Aussagenlogic. Braunschweig: Vieweg & Sohn.

[Rose A. 1953] The degree of completeness of the А 0-valued Łukasiewicz propositional calculus // J. of London Math. Soc. Vol. 28. P. 176-184.

[Ruitenburg W. 1995] Model theory of basic logic // Proceeding of 10th International Congress of Logic, Methodology and Philosophy of Sciences. Volume of abstracts. Florence. P. 201.

[Ruitenburg W. 1998] Basic predicate logic // Notre Dame Journal of Formal Logic. Vol. 39. N 1. P. 18-46.

[Schц nfinkel M. 1924] Uber die Bausteine der Mathematihschen Logik. Mathematischen Annalen. Bd. 92. p.305-316 (Англ. пер.: On the building blocks of mathematical logic//[Van Heijenoort J. (ed.) 1967]. P. 355-366).

[Scott D. 1971] On engendering an illusion of undenstanding // The Journal of Philosophy. Vol. 68. P. 787-807.

[Scroggs S.J. 1951] Extensions of the Lewis system S5 // The Journal of Symbolic Logic. Vol. 16. P. 112-120.

[Shannon C. 1938] A symbolic analysis of relay and switching circuits // Trans. Amer. Inst. Elect. Eng. Vol. 57. P. 713-723. (Рус. пер.: Символический анализ релейных и переключательных схем // Шеннон К. Работы по теории информации и кибернетике. М., 1963. C. 9-45).

[Sher G. Y. 1991] The Bounds of Logic. A Generalized Viewpont. Cambridge: The MIT Press.

[Sher G. Y. 1996] Review of [Gabbay D.M. (ed.) 1994] // The Journal of Symbolic Logic. Vol. 61. N 4. P. 1396-1400.

[Stanley B. & Sankappanavar H.P.1981] A Course in Universal Algebra. New York Inc.: Springer-Verlag.

[Surma S. J. 1982] On the origin and subsequent applications of the concept of Lindenbaum algebra // L. J. Cohen et al. (eds.) Logic, Methodology and Philosophy of Science VI.Warszaw: PWN. P. 719-734.

[Tarski A. 1930] Ь ber einige fundamentale Begriffe der Metamathematik // Comptes Rendus des Sй ances de la Sociй tй des Sciences et des Lettres de Varsovie. Classe III. Vol. 23, p. 22-29. (Англ. пер.: On some fundamental concepts of metamathematics // [Tarski 1956]. P. 30-37).

[Tarski A 1930a] Fundamentale Begriffe der Methodologie der deduktiven Wissenschaften I // Monatshefte fь r Mathematik und Physik. Bd. 37. P. 361-404. (Английский перевод: Fundamental concepts of the methodology of the deductive sciences // [Tarski 1956]. P. 60-109).

[Tarski A. 1956] Logic, semantics, metamathematics. Papers from 1923 to 1938. Oxford. (2nd ed. Indianopolis, 1983).

[Thomason R. H. (ed.) 1989]. Philosophical Logic and Artifical Intelligence.Dordrecht: Kluwer.

[Torrens A. 1988] On the role of the polynomial (x ® y) ® y in some implicative algebras // Zeitschrift fь r mathematische Logik und Grundlagen der Mathematik. Bd. 34. S. 117-122.

[Troelstra A. S. 1992] Lectures on linear logic. - Stanford: CSLI.

[Turquette A. R. 1963] Independent axioms for infinite-valued logic // The Journal of Symbolic Logic. Vol. 28, N 3. P. 217-221.

[Umezawa T. 1959] On intermediate propositional logics // The Journal of Symboloc Logic. Vol. 24. P. 20-36.

[Van Benthem J. 1991] Language in Action: Categories, Lambdas and Dynamic Logic. Amsterdam: North-Holland.

[Van Benthem J. & Doets K. 1983] Higher-order logic // Gabbay D. & Guenthner F. (eds.) Handbook of Philosophical Logic. Vol. I: Elements of classical logic. Dordrecht: Reidel. P. 275-329.

[Van Heijenoort J. (ed.) 1967] From Frege to Gц del: A Source Book in Mathematical Logic, 1879-1931. Cambr. (Mass.): Harvard Univ. Press.

[Wajsberg M. 1937] Metalogische Beitrдge // Wiadomos ci Matematyczne. Vol. 43. P. 131-168. (Англ. пер.: Contribution to metalogic // Wajsberg M. Logical Works. Wrocl aw, 1977. P. 172-200).

[Wang Hao 1994] What is logic? // The Monist. Vol. 77. N 3. P. 261-277.

[Wansing H. 1998] Displaying modal logic. Dordrecht: Kluwer.

[Whitehead A. & Russell B. 1910-1913] Principia Mathematica. Cambridge (England): Univ. Press. (Переиздано: Cambridge, 1962).

[Wуjcicki R. 1984] Lectures on Propositional Calculi. Wrocław: Ossolineum.

[Wуjcicki R. 1988] Theory of Logical Calculi: Basic Theory of Consequence Operations. Dordrecht: Kluwer.