This paper relates some episodes in the history of logic from the mid-twentieth Century to a highly influential line of research in logic programming and artificial intelligence that developed independently from around the end of the 1980s.1 In 1988 Michael Gelfond and Vladimir Lifschitz published a celebrated paper (1988) on the stable model semantics of logic programs. Today, having built on and enlarged those key ideas of 24 years ago, answer set programming (often abbreviated as ASP) has emerged over the last decade as a flourishing paradigm of declarative programming, rich in theoretical advances and maturing applications.2 This is one aspect of the legacy of stable models, and a very important one. Another aspect, equally important, but somewhat farther from the limelight today, lies in the ability of stable models to provide us with a valuable method of reasoning — to give it a name let us call it stable reasoning. In this essay I examine some of the foundational concepts underlying the approach of stable models. I try to answer the question: “What is a stable model?” by searching for a purely logical grasp of the stability concept. In so doing, I shall discuss some concepts and results in logic from more than 60 years ago. In particular, I look at questions such as:
-
How does a notion of stability presented in a work on intuitionistic mathematics in 1947 relate to the Gelfond-Lifschitz concept of 1988?
-
How does the notion of constructible falsity published in 1949 help to explain properties of negation arising in the language of ASP?
-
Why is a seminal paper by McKinsey and Tarski (1948) important for understanding the relations between answer sets and modal and epistemic logics, including recent results about modal embeddings of ontologies and rules?
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aguado, F. et al. (2008) ‘Strongly Equivalent Temporal Logic Programs’, in Hölldobler, S. et al. (eds) Lecture Notes in Artificial Intelligence, 5293: 11th European Conference on Logics in Artificial Intelligence (JELIA’08) (Berlin: Springer), 8–20.
Banda, M. G., and Pontelli, E. (eds) (2008) Logic Programming: 24th International Conference, ICLP 2008 Udine, Italy, December 9–13 2008 Proceedings (LNCS/Programming and Software Engineering), LNCS, 5366 (Berlin: Springer).
Baral, C. et al. (eds) (2005) Logic Programming and Nonmonotonic Reasoning, 8th International Conference, LPNMR 2005, Diamante, Italy, September 5–8, 2005, LNCS, 3662 (Berlin: Springer).
Boolos, G. (1980) ‘On systems of modal logic with provability interpretations’, Theoria, 46, 7–18.
de Bruijn, J., Eiter, T., and Tompits, H. (2008) ‘Embedding Approaches to Combining Rules and Ontologies into Autoepistemic Logic’, in G. Brewka, and J. Lang (eds) Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR2008, Sydney, Australia, September 16–19, 2008 (Chicago: AAAI Press).
Cabalar, P., and Ferraris, P. (2007) ‘Propositional Theories are Strongly Equivalent to Logic Programs’, Theory and Practice of Logic Programming, 7(6), 745–59.
Chagrov, A., and Zakharyaschev, M. (1992) ‘Modal Companions of Intermediate Propositional Logics’, Studia Logica, 51, 49–82.
— (1997) Modal Logic (Oxford: Oxford University Press).
van Dantzig, D. (1947) ‘On the Principles of Intuitionistic and Affirmative Mathematics’, Indagationes Mathematicae, 9, 429–40, 506–17.
— (1951) ‘Mathématique Stable et Mathématique Affirmative’ in Congrès International de Philosophie des Sciences, Paris1949, Vol. II, Logique, Actualités Scientifiques et Industrielles (ASI) (Paris: Hermann), 1951, 123–35.
Denecker, M., Marek, V., and Truszczyń ski, M. (1999) ‘Approximating Operators, Stable Operators, Well-Founded Fixpoints and Applications in Nonmonotonic Reasoning’, in J. Minker (ed.) NFS-Workshop on Logic-Based Artificial Intelligence (Dordrecht: Kluwer), 1–26.
Dung, P. M. (1993) ‘An Argumentation Semantics for Logic Programming with Explicit Negation’, in D. Warren (ed.) Proceedings ICLP 1993: Proceedings of the Tenth International Conference on Logic Programming, June 21–24, 1993, Budapest, Hungary (Cambridge, MA: The MIT Press), 616–30.
Esakia, L. (1979) ‘To the Theory of Modal and Superintuitionistic Systems’, (Russian), in V. A. Smirnov (ed.) Logical Deduction (Moscow: Nauka), 147–72.
Ferraris, P. (2005) ‘Answer Sets for Propositional Theories’, in Baral et al. (2005), 119–31.
Ferraris, P., Lee, J., and Lifschitz, V. (2007) ‘A New Perspective on Stable Models’, in Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 372–9.
Fink, M. (2008) ‘Equivalences in Answer Set Programming by Countermodels in the Logic of Here-and-there’, in Banda and Pontelli (2008), 99–113.
Gelfond, M. (1987) ‘On Stratified Autoepistemic Theories’, in K. Forbus, and H. E. Shrobe (eds) AAAI-87: Proceedings of the6th National Conference on Artificial Intelligence, Seattle, WA, July 1987 (San Francisco: Morgan Kaufmann), 207–11.
Gelfond, M., and Lifschitz, V. (1988) ‘The Stable Model Semantics for Logic Programs’, in K. Bowen, and R. Kowalski (eds) Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August15–19 (Cambridge, MA: The MIT Press), 1070–80.
— (1990) ‘Logic Programs with Classical Negation’, in D. Warren, and D. Szeredi (eds) Logic Programming, Proceedings of the Seventh International Conference, Jerusalem, Israel, June 18–20, 1990 (Cambridge, MA: The MIT Press), 579–97.
Gödel, K. (1933) ‘Eine Interpretation des intuitionistischen Aussagenkalkuls’, Ergebnisse eines mathematischen Kolloquiums, 4, 39–40; reprinted in Gödel (1986).
— (1986) Collected Works, Vol. I, K. Feferman et al. (eds) (Oxford: Oxford University Press).
Goldblatt, R. (1978) ‘Arithmetical Necessity, Provability and Intuitionistic Logic’, Theoria, 44, 36–46.
Gurevich, Y. (1977) ‘Intuitionistic Logic with Strong Negation’, Studia Logica, 36, 49–59.
Heymans, S., van Nieuwenborgh, D., and Vermeir, D. (2005) ‘Guarded Open Answer Set Programming’, in Baral et al. (2005), 92–104.
— (2008) ‘Open Answer Set Programming with Guarded Programs’, in ACM Transactions on Computational Logic (TOCL) 9(4), 1–53.
de Jongh, D., and Hendriks, L. (2003) ‘Characterization of Strongly Equivalent Logic Programs in Intermediate Logics’, Theory and Practice of Logic Programming, 3(3), 259–70.
Kolmogorov, A. N. (1925) ‘On the Principle of the Excluded Middle’, Mat. Sb. 646– 67 [in Russian]. Engl. trans. in van Heijenoort J. (1967) From Frege to Gödel: A Source Book in Mathematical Logic (Cambridge: Harvard University Press), 414–37.
— (1932) ‘Zur Deutung der intuitionistische Logik’, Mathematische Zeitschrift, 35, 58–65.
Kracht, M. (1998) ‘On Extensions of Intermediate Logics by Strong Negation’, Journal of Philosophical Logic, 27(1), 49–73.
Kuznetsov, A. V., and Muravitsky, A. J. (1977) ‘Magari’s Algebras’, in Proceedings of the 14th USSR Algebraic Conference, Part 2 (Novosibirsk), 105–6 [in Russian].
— (1980) ‘Provability as Modality’ in Actual Problems of Logic and Methodology of Science (Kiev: Naukova Dumka), 193–230 [in Russian].
Lee, J., Lifschitz, V., and Palla, R. (2008a) ‘A Reductive Semantics for Counting and Choice in Answer Set Programming’, in Proceedings of the Twenty-Third National Conference on Artificial Intelligence, 2008 (AAAI-08) (Chicago: AAAI Press), 472–9.
— (2008b) ‘Safe Formulas in the General Theory of Stable Models’, [Preliminary report] in Banda and Pontelli (2008), 672–6.
Lifschitz, V. (2008) ‘Twelve Definitions of a Stable Model’, in Banda and Pontelli (2008), 37–51.
Lifschitz, V., and Schwarz, G. (1993) ‘Extended Logic Programs as Autoepis-temic Theories’, in L. M. Pereira, and A. Nerode (eds) Logic Programming and Non-Monotonic Reasoning (Cambridge, MA: The MIT Press), 101–14.
Lifschitz, V., Pearce, D., and Valverde, A. (2001) ‘Strongly Equivalent Logic Programs’, ACM Transactions on Computational Logic, 2(4), 526–41.
— (2007) ‘A Characterization of Strong Equivalence for Logic Programs with Variables’, in C. Baral et al. (eds) Logic Programming and Nonmonotonic Reasoning, 9th International Conference, LPNMR 2007, Tempe, AZ, USA, May 15–17, 2007, Proceedings. LNCS 4483 (Berlin: Springer), 188–200.
Lifschitz, V., Tang, L., and Turner, H. (1999) ‘Nested Expressions in Logic Programs’, Annals of Mathematics and Artificial Intelligence, 25 (3–4), 369–89.
Łukasiewicz, J. (1941) ‘Die logic und das Grundlagenproblem’, in Les Entretiens de Zürich sur les fondements et la méthode de sciences mathématiques, 12, 6–9 (1938), Zürich, 82–100.
McKinsey, J. C., and Tarski, A. (1948) ‘Some Theorems about the Sentential Calculus of Lewis and Heyting, Journal of Symbolic Logic, 13, 1–15.
Maksimova, L., and Rybakov, V. (1974) ‘On the Lattice of Normal Modal Logics’, Algebra and Logic, 13, 188–216 [in Russian].
Marek, V., and Truszczyń ski, M. (1993a) ‘Reflexive Autoepistemic Logic and Logic Programming’, in L. M. Pereira, and A. Nerode (eds) Logic Programming and Non-monotonic Reasoning (Cambridge, MA: The MIT Press), 115–31.
— (1993b) Nonmonotonic Logic (Berlin: Springer).
Mariën, M., Gilis, D., and Denecker, M. (2004) ‘On the Relation between ID-Logic and Answer Set Programming’, in J. J. Alferes, and J. A. Leite (eds) Logics in Artificial Intelligence, 9th European Conference, JELIA 2004, LNCS 3229 (Berlin: Springer), 108–20.
Markov, A. A. (1949) ‘Constructible Falsity’, Mathematical Seminar of the LOMI, 6 Oct [in Russian].
Mints, G. (2010) ‘Cut-Free Formulations for a Quantified Logic of Here and There’, Annals of Pure and Applied Logic, 162 (3), 237–43.
Nelson, D. (1949) ‘Constructible Falsity’, Journal of Symbolic Logic, 14, 16–26.
Ono, H. (1983) ‘Model Extension Theorem and Craig’s Interpolation Theorem for Intermediate Predicate Logics’, Reports on Mathematical Logic, 15, 41–58.
Osorio, M., Navarro Perez, J. A., and Arrazola, J. (2005) ‘Safe Beliefs for Propositional Theories’, Annals of Pure and Applied Logic, 134, 63–82.
Pearce, D. (1997) ‘A New Logical Characterisation of Stable Models and Answer Sets’, in J. Dix et al. (eds) Nonmonotonic Extensions of Logic Programming. Proceedings NMELP 96, LNAI 1216 (Berlin: Springer), 57–70.
— (1999a) ‘From Here to There: Stable Negation in Logic Programming’, in D. Gabbay, and H. Wansing (eds) What is Negation? (Dordrecht: Kluwer).
— (1999b) ‘Stable Inference as Intuitionistic Validity’, Journal of Logic Programming, 38, 79–91.
— ‘Equilibrium Logic’, Annals of Mathematics and Artificial Intelligence, 47, 3–41.
Pearce, D., and Valverde, A. (2004) ‘Towards a First Order Equilibrium Logic for Nonmonotonic Reasoning’, in J. J. Alferes, and J. Leite (eds) Logics in Artificial Intelligence, Proceedings JELIA 2004, LNAI 3229 (Berlin: Springer), 147–60.
— (2005) ‘A First-Order Nonmonotonic Extension of Constructive Logic’, Studia Logica, 80(2–3), 321–46.
— (2006) ‘Quantified Equilibrium Logic’ [Tech. report, Univ. Rey Juan Carlos]. Available at http://www.satd.uma.es/matap/investig/tr/ma06_02.pdf [Accessed 18 October 2012].
— (2008) ‘Quantified Equilibrium Logic and Foundations for Answer Set Programs’, in Banda and Pontelli (2008), 546–60.
Pearce, D., and Wagner, G. (1990) ‘Reasoning with Negative Information I: Strong Negation in Logic programs’, in L. Haaparanta et al. (eds) Language, Knowledge and Intentionality: Perspectives on the Philosophy of Jaakko Hintikka (Helsinki: Acta Philosophica Fennica), 49, 430–53.
Rautenberg, W. (1979) Klassische und nichtklassische Aussagenlogik (Braunschwieg and Wiesbaden: Vieweg Verlag).
Smetanich, Y. S. (1960) ‘On the Completeness of a Propositional Calculus with an Additional Unary Operation’, in Proceeding of Moscow Mathematical Society, 9, 357–71 [in Russian].
Stalnaker, R. (1980) A Note on Non-Monotonic Modal Logic [Manuscript] (Cornell University). Reprinted in Artificial Intelligence, 64 (1993), 183–96.
Vorob’ev, N. N. (1952a) ‘A Constructive Propositional Calculus with Strong Negation’, in Doklady Akademii Nauk SSSR, 85 465–8 [in Russian].
— (1952b) ‘The Problem of Deducibility in Constructive Propositional Calculus with Strong Negation’, in Doklady Akademii Nauk SSSR, 85, 689–92 [in Russian].
Wang, K., and Zang, Y. (2005) ‘Nested Epistemic Logic Programs’, in Baral et al. (2005), 279–90.
Wittocx, J. et al. (2006) ‘Predicate Introduction under Stable and Well-Founded Semantics’, in S. Etalle, and M. Truszczyński (eds) Logic Programming, 22nd International Conference, ICLP 2006, Seattle, WA, USA, August 17–20, 2006, Proceedings. LNCS 4079 (Berlin: Springer), 242–56.
Editor information
Editors and Affiliations
Copyright information
© 2014 David Pearce
About this chapter
Cite this chapter
Pearce, D. (2014). Sixty Years of Stable Models. In: Mulligan, K., Kijania-Placek, K., Placek, T. (eds) The History and Philosophy of Polish Logic. History of Analytic Philosophy. Palgrave Macmillan, London. https://doi.org/10.1057/9781137030894_4
Download citation
DOI: https://doi.org/10.1057/9781137030894_4
Publisher Name: Palgrave Macmillan, London
Print ISBN: 978-1-349-44063-4
Online ISBN: 978-1-137-03089-4
eBook Packages: Palgrave Religion & Philosophy CollectionPhilosophy and Religion (R0)