Exercises


  • 8.1 Show that {U : i(w) U} is a filter. Also show that, given a probability measure μ on W, the set {U W : μ(U) = 1} is a filter.

  • 8.2 This exercise examines the connection between filters and epistemic frames. Suppose that W is a set of worlds and associates with every world in W a filter.

    1. If W is finite, show that there exists a (unique) binary relation on W such that (w) = {U : (w) U}

    2. (b) What conditions on guarantee that is (i) reflexive, (ii) transitive, and (iii) Euclidean?

    3. (c) Show that if W is infinite, there is a function such that for no binary relation on W is it the case that (w) = (U : i(w) U}.

  • 8.3 Show that if U V and Pl(U) > Pl(U), then Pl(V) > Pl(V).

  • 8.4 Show that if Pl is a cpm satisfying CPl5, then Pl(U | V) > Pl(U | V) iff Pl(U V) > Pl(U V).

  • 8.5 Prove Proposition 8.1.1.

  • 8.6 Show that the plausibility measure Pllot defined in Example 8.1.2 satisfies Pl4.

  • * 8.7 This exercise compares the expressive power of the belief operator defined in terms of an accessibility relation and the belief operator defined in terms of plausibility measures that satisfy Pl4. An epistemic belief structure is one of the form M = (W, 1,, n, 1,, n, π), where 1,, n are accessibility relations used to capture knowledge and 1,, n are accessibility relations used to capture belief. Let KBn be the language with modal operators K1, , Kn for knowledge and B1, , Bn for belief. As expected, the semantics for Biφ is

    (The semantics of knowledge remains unchanged: (M, w) Kiφ iff (M, w) φ for all w i(w).)

    1. Given an epistemic belief structure M = (W, 1,,n, 1,, n, π), define plausibility assignments 1,,n by taking i(w) = (i(w), Plw,i), where, for U i(w)),

      Let M = (W, 1,,n, 1,,n, π) Show that M is an epistemic belief structure (i.e., show that all the plausibility measures that arise satisfy Pl4) and that M and M agree on all formulas in KB, that is, if φ KBn, then, for all w W,

    2. Given an epistemic belief structure M = (W, 1,, n, 1,, n, π), where W is finite, define a binary relation i by setting i(w) = {U : Plw,i(U Ww,i) > Plw,i(U Ww,i)} if Pl(Ww,i)> , and setting i (w) = if Pl(Ww, i) =. Let M = (W, 1,, n, 1,, n, π). Show that M and M agree on all formulas in KB, that is, if φ KBn then, for all w W,

      (Hint: If your proof does not use the fact that W is finite and invoke Pl4, then it is probably not completely correct.)

    3. Show that the construction in part (b) does not work if W is infinite, by constructing a structure M for knowledge and qualitative plausibility for which the set W of possible worlds is infinite and the corresponding structure M for knowledge and belief does not agree with M on all formulas in KB.

  • 8.8 Consider a simple measurable plausibility structure M = (W, Pl, π), where Pl satisfies Pl4. Define B, as in Section 8.2, in terms of plausibility. Show that this definition satisfies the axioms of KD45. (It can actually be shown that KD45 is a sound and complete axiomatization with respect to this semantics, but that is beyond the scope of this book.)

  • 8.9 Prove Proposition 8.2.1.

  • 8.10 State analogues of CONS, SDP, and UNIF in the case where a binary relation i is used to model belief, and prove an analogue of Proposition 8.2.1 for your definition.

  • 8.11 Another property of interest relating knowledge and belief is called certainty.It is characterized by the following two axioms:

    1. Show that if B satisfies the axioms of KD45 and the entailment property holds, then B satisfies negative certainty as well.

    2. Show that if B satisfies the axioms of KD45, K satisfies the axioms of S5, the entailment property holds, and positive certainty for B holds, then B is equivalent to K; that is, Bφ Kφ is provable. Thus, under these assumptions, an agent cannot hold false beliefs: φ Bφ is not satisfiable. (This result holds even if B does not satisfy the introspection axioms K4 and K5.)

  • 8.12 Show that if φ ψ is true under a truth assignment v, then so is φ φ′ ψ, no matter what φ′ is.

  • 8.13 Show that all the properties of P hold if is interpreted as , the material conditional.

  • 8.14 Show that, in Example 8.3.1, if is interpreted as , then penguin must be false.

  • 8.15 Show that, if μ(flyM | birdM) = 1, μ(flyM | penguinM) = 0, and μ(birdM | penguinM) = 1, then μ(penguinM) = 0.

  • 8.16 Show that soundness holds in Theorem 8.4.1. That is, show that if Σ P φ ψ then Σ cps φ ψ.

  • 8.17 Suppose that M meas. For this exercise, use the definition of in terms of probability: M φ ψ if μ(φM) = 0 or μ(ψM | φM) > μ( ψM | φM). Show that the following are equivalent:

    1. M φ ψ;

    2. μ(φM) = 0 or μ(φ ψM) > μ(φ ψM);

    3. μ(φM) = 0 or μ(ψM | φM) > 1/2.

    Moreover, show that this interpretation satisfies LLE, RW, and REF.

  • 8.18 Show that the OR rule is violated in the structure M1 of Example 8.4.2.

  • 8.19 Fix > 0. For this exercise, if M meas, say that M φ ψ if μ(φM) = 0 or μ(ψM | φM) > 1 . Show that this interpretation satisfies LLE, RW, and REF, but not AND, CM, or OR.

  • 8.20 Given a simple nonstandard probability structure M = (W, μns, π) (which is just like a simple probability structure, except that now μns is a nonstandard probability measure on W), say M φ ψ if either μns(φM = 0 or the closest standard real number to μns (ψM | φM) is 1. Show this approach satisfies all the properties of P. (In fact, it follows from Theorem 8.4.15 that P is a sound and complete axiomatization of default reasoning with respect to nonstandard probability structures.)

  • 8.21 Show directly that OR and CM hold in simple PS structures (i.e., without using Theorems 8.4.10 and 8.4.12).

  • * 8.22 Show that {p q r, p r}P p q.

  • 8.23 Show directly that OR and CM hold in possibility structures (i.e., without using Theorems 8.4.10 and 8.4.12). In addition, complete the proof of the soundness of the AND rule given in Theorem 8.4.5 by showing that (U1 U2) (U1 V2) = U1 and that if max(α, β) > max(γ, δ) and max(α, γ) > max(β, δ), then α > max(β, γ, δ).

  • 8.24 Show that M φ ψ iff φM ψM for every structure M.

  • 8.25 Prove Theorem 8.4.7.

  • 8.26 Prove Lemma 8.4.8.

  • 8.27 Proposition 8.1.1 gives a sense in which Pl4 is necessary and sufficient for conditional beliefs to be closed under conjunction. The AND rule can also be viewed as saying that conditional beliefs are closed under conjunction (viewing φ ψ as B(ψ| φ)). This exercise shows that Pl4 is necessary for the AND rule in three (related) senses.

    1. Suppose that (W, Pl) is a plausibility space that does not satisfy Pl4. Show that there exists an interpretation π such that the simple measurable plausibility structure (W, Pl, π) does not satisfy the AND rule.

    2. Suppose that M = (W, Pl, π) is a plausibility structure such that π(w) π(w) if w w and Pl does not satisfy Pl4. Again, show that M does not satisfy the AND rule.

    3. Suppose that M = (W, Pl, π) is a simple plausibility structure such that Pl does not satisfy Pl4 when restricted to sets definable by formulas. That is, there exist formulas φ1, φ2, and φ3 such that φ1M, φ2M, and φ3M are pairwise disjoint, Pl(φ1 φ2M) > Pl(φ3M), Pl(φ1 φ3M) > Pl(φ2M), and Pl(φ1M) Pl(φ2 φ3M). Again, show that M does not satisfy the AND rule.

    Show that the requirement in part (b) that π(w) π(w) if w w is necessary by demonstrating a plausibility structure that does not satisfy Pl4 and yet satisfies the AND rule. (Of course, for this plausibility structure, it must be the case that there are two distinct worlds that satisfy the same truth assignment.)

  • 8.28 Show that if M = (W, Pl, π) is a simple measurable plausibility structure where Pl satisfies Pl4, then M satisfies CM, and if M φ1 ψ, M φ2 ψ, and either Pl(φ1M) or Pl(φ2M) , then M (φ1 φ2) ψ.

  • 8.29 Find a belief function Bel such that Bel(U) = Bel(V) = 0 but Bel(U V) 0.

  • 8.30 Show that CM and OR are sound in qual.

  • * 8.31 This exercise gives the proof of Theorem 8.4.11. Fix a simple measure conditional probability structure M = (W, μ, π).

    1. Define a partial preorder ≽′ on subsets of W such that U ≽′ V if μ(U | U V) = 1. Show that ≽′ is reflexive and transitive.

    2. Show by means of a counterexample that ≽′ is not necessarily antisymmetric.

    3. Define a relation ~ on subsets of W by defining U ~ V if U ≽′ V and V U. Show that ~ is reflexive, symmetric, and transitive.

    4. Define [U] ={V : V ~ U}. Since ~ is an equivalence relation, show that for all U, U W, either [U] = [U] or[U] [U] = . Let W/~ ={[U]: U W}.

    5. Define a relation on W/~ by defining [U] [V] iff there exist some U [U] and V [V] such that U V. Show that is a partial order (i.e., reflexive, antisymmetric, and transitive).

    6. Show that [] = {} and that [] is the element in W/~.

    7. Define a plausibility measure Pl on W by taking Pl(U) = [U] for U W. Show that Pl satisfies Pl1–5.

    8. Let Mμ = (W, Pl, π). By part (g), Mμ qual. Show that M φ ψ iff Mμ φ ψ.

  • * 8.32 This exercise fills in the details of the proof of Theorem 8.4.12. The general lines are similar to those of Exercise 8.31. Fix a PS structure M = (W, (μ1, μ2, ), π).

    1. Define a partial preorder ≽′ on subsets of W such that U ≽′ V if limi→∞ μi(U | U V) = 1. Show that ≽′ is reflexive and transitive.

    2. Show by example that ≽′ is not necessarily antisymmetric. This problem can be dealt with just as in Exercise 8.32. Define ~ on subsets of W so that U ~ V if U ≽′ V and V ≽′ U, let [U] ={V : V ~ U}, and define a relation on W/~ by defining [U] [V ] iff there exist some U [U] and V [V ] such that U V. Show that is a partial order (i.e., reflexive, antisymmetric, and transitive).

    3. Show that [] consists of all sets U such that there exists some N such that μn(U) = 0 for all n > N and that [] is the element in the partially ordered domain W/~.

    4. Define a plausibility measure Pl on W by taking Pl(U) = [U], for U W. Show that Pl satisfies Pl1–5.

    5. Let MPS = (W, Pl, π). By part (d), MPS qual. Show that M φ ψ iff MPS φ ψ.

  • 8.33 Show that Pl4 and Pl5 completely characterize the plausibility structures that satisfy P in the following sense. Let be a collection of simple plausibility structures such that for each structure M = (W, Pl, π) , if w w W, then π(w) π(w). Show that if there is a structure in that does not satisfy Pl4 or Pl5, then P is not sound in (Note that the argument in the case of Pl4 is just part (b) of Exercise 8.27; a similar argument works for Pl5. In fact, variants of this results corresponding to parts (a) and (c) of Exercise 8.27 can also be proved.)

  • 8.34 Prove Theorem 8.4.14.

  • * 8.35 This exercise provides a proof of the first half of Theorem 8.4.15, namely, that richness is necessary for completeness.

    1. Let φ1, , φn be a collection of mutually exclusive and satisfiable propositional formulas. Let Σ consist of the default φn false and the defaults φi φj φi for all 1 i < j n. Show that (W, Pl, π) Σ if and only if there is some j with 1 j n such that

    2. Suppose is not rich. Let φ1, , φn be the formulas that provide a counterexample to richness and let Σ be the set of defaults defined in part (a). Show that if (W, Pl, π) satisfies the defaults in Σ, then Pl(φn1M) = .

    3. Using part (b), show that Σ φn1 false.

    4. Show that Σ φn1 false. (Hint: Show that there exists a qualitative plausibility structure satisfying all the defaults in Σ but not φn1 false, and then use the fact that P is sound with respect to qual)

    This shows that if is not rich, then P is not complete with respect to . Although Σ φn1 false, the default φn1 false is not provable from Σ in P.

  • ** 8.36 This exercise provides a proof of the second half of Theorem 8.4.15, namely, that richness is sufficient for completeness. Suppose that there is some Σ and φ ψ such that Σ φ ψ but Σ φ ψ. Show that is not rich as follows.

    1. Let Φ consist of all the primitive propositions that appear in Σ, φ, or ψ. Show that there is a preferential structure structure M = (W, , π) such that

      1. if w w, then either w w or w w (so that is a total order);

      2. if w w, then (π(w))(p) (π(wj))(p) for some p Φ if i j (so that the truth assignments in all worlds are different);

      3. M Σ;

      (Note that this result essentially proves the completeness of P for tot).

    2. Suppose that Φ ={p1, , pm}. Define an atom over Φ to be a conjunction of the form q1 qm, where qi is either pi or pi. Thus, an atom over Φ can be identified with a truth assignment to the primitive propositions in Φ . Let φi be the atom over Φ that characterizes the truth assignment to wi, i = 1, , n, and let φn+1 = (φ1 φn). Show that φ1, , φn+1 are mutually exclusive.

    3. Show that if M = (W, Pl, π′) is a simple plausibility structure such that Pl(φ1M) > > Pl(φn+1M) = , then M satisfies the defaults in Σ but not φ ψ.

    4. Show that is not rich. (Hint: If were rich, it would contain a structure like that in part (c). But that would contradict the assumption that Σ φ ψ).

  • 8.37 This exercise refers to Example 8.5.1. Show that

    1. (penguin red) fly;

    2. penguin winged and (penguin bird) winged;

    3. (penguin yellow) easy-to-see;

    4. robin winged and (robin bird) winged.

    (Hint: For part (a), by Theorem 8.4.5, it suffices to find a preferential structure—or a possibility structure or a ranking structure—satisfying all the formulas in Σ1, but not penguin red fly. A similar approach works for parts (b), (c), and (d).)

  • * 8.38 Show that if rankΣ , then there is a unique structure MΣ rankΣ that is most preferred, in that MΣ M for all M rankΣ.

  • 8.39 Complete the proof of Lemma 8.5.2, by showing that

    1. in MΣa, all worlds satisfying φ1 φ2 φ3 have rank 0 and all worlds satisfying φ1 φ2 or φ2 φ3 have rank 1; and

    2. in MΣb, (i) all worlds satisfying φ1 φ2 φ3 have rank 0, (ii) there are some worlds satisfying φ1 φ2 φ3, (iii) all worlds satisfying φ1 φ2 φ3 φ4 have rank 1, and (iv) all worlds satisfying φ1 φ3 or φ1 φ4 have rank 2.

  • 8.40 Show that (penguin bird) winged and (penguin yellow) easy-to-see.

  • 8.41 Complete the proof of Proposition 8.5.3 by showing that

    1. if k = for some k > 0, then there is no structure M ps such that M Σ,

    2. if k for all k 1, then MmeΣ Σ.

  • * 8.42 The CUT rule is the following:

    CUT. From φ ψ1 and φ ψ1 ψ2 infer φ ψ2.

    The CUT rule is essentially the converse of CM. It says that if ψ2 follows (by default) from φ ψ1 and ψ1 follows by default from φ, then ψ2 follows from φ alone. Show that CUT is provable in P. (Hint: First show that both φ ψ1 ψ1 ψ2 and φ ψ1 ψ1 ψ2 are provable from φ ψ1 ψ2.)

  • 8.43 Prove Proposition 8.6.2.

  • 8.44 Let W ={a, b, c}. Define two plausibility measures, Pl1 and Pl2, on W. Each of these plausibility measures assigns to each subset of W a triple of integers. Define a straightforward ordering on triples: (i, j, k) (i, j, k) if i i, j j, and k k; (i, j, k) < (i, j, k) if (i, j, k) (i, j, k) and (i, j, k) (i, j, k). Pl1 is defined so that Pl1() = (0, 0, 0), Pl1(a) = (1, 0, 0), Pl1(b) = (0, 1, 0), Pl1(c) = (0, 0, 1), Pl1({a, b}) = (1, 1, 1), Pl1({a, c}) = (2, 0, 1), Pl1({b, c}) = (0, 2, 1), and Pl1({a, b, c}) = (2, 2, 2).Pl2 is identical to Pl1 except that Pl2({a, b}) = (2, 2, 1). Let Φ ={pa, pb, pc} and define π so that π(d)(pe) = true iff d = e (so that pa is true only at world a, pb is true only at world b, and pc is true only at world c). Let Mj = (W, j1, π), where j1(w) = (W, Plj), for j = 1, 2.

    1. Show that both M1 and M2 are in qual; that is, show that Pl1 and Pl2 satisfy Pl4 and Pl5.

    2. Show that if U and V are disjoint subsets of W, then Pl1(U) > Pl1(V) iff Pl2(U) > Pl2(V).

    3. Show as a consequence that (M1, w) φ iff (M2, w) φ for all formulas φ 1 and all w W.

    4. Note, however, that (M1, w) (1(pa pb) > 1(pb pc)) while (M2, w) 1(pa pb) > 1(pb pc).

    This exercise shows that 1(pa pb) > 1(pb pc) is not equivalent to any formula in 1. For if it were equivalent to some formula φ, then by part (d), it would follow that (M1, a) φ and (M2, a) φ. However, part (c) shows that this cannot happen.

  • 8.45 Prove that system AXcondn is a sound axiomatization of n with respect to both prefn and qualn.

  • 8.46 Show that C5 does not hold in general in qualn or prefn, by providing a counterexample.

  • 8.47 Show that Pl6 holds if Pl is a total preorder when restricted to disjoint sets. Conversely, show that if Pl satisfies Pl6, then there is a total order on disjoint sets such that U1 U2 iff Pl(U1) < Pl(U2) for disjoint sets U1 and U2.

  • 8.48 Show that the following are equivalent:

    1. Pl(U1) < Pl(U3) and Pl(U2) < Pl(U3) implies that Pl(U1 U2) < Pl(U3). (This is the union property.)

    2. Pl(U1 U2) = max(Pl(U1), Pl(U2)).

    3. If Pl(U1) < Pl(U2 U3), then either Pl(U1) < Pl(U2) or Pl(U1) < Pl(U3). (This is Pl8, without the restriction to disjoint sets.)

    (Hint: It is probably easiest to prove that both (a) and (c) are equivalent to (b).)

  • * 8.49 Prove Proposition 8.6.4.

  • 8.50 Show that C7 is valid in counterfactual preferential structures.

  • 8.51 Show that counterfactual ranking structures (i.e., ranking structures satisfying Cfacκ) and counterfactual plausibility structures (i.e., plausibility structures satisfying CfacPl) satisfy C7.

  • 8.52 Construct conditions analogous to Cfac appropriate for possibility structures and PS structures, and show that the resulting classes of structures satisfy C7.

  • 8.53 In counterfactual preferential structures, there may in general be more than one world closest to w satisfying φ. In this exercise I consider counterfactual preferential structures where, for each formula φ and world w, there is always a unique closest world to w satisfying φ.

    1. M = (W, , π), where (w) = (Ww, w), is a totally ordered (counterfactual) structure if, for all w W, w is a total order—that is, for all w, w W such that w w, either w w w or w w w. Show that in totally ordered structures, there is always a unique closest world to w satisfying φ for each world w and formula φ.

    2. Show that in totally ordered counterfactual structures, the following axiom is valid:

      • C8. (φ ψ) (φ ψ).

        In fact, it can be shown that C8 characterizes totally ordered counterfactual structures (although doing so is beyond the scope of this book).

    3. Show that C5 follows from C8 and all the other axioms and inference rules in AXcond.




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