KR Conference 2012 Conference Paper
- Gerhard Lakemeyer
- Hector J. Levesque
made it possible to study autoepistemic reasoning within a classical monotonic logic, leading, among other things, to an axiomatic characterization of the logic in the propositional case, and a first-order account that handles quantifying-in. In subsequent work by Lakemeyer and Levesque, henceforth called LL, [2005; 2006], only-knowing was extended to capture other forms of nonmonotonic reasoning, and in particular, the default logic (DL) proposed by Reiter [1980] and a variant of AEL due to Konolige [1988]. As described by Reiter, a default rule α: β / γ has an intuitive reading of “if α is believed and it is consistent to believe β then infer that γ is true. ” Hence Konolige proposed translating the default rule into a sentence of AEL of the form Only-knowing was originally introduced by Levesque to capture the beliefs of an agent in the sense that its knowledge base is all the agent knows. When a knowledge base contains defaults Levesque also showed an exact correspondence between only-knowing and autoepistemic logic. Later these results were extended by Lakemeyer and Levesque to also capture a variant of autoepistemic logic proposed by Konolige and Reiter’s default logic. One of the benefits of such an approach is that various nonmonotonic formalisms can be compared within a single monotonic logic leading, among other things, to the first axiom system for default logic. In this paper, we will bring another large class of nonmonotonic systems, which were first studied by McDermott and Doyle, into the only-knowing fold. Among other things, we will provide the first possible-world semantics for such systems, providing a new perspective on the nature of modal approaches to nonmonotonic reasoning. Kα ∧ Mβ ⊃ γ. is valid, which can be read as “if we only know that P (a) or P (b), then we know that something is a P, but not what. ” Levesque also showed that, when the KB itself is allowed to mention K, then O captures the autoepistemic logic (AEL) proposed by Moore [1985], in the sense that the beliefs entailed by only-knowing KB are precisely those which are in all stable expansions of KB. This connection In the simplest case, M is understood as the dual of K in the sense that Mβ stands for ¬K¬β. To properly characterize DL, however, a more complex treatment of the M is needed. Nonetheless, LL were able to present a variant of only-knowing that did the job and allowed the properties of DL to be understood in terms of an underlying model of belief in a classical monotonic logic: a model theory based on possible worlds, and later, a proof theory based on axioms and rules of inference [Lakemeyer and Levesque, 2005; 2006]. 2 In this paper, we continue this work and bring another large class of nonmonotonic systems into the only-knowing fold. We investigate the so-called nonmonotonic modal systems (NMS) first introduced by McDermott and Doyle [1980], and reconstructed by Marek et al. [1993]. Roughly speaking, an NMS starts with a classical modal system of belief (like the system K or K45 or T, in the terminology of Chellas [1980]), and declares a set of formulas to be an expansion of α in the NMS if it consists of the formulas that can be derived in the modal system from α together with the assumptions ¬Kβ for those β that cannot be derived. Marek et al. show various properties of these NMS based on a variety of modal logics, including how different modal systems λ1 and λ2 can sometimes give rise to the same NMS (that is, where the λ1 -expansions coincide with the λ2 -expansions). Copyright c 2012, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved. 1 In this paper, we use the terms “knowledge” and “belief” interchangeably to mean belief. 2 We remark that other nonmonotonic logics with two distinct modalities were proposed that also capture DL such as [Lin and Shoham, 1990; Lifschitz, 1994]. See [Lakemeyer and Levesque, 2005] for a discussion how these relate to LL’s work.