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

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

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

Пример

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

Редактировать
РедакторСтатья
Джон ДоуФормальная логика
Джошуа А. НортонФормальная логика
Сара ДжонсонВведение в пространственные базы данных
Чарльз ПонциФормальная логика
Эмма Ли-ЧунФормальная логика


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

Формализация в логике

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

{ Э н г л я с час ( Ф г е г ) ∨ я г я с час ( Ф г е г ) } {\displaystyle \{Английский(Фред)\vee Ирландский(Фред)\}}

не влечет за собой ни то, ни другое . Э н г л я с час ( Ф г е г ) {\displaystyle Английский(Фред)} я г я с час ( Ф г е г ) {\displaystyle Ирландский(Фред)}

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

{ Э н г л я с час ( Ф г е г ) ∨ я г я с час ( Ф г е г ) , ¬ Э н г л я с час ( Ф г е г ) , ¬ я г я с час ( Ф г е г ) } {\displaystyle \{Английский(Фред)\vee Ирландский(Фред),\neg Английский(Фред),\neg Ирландский(Фред)\}}

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

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

К ∪ { ¬ ф   |   ф ∈ Ф } {\displaystyle K\cup \{\neg f~|~f\in F\}} .

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

CWA (предположение о замкнутом мире)
ф {\displaystyle f} является положительным литералом, не вытекающим из ; К {\displaystyle К}
GCWA (обобщенный CWA)
ф {\displaystyle f} является положительным литералом, таким что для каждого положительного предложения, такого что , он имеет место ; [2] с {\displaystyle с} К ⊬ с {\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 (3): 237– 263, doi :10.1023/A:1005723423016
  4. ^ Suchenek, Marek A. (2000), «Оценка запросов в условиях замкнутого мира. Часть II: Иерархический случай», Kluwer Academic Publishers / Springer , 25 (4): 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. П 2 п П 2 п − с о м п л е т е {\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. ^ Motro (1989). «Целостность = Достоверность + Полнота». ACM Transactions on Database Systems . 14 (4): 480– 502. doi :10.1145/76902.76904.
  11. ^ Разневский, Саймон; Савкович, Огнен; Нутт, Вернер (2015). «Переворачивая предположение о частичной замкнутости мира вверх дном» (PDF) .
  • https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
  • Рассуждение о закрытом мире в семантической паутине посредством эпистемических операторов
  • Отрывок из выступления Рейтера 1978 года о предположении о замкнутом мире
Получено с "https://en.wikipedia.org/w/index.php?title=Предположение_закрытого_мира&oldid=1271360450"