Дискретно-непрерывная математика (стр. 65 )

Таким образом, от изучения свойств конкретной логики мы пе­реходим к изучению свойств решетки логик. Развитие этой темы см. в конце последнего раздела в Приложении.

8.5. Релевантные логики

Литература по релевантным логикам столь обширна и разнообраз­на, что авторы фундаментальной статьи [Dunn and Restall 2002] даже не называют ее обзором. Классическими монографиями яв­ляются следующие: [Anderson and Belnap 1975] и [Anderson, Belnap and Dunn 1992].

Мы в основном сконцентрируемся на уже не раз упоминав­шейся нами пропозициональной системе релевантной логики R и на её расширении RM, которое имеет ряд общих черт с логикой Гёделя-Даммита

8.5.1. Критерий релевантности и логика R

Модальные логики не решили проблем с парадоксами импликации и в свою очередь были выявлены парадоксы строгой импликации. Аналогами предыдущих двух парадоксов (см. 8.4.1), но в более очевидной форме, являются следующие формулы:

Обратим внимание, что антецеденты и консеквенты этих фор­мул не имеют общих переменных. В I960 г. предло­жил критерий релевантности, который должна выполнять «хоро­шая» система логического следования R: если есть теорема R, тогда существует некоторая пропозициональная переменная р, которая входит как в А, так и в В [Belnap 1960].

( Заметим, что для доказательства Белнап использовал 8-элементную решетку. Критерий релевантности был независимо открыт также [Донченко 1963].)

Стандартной аксиоматизацией системы R является следующая (см. [Dunn 2000]):

Правила вывода:

1. Modus ponens,

2. Подстановка,

3.(правило адъюнкции).

( Первая аксиоматизация системы R появилась в [Belnap 1967] посредством до­бавления аксиомы (Demodaliser) к системе следования Е. Последняя является результатом модификации и реконструкции А. елнапом (см. [Anderson and Belnap 1975]) системы П' с так называемой сильной импликацией, сформулированной В. Аккерманом в 1956 г. Система Е является одновременно релевантной и модальной логикой. В дейст­вительности, определяя находим, что Е имеет нечто похо­жее на модальности в S4 (см. там же, §4,3 и §10). Импликативный фрагмент R (аксиомы Rl — R4) обозначается посредством Известно, что может быть аксиоматизирован посредством следующих аксиом: (R4), и (Demodaliser). Тогда сильная импли­кация аксиоматизируется посредством отбрасывания (Demodaliser) из )

Примечательным свойством релевантных систем является то, что правило дизъюнктивного силлогизма (Dis)

для них не имеет места, поскольку соответствующая формула

не является теоремой Е и R.

(Уже в [Lewis and Longford 1932] показано, как из с помощью правила Dis выводима любая формула q. В современной нотации это выглядит так:

).

Если мы добавим «парадоксальную» формулу к

R, то получим классическую логику С2.

(Релевантисты называют эту формулу «позитивным парадоксом».)

Если в R отбросим аксио­му то получим конструктивную {интуиционистскую) версию релевантной логики [Dunn 2000].

(Отметим, что в [Смирнов 1972] построено «абсолютное исчисление предика­тов», которое после осознания того, что импликативный фрагмент этого исчис­ления есть импликативный фрагмент R, было обозначено в [Смирнов 1979] как RA. В секвенциальном виде GRA — это интуиционистская система в генценов-ской формулировке без структурных правил утончения. Показывается, как от GRA можно элегантно перейти к минимальной интуиционистской логике (о ней чуть ниже), к самой интуиционистской и к классической. В гильбертовском виде RA есть R без закона дистрибутивности и без закона снятия двойно­го отрицания. )

Добавление к этой версии приводит к интуиционистской логике Int. Здесь правило адъюнкции заменяется на аксиому

Мы уже знаем (см. выше раздел 5.4.4), что имеется четырех­значная матрица Смайли , которая является характеристиче­ской для первопорядкового cледования в Е и R. Интересный ре­зультат содержится в [Swiiydowicz 2008]: R имеет континуальное множество предтабличных расширений.

8.5.2. Некоторые свойства

Казалось бы, все проблемы решены и наконец-то формализована подходящая теория логического следования. Более того, в [Dunn 1966] (и независимо в [Максимова 1967)]) проведена алгебраизация системы R посредством введения моноида Де Моргана и показано, что алгебра Линденбаума для R есть в точности моноид Де Морга­на. Эта структура есть соединение дистрибутивной решетки Де Моргана и абелева моноида с дополнительными условиями, од­ним из которых является неидемпотентность моноидной операции 29. Важным является то, что моноиды Де Моргана резидуированы, т. е. там относительно операцииимеется резидуальная операция →:

Хотя стоит заметить, что здесь эта операция есть В свою

очередь,

Однако построить крипковскую семантику для R не удавалось, пока в 1973 г. не была изобретена тернарная семантика Крите, т. е. с тернарным отношением достижимости (см. [Роутлей и Мейер 1981]). Стоит сказать, что и по сей день ее интуитивное содержание остается неясным.

С самого появления системы R много внимания было уделено проблеме разрешения (см. обзор этой проблематики в [Dunn and Restall 2002]. Интерес подогревался еще тем, что в [Наrrор 1965] было высказано утверждение, что все философски инте­ресные пропозициональные логики должны быть разрешимы.

Оказалось, эта проблема легко решается для различных фраг­ментов R: для это было сделано в 1959 г. С. Крипке кото­рый представил указанные логики в виде секвенциальных исчисле­ний. В 1961 г., применяя метод Крипке, была доказана разрешимость импликативно-негативного фрагмента Е (N. Belnap and J. Wallace), что непосредственно распространялось на такой же фрагмент R, а в 1966 г. была доказана разрешимость R без закона дистрибутивности (R. Meyer). Более того, в 1968 г. было показано, что система R с аксиомой (об этой системе в следую­щем разделе), разрешима (R. Meyer).

Однако совершенно неожиданно появилось доказательство то­го, что системы E, R (и родственные им) неразрешимы [Urquhart 1984]. А затем оказалось, что интерполяционное свойство —

фундаментальное свойство всех «хороших» логических систем - для Е и R не имеет места [Urqiihart 1993].

И тем не менее, основополагающая идея о том (начиная с мат­рицы Смайли), что четырехзначная семантика может оказаться адекватной для R, была наконец реализована в [Mares 2005], где была построена для R четырехзначная окрестностная семантика Крипке.

В 1957 г. В. Крейг (W. Craig) доказал теорему об интерполяции в классической логике предикатов: если выводимото можно построить формулу В, со­держащую лишь термины, входящие и в А, и в С, такую, что выводимы Эта теорема имеет место для рассмотренных выше логик Вызвало удивление, что интерполяционным свойством не обла­дают конечнозначные логики Лукасевича и сама логика(см. \Krzystek and Zachorowski 1977]). Но здесь как раз ничего удивительного нет, учитывая чисто теоретико-числовую природу (см. выше раздел 8.1).