Abstract
The purpose of this paper is to expand the syntax and semantics of logic programs and disjunctive databases to allow for the correct representation of incomplete information in the presence of multiple extensions. The language of logic programs with classical negation, epistemic disjunction, and negation by failure is further expanded by new modal operators K and M (where for the set of rulesT and formulaF, KF stands for “F is known to be true by a reasoner with a set of premisesT” and MF means “F may be believed to be true” by the same reasoner). Sets of rules in the extended language will be called epistemic specifications. We will define the semantics of epistemic specifications (which expands the semantics of disjunctive databases from) and demonstrate their applicability to formalization of various forms of commonsense reasoning. In particular, we suggest a new formalization of the closed world assumption which seems to better correspond to the assumption's intuitive meaning.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
N. Bidoit and C. Froidevaux, Minimalism subsumes default logic and circumscription, in:Proc. LICS-87 (1987) pp. 89–97.
C. Baral, J. Lobo and J. Minker, Wf3: A semantics for negation in normal disjunctive logic programs, in:Proc. Int. Symp. Methodologies of Intelligent Systems (1991).
C. Sakama, Possible model semantics for disjunctive databases, in:Proc. 1st Int. Conf. on Deductive and Object Oriented Databases (1989) pp. 1055–1060.
E. Chan, A possible world semantics for non-horn databases, Technical Report CS-89-47, University of Waterloo (1989).
K. Clark, Negation as failure, in:Logic and Data Bases, eds. H. Gallaire and J. Minker (Plenum, New York, 1978) pp. 293–322.
M. Gelfond, On stratified autoepistemic theories, in: Proc. AAAI-87 (1987) 207–211.
M. Gelfond, Strong introspection, in: Proc. AAAI-91 (1991) 386–391.
M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in:Logic Programming: Proc. 5th Int. Conf. Symp., eds. R. Kowalski and K. Bowen (1988) pp. 1070–1080.
M. Gelfond and V. Lifschitz, Logic programs with classical negation, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 579–597.
M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Comp. (1991) pp. 365–387.
M. Gelfond, V. Lifschitz, H. Przymusińska and M. Truszczyński, Disjunctive defaults, in:Principles of Knowledge Representation and Reasoning: Proc. 2nd Int. Conf. eds. J. Allen, R. Fikes and E. Sandewall (1991) pp. 230–237.
M. Gelfond and H. Przymusinska, Negation as failure: Careful closure procedure, Artificial Intelligence 30 (1986) 273–287.
M. Gelfond and H. Przymusińska, Definitions in epistemic specifications, in:Logic Programming and Non-monotonic Reasoning: Proc. 1st Int. Workshop, eds. A. Nerod, V. Marek and V.S. Subramanian (1991) pp. 245–259.
M. Gelfond, H. Przymusinska and T. Przymusinski, The extended closed world assumption and its relation to parallel circumscription, in:Proc. 5th ACM Symp. on Principles of Database Systems (1986) pp. 133–139.
R. Kowalski and F. Sadri, Logic programs with exceptions, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 598–613.
H. Levesque, Making believers out of computers, Artificial Intelligence 30 (1986) 81–108.
H. Levesque, All I know: a study in autoepistemic logic, Artificial Intelligence 42 (1990) 263–310.
J. Lobo, J. Minker and A. Rajasekar,Foundations of Disjunctive Logic Programming (MIT Press, 1992).
J. Lloyd and R. Topor, Making prolog more expressive, J. Logic Progr. 3 (1984) 225–240.
J. McCarthy, Circumscription — a form of non-monotonic reasoning, Artificial Intelligence 13(1, 2) (1980) 27–39, 171–172.
D. McDermott and J. Doyle, Nonmonotonic logic I, Artificial Intelligence 13 (1980) 41–72.
J. Minker, On indefinite data bases and the closed world assumption, in:Proc. CADE-82 (1982) pp. 292–308.
R. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence 25 (1985) 75–94.
W. Marek and M. Truszczyński, Modal logic for default reasoning, to appear.
L. Pereira, L. Caires and J. Alferes, Hypothetical reasoning with well founded semantics, in:Proc. 3rd Scand. Conf. on AI (1991).
H. Przymusinska and T. Przymusinski, Semantic issues in deductive databases and logic programs, in:Formal Techniques in Artificial Intelligence, ed. R. Manerji (North-Holland, Amsterdam, 1990) pp. 321–367.
T. Przymusinski, On the declarative semantics of deductive databases and logic programs, in:Foundations of Deductive Databases and Logic Programming, ed. J. Minker (Morgan Kaufmann, San Mateo, CA, 1988) pp. 193–216.
T. Przymusinski, Extended stable semantics for normal and disjunctive programs, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 459–477.
D. Pearce and G. Wagner, Reasoning with negative information 1 — strong negation in logic programming, Technical Report, Gruppe für Logic, Wissentheorie and Information, Freie Universität Berlin (1989).
R. Reiter, On closed world data bases, in:Logic and Data Bases, eds. H. Gallaire and J. Minker (Plenum, New York, 1978) pp. 119–140.
R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81–132.
R. Reiter, On asking what a database knows, in:Computational Logic: Symp. Proc, ed. J. Lloyd (Springer, 1990) pp. 96–113.
K. Ross and R. Topor, Inferring negative information from disjunctive databases, J. Automated Reasoning 4(4) (1988) 397–424.
G. Wagner, Database needs two kinds of negation, in:Proc. MFDBS-91, Lecture Notes in Computer Science, 495 (1991).
L. Yahya and A. Henschen, Deduction in non-horn databases, J. Automated Reasoning 1 (1985) 141–160.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gelfond, M. Logic programming and reasoning with incomplete information. Ann Math Artif Intell 12, 89–116 (1994). https://doi.org/10.1007/BF01530762
Issue Date:
DOI: https://doi.org/10.1007/BF01530762