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

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

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

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

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

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

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

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

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

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

не влечет за собой ни $English(Fred)$ ни $Irish(Fred)$ .

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

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

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

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

K\cup \{\neg f~|~f\in F\}

.

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

CWA (предположение о закрытом мире): $f$ является положительным литералом, не вытекающим из $K$ ;

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

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

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

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

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

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

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

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

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

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

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

[2] Минкер, Джек (1982), «О неопределенных базах данных и предположении о закрытом мире», 6-я конференция по автоматизированному выводу , конспекты лекций по информатике, том. 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] Сученек, Марек А. (2000), «Оценка запросов в условиях закрытого мира. Часть II: Иерархический случай» , Kluwer Academic Publishers / Springer (25): 247–289, doi : 10.1023/A:1006319819647

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

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

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

[PCWA2015-8] Разневский, Саймон; Савкович, Огнен; Натт, Вернер (2015). «Перевернув предположение о частично закрытом мире с ног на голову» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]