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

Предположение о замкнутом мире ( CWA ) в формальной системе логики, используемой для представления знаний , является предположением о том, что утверждение, которое является истинным, также известно как истинное. Следовательно, наоборот, то, что в настоящее время не известно как истинное, является ложным. То же самое название также относится к логической формализации этого предположения Рэймондом Рейтером . ^[1] Противоположностью предположения о замкнутом мире является предположение об открытом мире (OWA), утверждающее, что отсутствие знаний не подразумевает ложность. Решения о CWA против OWA определяют понимание фактической семантики концептуального выражения с теми же обозначениями понятий. Успешная формализация семантики естественного языка обычно не может избежать явного раскрытия того, основаны ли неявные логические фоны на CWA или OWA.

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

Пример

В контексте управления знаниями предположение о закрытости мира используется по крайней мере в двух ситуациях: (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)\}}$

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

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

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

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

CWA (предположение о замкнутом мире)

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

GCWA (обобщенный CWA)

${\displaystyle f}$является положительным литералом, таким что для каждого положительного предложения, такого что , он имеет место ; ^[2] ${\displaystyle c}$ ${\displaystyle K\not \vdash c}$ ${\displaystyle K\not \vdash c\vee f}$

EGCWA (расширенный GCWA)

то же, что и выше, но представляет собой конъюнкцию положительных литералов; ${\displaystyle f}$

CCWA (осторожно CWA)

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

ECWA (расширенный CWA)

похож на CCWA, но представляет собой произвольную формулу, не содержащую литералов из заданного набора. ^{[3] [4]} ${\displaystyle f}$

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

В ситуациях, когда невозможно предположить замкнутый мир для всех предикатов, но некоторые из них известны как замкнутые, можно использовать предположение о частично замкнутом мире . Этот режим рассматривает базы знаний в целом как открытые, т. е. потенциально неполные, но позволяет использовать утверждения о полноте для указания частей базы знаний, которые являются замкнутыми. ^[8]

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

Язык логических программ с сильным отрицанием позволяет нам постулировать предположение о закрытости мира для некоторых утверждений и оставить другие утверждения в области предположения об открытом мире. ^[9] Промежуточная почва между OWA и CWA предоставляетсяПредположение о частичном закрытом мире (PCWA). Согласно PCWA, база знаний обычно рассматривается в рамках семантики открытого мира, однако возможно утверждать части, которые должны рассматриваться в рамках семантики закрытого мира, посредством утверждений о полноте. PCWA особенно необходим в ситуациях, когда CWA неприменим из-за открытого домена, однако OWA слишком доверчив, допуская, что что-либо может быть истинным. ^{[10] [11]}

Смотрите также

• Предположение об открытом мире
• Предположение о частичной замкнутости мира
• Немонотонная логика
• Ограничение (логика)
• Отрицание как неудача
• Логика по умолчанию
• Стабильная модель семантики
• Уникальное предположение имени

Ссылки

1. Рейтер, Рэймонд (1978). «О базах данных закрытого мира». В Галлере, Эрве; Минкер, Джек. Логика и базы данных. Plenum Press. стр. 119–140. ISBN  9780306400605 .
2. Минкер, Джек (1982), «О неопределенных базах данных и предположении о замкнутом мире», 6-я конференция по автоматизированной дедукции , Lecture Notes in Computer Science, т. 138, Springer Berlin Heidelberg , стр. 292–308, doi :10.1007/BFb0000066, ISBN 978-3-540-11558-8
3. Сученек, Марек А. (1997), «Оценка запросов в условиях замкнутого мира», Kluwer Academic Publishers / Springer (18): 237–263, doi :10.1023/A:1005723423016
4. Suchenek, Marek A. (2000), «Оценка запросов в условиях замкнутого мира. Часть II: Иерархический случай», Kluwer Academic Publishers / Springer (25): 247–289, doi :10.1023/A:1006319819647
5. Эйтер, Томас; Готтлоб, Георг (июнь 1993 г.). «Пропозициональное ограничение и расширенное рассуждение о замкнутом мире — это Π 2 p ». Теоретическая информатика. 114 (2): 231–245. doi :10.1016/0304-3975(93)90073-3. ISSN 0304-3975. ${\displaystyle {\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete}$
6. Лифшиц, Владимир (ноябрь 1985 г.). «Базы данных замкнутого мира и ограничение». Искусственный интеллект. 27 (2): 229–235. doi :10.1016/0004-3702(85)90055-4. ISSN 0004-3702.
7. Кадоли, Марко; Ленцерини, Маурицио (апрель 1994 г.). «Сложность пропозиционального замкнутого мирового рассуждения и ограничения». Журнал компьютерных и системных наук. 48 (2): 255–310. doi :10.1016/S0022-0000(05)80004-2. ISSN 0022-0000.
8. Разневский, Саймон; Савкович, Огнен; Нутт, Вернер (2015). «Переворачивая предположение о частичной замкнутости мира вверх дном» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
9. Рассел, Стюарт Дж.; Норвиг, Питер (2010). Искусственный интеллект: современный подход (3-е изд.). Верхняя Сэддл-Ривер: Prentice Hall.
10. Мотро (1989). «Целостность = Достоверность + Полнота».
11. Разневский, Саймон; Савкович, Огнен; Нутт, Вернер (2015). «Переворачивая предположение о частичной замкнутости мира вверх дном» (PDF) .

Внешние ссылки

• https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
• Рассуждение о закрытом мире в семантической паутине посредством эпистемических операторов
• Отрывок из выступления Рейтера 1978 года о предположении о замкнутом мире