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

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

Теперь мы можем уточнить, что мы понимаем под подходящим расширением до существует ли независимая аксиомати-

зация формулами I, В, С, W, K1 и X? [Карпенко 1992].

В силу теоремы Тарского-Бернайса (см. [Lukasiewicz and Tarski 1930]) импликативный фрагмент классической

пропозициональной логики аксиоматизируем посредством формул

В', К и Р с правилами МР и подстановкой, где

(закон Пирса).

Как уже отмечалось, обычно получают за счет добавления

к формулы Р, но закон Пирса в качестве кандидата на место формулы X явно не пригоден, посколькууже является

аксиоматизацией т. е. и, значит, множество

формул не является независимой аксиоматизацией

Покажем, что

Утверждение 4.

Утверждение 5.(см. [Wajsberg 1937], [Prior 1962], [Тапака 1967]).

Отсюда, в силу теоремы Тарского-Бернайса, есть

.

Таким образом, решение проблемы надо искать посредством ослабления формулы Р. При этом X должна быть достаточно «сильной», чтобы формулы аксиоматизировали

и достаточно «слабой», чтобы все формулы были независимы.

Найдена подходящая формула X1:

гдеесть подстановочный случай форму-

лы есть подстановочный случай формулы

есть подстановочный случай формулы

Теорема 2. Множество формул является незави-

симой аксиоматизацией (см. [Карпенко 1993; 1997]).

Заметим, что здесь при доказательстве независимости I, В, С, W, K1 используются те же самые матрицы, что и в Теореме 1. Для доказательства независимости аксиомы X1 нужна

Матрица 6 (трехзначная импликация Рейтинга):

Итак, поставленная выше проблема расширения до решена. Правда, формула X1 содержит 21 переменную и 5 ее подформул являются тавтологиями классической пропозициональ­ной логики TV, т. е. аксиома X1 является неорганической в смысле Вайсберга и Лесневского (см. [Чёрч I960]). Поэтому жела­тельно было бы упростить формулу X1.

Заметим, что вся формулаесть подстановочный

случай формулы

(Данная формула является одной из аксиом в аксиоматизации бесконечнозначной логики Лукасевича(см. выше раздел 8,1).)

которую мы обозначили посредством D (см. Утверждение 5, фор­мула 11). В итоге, формула Х2 выглядит следующим образом:

Теорема 3. Множество формул является незави-

симой аксиоматизацией [Карпенко 1993].

(і). Проблемы возникают с доказательством независимости аксиомы В. В указанных работах при доказательстве этого случая использована метатеорема С. Яськовского [Jaskowski 1948]. Из ее доказательства следует, что имеется шестиэлементная матрица, ко­торая фальсифицирует аксиому В. Однако в [Ulrich 1994] была найдена подходящая четырехэлементная

Матрица 7:

Утверждение7.

Таким образом, теорема 3 доказана.

Формула Х2 тоже является неорганической (три ее подформу­лы есть тавтологии TV), но она состоит из вхождений только двух различных переменных, число их вхождений 10 и к тому же триви­ально доказывается пункт (ii).

Теперь построим решетку подлогик множества

{I, В, С, W, K1, X2}. Для простоты изображения в качестве нуля решетки возьмем логику BCI:

Импликативные логики, указанные на вершинах этой решетки, хорошо известны и описаны в литературе (кроме Особый интерес представляет логика ВСКХ2.

Утверждение 8.

Доказательство очевидно.

Логика BCKD является фрагментом бесконечнозначной логи­ки Лукасевича , и впервые изучались в [Rose and Rosser 1958]. В [Dyrda 1985] эта логика получила название "коммутативная ВСК-логика" и рассмотрены ее расширения.

Заметим, что

Логикапримечательна тем, что добавление к ней закона

линейности

дает импликативный фрагмент логики (см. [Rose 1956] (в Другой формулировке) и [Meyer 1966]).

( В [Wozniakowska 1978] дается другая аксиоматизация как результат отделимости: К, D и

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

Утверждение 9.

Для доказательства используется

Матрица 8:

Очевидно, что Х1 доказуема в

4. Максимальная решетка логики и

В связи с тем, что имеются разные -конструкции, возникает естественный вопрос о классе формул X1. В [Slaney and Bunder 1994] ставятся следующие две конкретные проблемы:

(1) Существует ли бесконечное число различных систем

(2) Имеются ли наиболее слабая, и наиболее сильная сис­темы

Постановка проблемы обязана тому, что указанные авторы в качестве кандидата на место формулы X предложили формулу

(Эта формула под названием U появляется в разделе 8.5.3.1 и является одной из аксиом в аксиоматизации импликативного фрагмента логики RM.)