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

Релевантная логика

Слово "'relevant" переводится как "относящийся к делу". Имеется в виду наличие связи по смыслу между двумя вещами. Когда говорят, что нечто не относится к делу, то подразумевают, что оно никак не связано с этим делом. А короче можно сказать - нерелевантно.

Релевантные логики - это неклассические логики. Называемые "relevance logics" в Северной Америке и "relevant logics" в Британии и Австралии, эти системы разрабатывались как попытка избежать парадоксов материальной и строгой импликации.

Материальная импликация (относится к классической логике и булевой алгебре) выражается формулой

A B = ~A B.

Строгая импликация (относится к модальной логике) выражается формулой

A B = w (~A(w) B(w)).

где w - одна ситуация из множества возможных ситуаций W, A(w) - истинность высказывания A в ситуации w, B(w) - истинность высказывания A в ситуации w. Обычно говорят о возможных мирах, а не о возможных ситуациях, но мне термин "возможная ситуация" кажется более адекватным. В импликациях формула A называется посылкой или условием, а формула B - заключением, выводом или следствием.

Среди парадоксов материальной импликации следующие:

p (q p)

То есть, истинное высказывание следует из любого. Эта формула обычно дается как аксиома, когда классическую логику излагают в виде аксиоматической системы.

~p (p q)

То есть, из лжи следует все. Самый известный из парадоксов импликации.

(p q) (q p)

Среди парадоксов строгой импликации следующие:

(p & ~p) q

Очень похоже на "из лжи следует все", т.к. p & ~p = false.

p (q q)

p (q ~q)

Очень похоже на "истинное высказывание следует из любого", т.к. q q = true, и q ~q = true.

Многие философы, начиная с Hugh MacColl (1908), заявляли, что эти формулы противоречат интуиции. Они утверждали, что эти формулы нельзя признать правильными, если понимать "" так, как мы ее представляем себе до изучения классической логики.

Имеется в виду, если понимать формулу A B как утверждение "если A, то B" в повседневном, обиходном языке, а не в математических книжках.

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

"Так называемые" потому, что это не парадоксы внутри математики, а просто результат неправильного применения математики в области лингвистики.

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

"Луна сделана из зеленого сыра. Поэтому в Эквадоре сейчас идет дождь или не идет."

Это высказывание имеет вид: p (q ~q). Сравните с формулами, приведенными выше.

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

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

Считается, что основной принцип формальной логики (и математики вообще) - работать с формой, а не с содержанием. Например, 2 + 2 = 4, независимо от того, имеется в виду 2 яблока или 2 коровы.

Но все-таки там есть один формальный принцип, который они применяют, чтобы "оставаться в теме". Это "принцип общих переменных". Этот принцип говорит, что никакая формула вида A B не может быть доказана в релевантной логике, если формулы A и B не имеют общих пропозициональных переменных (иногда называемых пропозициональными символами), и что никакое умозаключение не может быть истинным, если посылка и заключение не имеют хотя бы одной общей пропозициональной переменной.

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

В "следующей логике" никакой философии не нужно. Простая формула - и все.

В этой статье мы дадим краткий и сравнительно неформальный обзор в области релевантной логики.

• 1. Семантика
• 2. Теория доказательств
• 3. Релевантные логические системы
• 4. Применение релевантной логики

1. Семантика

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

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

Семантика, о которой я расскажу здесь, это семантика тернарного отношения Рутли и Мейера (Richard Routley и Robert K. Meyer).

"Тернарное" - значит отношение имеет три параметра, например: X ударил предметом Y по Z.

Эта семантика - развитие "семантики полурешеток" Аласдаира Уркухарта (Alasdair Urquhart) (Urquhart 1972). Есть похожая семантика Кита Файна (Kit Fine) (которая тоже основана на идеях Уркухарта), который занимался исследованиями в тот же период, когда создавалась теория Рутли-Мейера (Fine 1974). И еще есть алгебраическая семантика от Майкла Данна (J. Michael Dunn). Модели Уркухарта, Файна и Данна, сами по себе, очень интересны, но у нас нет времени их рассматривать.

Идея, стоящая за тернарным отношением довольно проста. Рассмотрим попытку К.И.Льюиса избежать парадоксов материальной импликации. Он добавил в классическую логику новую связку "", то есть, строгую импликацию. В терминах семантик Крипке A B истинно в мире w тогда и только тогда, когда для всех миров w' таких, что w' возможно в w, A ложно или B истинно. Здесь в семантике Крипке для модальной логики отношение возможности (accessibility) бинарное. Оно связывает пару миров. К сожалению, с точки зрения релевантной логики, теория строгой импликации все еще нерелевантна. То есть, мы все еще можем доказать формулы вроде

p (q q)

Как и семантика модальной логики, семантика релевантной логики связывает отношение истинности с мирами. Но Рутли и Мейер сделали модальную логику чуть лучше, используя трехместное отношение между мирами. Это допускает миры, в которых нельзя доказать q q и, как следствие, миры, где нельзя доказать p (q q). Их условие истинности для импликации таково:

B C истинно в мире a тогда и только тогда, когда для всех миров b и c, таких, что Rabc (R - отношение возможности) B ложно в b или C истинно в c.

У новичка может уйти какое-то время, чтобы понять это условие истинности. Но после недолгого рассмотрения можно увидеть, что это просто обобщение для условия истинности Крипке для строгой импликации (которое получается, если принять b = c).

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

Это варианты modus ponens

Если мы сделаем тернарное отношение симметричным для первых двух параметров, то есть, введем ограничение, что для любых миров a, b, c если Rabc, то и Rbac, то тем самым сможем доказать, что A ((A B) B).

Тернарное отношение возможности нуждается в философской интерпретации для того, чтобы придать релевантной импликации определенный смысл в этой семантике. За последнее время было разработано три интерпретации, основанных на теориях, описывающих природу информации. Одна интерпретация тернарного отношения, принадлежащая Данну, продолжает идеи Уркухартовой семантики полурешеток. В семантике Уркухарта, вместо того, чтобы трактовать значения переменных как возможные (или невозможные) миры, они рассматриваваются как фрагменты информации. В семантике полурешеток оператор "ο" принимает два операнда, и формула a ο b означает комбинацию информаций в a и b. Семантика Рутли-Мейера не содержит никакой операции "комбинирования" миров, но мы можем получить примерно такой же результат с помощью тернарного отношения. В понимании Данна, Rabc означает, что "комбинация информационных состояний a и b содержится в информационном состоянии c. " (Dunn 1986).

Другая интерпретация предложена Джоном Барвисом (Jon Barwise) (1993) и развита у Ресталла (Restall) (1996). С этой точки зрения миры можно представить как информационно-теоретические "сайты" или "каналы". Сайт - это контекст, в котором получена информация, а канал - это средство, через которое получена информация. Таким образом, непример, когда новости БиБиСи показываются в моей гостиной, мы можем рассматривать гостиную как сайт, а провода, спутники и все остальное, что соединяет мой телевизор со студией в Лондоне, как канал. Применяя теорию каналов для интерпретации семантики Рутли-Мейера, мы считаем, что Rabc имеет следующий смысл: a - это информационно-теоретический канал между сайтами b и c. Тогда мы полагаем, что B C истинно в a - это значит, что - всякий раз, когда a соединяет сайт b, на котором получают B, с сайтом c, то на сайте c получают C.

Замысловато, но так в тексте. Если говорить более простым языком, то a - канал, который соединяет точки b и с. Этот канал обладает таким свойством, что всякий раз, когда в точке b получают информацию B, то в точке c получают информацию C. На фоне таких наворотов, Кажется, гораздо проще написать "если B, то C", тем более, что в определении используется конструкция "когда бы ни... то...", которая синоним конструкции "если... то..." (в английском варианте тоже). Получается определение "сепульки" через "сепуляторий".

Аналогично Марес (Mares) (1997) использовал теорию информации, Дэвида Израэля и Джона Перри (Israel and John Perry (1990)). Согласно их теории, помимо другой информации мир содержит информационные связи такие, как законы природы, обычаи и т.д. Например, Ньютонов мир содержит информацию о том, что любая материя притягивает другую материю. В терминах этой теории информации этот мир содержит информацию о том, что две материальные вещи несут информацию о том, что они притягивают друг друга. С этой точки зрения Rabc тогда и только тогда, когда, согласно информационным связям мира a, вся информаций, которую несет несет мир b, содержится в c. Таким образом, например, если a - Ньютонов мир, и информация о том, что x и y материальны, содержится в b, тогда информация о том, что x и y притягивают друг друга, содержится в c.

Игра словами "содержит" и "несет". Что несет один мир, то содержит другой.

Другая интерпретация, разработанная Маресом (2004). Эта интерпретация использует семантику Рутли-Мейера, чтобы формализовать идею "импликации ситуаций" ("situated implication"). Эта интерпретация рассматривает "миры" в семантике Рутли-Мейера как ситуации.

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

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

Мы можем смоделировать рассуждения с ситуациями используя отношение I (для "импликации"). Тогда мы имеем IabP, где P - высказывание, если и только если информация, в a и в b вместе дает нам право заключить, что в той ситуации P истинно. О самом высказывании мы можем думать как о множества ситуаций. Будем считать B C истинным в a если и только если для всех ситуаций b, в которых истинно B, Iab|C|, где |C| - это множество ситуаций, в которых C истинно. Будем считать Rabc истинным если и только если c является частью любого высказывания P такого, что IabP. С добавлением постулата, что для любого множества высказываний P таких, что IabP, пересечение этого множества X таково, что IabX, мы обнаружим, что импликации, которые окажутся истинными в ситуациях, когда удовлетворяется условие истинности I, - это те же самые импликацияи, которые истинны по условию истинности Рутли-Мейера.

В тексте действительно не указано, с каким таким множеством пересекается множество X. Видимо, с любым.

Таким образом, идея рассуждений с ситуациями дает нам путь для понимания семантики Рутли-Мейера. (Это очень краткая версия обсуждения рассуждений с сиуациями, которая содержится в части 2 и 3 Марес (2004)).

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

Самого со себе использования тернарного отношения не достатчно чтобы избежать парадоксов импликации. Из всего, о чем мы говорили до сих пор, неочевидно, как семантика позволяет избежать парадоксов вроде (p & ~p) q и p (q ~q). Эти парадоксы избегаются через включение противоречивых и недвузначных миров в семантику.

Видимо, под противоречивым миром понимается мир, где не действует закон противоречия p & ~p = false, а под недвузначными мир, где не действует закон исключенного третьего p ~p = true.

Например, если невозможны миры, в которых истинно (p & ~p), то, согласно нашему условию истинности для операции "", формула (p & ~p) q также будет истинной всюду. Аналогично, если во всех мирах истинно (q ~q), то во всех мирах истинно p (q ~q)

Это приводит нас к семантике для операции отрицания. Использование недвузначных и противоречивых миров требует неклассического условия истинности для отрицания. В начале 70-х, Ричард и Вал Рутли (Richard и Val Routley) изобрели их "оператор звездочку" для трактовки отрицания. Этот оператор является опреатором над мирами. Для каждого мира a существует мир a*. И

~A истинно в a тогда и только тогда, когда A ложно в a*.

И снова у нас возникают трудности с интерпретацией части формальной семантики. Одна интерпретация звездочки Рутли принадлежит Данну (1993). Данн использовал бинарное отношение C для миров. Cab означает, что b совместимо с a. Тогда a* - это максимальный мир (т.е. мир, содержащий максимум информации), из тех, что совместимы с a

Есть и другие семантики для отрицания. Одна, придуманная Данном и доработанная Рутли, является четырехзначной семантикой. Эта сематника связана с трактовкой в параконсистентной логике. Другие трактовки отрицания, некоторые из которых используются в релевантной логике, можно найти у Вансинга (Wansing) (2001).

2. Теория доказательств

В настоящее время существует множество подходов к теории доказательств для релевантной логики. Тут и последовательные вычисления по Грегори Минтсу и Данну (Gregory Mints (1972) и J.M. Dunn (1973)) для фрагмента (без отрицания) логики R и элегантный и очень общий подход, названный "Display Логика" Нюэля Белнапа (Nuel Belnap) (1982) По поводу сказанного, смотрите дополнительные материалы:

Логика R

Но здесь я буду рассматривать только систему естественного вывода АНдерсона и Белнапа (Anderson, Belnap) для релевантной логики R

Система естественного вывода Андерсона и Белнапа основана на системах естественного вывода Фитча (Fitch) для классической и интуиционистской логики. Проще всего разобратся с этой техникой на примере.

1. A{1}	Гипотеза
2. (A B){2}	Гипотеза
3. B{1,2}	1,2, E

Автор забыл пояснить, что означают символы в правом столбце. Существуют так называемые "правила введения" и "правила удаления", благодаря которым в формулу вводится еще одна связка или связка удаляется. Скажем, правило введения "" по определенному правилу составляет новую формулу из старых, добавляя в нее дополнительную связку "". В правом столбце "E" означает удаление связки, а "I" введение связки. Сама связка, которая вводится или удаляется, стоит перед символом "E" или "I". Это относительно распространенная система обзначений.

Это простой случай modus ponens. Числа в фигурных скобказ нумеруют гипотезы, применяемые для доказательства формулы. Мы будем называть их "индексами". Индексы в следствии показывают, какие гипотезы использовались для доказательства следствия. В "доказательстве", приведенном ниже, вторая посылка на деле не используется:

1. A{1}	Гипотеза
2. B{2}	Гипотеза
3. (A B){3}	Гипотеза
4. B{1,3}	1,3, E

Это "доказательство" на деле лишь показывает, что переход от A и A B к B релевантно правильный. Поскольку число 2 не присутствует в нижних индексах вывода, то вторая "посылка" на самом деле не считается посылкой.

Аналогично, когда импликация доказана релевантно, то принятие посылки должно быть обязательно использовано для доказательства заключения. Вот пример доказательства импликации:

1. A{1}	Гипотеза
2. (A B){2}	Гипотеза
3. B{1,2}	1,2, E
4. ((A B) B){1}	2,3, I
5. A ((A B) B)	1,4, I

Когда мы не используем гипотезы, как в строках 4 и 5 этого доказательства, то номер гипотезы обязательно должен присутствовать в нижнем индексе формулы, которая стала заключением импликации.

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

1. A{1}	Гипотеза
2. B{2}	Гипотеза
3. (A & B){1,2}	1,2, &I
4. B{1,2}	3, &E
5. (B B){1}	2,4, I
6. A (B B)	1,5, I

Для приверженца релеватной логики первая посылка тут совершенно неуместна. Имеется в виду первая переменная A в последней строке. Чтобы запретить выводы, подобные этому, Андерсон и Белнап дают следующее правило введения конъюнкции:

Из A_i и B_i получаем (A & B)_i.

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

Там, конечно, есть много чего еще в этой системе натурального вывода (см. Anderson и Belnap 1975, Anderson, Belnap, иd Dunn 1992), но для наших целей этого достаточно. Теория релевантности, которой увлекаются по крайней мере некоторые приверженцы релевантной логики, может быть понята в терминах того, как в соответствующей системе естественного вывода записывается реальное использование посылок.

3. Релевантные логические системы

В работе Андерсона и Белнапа централными системами релевантной логики были логика E релевантного следования (entailment) и система R релевантной импликации. Связь между двумя системами заключается в том, что связка следования в E предполагалась строгой (т.е. необходимой) релевантной импликацией. Чтобы показать связь, Мейер добавил оператор необходимости в R (чтобы получить логику NR). Лариса Максимова, однако, обнаружила, что NR и E имеют существенные различия - так как есть теоремы NR (при естественном переводе), которых нет в E.

Под "естественным переводом" имеется в виду наиболее простой способ перевода формул из одной системы в другую

Это поставило некоторых логиков в затруднительное положение. Они должны были решить, то ли принять NR как систему строгой релевантной импликации, то ли заявить, что NR в чем-то неадекватна, и что E должна считаться системой со строгой релевантной импликацией. (Конечно, они могли принять обе системы и согласиться с тем, что взаимосвязь между E и R другая).

С другой стороны, были логики, которые отвергли обе системы R и E. Были такие, кто уподобился Арнону Аврону (Arnon Avron), который принял логику еще строже, чем R (Avron 1990). И были такие, как Ross Brady, John Slaney, Steve Giambrone, Richard Sylvan, Graham Priest, Greg Restall, и другие, кто отстаивал системы более слабые, чем R или E. Одна до крайности слабая система - логика S Роберта Мейера и Эррола Мартина (Robert Meyer, Errol Martin). Как доказал Мартин, эта логика не содержит теорем в форме A A. Другими словами, согласно S. никакая посылка не доказывает сама себя и невозможна аргументация в форме "A, поэтому A", Таким образом, эта логика не допускаят любые циклические переходы.

Под "сильной" логикой имеется в виду та, в которой за истину принимается больше допущений, т.е. в ней больше аксиом.

Дополнительная информация об этих логических системах есть по ссылкам: logic E, logic R, logic NR, and logic S.

Среди аргументов в пользу слабых систем то, что, в отличие от R или E, многие из них разрешимы. Другое свойство слабых систем, которое делает их привлекательными,- то, что они могут быть использованы для построения наивной теории множеств. Наивная теория множеств - это теория множеств, которая включает в себя аксиому свертывания, т.е. для любой формулы A(y),

x y (y x A(y))

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

В классике эта аксиома ведет к парадоксу Рассела, который представляет собой противоречие, а из противоречия можно вывести все, что угодно.

Таким образом, наивная теория множеств, основанная на таких системах, как E и R является, так сказать, "тривиальной". Вот интуитивный набросок доказательства тривиальности наивной теории множеств, использующей правила вывода из логики R. Пусть p - произвольное высказывание:

1. xy(y x (y y p))	Аксиома свертывания
2. y(y z (y y p))	1, Existential Instantiation
3. z z (z z p)	2, Universal Instantiation
4. z z (z z p)	3, по определению "", удаление "&"
5. (z z (z z p)) (z z p)	Аксиома сокращения (Contraction)
6. z z p	4,5, Modus Ponens
7. (z z p)) z z	3, по определению "", удаление "&"
8. z z	6,7, Modus Ponens
9. p	6,8, Modus Ponens

См. систему аксиом в R

Тем самым мы показали, что произвольное высказывание может быть доказано в наивной теории множеств. Это печально известный Парадокс Curry. Существование этого парадокса привело Grishen, Brady, Restall, Priest, и других к отказу от аксиомы сокращения

((A (A B)) (A B))

Брэди (Brady) показал, что если убрать сокращение и некоторые другие ключевые соглашения из R, то мы получим логику, в которой можно принять аксиому свертывания без того, чтобы получить тривиальную систему. (Brady 2005).

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

1. A (A B){1}	Гипотеза
2. A{2}	Гипотеза
3. A B{1,2}	1,2, E
4. B{1,2}	2,3, E
5. A B{1}	2-4, I
6. (A (A B)) (A B)	1-5, I

Благодаря тому факту, что нижние индексы - это множества, появляется доказательство сокращения. Мы не следим, сколько раз (больше одного) гипотеза используется в доказательстве. Для того, чтобы избавиться от сокращения, нам нужен способ подсчета использований гипотез. Таким образом, системы естественного вывода для систем, свобожных от сокращения используют релевантные числовые "мультимножества" вместо множеств - это структуры, в которых подсчитывается число вхождений каждого элемента, но порядок вхождения не имеет значения.

В некоторых языках программирования есть такой контейнер "multiset". В него можно "положить" объект несколько раз, в результате потом мы сможем узнать, сколько раз его туда положили, но не сможем узнать, в каком порядке положили объекты. А в обычном множестве нельзя узнать и сколько раз положили.

Можно сконструировать даже более слабые системы, в которых сохраняется и порядок использования гипотез (см. Read 1986 и Restall 2000).

4. Применение релевантной логики

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