Предположение о замкнутости мира

В информационных системах управления знаниями предположение о замкнутости мира применяют как минимум в двух ситуациях:

1) если база знаний является полной (например, корпоративная база данных, содержащая сведения обо всех сотрудниках);

2) если база знаний не является полной, но из имеющейся информации нужно вывести однозначный и наиболее вероятный ответ.

Например, если в базе данных содержится следующая таблица об авторах, редактировавших статью, то на запрос о людях, не редактировавших статью по формальной логике, обычно ожидают получить в ответ «Сара Джонсон»:

В предположении о замкнутости мира таблица считается полной, то есть в ней приведены все факты отношения редактор—статья, и Сара Джонсон — единственный редактор, не участвовавший в работе над статьёй по формальной логике. Напротив, при предположении об открытом мире не предполагается, что таблица содержит все возможные пары редактор—статья, и на вопрос, кто не редактировал статью по формальной логике, нельзя дать однозначный ответ, поскольку в таблице могут отсутствовать другие редакторы или сведения об иных статьях, с которыми работала Сара Джонсон.

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

${\displaystyle \{English(Fred)\vee Irish(Fred)\}}$

логически не выводит ни ${\displaystyle English(Fred)}$, ни ${\displaystyle Irish(Fred)}$.

Добавление отрицаний этих двух литералов приводит к

${\displaystyle \{English(Fred)\vee Irish(Fred),\neg English(Fred),\neg Irish(Fred)\}}$,

что противоречиво. Иными словами, подобная формализация предположения о замкнутости мира может превратить согласованную базу знаний в противоречивую. CWA не приводит к противоречию для базы знаний ${\displaystyle K}$ тогда и только тогда, когда пересечение всех гербрандовых моделей ${\displaystyle K}$ само является моделью ${\displaystyle K}$; в пропозициональном случае это эквивалентно тому, что у ${\displaystyle K}$ есть единственная минимальная модель, где модель минимальна, если ни одна другая модель не задаёт меньшее подмножество истинных переменных.

Для устранения этой проблемы были предложены альтернативные формализации. Пусть рассматриваемая база знаний ${\displaystyle K}$ является пропозициональной. Во всех случаях формализация CWA основана на добавлении к ${\displaystyle K}$ отрицаний тех формул, которые «свободны для отрицания», то есть могут быть предположены ложными. Формально, предположение о замкнутости мира для базы знаний ${\displaystyle K}$ генерирует базу знаний вида:

${\displaystyle K\cup \{\neg f~|~f\in F\}}$.

Множество ${\displaystyle F}$ формул, свободных для отрицания, может определяться по-разному, что порождает различные формализации CWA. Ниже приведены определения того, когда формула ${\displaystyle f}$ свободна для отрицания в соответствующих формализациях:

CWA (closed-world assumption)

${\displaystyle f}$ — это положительный литерал, не вытекающий из ${\displaystyle K}$;

GCWA (обобщённое CWA, generalized CWA)

${\displaystyle f}$ — положительный литерал такой, что для каждой положительной дизъюнкции ${\displaystyle c}$, не следующей из ${\displaystyle K}$, также не следует дизъюнкция ${\displaystyle c\vee f}$;

EGCWA (расширенное GCWA, extended GCWA)

аналогично GCWA, только ${\displaystyle f}$ — конъюнкция положительных литералов;

CCWA (осторожное CWA, careful CWA)

аналогично GCWA, но положительная дизъюнкция учитывается только если состоит из положительных литералов определённого множества и (положительных или отрицательных) литералов из другого множества;

ECWA (extended CWA)

аналогично CCWA, но ${\displaystyle f}$ — произвольная формула, не содержащая литералов из заданного множества^[2].

ECWA и формализм циркумскрипции (огрнаничения) совпадают для пропозициональных теорий^[3]. Сложность запроса (проверка логического следования формулы из другой формулы при предположении CWA) обычно относится ко второму уровню полиномиальной иерархии для произвольных формул, и лежит в диапазоне от P до coNP для хорновских формул. Проверка, приводит ли исходное предположение о замкнутости мира к противоречию, требует не более логарифмического числа обращений к NP-оракулу; однако точная сложность этой задачи пока неизвестна^[4].

Если невозможно принять предположение о замкнутости мира для всех предикатов, но некоторые из них заданы полностью, применяется частичное предположение о замкнутости мира (англ. partial-closed world assumption, PCWA). В этом подходе базы знаний в целом считаются открытыми, то есть, потенциально неполными, но путём специальных утверждений о полноте можно выделять их закрытые части^[5].

Язык логических программ с сильным отрицанием позволяет применять предположение о замкнутости мира только для некоторых утверждений, оставляя остальные в сфере предположения об открытом мире^[6]. Промежуточное положение между OWA и CWA занимает частичное предположение о замкнутости мира (PCWA). Согласно PCWA, база знаний в целом трактуется в рамках открытой семантики, однако отдельные её части могут быть помечены как закрытые с помощью утверждений о полноте. Такой подход особенно необходим в случаях, когда применение CWA невозможно из-за открытых предметных областей, а OWA слишком допускает возможность любой гипотезы^[7].