Логика высказываний

 

 Импликация  Лукасевича и трехзначная интуиционистская логика.

 

Трехзначная интуиционистская логика С₃ появилась в работе А.Гейтинга, где впервые было сформулировано пропозициональное (и предикатное) интуиционистское исчисление Н. Аксиоматизация последнего получается посредством удаления закона исключенного третьего ۷ р из аксиоматики классической логики С₂ (см. выше 1.4.).

Матрицы для G₃, появившиеся в результате доказательства независимости Н, выглядят следующим образом:

 

 

p	ךּ p
1	0
½	0
0	1

=>	1	½	0
1	1	½	0
½	1	1	0
0	1	1	1

 
        Истинностные таблицы для ۷ и ^ в точности совпадают с таблицами для этих связок в L₃ и К₃, однако разница между системами связок весьма существенна, поскольку в G₃ через ךּ p и p _=> qнельзя выразить p ۷ q, p ^ q. Но

                    

Отсюда следует, что в качестве исходных связок в G₃ можно взять связки Легко убедиться, что ни , ни не являются здесь тавтологиями, хотя первая есть тавтология в L₃.

Впервые G₃ была аксиоматизирована Я. Лукасевичем. Она получается за счет добавления к аксиомам интуиционистского пропозиционального исчисления Н аксиомы  (ךּ p => q) => (((q => p) => q) => q).

 Нетрудно показать, что логические связки G₃ выразимы посредством связок из L₃:

              ךּ р =~ (~р → р),

      p => q = ךּ(~(p → q))۷q.

Впервые выразимость связок из G₃ посредством L₃ была представлена Г. Мойсилом, но формула для выразимости р => q гораздо сложнее. У Л. Монтейро это выглядит следующим образом:

              p => q = L ~ p ۷ q (M ~p ^ Mq)

Заметим, что результат  Мойсила позволяет дать аксиоматизацию L₃ на основе интуиционистской импликации =>, что и было сделано Л. Итурриоз.

Очевидно, что G₃ не эквивалентна L₃, поскольку ~ р нельзя выразить связками G₃. Таким образом, G₃ L_3. Однако если добавить связку ~ к G₃, то, как показал Мойсил, получим L₃:

                                 p → q = (p =>q) ۷ (~ q => ~ p)

Можно дать другое определение  трехзначной импликации Лукасевича, используя наравне с интуиционистской импликацией => дуальную ей, которая обозначается посредством <= и называется «брауэровой». Последняя определяется следующим образом p <= q = ~ (~ p => ~ q)

Отрицание Ґ, дуальное к ךּ, определяется как Ґр = р <= 1.

Оказывается, посредством связок ךּ , Ґ , ۷, ^ можно определить отрицание Лукасевича:

     ~ р = ךּр ۷ (p ^ Ґp)

Более того, посредством  этих связок можно определить также импликацию Гейтинга: p => q = (ךּp ۷ ךּךּq) ^ (Ґp ۷ q)

Отсюда следует, что  трехзначная логика Лукасевича L₃ есть в точности трехзначная Н-В-логика. Заметим, что в ней импликацию Лукасевича можно определить следующим образом:

 

 

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

Для того чтобы перейти к алгебраизации L₃, сначала рассмотрим исключительно важный класс алгебр, а именно алгебры Гейтинга и связанные с ними другие алгебраические структуры. Алгебры Гейтинга являются алгебраическим примером интуиционистской логики.

Пусть х, у € L. Элемент z € L. называется псевдодополнением элемента х относительно у, если z - наибольший элемент со свойством . Относительное псевдодополнение обозначается посредством х => у. Решетка L называется импликативной, если х => у существует для всех элементов х, у € L. Заметим, что решетка с => обладает наибольшим элементом 1, так как для любого х, х => х = 1; и, главное, решетка с => является дистрибутивной. Каждая импликативная решетка с наименьшим элементом 0 есть алгебра Гейтинга. Или, по-другому, алгебры Гейтинга являются решетками с 0, резидуальными относительно пересечения, где «резидуалом» относительно ^ является как раз операция =>, определяемая следующим образом:

              т.т.т., когда

Как эквациональный класс <L, ۷,^,=>, 0, 1> есть алгебра Гейтинга, если <L, ۷,^,, 0, 1> есть ограниченная дистрибутивная решётка и для бинарной операции => выполняется следующие три тождества:

(H1). х^(х=>у) = х^у

(1-12). х^(у=>z) = х^(х^у => х^z).

(113). (х^у=>х) ^z=z.

Очевидно, любая булева алгебра есть алгебра Гейтинга.

Дистрибутивные решетки с операцией => (но в других обозначениях), а также с дуальной к ней операцией <= впервые исследовались Т.Сколемом, начиная с 1919 г. Такие алгебры Х. Карри называет сколемовскими структурами. Алгебры Гейтинга под названием брауэровы алгебры были введены Г.Биркгофом в 1940 г.

Алгебра <L, ۷,^,=>,<=, 0, 1> называется дважды  гейтинговой алгеброй, или дважды брауэровой алгеброй, или полубулевой алгеброй, или алгеброй Сколема, если <L, ۷,^,=>, 0, 1> есть алгебра Гейтинга, а <= есть бинарная операция, дуальная к =>, т.е. элемент z(=х<=у) Является наименьшим элементом со свойством хUz≥у. Операция х<=у называется псевдоразностью. Обычно алгебра <L, ۷,^,<=, 0, 1> изучается под названием брауэровой алгебры. Или, по-другому, алгебры Брауэра являются решетками с 1, резидуальными относительно объединения:

                          х≥у=>z т.т.т., когда х۷у≥z.

Алгебра <L, ۷,^,=>,~, 0, 1> называется симметрической алгеброй Гейтинга, если <L, ۷,^,=>,0, 1> есть алгебра Гейтинга и <L, ۷,^,~, 0, 1> есть алгебра де Моргана. Операция ~ на решетке L позволяет рассмотреть принцип дуальности: каждое утверждение, доказанное для ۷, ^, ~ остается истинным, если ۷, ^  заменить соответственно на ^ и ۷. Более того, здесь х<=у = ~ (~х =>~у). Таким образом, симметрическая алгебра Гейтинга есть дважды алгебра Гейтинга.

Заметим, что в алгебре Гейтинга имеет место ךּх = х =>0, где унарная операция ךּ называется псевдодополнением (интуиционистское отрицание), и Ґх = х<=1, где унарная операция Ґ называется дуальным псевдодополнением.

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

Алгебра  <L, ۷,^,ךּ, 0, 1> называется р-алгеброй, если <L, ۷,^, 0, 1> есть ограниченная решётка и для любого х€L элемент ךּх является псевдодополнением элемента х. Алгебра <L, ۷,^,ךּ, Ґ, 0, 1> называется дважды р-алгеброй, если <L, ۷,^,ךּ, 0, 1> есть р-алгебра и <L, ۷,^,Ґ, 0, 1> — дуальная р-алгебра.

Дистрибутивная р-алгебра  называется стоуновой, если она удовлетворяет стоунову тождеству

                                  ךּ х ۷ךּ ךּ х=1,

и дважды стоунова, если выполняется также тождество

                                  Ґ х^Ґ Ґ х=0.

Если к алгебре Гейтинга <L, ۷,^,=>,0, 1> добавить, например, закон исключенного третьего х۷ ךּ х = 1 или закон двойного отрицания ךּ ךּ х = х то получим аксиоматизацию булевой алгебры.

Теперь рассмотрим алгебраические примеры трехзначной логики Лукасевича L₃. В предыдущем разделе было показано, что логики со множествами связок {→,~} и {٧,^,~, М} эквивалентны. Именно в этой сигнатуре Г.Мойсилом было введено понятие трёхэлементной алгебры Лукасевича, аксиоматизация которой была значительно упрощена А.Монтейро : Алгебра

                       Ĺ₃=<{1, ½,0}, ۷,^,~, М, 1>

есть трёхэлементная алгебра Лукасевича, где <{1, ½,0}, ۷,^, 1> есть дистрибутивная решетка с 1 и для унарных операторов ~ и М выполняются следующие тождества:

1. ~~х=х,

2. ~ (х^у)=~х۷~у,

3. . ~х۷Мх=1,

4. х^~х=~х^Мх,

5. М(х^у)Мх^Му.

Или, по-другому, трёхэлементная алгебра Лукасевича Ĺ₃ есть алгебра де Моргана, снабженная операцией М, удовлетворяющей условиям (3), (4), (5). Или, по-другому, Ĺ₃ есть алгебра Клини, снабженная операцией М, удовлетворяющей условиям (3), (4). Заметим, что существует большое число алгебраических построений для L₃, эквивалентных между собой. Чтобы все их систематизировать, обратим внимание на следующий факт: все сформулированные выше алгебры, начиная с алгебры де Моргана на двухэлементном множестве {0, 1} превращаются в булеву двухэлементную алгебру.

С введением третьего элемента проблема становится не столь тривиальной, однако, все указанные дважды алгебры, а также симметрическая алгебра Гейтинга и некоторые объединения их сигнатуры являются трёхэлементными алгебрами Лукасевича Ĺ₃, поскольку трёхзначные логики со множествами связок {٧,^,ךּ,Ґ},{٧,^,=>,<=}, {٧,^,=>,~}, {٧,^,=>,Ґ}, {٧,^,<= ,ךּ}, {٧,^,~,ךּ } эквивалентны.

 Заметим, что приведенную  выше аксиоматизацию Ĺ₃ можно рассматривать как аксиоматизацию в терминах алгебры де Моргана с псевдодополнением ךּ если заменить всюду оператор М на ךּךּ.

Интересно проследить изменение  алгебраических структур с увеличением  числа элементов. Например, известно, что если n > 3, то отрицание де Моргана нельзя определить посредством псевдодополнения и дуального псевдодополнения вместе с решеточными операциями. Всё дело в том, что функциональные свойства L₃ настолько «богаты» и обладают таким «критическим» свойством, что допускают столь много различных алгебраических характеризаций.

 

 

 

 

 

 

   Заключение

 Пионеры многозначных  логик Э. Пост, Я. Лукасевич и Д.А. Бочвар создавали свои системы, имея разные цели. N-значные функционально полные системы Э. Поста Р_n являются обобщением (с циклическим отрицанием) двузначной логики, не имеющими сколь-нибудь семантически содержательной интерпретации. Трёхзначная логика Бочвара В₃ с промежуточным истинностным значением “бессмысленно” предназначена для формализации логических и семантических парадоксов (её семантическое истолкование очевидно — потеря смысла высказываний в формально корректном языке). Трехзначная логика Я. Лукасевича, созданная им в 1920 г., имела философскую мотивацию и была связана с его идеей опровергнуть аристотелевскую доктрину логического фатализма, основанную на двузначной логике.

Однако n-значные обобщения логики Я Лукасевича оказались интересным логико-математическим формализмом, который, не имея ясного семантического истолкования (имеются в виду истинностные значения, отличные от “истины” и “лжи”), породил многочисленные исследования логического и алгебраического характера.

Многочисленные попытки  построить семантическое истолкование n-значных логик Я. Лукасевича  бывали остроумными, но не исчерпывающе убедительными (например, интерптретация Скотта посредством идеи “степени ошибки”).

Первым глубоким результатом, устанавливающим связь между логиками Я. Лукасевича и арифметическими фактами, была теорема Р. Мак-Нотона о L_∞ и её конечных фрагментах.

Затем были обнаружены факты связи L_n, и простых чисел, а именно было показано, что логика Я. Лукасевича L_n функционально предполна т.т.т., когда (n-1) — простое число, а также было обнаружено, что L_n, имеет I-J-совершенную дизъюнктивную нормальную форму т.т.т., когда (n-1) есть степень простого числа.

Напомним, что множество  функций Х n-значной логики называется предполным в Р_n, если Х≠Р_n, и для всякой F такой, что F € Х, [ХU{F}] = Р_n, где [ХU{F}] — множество всех суперпозиций функций из ХU{F}.

Александр Степанович Карпенко в многочисленных работах получил  ряд глубоких и трудно доказуемых результатов, устанавливающих интересные связи между логиками L_n и логиками функционально эквивалентными L_n с одной стороны, и арифметическими фактами, с другой стороны. Он построил характеризации чётных чисел и нечётных чисел, соответственно посредством логических исчислений, функционально эквивалентных логикам Я. Лукасевича.

Весьма эффектными и  труднодоказуемыми результатами А. С. Карпенко являются теоремы о характеризации простых чисел через аналоги штриха Шеффера для соответствующих n-значных логик.

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

В 1979 г. д. А. Бочвар высказал идею о том, что многозначные логики следует рассматривать как фрагменты формализованных семантик. Если принять эту идею, то для трёх трёхзначных логик В₃ (логика Бочвара), Е₃ (логика Эббингхауза) и L₃ (логика Лукасевича) имеют место следующие включения (относительно множеств тавтологий и множества функций в них выразимых): В₃‹ Е₃‹ L₃. для этих логик допустима следующая интерпретация: В₃—логика “математической бессмыслицы” (парадоксальность высказываний, деление на ноль и т. п.), Е₃ — логика “лингвистической бессмыслицы”, L₃ — логика неопределенности (понимаемой в том смысле, что промежуточное истинностное значение может быть либо истинным, либо ложным, но этот факт не установлен).