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

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

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

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

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

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

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

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

• GCWA (обобщённое ПЗМ, англ. generalized CWA ): положительный литерал ${\displaystyle \phi }$ является элементом ${\displaystyle F}$ если не существует дизъюнкции положительных литералов ${\displaystyle \psi }$ таковой, что ${\displaystyle \Sigma \vdash \phi \vee \psi }$ но ${\displaystyle \Sigma \nvdash \psi }$ .
• CCWA (осторожное ПЗМ, англ. careful CWA ): множество положительных литералов разбивается на три части: ${\displaystyle P^{+}}$ , ${\displaystyle Q^{+}}$ , ${\displaystyle Z^{+}}$ . Элементы ${\displaystyle F}$ определяется так же, как в GCWA, но ${\displaystyle \psi }$ является дизъюнкцией литералов из ${\displaystyle P^{+}}$ и ${\displaystyle Q^{+}}$ и отрицаний литералов из ${\displaystyle Q^{+}}$ .
• EGCWA (расширенное обобщённое ПЗМ, англ. extended GCWA ): то же, что и GCWA, но ${\displaystyle \phi }$ может быть конъюнкцией положительный литералов.
• ECWA (расширенное ПЗМ, англ. extended CWA ): то же, что и CCWA, но ${\displaystyle \phi }$ может быть любой замкнутой формулой, которая не включает литералы из ${\displaystyle 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 // . — Nova Publishers, 2006. — С. 143—149. — 171 с. — ISBN 1594545626 .
• J. C. Shepherdson. Negation as Failure, Completion and Stratification // / Под ред. 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 ${\displaystyle \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.

Ссылки

• от 19 мая 2011 на Wayback Machine