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

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

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

Пример [ править ]

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

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

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

Формализация в логике [ править ]

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

{\ Displaystyle \ {английский (Фред) \ vee ирландский (Фред) \}}

влечет за собой ни, ни . ${\ displaystyle английский (Фред)}$ ${\ displaystyle Irish (Фред)}$

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

{\ Displaystyle \ {английский (Фред) \ vee ирландский (Фред), \ neg английский (Фред), \ neg ирландский (Фред) \}}

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

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

{\ Displaystyle К \ чашка \ {\ neg f ~ | ~ f \ in F \}}

.

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

CWA (предположение о замкнутом мире): ${\ displaystyle f}$ положительный литерал, не влекущий за собой ; ${\ displaystyle K}$

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

EGCWA (расширенный GCWA): то же, что и выше, но представляет собой соединение положительных литералов; $f$

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

ECWA (расширенный CWA): аналогичен CCWA, но представляет собой произвольную формулу, не содержащую литералов из заданного набора. $f$

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

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

См. Также [ править ]

Ссылки [ править ]

Перейти ↑ Reiter, Raymond (1978). «О закрытых мировых базах данных». В Галлере, Эрве; Минкер, Джек. Логика и базы данных. Пленум Пресс. С. 119–140. ISBN 9780306400605 .
^ Minker, Джек (1982), "О неопределенных баз данных и закрытого мира предположения", 6 - й конференции по автоматизированной дедукции , Lecture Notes в области компьютерных наук, 138 , Springer Berlin Heidelberg , стр 292-308,. Дой : 10,1007 / BFb0000066 , ISBN 978-3-540-11558-8
^ Эйтер, Томас; Готтлоб, Георг (июнь 1993 г.). «Пропозициональная ограниченность и расширенное рассуждение о замкнутом мире составляют 2 p ». Теоретическая информатика. 114 (2): 231–245. DOI : 10.1016 / 0304-3975 (93) 90073-3 . ISSN 0304-3975. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$
^ Лифшиц, Владимир (ноябрь 1985). «Базы данных замкнутого мира и ограниченность». Искусственный интеллект. 27 (2): 229–235. DOI : 10.1016 / 0004-3702 (85) 90055-4 . ISSN 0004-3702.
^ Кадоли, Марко; Лензерини, Маурицио (апрель 1994). «Сложность пропозиционального рассуждения о закрытом мире и ограничения». Журнал компьютерных и системных наук. 48 (2): 255–310. DOI : 10.1016 / S0022-0000 (05) 80004-2 . ISSN 0022-0000.
^ Разневский, Саймон; Савкович, Огнен; Натт, Вернер (2015). «Переворачивание предположения о частично замкнутом мире с ног на голову» (PDF) . Cite journal requires |journal= (help)

Внешние ссылки [ править ]

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

[1] Перейти ↑ Reiter, Raymond (1978). «О закрытых мировых базах данных». В Галлере, Эрве; Минкер, Джек. Логика и базы данных. Пленум Пресс. С. 119–140. ISBN 9780306400605 .

[2] Minker, Джек (1982), "О неопределенных баз данных и закрытого мира предположения", 6 - й конференции по автоматизированной дедукции , Lecture Notes в области компьютерных наук, 138 , Springer Berlin Heidelberg , стр 292-308,. Дой : 10,1007 / BFb0000066 , ISBN 978-3-540-11558-8

[3] Эйтер, Томас; Готтлоб, Георг (июнь 1993 г.). «Пропозициональная ограниченность и расширенное рассуждение о замкнутом мире составляют 2 p ». Теоретическая информатика. 114 (2): 231–245. DOI : 10.1016 / 0304-3975 (93) 90073-3 . ISSN 0304-3975. ${\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete$

[4] Лифшиц, Владимир (ноябрь 1985). «Базы данных замкнутого мира и ограниченность». Искусственный интеллект. 27 (2): 229–235. DOI : 10.1016 / 0004-3702 (85) 90055-4 . ISSN 0004-3702.

[5] Кадоли, Марко; Лензерини, Маурицио (апрель 1994). «Сложность пропозиционального рассуждения о закрытом мире и ограничения». Журнал компьютерных и системных наук. 48 (2): 255–310. DOI : 10.1016 / S0022-0000 (05) 80004-2 . ISSN 0022-0000.

[PCWA2015-6] Разневский, Саймон; Савкович, Огнен; Натт, Вернер (2015). «Переворачивание предположения о частично замкнутом мире с ног на голову» (PDF) . Cite journal requires |journal= (help)

[1]