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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Предположение о замкнутости мира (Шаблон:Lang-en) — стратегия, при которой положительный литерал, который не является следствием формул в некоторой базе знаний, считается ложным. Данное предположение позволяет упростить систему замещением неоднозначности (есть — нет — неизвестно) дуализмом (есть — нет). Широко используется в компьютерных системах, в том числе в СУБД.

Например: имея базу знаний, состоящую из литералов

  • «Вася любит собак»;
  • «Женя любит кошек»;
  • «Женя не любит собак»;

в логике первого порядка невозможно дать определённый ответ на вопрос, любит ли Вася кошек, поскольку невозможно доказать ни литерал «Вася любит кошек», ни «Вася не любит кошек». Но при предположении о замкнутости мира, положительный литерал «Вася любит кошек» считается ложным, что позволяет заключить, что Вася кошек не любит.

Формальное определение в логике

Если <math>\Sigma</math> — множество формул, то <math>\Sigma</math> при наивном предположении о замкнутости мира является множеством <math>CWA(\Sigma) = \Sigma \cup \{\neg \phi : \Sigma \nvdash \phi\}</math>, то есть объединение <math>\Sigma</math> и множества отрицаний тех положительных литералов, которые не следуют из <math>\Sigma</math>.

При этом <math>CWA(\Sigma)</math> может оказаться логически противоречивым; например, если <math>p</math>, <math>q</math> положительные литералы, то <math>CWA(\{p \vee q\}) = \{p \vee q, \neg p, \neg q\}</math>. Но если <math>\Sigma</math> состоит из дизъюнктов Хорна, то противоречивости не будет.

Существует ряд альтернативных предположений о замкнутости мира которые имеют форму <math>\Sigma \cup \{\neg \phi : \phi \in F\}</math> и отличаются определением множества <math>F</math>:

  • GCWA (обобщённое ПЗМ, Шаблон:Lang-en): положительный литерал <math>\phi</math> является элементом <math>F</math> если не существует дизъюнкции положительных литералов <math>\psi</math> таковой, что <math>\Sigma \vdash \phi \vee \psi</math> но <math>\Sigma \nvdash \psi</math>.
  • CCWA (осторожное ПЗМ, Шаблон:Lang-en): множество положительных литералов разбивается на три части: <math>P^+</math>, <math>Q^+</math>, <math>Z^+</math>. Элементы <math>F</math> определяется так же, как в GCWA, но <math>\psi</math> является дизъюнкцией литералов из <math>P^+</math> и <math>Q^+</math> и отрицаний литералов из <math>Q^+</math>.
  • EGCWA (расширенное обобщённое ПЗМ, Шаблон:Lang-en): то же, что и GCWA, но <math>\phi</math> может быть конъюнкцией положительный литералов.
  • ECWA (расширенное ПЗМ, Шаблон:Lang-en): то же, что и CCWA, но <math>\phi</math> может быть любой замкнутой формулой, которая не включает литералы из <math>Z^+</math>.

См. также

Литература

  • Шаблон:Книга
  • Шаблон:Книга
  • Шаблон:Книга
  • M. Cadoli and M. Lenzerini (1994). The complexity of propositional closed world reasoning and circumscription. Journal of Computer and System Sciences, 48:255-310.
  • T. Eiter and G. Gottlob (1993). Propositional circumscription and extended closed world reasoning are <math>\Pi^p_2</math>-complete. Theoretical Computer Science, 114:231-45.
  • A. Rajasekar, J. Lobo, and J. Minker (1989). Weak generalized closed world assumption. Journal of Automated Reasoning, 5:293-307.
  • V. Lifschitz (1985). Closed-world databases and circumscription. Artificial Intelligence, 27:229-35.
  • J. Minker (1982). On indefinite databases and the closed world assumption. In Proceedings of the Sixth International Conference on Automated Deduction (CADE’82), pp. 292—308.
  • R. Reiter (1978). On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 119-40. Plenum Publ. Co., New York.

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Предположение_о_замкнутости_мира&oldid=10638704