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

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

Рассмотрим бинарное отношение ≈ на множестве формул Fm пропозиционального языка классической логики т. т.т.,

когда А≡В есть доказуемая формула. Легко убедиться, что ≈ есть отношение эквивалентности на множестве формул Fm и является конгруэнцией на алгебре формул Тогда

обозначает фактор-множество по отношению эквивалентности ≈ . Класс эквивалентности, содержащий А, будем обозначать посредством |A|, Для произвольных классов эквивалентности |A| и |B| из пусть и Тогда алгебра называется алгеброй Линденбаума (классической логики) и есть не что иное, как булева алгебра. Другими словами, алгебры Линденбаума классической пропозициональной логики, полученные подобным образом, являются (с точностью до изоморфизма) счетными булевыми алгебрами. Нулевым элементом 0 здесь является класс всех противоречий а единицей 1 - класс эквивалентности, состоящий из всех тавтологий

Легко видеть, что между эквивалентностями классической логики высказываний С2 и тождествами булевой алгебры сущест­вует соответствие. Например, между формулой и первым тождеством в (II). Более того, в С2 т. т.т,, когда А* = 1 в где A* есть аналог А на языке алгебры Таким образом, возникают средства для алгебраического доказательства дедук­тивной полноты логических исчислений. Основываясь на этом, А. Тарский в 1935 г. в точности устанавливает связь между классическим пропозициональным исчислением и булевой алгеброй (так называемый метод Линденбаума-Тарского).

Л. Хенкином, Р. Сикорским, Е. Расёвой и др. было осознано, что этот метод может быть приме­нен к другим логикам со связкой импликации, удовлетворяющей некоторым базисным свойствам. Такого рода обобщение было проведено в книге Е. Расёвой [Rasiowa 1974], где впервые вводится понятие «алгебраического примера (counter-part) логики». Магистральное развитие алгебраической логики состояло в систематическом исследовании широкого класса логик алгебраическими методами. Одной из целей явилось установление общего критерия для класса алгебр (или для класса математических объектов, тесно связанных с алгебрами) быть алгебраическим примером логики и развитие для этого самих методов.

Первым примером алгебраической семантики для пропозициональных логик являются класс ВА булевых алгебр, который является алгебраической семантикой для классической логики С2. Каждая булева алгебра имеет наибольший элемент согласно их естественному порядку, который обычно обозначается посредством 1А. Этот элемент взят как выделенный, относительно которого дана алгебраическая семантика. Тогда точное определение алгебраической семантики для классической логики С2 выглядит следующим образом:

т. т.т., когда для каждой и каждой оценки v

на А, если для всех тогда

Импликация слева направо есть теорема об алгебраической корректности, а импликация в другую сторону есть теорема об алгебраической полноте, доказательство которой основано на методе Линденбаума-Тарского (см. изложение этого метода в [Jansana 2006]).

Заметим, что если вместо класса ВА булевых алгебр возьмем класс алгебр Рейтинга, то этот класс является в точности алгебраической семантикой (в выше определенном смысле) для интуиционистской пропозициональной логики Int.

Класс логик, для которых имеет место алгебраическая семантика, обычно детерминированная алгеброй Линденбаума, получил название протоалгебраизуемых логик [Blok and Pigozzi 1986]. Протоалгебраизуемые логики включают в себя почти все хорошо известные логики и составляют главный класс логик, для которых углубленные методы универсальной алгебры могут быть применены к их логическим матрицам, чтобы получить строгие и интересные результаты. Именно алгебры Линденбаума являются фундаментальным свойством протоалгебраизуемых логик.

Однако не всякая логика может быть алгебраизуема подобным образом. Для этого логическая связка эквиваленции должна быть подходящей. Например, в релевантной логике R и логике следо­вания Е (см. ниже раздел 8.5) существуют теоремы А и В, для которых импликация А → В не есть теорема. Следовательно, множество всех теорем не совпадает с классом эквивалентности, определенным отношением ≈. Поэтому встал вопрос об обобщении метода Линденбаума-Тарского, т. е. ставится вопрос о подходящем обобщении отношения конгруэнтности на алгебрах и построении более общей теории алгебраизуемых логик. В работе В. Блока и Д. Пигоцци [Blok andPigozzi 1989] вводится лейбницево отношение конгруэнтности', строго определяется понятие алгебраической семантики (см. выше), а понятию алгебраизуемая логика дано математически точное определение. Основополагающая идея состояла в следующем: логика является алгебраизуемой, если существует класс алгебр, относящийся к этой логике точно так же, как существует класс булевых алгебр, относящихся к классической логике. Заметим, что понятие алгебраизуемой логики, введенное в этой работе, относится только к финитарным логикам, которые еще называются "конечно-алгебраизуемыми | логиками".

Здесь уже релевантная логика R является алгебраизуемой, но не Е (об этих логиках см. в разделе 8.5.1). Неалгебраизуемыми оказываются импликативные фрагменты этих логик, в то время как и алгебраизуемы. Доказано также, что известная паранепротиворечивая логика да Косты C1 неалгебраизуема (см. об этом ниже в разделе 8.6.3.1), а следовательно, все логики из класса Сn. С алгебраизацией паранепротиворечивых логик вообще возникают трудности, в силу отсутствия в них правила подстановочности эвивалентности (см. там же). Тем не менее алгебраическая семантика имеет место для исключительно широкого класса логических систем. См. [Font and

Jansana 1996] и [Blok and Rebagliato 2003]. Наличие алгебраической семантики для некоторой логики L имеет большое методологическое значение. Речь идет о связи между отдельным металогическим свойством специфической логики L, которая является алгебраизуемой, и алгебраическим свойством ассоциированного с нею класса алгебр Alg(L). Например, L допускает строго полную гильбертовскую аксиоматизацию т. т.т., когда т. т.т., когда Alg(L) есть финитно аксиоматизируемое квази-многообразие. Алгебраизация логики достигла такого уровня, что возникла уверенность, что всё в логике есть законы алгебры (см., например, [Halmos and Givant 1998]).

Абстракция метода Линденбаума-Тарского играет главную роль в развитии самой алгебраической логики. В результате в конце XX века появился термин "абстрактная алгебраическая логика" (см. обзор [Font, Jansana, and Pigozzi 2003]). Здесь дается классификация логик под названием "иерархия Лейбница". Приводится 10 классов логик (см. рис. 1 на с. 49), в один из которых входит всего лишь классическая логика С2 наряду с интуиционистской логикой Int, нормальными модальными логиками Льюиса, различными конечнозначными логиками, бесконечнозначной логикой Лукасевичаи т. д. Алгебраизацию многозначных логик Лукасевича мы в дальнейшем рассмотрим,

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

4.5.1. Алгебраизация

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

Именно в этой сигнатуре в [Moisil 1940] было введено понятие трехэлементной алгебры Лукасевича, аксиоматизация которой была значительно упрощена А. Монтейро [Monteiro A. 1963]: Алгебра

есть трехэлементная алгебра Лукасевича, где