Belief, awareness, and limited reasoning.

*(English)*Zbl 0634.03013The paper is a fundamental contribution to the logic of knowledge and belief. Some approaches to modelling lack of logical omniscience are presented in the paper. (An agent is logically omniscient if his beliefs are closed under logical consequence.) It is stressed that the problem of logical omniscience stems from a number of different sources.

The traditional possible-worlds semantics for knowledge and belief, and Levesque’s logic (LL) of implicit and explicit belief are reviewed. The first one suffers from the problem of logical omniscience.

Partial situations and incoherent situations are allowed in LL. Modal operators B, L of explicit and implicit belief are defined. Explicit belief does not suffer from the problems of logical omniscience: Bp\(\wedge B(p\Rightarrow q)\wedge \sim Bq\), \(\sim B(p\vee \sim p)\), B(p\(\wedge \sim p)\) are satisfiable, for example. In LL an agent’s lack of knowledge of valid formulas is due to the lack of awareness on the part of the agent of some primitive propositions. If we define Ap (to be aware of p) as B(p\(\vee \sim p)\) then for every valid propositional formula \(\phi\) there holds: \(\vDash A\phi \Rightarrow B\phi.\)

A logic of awareness (LA), an extension of LL, is semantically characterized by a Kripke structure for awareness. The effect of taking partial states is achieved in terms of support relations relative to a set \(\Psi\) of primitive propositions: \(\vDash_ T^{\Psi}\), \(\vDash_ F^{\Psi}\) (awareness is limited to primitive propositions). There are some differences between LL and LA: \((B_ ip\wedge B_ i(p\Rightarrow q))\Rightarrow B_ iq\) is valid in LA, \(B_ i(p\wedge \sim p)\) is not satisfiable in LA; some weak points of LL are removed; nested beliefs are allowed in LA, LA is a multiagent case of epistemic logic.

A logic of general awareness (LGA). Limiting awareness to primitive propositions is not sufficient for a model of resource-bounded reasoning. In a Kripke structure of general awareness sets of arbitrary formulas \({\mathcal A}_ i(s)\) are contained, of which agent i is aware in state s. An awareness operator is explicitly introduced into LGA. The authors do not place any restrictions on \({\mathcal A}_ i(s)\). Some possible restrictions leading to interesting distinct notions are discussed. In LGA, a satisfiable formula is, e.g., \(\sim (B_ i(p\wedge q)\equiv B_ i(q\wedge p))\). The equivalence \(B_ ip\equiv L_ ip\wedge A_ ip\) is valid.

The third system is a logic of local reasoning. An intuition behind this logic could be stated as follows: Agents can hold inconsistent beliefs, beliefs tend to come in non-interacting clusters. A Kripke structure for local reasoning contains nonempty sets of nonempty subsets of all states (frames of mind). \(B_ ip\) intuitively means that agent i believes p in some frame of mind (a local belief). The implicit belief is in a sense a result of pooling together the information of various frames of mind. \(B_ ip\wedge B_ i\sim p\) is satisfiable, but \(B_ i(p\wedge \sim p)\) is impossible. \(L_ i(false)\) is consistent, \(L_ i\) does not satisfy the axioms of the classical logic of belief.

A way of incorporating time into the framework of epistemic logic is presented. Knowledge acquisition and forgetting are possible applications.

Decision procedures and complete axiomatizations of the logics introduced in the paper are discussed. The approach of Fagin and Halpern seems to be fruitful in providing tools for constructing reasonable semantic models of notions of knowledge with a variety of properties.

The traditional possible-worlds semantics for knowledge and belief, and Levesque’s logic (LL) of implicit and explicit belief are reviewed. The first one suffers from the problem of logical omniscience.

Partial situations and incoherent situations are allowed in LL. Modal operators B, L of explicit and implicit belief are defined. Explicit belief does not suffer from the problems of logical omniscience: Bp\(\wedge B(p\Rightarrow q)\wedge \sim Bq\), \(\sim B(p\vee \sim p)\), B(p\(\wedge \sim p)\) are satisfiable, for example. In LL an agent’s lack of knowledge of valid formulas is due to the lack of awareness on the part of the agent of some primitive propositions. If we define Ap (to be aware of p) as B(p\(\vee \sim p)\) then for every valid propositional formula \(\phi\) there holds: \(\vDash A\phi \Rightarrow B\phi.\)

A logic of awareness (LA), an extension of LL, is semantically characterized by a Kripke structure for awareness. The effect of taking partial states is achieved in terms of support relations relative to a set \(\Psi\) of primitive propositions: \(\vDash_ T^{\Psi}\), \(\vDash_ F^{\Psi}\) (awareness is limited to primitive propositions). There are some differences between LL and LA: \((B_ ip\wedge B_ i(p\Rightarrow q))\Rightarrow B_ iq\) is valid in LA, \(B_ i(p\wedge \sim p)\) is not satisfiable in LA; some weak points of LL are removed; nested beliefs are allowed in LA, LA is a multiagent case of epistemic logic.

A logic of general awareness (LGA). Limiting awareness to primitive propositions is not sufficient for a model of resource-bounded reasoning. In a Kripke structure of general awareness sets of arbitrary formulas \({\mathcal A}_ i(s)\) are contained, of which agent i is aware in state s. An awareness operator is explicitly introduced into LGA. The authors do not place any restrictions on \({\mathcal A}_ i(s)\). Some possible restrictions leading to interesting distinct notions are discussed. In LGA, a satisfiable formula is, e.g., \(\sim (B_ i(p\wedge q)\equiv B_ i(q\wedge p))\). The equivalence \(B_ ip\equiv L_ ip\wedge A_ ip\) is valid.

The third system is a logic of local reasoning. An intuition behind this logic could be stated as follows: Agents can hold inconsistent beliefs, beliefs tend to come in non-interacting clusters. A Kripke structure for local reasoning contains nonempty sets of nonempty subsets of all states (frames of mind). \(B_ ip\) intuitively means that agent i believes p in some frame of mind (a local belief). The implicit belief is in a sense a result of pooling together the information of various frames of mind. \(B_ ip\wedge B_ i\sim p\) is satisfiable, but \(B_ i(p\wedge \sim p)\) is impossible. \(L_ i(false)\) is consistent, \(L_ i\) does not satisfy the axioms of the classical logic of belief.

A way of incorporating time into the framework of epistemic logic is presented. Knowledge acquisition and forgetting are possible applications.

Decision procedures and complete axiomatizations of the logics introduced in the paper are discussed. The approach of Fagin and Halpern seems to be fruitful in providing tools for constructing reasonable semantic models of notions of knowledge with a variety of properties.

Reviewer: J.Sefránek

##### MSC:

03B45 | Modal logic (including the logic of norms) |

68T99 | Artificial intelligence |

03B25 | Decidability of theories and sets of sentences |

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

logic of knowledge and belief; logical omniscience; possible-worlds semantics; Levesque’s logic; logic of awareness; Kripke structure; logic of local reasoning; decision procedures; complete axiomatizations
PDF
BibTeX
XML
Cite

\textit{R. Fagin} and \textit{J. Y. Halpern}, Artif. Intell. 34, No. 1, 39--76 (1988; Zbl 0634.03013)

Full Text:
DOI

##### References:

[1] | Anderson, A.R.; Belnap, N.D., Entailment, the logic of relevance and necessity, (1975), Princeton University Press Princeton, NJ · Zbl 0323.02030 |

[2] | Borgida, A.; Imielinski, T., Decision making in committees—a framework for dealing with inconsistency and non-monotonicity, (), 21-32 |

[3] | Chellas, B.F., Modal logic, (1980), Cambridge University Press New York · Zbl 0431.03009 |

[4] | Cresswell, M.J., Logics and languages, (1973), Methuen, London · Zbl 0287.02009 |

[5] | Doyle, J., A society of mind, (), 309-314 |

[6] | Eberle, R.A., A logic of believing, knowing and inferring, Synthese, 26, 356-382, (1974) · Zbl 0285.02026 |

[7] | Fagin, R.; Halpern, J.Y., Belief, awareness, and limited reasoning: preliminary report, (), 491-501 |

[8] | Fagin, R.; Halpern, J.Y.; Vardi, M.Y., A model-theoretic analysis of knowledge, (), 268-278 |

[9] | Fagin, R.; Vardi, M.Y., An internal semantics for modal logic, (), 305-315 |

[10] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof-systems, (), 291-304 · Zbl 0900.94025 |

[11] | Hadley, R.F., Logical omniscience, AI semantics, and models of belief, Simon fraser university tech. rept. LCCR TR 86-3, (1986), Burnaby, BC |

[12] | Halpern, J.Y.; Fagin, R., A formal model of knowledge, action, and communication in distributed systems: preliminary report, (), 224-236 |

[13] | Halpern, J.Y.; Moses, Y.O., Knowledge and common knowledge in a distributed environment, (), IBM research rept. RJ 4421, 50-61, (1986), second revision |

[14] | Halpern, J.Y.; Moses, Y.O., A guide to the modal logics of knowledge and belief, (), 480-490 |

[15] | Halpern, J.Y.; Reif, J.H., The propositional dynamic logic of deterministic, well-structured programs, Theor. comput. sci., 27, 127-165, (1983) · Zbl 0552.68035 |

[16] | Halpern, J.Y.; Vardi, M.Y., The complexity of reasoning about knowledge and time, (), 304-315 |

[17] | Hintikka, J., Knowledge and belief, (1962), Cornell University Press Ithaca, NY |

[18] | Hintikka, J., Impossible possible worlds vindicated, J. philos. logic, 4, 475-484, (1975) · Zbl 0334.02003 |

[19] | Hughes, G.E.; Cresswell, M.J., An introduction to modal logic, (1968), Methuen, London · Zbl 0205.00503 |

[20] | Konolige, K., Belief and incompleteness, () · Zbl 0661.68099 |

[21] | Konolige, K., What awareness isn’t: A sentential view of implicit and explicit belief, (), 241-250 |

[22] | Kripke, S., Semantical analysis of modal logic, Z. math. logik grundl. math., 9, 67-96, (1963) · Zbl 0118.01305 |

[23] | Ladner, R., The computational complexity of provability in systems of modal propositional logic, SIAM J. comput., 6, 3, 467-480, (1977) · Zbl 0373.02025 |

[24] | Lakemeyer, G., Tractable meta-reasoning in propositional logics of belief, (1987), unpublished manuscript |

[25] | Lehmann, D.J., Knowledge, common knowledge, and related puzzles, (), 62-67 |

[26] | Levesque, H.J., A logic of implicit and explicit belief, (), Lab. tech. rept. FLAIR #32, 198-202, (1984), Palo Alto, CA |

[27] | H.J. Levesque, Global and local consistency and completeness of beliefs, to appear. |

[28] | Lukasiewicz, J., O logice trojwartosciowej (on three-valued logic), Ruch filozoficzny, 5, 169-171, (1920) |

[29] | Makinson, D., On some completeness theorems in modal logic, Z. math. logik grundl. math., 12, 379-384, (1966) · Zbl 0295.02014 |

[30] | Merritt, M.J., Cryptographic protocols, () |

[31] | Minsky, M., Plain talk about neurodevelopmental epistemology, (), 1083-1092 |

[32] | Moore, R.C.; Hendrix, G., Computational models of beliefs and the semantics of belief sentences, () |

[33] | Moses, Y.; Tuttle, M., Programming simultaneous actions using common knowledge, (), 208-221 |

[34] | Rantala, V., Impossible worlds semantics and logical omniscience, Acta philos. fennica, 35, 106-115, (1982) · Zbl 0519.03002 |

[35] | Rescher, N.; Brandom, R., Knowledge and belief, (1979), Rowman and Littlefield |

[36] | Rivest, R.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM, 21, 2, 120-126, (1978) · Zbl 0368.94005 |

[37] | Rosenschein, S.J., Formal theories of knowledge in AI and robotics, New generation comput., 3, 345-357, (1985) · Zbl 0596.68061 |

[38] | Sato, M., A study of Kripke-style methods of some modal logics by Gentzen’s sequential method, Publications research inst. math. sci. Kyoto univ., 13, 2, (1977) · Zbl 0405.03013 |

[39] | Segerberg, K., An essay on classical modal logic, (1972), Philosophical Studies Uppsala |

[40] | Sistla, A.P.; Clarke, E.M., The complexity of propositional linear temporal logics, J. ACM, 32, 3, 240-251, (1985) · Zbl 0632.68034 |

[41] | Stalnaker, R., Inquiry, (1985), MIT Press Cambridge, MA |

[42] | Vardi, M.Y., On epistemic logic and logical omniscience, (), 293-306 |

[43] | Wigner, E.P., The unreasonable effectiveness of mathematics in the natural sciences, Comm. pure appl. math., 13, 1-14, (1960) · Zbl 0102.00703 |

[44] | Zadrozny, W., Explicit and implicit beliefs, a solution of a probem of H. levesque, (1985), Unpublished manuscript |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.