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

Заметим, что такое определение четырехзначной импликации в явном виде (и в связи с логикой DM4) впервые встречается в

[Avrori 1991]. Более того, здесь показано, что как и трехзначные логики RM3 и PCont, точно так же и четырехзначные логики BN4 и Par функционально эквивалентны:

5.4.4.4. Бирешетки

М. Гинзберг [Ginsberg 1986; 1988] был первым, кто обобщил идеи Белнапа и рассмотрел произвольное множество с двумя частичны­ми порядками, каждый из которых на этом множестве задает свою собственную полную решетку. Главное то, что эти две решетки существуют не сами по себе, а связаны между собой. Это обобще­ние можно представить следующим образом.

Пусть есть решетки, каждая с наибольшим и

наименьшим элементом. Посредством обозначается

где

Отсюда легко дать характеризацию решеточных операций в

Такая алгебраическая структура была названа бирешеткой (bilattice) и основной мотивацией для Гинзберга было использование бирешеток в качестве основания в различных системах искусствен­ного интеллекта. Если L1 и L2 каждая является дистрибутивной решеткой, то тоже дистрибутивная решетка. Более того, Гинзберг пока­зал, что имеют место все 12 возможных дистрибутивных законов, т. е. операции взаимосвязаны между собой. Например,

В [Ginsberg 1988] доказана теорема представления для бирешеток: еслиесть дистрибутивная бирешетка, тогда имеются ди­стрибутивные решетки L1 и L2 такие, что изоморфна

Иногда бирешетку представляют в виде

где В есть непустое множество.

Следуя Гинзбергу, на вводится регулярное отрицание ~ (здесь оно обычно обозначается посредством которое удовле­творяет следующим условиям:

Специальный интерес для нас представляет следующий при­мер. Пусть L1 ~ L2 есть двухэлементная решетка {0, 1}, где 0 < 1. Тогда есть не что иное, как "комбинация" двух решеток А4 и L4, где 1 есть <1, 0>, 0 есть <0, 1>, b есть <1, 1> и п есть <0, 0>. В итоге мы имеем наиболее простую нетривиальную бирешетку, которая обозначается посредством FOUR,

Целый ряд работ логического характера, связанных с бирешетками, принадлежит М. Фиттингу. В [Fitting 1989] вводятся обо­значения для решеточных операций в решетке кото­рые называются соответственно 'доверчивость' (gullability) и 'консенсус' (consensus):

Здесь же впервые дается аксиоматизация в виде аналитических таблиц логики со множеством связок Вводится

также унарная операция под названием "конфляция"

(conflation): Эта операция есть не что иное, как рассмотренный выше эндоморфизм g.

Для всех этих трех операций Фиттинг дает содержательное обоснование. В [Fitting 1990] вводится важное понятие сплетен­ной (interlaced) бирешетки: Бирешетка (с отрицанием или без него) называется сплетенной, если каждая из операций является монотонной относительно обоих порядков Это

понятие является прямым обобщением клиниевского понятия регу­лярности трехзначных логических связок (см. 3.4.1). Из условия сплетенности следуют такие "странные" (см. [Белнап 1981) свойства операций, как а также

Фиттинг показал, что каждая дистрибутивная бирешетка является сплетенной [Fitting 1992]. Новые операции понадобились Фиттингу при разработке языка логики программирования, имею­щего дело с базами распределенного знания [Fitting 1991]. Он был первым, кто осознал значимость бирешеток для семантики логики программирования. Исходя из работы [Dunn 1976], Фиттинг в [Fit­ting 1989] (см., также [Fitting 1994]) представил исчисление, осно­ванное на FOUR, в виде аналитических таблиц. Интересно, что во второй работе Фитинг по аналогии с Кз обобщил логики и LISP (см. выше раздел 3.4) до дистрибутивных бирешеток в том смысле, что каждая из них является частью соответствующих би­решеток. Наконец, Фиттинг первым [Fitting 1992; 1994] исследует бирешетки с отрицанием ~х и конфляцией —х (в последней работе доказывается теорема представления). Заметим также, что суммар­ный итог многочисленных работ Фиттинга по бирешеткам можно найти в [Fitting 2006].

Несколько слов об обобщении бирешеток. В [Lakshrnanan and Sadri 1994] бирешетки расширяются третьим отношением порядка, названным "отношением точности", предназначенным для эффек­тивного рассмотрения различных степеней веры и сомнения в де­дуктивных вероятностных базах данных. В [Shramko, Dunn and Ta-kenaka 2001] (см. также [Шрамко 2002]) введено понятие трирешетки конструктивных истинностных значений SIXTEEN с дополнительным третьим частичным порядком упорядочиваю­щим 16 истинностных значений по их конструктивности. В [Shramko and Warning 2005] (см. также [Ванзинг и Шрамко 2005]) вводится понятие п-мерной мулътирешетки как структуры, на ко­торой определены в точности п частичных порядков. В этих рабо­тах исследуется также сама

16-значная логика, соответствующая структуре SIXTEEN. Подчеркивается фундаментальная роль теории следования первой ступени (см. выше раздел 5.4.4).

5.4.4.4.1. Логическая бирешетка: импликация и классическое отрицание

Большой интерес представляют работы А. Ариэли и А. Аврона, в которых вводится понятие логической бирешетки и строятся соот­ветствующие логики [Arieli and Avron 1994; 1996]. Здесь решается проблема выделенных значений и проблема определения подходя­щей импликации.

Понятие логической бирешетки в некотором смысле является обобщением понятия логической матрицы, которая, напомним, есть пара в которой есть алгебра с множеством выде-

ленных значений D. Логической бирешеткой называется пара

в которой есть бирешетка и F есть простой бифильтр на .

(Бифильтр бирещетки есть непустое подмножество такое, что

Бифильтр называется простым, если также выполняются условия:

)

Пусть BL есть стандартный пропозициональный язык

.

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

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