Abstract
In his treatise Meaning and Necessity, Carnap introduced an original approach to modal logic which is quite different from the well-known Lewis systems. Recently, it turned out that there are interesting connections between Carnap's modal logic and finite model theory for modal logics. In addition, Carnap's logic has applications in the field of epistemic reasoning. It was also shown that formulas of Carnap's logic are structurally equivalent to trees of NP queries, more precisely, of satisfiability tests. In this paper, we give a survey of these results. Moreover, we extend Carnap's logic in a natural way by the possibility of deriving consequences from nonmodal theories and show that the resulting formalism is nonmonotonic. Finally, we explain the relationship between Carnap's logic and autoepistemic logic and show that autoepistemic reasoning corresponds to solving problems equivalent to (possibly cyclic) graphs of interdependent NP queries.
This work was done in the context of the Christian Doppler Laboratory for Expert Systems. Some of the results of the present paper were also presented in [10]. A journal version, integrating the results of [10] and most of the results of the present paper is available from the author.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Bressan. A General Interpreted Modal Calculus. Yale University Press, New Haven and London, 1972.
S.R. Buss and L. Hay. On Truth-Table Reducibility to SAT. Information and Computation, 91:86–102, 1991.
R. Carnap. Meaning and Necessity. The University of Chicago Press, 1947.
B. Chellas. Modal Logic, an Introduction. Cambridge Univ. Press, Cambridge, UK, 1980.
F.M. Donini, M. Lenzerini, D. Nardi, W. Nutt, and A. Schaerf. Adding Epistemic Operators to Concept Languages. In Proc. of the 3rd Int. Conf. on Principles of Knowledge Representation and Reasoning KR-92, pages 342–353, 1992.
R. Fagin. Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50–58, 1976.
Michael Garey and David S. Johnson. Computers and Intractability — A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.
Y.V. Glebskii, D.I. Kogan, M.I. Liogon'kii, and V.A. Talanov. Range and Degree of Realizability of Formulas in the Restricted Predicate Calculus (in Russian). Kibernetika, 2:17–28, 1969. English translation in Cybernetics, vol.5 (1969), pp.142–154.
G. Gottlob. Complexity Results for Nonmonotonic Logics. The Journal of Logic and Computation, 2:3:397–425, June 1992.
G. Gottlob. NP Trees and Carnap's Modal Logic. In Proc. 34th Annual Symp. on Foundations of Comp. Sci. (FOCS'93), Palo Alto, CA, IEEE Computer Soc. Press, pp. 42–51, 1993.
J.Y. Halpern and B. Kapron. Zero-One Laws for Modal Logic. In Proc. of the Seventh Annual IEEE Symposium on Logic in Computer Science, 1992. Full version: Tech Report RJ 8836 (79218), 1992, IBM Research Division, Almaden Research Center. (See also ref. [12].)
J.Y. Halpern and B. Kapron. Zero-One Laws for Modal Logic. To appear in Annals of Pure and Applied Logic. (Updated version of [11] which takes into account the results of [10].)
J.Y. Halpern and Y. Moses. Towards A Theory of Knowledge and Ignorance: Preliminary Report. In Proc. Non-Monotonic Reasoning Workshop AAAI, pages 125–143, 1984. Reprinted in Logics and Models of Concurrent Systems K. Apt editor, Springer Verlag, 1985, pp.459–476.
L. Hemachandra. The Strong Exponential Hierarchy Collapses. Journal of Computer and System Sciences, 39:299–322, 1989.
G.E. Huges and M. J. Cresswell. An Introduction to Modal Logic. Methuen London, 1978.
David S. Johnson. A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, chapter 2, pages 67–161, Elsevier Science Publishers B.V. (North-Holland), 1990.
Hector J. Levesque. Foundations of a Functional Approach to Knowledge Representation. Artificial Intelligence, 23(1984), pp. 155–212, 1984.
W. Marek. Stable Theories in Autoepistemic Logic. Fundamenta Informaticae, 12:243–254, 1989.
W. Marek, G. Schwarz, and M. Truszczynski. Modal Nonmonotonic Logics: Ranges, Characterization, Computation. Journal of the ACM, 40(4):963–990, 1993.
W. Marek and M. Truszczyński. Autoepistemic Logic. Journal of the ACM, 38(3):588–619, 1991.
W. Marek and M. Truszczyński. Nonmonotonic Logic. Springer, Berlin 1993.
D. McDermott and J. Doyle. Nonmonotonic Logic II. JACM 29:1982, pp. 33–57.
D. McDermott and J. Doyle. Nonmonotonic Logic I. Artificial Intelligence 13:1980, pp. 41–72.
R.C. Moore. Semantical Considerations on Nonmonotonic Logics. Artificial Intelligence, 25:75–94, 1985.
I. Niemelä. Decision Procedure for Autoepistemic Logic. In Proceedings of 9th Conference on Automated Deduction CADE-88, pages 676–684, 1988.
I. Niemelä. On the Decidability and Complexity of Autoepistemic Reasoning. Fundamenta Informaticae, 17:117–155, 1992.
I. Niemelä. Towards Automatic Autoepistemic Reasoning. In Proc. Europ. Workshop on Logics in AI, Amsterdam, September 1990, Springer, 1991.
C.H. Papadimitriou and S. Zachos. Two Remarks on the Power of Counting. In Proc. 6th GI Conf. on Theoretical Computer Science, pages 269–276, Springer Verlag, 1983.
R. Reiter. On Asking what a Database Knows. In Lloyd, J. W., editor, Symposium on Computational Logics, pages 96–113, Springer Verlag, ESPRIT Basic Research Action Series, 1990.
R.C Stalnaker. A Note on Nonmonotonic Modal Logic. 1980. Manuscript, Dept of Philosophy, Cornell Univ.
John E. Savage. The Complexity of Computing. John Wiley & Sons, 1976.
G. F. Shvarts. Autoepistemic Modal Logic of Knowledge. In Logic Programming and Nonmonotonic Reasoning, A. Nerode, W. Marek, and V.S. Subrahmanian, eds. MIT Press, Cambridge, Mass., 1991, pp. 260–274.
Klaus Wagner. Bounded Query Classes. SIAM J. Comp., 19(5):833–846, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gottlob, G. (1994). From Carnap's modal logic to autoepistemic logic. In: MacNish, C., Pearce, D., Pereira, L.M. (eds) Logics in Artificial Intelligence. JELIA 1994. Lecture Notes in Computer Science, vol 838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021961
Download citation
DOI: https://doi.org/10.1007/BFb0021961
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58332-5
Online ISBN: 978-3-540-48657-2
eBook Packages: Springer Book Archive