Abstract
An important limitation of traditional logic programming as a knowledge representation tool, in comparison with classical logic, is that logic programming does not allow us to deal directly with incomplete information. In order to overcome this limitation, we extend the class of general logic programs by including classical negation, in addition to negation-as-failure. The semantics of such extended programs is based on the method of stable models. The concept of a disjunctive database can be extended in a similar way. We show that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available. Computationally, classical negation can be eliminated from extended programs by a simple preprocessor. Extended programs are identical to a special case of default theories in the sense of Reiter.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bidoit, N. and Froidevaux, C., “Minimalism Subsumes Default Logic and Cricumscription,” inProc. of LICS-87, pp. 89–97, 1987.
Bidoit, N. and Froidevaux, C., “Negation by Default and Nonstratifiable Logic Programs,”Technical Report, 437, Université Paris XI, 1988.
Blair, H. and Subrahmanian, V. S., “Paraconsistent Logic Programming,”Theoretical Computer Science, 68, pp. 135–154, 1989.
Fitting, M., “A Kripke-Kleene Semantics for Logic Programs,”Journal of Logic Programming, 2, 4, pp. 295–312, 1985.
Gelfond, M. and Lifschitz, V., “The Stable Model Semantics for Logic Programming,” inLogic Programming (R. Kowalski and K. Bowen, eds.):Proc. of the Fifth Int’l Conf. and Symp., pp. 1070–1080, 1988.
Gelfond, M. and Lifschitz, V., “Compiling Circumscriptive Theories into Logic Programs,” inNon-Monotonic Reasoning (M. Reinfrank, J. de Kleer, M. Ginsberg and E. Sandewall, eds.):2nd International Workshop (Lecture Notes in Artificial Intelligence, 346), Springer-Verlag, pp. 74–99, 1989.
Gelfond, M. and Lifschitz, V., “Logic Programs with Classical Negation,” inLogic Programming (D. Warren and P. Szeredi, eds.):Proc. of the Seventh Int’l Conf., pp. 579–597, 1990.
Gelfond, M., “On Stratified Autoepistemic Theories,” inProc. AAAI-87, pp. 207–211, 1987.
Gelfond, M., “Autoepistemic Logic and Formalization of Commonsense Reasoning,” inNon-Monotonic Reasoning (M. Reinfrank, J. de Kleer, M. Ginsberg and E. Sandewall, eds.):2nd International Workshop (Lecture Notes in Artificial Intelligence, 346), Springer-Verlag, pp. 176–186, 1989.
Kowalski, R. and Sadri, F., “Logic Programs with Exceptions,” inLogic Programming (D. Warren and P. Szeredi, eds.):Proc. of the Seventh Int’l Conf., pp. 598–613, 1990.
Kowalski, R., “The Treatment of Negation in Logic Programs for Representing Legislation,” inProc. of the Second Int’l Conf. on Artificial Intelligence and Law, pp. 11–15, 1989.
Lifschitz, V., “Between Circumscription and Autoepistemic Logic,” inProc. of the First Int’l Conf. on Principles of Knowledge Representation and Reasoning (R. Brachman, H. Levesque and R. Reiter, eds.), pp. 235–244, 1989.
Lin, F. and Shoham, Y., “Argument Systems: A Uniform Basis for Nonmonotonic Reasoning,” inProc. of the First Int’l Conf. on Principles of Knowledge Representation and Reasoning (R. Brachman, H. Levesque and R. Reiter, eds.), pp. 245–255, 1989.
Lloyd, J.,Foundations of Logic Programming, Springer-Verlag, 1984.
Marek, W. and Truszczyński, M., “Autoepistemic Logic, Defaults and Truth Maintenance,”Manuscript, 1989.
Marek, W. and Truszczyński, M., “Relating Autoepistemic and Default Logic,” inProc. of the First Int’l Conf. on Principles of Knowledge Representation and Reasoning (R. Brachman, H. Levesque and R. Reiter, eds.), pp. 276–288, 1989.
McCarthy, J., “Applications of Circumscription to Formalizing Common Sense Knowledge,”Artificial Intelligence, 26, 3, pp. 89–116, 1986.
Minker, J., “On Indefinite Data Bases and the Closed World Assumption,” inProc. of CADE-82, pp. 292–308, 1982.
Moore, R., “Semantical Considerations on Nonmonotonic Logic,”Artificial Intelligence, 25, 1, pp. 75–94, 1985.
Poole, D. and Goebel, R., “Gracefully Adding Negation and Disjunction to Prolog,” inProc. of the Third Int’l Conf. on Logic Programming (E. Shapiro, ed.), pp. 635–641, 1986.
Przymusinski, T., “On the Relationship between Logic Programming and Non-Monotonic Reasoning,” inProc. AAAI-88, pp. 444–448, 1988.
Przymusinski, T., “Three-Valued Formalizations of Non-Monotonic Reasoning and Logic Programming,” inProc. of the First Int’l Conf. on Principles of Knowledge Representation and Reasoning (R. Brachman, H. Levesque and R. Reiter, eds.), pp. 341–348, 1989.
Przymusinski, T., “Extended Stable Semantics for Normal and Disjunctive Programs,” inLogic Programming (D. Warren and P. Szeredi, eds.):Proc. of the Seventh Int’l Conf., pp. 459–477, 1990.
Reiter, R., “On Closed World Data Bases,” inLogic and Data Bases (H. Gallaire and J. Minker, eds.), Plenum Press, New York, pp. 119–140, 1978.
Reiter, R., “A Logic for Default Reasoning,”Artificial Intelligence, 13, 1, 2, pp. 81–132, 1980.
Van Gelder, A., Ross, K. and Schlipf, J., “The Well-Founded Semantics for General Logic Programs,”Journal of ACM, 1991, Vol. 38 No. 3 July 1991, pp. 620–650, 1991.
Wagner, G., “The Two Sources of Nonmonotonicity in Vivid Logic: Weak Falsity and Inconsistency Handling,” inProc. of the Workshop on Nonmonotonic Reasoning (G. Brewka and H. Freitag, eds.), 1989.
Author information
Authors and Affiliations
About this article
Cite this article
Gelfond, M., Lifschitz, V. Classical negation in logic programs and disjunctive databases. New Gener Comput 9, 365–385 (1991). https://doi.org/10.1007/BF03037169
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03037169