Предположение о замкнутости мира (Hjy;hklk'yuny k [gbturmkvmn bnjg)

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

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

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

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

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

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

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

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

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

Ссылки