Abstract
The Hintikka-style modal logic approach to knowledge contains a well-known defect of logical omniscience, i.e., the unrealistic feature that an agent knows all logical consequences of her assumptions. In this paper, we suggest the following Logical Omniscience Test (LOT): an epistemic system E is not logically omniscient if for any valid in E knowledge assertion \(\mathcal{A}\) of type ‘Fis known,’ there is a proof of F in E, the complexity of which is bounded by some polynomial in the length of \(\mathcal{A}\). We show that the usual epistemic modal logics are logically omniscient (modulo some common complexity assumptions). We also apply LOT to evidence-based knowledge systems, which, along with the usual knowledge operator K i (F) (‘agent i knows F’), contain evidence assertions t:F (‘t is a justification for F’). In evidence-based systems, the evidence part is an appropriate extension of the Logic of Proofs LP, which guarantees that the collection of evidence terms t is rich enough to match modal logic. We show that evidence-based knowledge systems are logically omniscient w.r.t. the usual knowledge and are not logically omniscient w.r.t. evidence-based knowledge.
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
Alechina, N., Logan, B.: Ascribing beliefs to resource bounded agents. In: Proceedings of the 1st International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS-2002), Bologna, Italy, vol. II, pp. 881–888. ACM Press, New York (2002)
Artemov, S.: Operational modal logic. Technical Report MSI 95-29, Cornell University (1995)
Artemov, S.: Explicit provability and constructive semantics. Bulletin of Symbolic Logic 7(1), 1–36 (2001)
Artemov, S.: Justified Common Knowledge. Theoretical Computer Science 357(1-3), 4–22 (2006)
Artemov, S., Kazakov, E., Shapiro, D.: Epistemic logic with justifications. Technical Report CFIS 99-12, Cornell University (1999)
Artemov, S., Nogina, E.: Logic of knowledge with justifications from the provability perspective. Technical Report TR-2004011, CUNY Ph.D. Program in Computer Science (2004)
Artemov, S., Nogina, E.: Introducing justification into epistemic logic. Journal of Logic and Computation 15(6), 1059–1073 (2005)
Artemov, S., Nogina, E.: On epistemic logic with justification. In: van der Meyden, R. (ed.) Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2005), Singapore, June 10–12, 2005, pp. 279–294. National University of Singapore (2005)
Aumann, R.: Reasoning about knowledge in economics. In: Halpern, J. (ed.) Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge (TARK 1986), Monterey, CA, USA, p. 251. Morgan Kaufmann, San Francisco (1986)
Bonjour, L.: The coherence theory of empirical knowledge. Philosophical Studies, 30, 281–312 (1976), reprinted in Contemporary Readings in Epistemology. In: Goodman, M.F., Snyder, R.A. (eds)., pp.70–89. Prentice Hall, Englewood Cliffs (1993)
Cook, S., Reckhow, R.: On the lengths of proofs in the propositional calculus (preliminary version). In: Conference Record of 6th Annual ACM Symposium on Theory of Computing STOC 1974, Seattle, WA, USA, pp. 135–148. ACM Press, New York (1974)
Corbin, J., Bidoit, M.: A rehabilitation of Robinson’s unification algorithm. In: Mason, R.E.A. (ed.) Proceedings of the IFIP 9th World Computer Congress (IFIP Congress-1983), Paris, France, pp. 909–914. North-Holland, Amsterdam (1983)
Elgot-Drapkin, J., Miller, M., Perlis, D.: Memory, Reason, and Time: The Step-logic approach. In: Cummins, R., Pollock, J. (eds.) Philosophy and AI: Essays at the Interface, pp. 79–103. MIT Press, Cambridge (1991)
Fagin, R., Halpern, J.: Belief, awareness, and limited reasoning: Preliminary report. In: Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI 1985), pp. 491–501 (1985)
Fagin, R., Halpern, J.: Belief, awareness, and limited reasoning. Artificial Intelligence 34(1), 39–76 (1988)
Fagin, R., Halpern, J., Vardi, M.: A nonstandard approach to the logical omniscience problem. Artificial Intelligence 79(2), 203–240 (1995)
Fitting, M.: A semantics for the logic of proofs. Technical Report TR-2003012, CUNY Ph.D. Program in Computer Science (2003)
Fitting, M.: Semantics and tableaus for LPS4. Technical Report TR-2004016, CUNY Ph.D. Program in Computer Science (2004)
Fitting, M.: The logic of proofs, semantically. Annals of Pure and Applied Logic 132(1), 1–25 (2005)
Gettier, E.: Is Justified True Belief Knowledge? Analysis 23, 121–123 (1963)
Goldman, A.: A causal theory of knowing. The Journal of Philosophy 64, 335–372 (1967)
Halpern, J., Moses, Y.: A guide to modal logics of knowledge and belief. In: Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI 1985), pp. 480–490 (1985)
Halpern, J., Moses, Y.: A guide to completeness and complexity for modal logics of knowledge and beliefs. Journal of Artificial Intelligence 54, 319–379 (1992)
Hendricks, V.: Active agents. Journal of Logic, Language and Information 12(4), 469–495 (2003)
Hintikka, J.: Knowledge and Belief. Cornell University Press (1962)
Hintikka, J.: Impossible possible worlds vindicated. Journal of Philosophical Logic 4, 475–484 (1975)
Konolige, K.: A Deductive Model of Belief. Research Notes in Artificial Intelligence. Morgan Kaufmann, San Francisco (1986)
Krupski, N.: On the complexity of the reflected logic of proofs. Theoretical Computer Science 357, 136–142 (2006)
Kuznets, R.: Complexity of evidence-based knowledge. In: Proceeding of Rationality and Knowledge workshop of ESSLLI 2006 (accepted for publication, 2006)
Ladner, R.: The computational complexity of provability in systems of modal propositional logic. SIAM Journal on Computing 6(3), 467–480 (1977)
Lehrer, K., Paxson, T.: Knowledge: undefeated justified true belief. The Journal of Philosophy 66, 1–22 (1969)
Lenzen, W.: Knowledge, belief and subjective probability. In: Hendricks, V., Jörgensen, K., Pedersen, S. (eds.) Knowledge Contributors. Kluwer Academic Publishers, Dordrecht (2003)
Levesque, H.: A logic of implicit and explicit belief. In: Brachman, R. (ed.) Proceedings of the National Conference on Artificial Intelligence (AAAI-1984), Austin, TX, USA, pp. 198–202. AAAI Press, Menlo Park (1984)
Lewis, D.: Elusive knowledge. Australian Journal of Philosophy 7, 549–567 (1996)
Mkrtychev, A.: Models for the logic of proofs. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol. 1234, pp. 266–275. Springer, Heidelberg (1997)
Montague, R.: Universal Grammar. Theoria 36, 373–398 (1970)
Moore, R.: Reasoning about knowledge in artificial intelligence. In: Halpern, J.Y. (ed.) Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-1986), Monterey, CA, USA, p. 81. Morgan Kaufmann, San Francisco (1986)
Moses, Y.: Resource-bounded knowledge. In: Vardi, M. (ed.) Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-1988), Pacific Grove, CA, USA, pp. 261–275. Morgan Kaufmann, San Francisco (1988)
Nozick, R.: Philosophical Explanations. Harvard University Press (1981)
Parikh, R.: Knowledge and the problem of logical omniscience. In: Ras, Z., Zemankova, M. (eds.) Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems (ISMIS 1987), Charlotte, NC, USA, pp. 432–439. North-Holland, Amsterdam (1987)
Parikh, R.: Logical omniscience. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 22–29. Springer, Heidelberg (1995)
Parikh, R.: Logical omniscience and common knowledge: WHAT do we know and what do WE know? In: van der Meyden, R. (ed.) Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), Singapore, June 10–12, 2005, pp. 62–77. National University of Singapore (2005)
Pudlak, P.: The Lengths of Proofs. In: Buss, S. (ed.) Handbook of Proof Theory, pp. 547–637. Elsevier, Amsterdam (1998)
Rantala, V.: Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica 35, 18–24 (1982)
Scott, D.: Advice in modal logic. In: Lambert, K. (ed.) Philosophical Problems in Logic, pp. 143–173. Reidel (1970)
Shin, H., Williamson, T.: Representing the knowledge of turing machine. Theory and Decision 37(1), 125–146 (1994)
Vardi, M.: On epistemic logic and logical omniscience. In: Halpern, J. (ed.) Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge (TARK 1986), Monterey, CA, USA, pp. 293–305. Morgan Kaufmann, San Francisco (1986)
Wansing, H.: A general possible worlds framework for reasoning about knowledge. Studia Logica 49(4), 523–539 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Artemov, S., Kuznets, R. (2006). Logical Omniscience Via Proof Complexity. In: Ésik, Z. (eds) Computer Science Logic. CSL 2006. Lecture Notes in Computer Science, vol 4207. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11874683_9
Download citation
DOI: https://doi.org/10.1007/11874683_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45458-8
Online ISBN: 978-3-540-45459-5
eBook Packages: Computer ScienceComputer Science (R0)