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

ционально эквивалентны. А это значит, что логику V2 можно раз­вивать на основе оператора g, который будет играть особую роль в разделе 5.4.6 (см. также раздел 5.4.4.2).

5.4.4. Логика Белнапа DM4

В 1962 г. А. Андерсон и Н. Белнап предложили рассмотреть мно­жество выводов, которые они назвали "тавтологическими следст­виями", или "следованиями первой ступени" (first degree enlailmenf). Содержательно, это множество выводов должно было включать в себя все разумные выводы, содержащие связки а

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

вхождений связки →. Формализация этих выводов привела к сис­теме Efdo [Anderson and Belnap 1963], которая является фрагментом системы логики следования Е и R (см., например, [Dunn 1986]). Т. Дж. Смайли нашел четырехзначную матрицу которая является характеристической для Efdс (см. [Anderson and Belnap 1975]):

где

Операции есть в точностииз четырехзначной -

модальной логики Лукасевича.

Позже Дж. Данн предложил различные семантики для тавтоло­гических следствий, некоторые из котрых были тесно связаны с че­тырехзначной матрицей Смайли. В [Dunn 1976] Данну принадле­жит основополагающая идея, которая заключается в отождествлении четырех значений с четырьмя подмножествами булева множества {1,0}, т. е.

В работах [Belnap 1977] предложена "полезная четы­рехзначная логика", которая со временем вызвала необычайный интерес, особенно среди специалистов в области информатики и искусственного интеллекта. Исходная интенция Белнапа заключа­ется в том, что компьютер должен нормально работать в условиях неполноты и/или противоречивости поступающей информации (информация может поступать из различных (возможно, независи­мых) источников). Белнаповский компьютер оценивает истинность высказывания в соответствии с полученной информацией. Тогда, кроме двух стандартных (классических) случаев, когда компьютеру сообщается, что высказывние является либо истинным - {1}, либо ложным - {0}, возможны еще два случая, когда источники ничего не говорят об истинности данного высказывания, т. е. возникает си­туация "истинностно-значного провала" (gap) — , или же сообща­ется противоречивая информация, и тогда возникает ситуация "ис-тинностно-значной пресыщенности" (glut) - {1, 0}. Для этих четырех "информационных ситуаций" Белнап вводит, соответст­венно, следующие четыре истинностных значения: Т (True), F (False), N (None) и В (Both). Мы для унификации и для простоты чтения будем использовать, как и ранее, следующие истинностные значения: 1, 0, п и b.

Далее Белнап предлагает рассмотреть на множестве два частичных порядка. Первый порядок естественно возникает на

множествеи является отношением теоретико-

множественного включения Тогда элементы 1 и 0 находятся ме­жду п и b и являются несравнимыми. На диаграмме Хассе это вы­глядит следующим образом:

Очевидно, этот порядок задает полную решетку, которую Белнап, следуя Д. Скотту [Scott 1973], называет "аппроксимационной решеткой" и обозначает посредством А4, а сам решеточный поря­док на А4 может быть интерпретирован как "информационный" порядок чем "выше" находится элемент данной решетки, тем больше информации он несет.

При другом порядке элементы п и b находятся между 1 и 0 и являются несравнимыми. Заметим, что новую упорядоченность элементов можно получить за счет поворота предыдущей решетки вправо:

Этот порядок тоже задает полную решетку, которую Белнап называет "логической решеткой" и обозначает посредством L4, а сам решеточный порядок на L4 может быть интерпретирован как "логический" порядок чем "выше" находится элемент данной решетки, тем больше истинности он несет. Именно логике, осно-ванной на свойствах этой решетки, Белнап уделяет основное вни­мание.

Отношение играет особую роль, поскольку именно этот по­рядок детерминирует работу белнаповского компьютера. Перед Белнапом стоит задача определения логических связок (решеточ­ных операций) дизъюнкции и конъюнкции Исходя «всего лишь из трех соображений: таблиц истинности для двузначной ло­гики, монотонности и соответствия между Белнап (см. [Белнап 1981]) получает в точности таблицы истинности для как в матрице Смайли для Efdс. В свою очередь, отрицание ~ также совпадает с отрицанием в матрице Смайли. Такое отрицание называется отрицанием Де Моргана. Логику с такими связками обозначают посредством DM4, поскольку ее алгебраическим при­мером является решетка Де Моргана (квазибулева алгебра), четырехэлементный случай которой был приведен уже в [Biafynicki-Binila and Rasiowa 1957] (см. также [Rasiowa 1974]).

М. Фиттинг [Fitting 1989] (см. также [Fitting 1992]) обратил внимание на то, что четырехзначная логика Белнапа есть не что иное, как обобщение трехзначной логики Клини К3. Более того, ес­ли мы посмотрим на истинностные таблицы, приведенные выше для то увидим, что ограничения этих связок на множестве

в точности дают одну и ту же трехзначную ло­гику Клини К3.

Белнап ничего не говорит о связке импликации и оставляет от­крытым вопрос о множестве выделенных значений. Заметим, что при одном выделенном значении 1, как и при двух выделенных значениях 1 и b, эта логика не имеет тавтологий. Тем не менее, по­рядок позволяет ему естественно ввести отношение логического следования. Пусть v (оценка) есть отображение множества пропо­зициональных переменных на множество Тогда имеем:

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

Оказывается, это отношение логического следования эквива­лентно приведенному нами для логики Клини К3 (см. 3.4.1). Перепишим его следующим образом:

Теперь это отношение определяется для DM4 с множеством выделенных значений {1, b}. Доказательство эквивалентности см. в [Font 1997] и детально и независимым образом в [Зайцев и Шрамко 2004].

Конечно, возникает вопрос, каково отличие DM4 от К3, если первая есть обобщение второй и отношения логического следова­ния совпадают? Тщательному изучению DM4 посвящена статья [Font 1997] (см. добавление в [Font 1999]). Здесь представлено секвенциальное исчисление для DM4, его взаимоотноше­ние с подобными исчислениями для трехзначной логики Клини К3 и для классической логики С2. Главный результат заключается в следующем: класс решеток Де Моргана является алгебраическим примером DM4; точно так же, как класс булевых алгебр является алгебраическим примером С2. См. также [Рупко 1999]. Напомним, что операции матрицы для К3 образуют решетку Клини.

Четырехзначная логика Белнапа DM4 оказалась очень полез­ной в качестве базиса для других логик. Наиболее интересны её расширения модальными операторами, эндоморфизмами на дист­рибутивных решетках и, конечно, связкой импликации.

5.4.4.1. Логика DM4 с модальными операторами

На самом деле логика де Моргана как эквивалент алгебры Де Мор­гана была построена уже в [Ермолаева 1973], которая исходила из [работы Хао Вана [Wang 1961], где рассматривались два варианта импликации в трехзначной логике: импликация Лукасевича и импликация Клини (см. выше гл. 3).