Notes


An excellent introduction to propositional logic can be found in Enderton's text [1972], which is the source of the example about borogroves. Numerous alternatives to classical logic have been proposed over the years. Perhaps the best known include multi-valued logics [Rescher 1969; Rine 1984], intuitionistic logic [Heyting 1956], and relevance logics [Anderson and Belnap 1975].

A simple complete axiomatization for propositional logic is given by the two axioms

together with the inference rule Modus Ponens. A completeness proof can be found in [Popkorn 1994].

Modal logic was discussed by several authors in ancient times, but the first symbolic and systematic approach to the subject appears to be the work of Lewis beginning in 1912 and culminating in his book Symbolic Logic with Langford [Lewis and Langford 1959]. Modal logic was originally viewed as the logic of possibility and necessity. (That is, the only modal operators considered were operators for necessity and possibility.) More recently, it has become common to view knowledge, belief, time, and so on, as modalities, and the term "modal logic" has encompassed logics for reasoning about these notions as well. Possible-worlds semantics seems to have first been suggested by Carnap [1946; 1947], and was further developed independently by many researchers, reaching its current form with Kripke [1963]. The first to consider a modal logic of knowledge was Hintikka [1962]. A thorough discussion of modal logic can be found in some of the standard texts in the area, such as [Hughes and Cresswell 1968], [Chellas 1980], [Popkorn 1994], and [Blackburn, de Rijke, and Venema 2001].

The historical names S4 and S5 are due to Lewis, and are discussed in his book with Langford. The names K and T are due to Lemmon [1977], as is the idea of naming the logic for the significant axioms used.

The presentation of Section 7.2 is largely taken from [Fagin, Halpern, Moses, and Vardi 1995]. A proof of Theorem 7.2.1 can also be found there, as well as a discussion of approaches to giving semantics to knowledge that distinguish between logically equivalent formulas (in that one of two logically equivalent formulas may be known while the other is not) and take computational issues into account. Finally, the book contains an extensive bibliography of the literature on the subject. One particularly useful reference is [Lenzen 1978], which discusses in detail the justifications of various axioms for knowledge.

See [Halpern 2001c] for a recent discussion of a definition of rationality in terms of knowledge and counterfactuals (a topic discussed in Chapter 8). This paper represents only the very tip of the iceberg as far as rationality goes; the references in the paper give some additional pointers for further reading.

The logics QUn and QU, n were introduced in [Fagin, Halpern, and Megiddo 1990] and used for reasoning about both probability and belief functions. QUn can be viewed as a formalization of Nilsson's [1986] probabilistic logic; it is also a fragment of a propositional probabilistic dynamic logic introduced by Feldman [1984]. (Dynamic logic is a logic for reasoning about actions; see [Harel, Kozen, and Tiuryn 2000].) Theorems 7.3.3 and 7.7.1 are proved in [Fagin, Halpern, and Megiddo 1990]. (Actually, a somewhat simpler version of these theorems is proved. Only simple probability structures are considered, and the language is simplified so that in a likelihood term of the form (φ), the formula φ is required to be a propositional formula. Nevertheless, the same basic proof techniques work for the more general result stated here.) In addition, a finite collection of axioms is given that characterizes Ineq. Finally, the complexity of these logics is also considered. The satisfiability problem for QUn in simple probability structures (whether measurable or not) is shown to be NP-complete, no worse than that of propositional logic. The satisfiability problem for QUn in simple belief structures and in simple lower probability structures is also NP-complete [Fagin and Halpern 1991b; Halpern and Pucella 2001]. It would be interesting to understand if there is some deeper reason why the complexity of the satisfiability problem for all these logics turns out to be the same.

For QU, n, as shown in [Fagin, Halpern, and Megiddo 1990], satisfiability in simple probability structures can be decided in polynomial space (although no lower bound other than NP is known). The satisfiability problem for QU, n for other logics has not been considered, although I conjecture the PSPACE upper bound still holds.

For the more general probability structures considered here, where there are n agents and the probability assignment may depend on the world, the complexity of the satisfiability problem for both QUn and QU, n is PSPACE-complete [Fagin and Halpern 1994]. (The lower bound holds even if n = 1, as long as no constraints are placed on the probability assignment.) Again, although the satisfiability problem for other logics has not been considered, I conjecture that PSPACE completeness still holds.

Theorem 7.4.1, Exercise 7.10 and Exercise 7.11 are proved in [Fagin and Halpern 1991b], using results of [Fagin, Halpern, and Megiddo 1990]. Fari as del Cerro and Herzig [1991] provide a complete axiomatization for possn that is similar in spirit to (although their axiomatization is not quite complete as stated; see [Halpern 1997a]).

The proof of Theorem 7.5.1 follows similar lines to the proofs of Theorems 3.1 and 3.2 in [Halpern 1997a].

The logic of probability and knowledge considered here was introduced in [Fagin and Halpern 1994]. As mentioned in the notes to Chapter 6, this is also where the notions CONS, SDP, and UNIF were introduced; Theorems 7.6.1 and 7.6.2 are taken from there. Although this was the first paper to consider a combined logic of probability and knowledge, combinations of probability with other modal operators had been studied earlier. Propositional probabilistic variants of temporal logic (a logic for reasoning about time; see Chapter 6) were considered by Hart and Sharir [1984] and Lehmann and Shelah [1982], while probabilistic variants of dynamic logic were studied by Feldman [1984] and Kozen [1985]. Monderer and Samet [1989] also considered a semantic model that allows the combination of probability and knowledge, although they did not introduce a formal logic for reasoning about them.

The fact that CP implies no disagreement in expectation (and, in a sense, can be characterized by this property) was observed by Bonanno and Nehring [1999], Feinberg [1995; 2000], Morris [1994], and Samet [1998a]. The axiom CP2 (and CPn in Exercise 7.23) is taken from [Feinberg 2000; Samet 1998a]. An axiomatization of KQUC2 in the presence of CP can be found in [Halpern 1998a], from where Theorem 7.6.3 is taken.

See the notes to Chapter 4 for references regarding I and Irv. Some work has been done on providing a logical characterization of Irv (again, see the notes to Chapter 4); I am not aware of any work on characterizing I.

The material in Section 7.8 on reasoning about expectation is taken from [Halpern and Pucella 2002]. More details can be found there, including an axiomatization of reasoning about propositional gamble inequalities (EXP5).




Reasoning About Uncertainty
Reasoning about Uncertainty
ISBN: 0262582597
EAN: 2147483647
Year: 2005
Pages: 140

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net