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

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

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

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

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

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

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

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

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

• GCWA (обобщённое ПЗМ, англ. generalized CWA): положительный литерал $\mathrm{\varphi <!--\; \varphi \; -->}$$\phi$  является элементом $F$$F$  если не существует дизъюнкции положительных литералов $\mathrm{\psi <!--\; \psi \; -->}$$\psi$  таковой, что $\mathrm{\Sigma <!--\; \Sigma \; -->}⊢<!--\; ⊢\; -->\mathrm{\varphi <!--\; \varphi \; -->}\vee <!--\; \vee \; -->\mathrm{\psi <!--\; \psi \; -->}$$\Sigma \vdash \phi \vee \psi$  но $\mathrm{\Sigma <!--\; \Sigma \; -->}⊬<!--\; ⊬\; -->\mathrm{\psi <!--\; \psi \; -->}$$\Sigma \nvdash \psi$ .
• CCWA (осторожное ПЗМ, англ. careful CWA): множество положительных литералов разбивается на три части: $P^{+}$$P^{+}$ , $Q^{+}$$Q^{+}$ , $Z^{+}$$Z^{+}$ . Элементы $F$$F$  определяется так же, как в GCWA, но $\mathrm{\psi <!--\; \psi \; -->}$$\psi$  является дизъюнкцией литералов из $P^{+}$$P^{+}$  и $Q^{+}$$Q^{+}$  и отрицаний литералов из $Q^{+}$$Q^{+}$ .
• EGCWA (расширенное обобщённое ПЗМ, англ. extended GCWA): то же, что и GCWA, но $\mathrm{\varphi <!--\; \varphi \; -->}$$\phi$  может быть конъюнкцией положительный литералов.
• ECWA (расширенное ПЗМ, англ. extended CWA): то же, что и CCWA, но $\mathrm{\varphi <!--\; \varphi \; -->}$$\phi$  может быть любой замкнутой формулой, которая не включает литералы из $Z^{+}$$Z^{+}$ .

См. такжеПравить

• Предположение об открытости мира

ЛитератураПравить

• Stuart Russel, Peter Norvig. 10.7 — Reasoning with Default information // Artificial Intelligence: a Modern Approach. — 2-е изд. — Prentice Hall, 2003. — С. 354—356. — 1132 с. — ISBN 0137903952.
• Dritan Berzati. 8.2 — Negation as failure // Nonmonotonic Reasoning: a Unifying Framework. — Nova Publishers, 2006. — С. 143—149. — 171 с. — ISBN 1594545626.
• J. C. Shepherdson. Negation as Failure, Completion and Stratification // Handbook of Logic in Artificial Intelligence and Logic Programming / Под ред. Dov M. Gabbay, Christopher John Hogger, John Alan Robinson. — Oxford University Press, 1998. — Т. 5. — С. 370—401. — 816 с. — ISBN 0198537921.
• 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 ${\mathrm{\Pi <!--\; \Pi \; -->}}_2^p$$\Pi _{2}^{p}$ -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.

СсылкиПравить

• https://web.archive.org/web/20051220205009/http://cs.wwc.edu/~aabyan/Logic/CWA.html
• https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
• https://web.archive.org/web/20070607164326/http://esw.w3.org/topic/ClosedWorldAssumptions
• Closed World Reasoning in the Semantic Web through Epistemic Operators Архивная копия от 19 мая 2011 на Wayback Machine
• Excerpt from Reiter’s 1978 talk on the closed world assumption