Exercises


  • 7.1 Prove the remaining parts of Lemma 7.1.1.

  • 7.2 Prove that a formula φ is valid iff φ is not satisfiable.

  • 7.3 Show that {p (r q), p r} entails q.

  • 7.4 Show that M p q iff [[p]]M [[q]]M.

  • 7.5 Prove Proposition 7.2.3.

  • 7.6 Prove Proposition 7.2.4.

  • 7.7 Show that Ki(Φ ψ) (Kiφ Kiψ) is valid in all epistemic structures.

    7.8 Show that AXprobn is sound with respect to measn for the language QUn

  • 7.9 Show that AXbeln is sound with respect to both beln and probn for the language QUn.

  • 7.10 Given a (not necessarily measurable) probability structure M = (W, 1, , n, π), define a belief structure M = (W, (BEL1, , BELn, π) by taking Belw, i(U) = (μw, i)*(U). (Since every inner measure is a belief function, Belw, i is indeed a belief function.) Show that (M, w) φ iff (M, w) φ, for every formula φ QUn and w W. (In M, is interpreted as inner measure, as in Section 7.4.)

    This shows that every formula satisfiable in a probability structure is satisfiable in a belief structure. The next exercise shows that the converse also holds. This explains why belief structures and probability structures are characterized by exactly the same axiom system.

  • 7.11 Given a belief structure M = (W, BE1, , BEn), where W is finite and BEw,i = (Ww,i, Belw,i), this exercise shows how to construct a probability structure M = (W, 1, , n, π′) that satisfies the same formulas as M.

    Let w ={(U, u) : U W, u U}.For U W, define U* = {(U, u) : u U}. Clearly U* w.

    1. Show that if U V, then U* and V* are disjoint.

    2. Show that W =UW U*.

      Define i (U, u) = (W(U,u),i, (U,u),i) as follows:

      • Let w(U, u), i ={(V, v) W : V Wu,i}.

      • Take the sets V* for V Wu, i to be a basis for (U,u),i. (That is, the sets in (U,u),i consist of all possible unions of sets of the form V* for V Wu, i.)

      • Let mw, i be the mass function corresponding to Belw, i. Let μ(U, u), i(V*) = mu, i(V) for V Wu, i, and extend μ(U, u), i to all the sets in (U,u),i by finite additivity.

      Finally, define π′(U, u) (u) for all (U, u) W. This completes the definition of M.

    3. Show that (M, u) φ iff (M, (U, u)) φ for all sets U such that u U.

    Note that this result essentially says that a belief function on W can be viewed as the inner measure corresponding to a probability measure defined on W, at least as far as sets definable by formulas are concerned. That is, Belu, i([[φ]]M) = (μ(U, u), i)*([[φ]]M) for all formulas φ.

  • 7.12 Show that all the axioms in AXbeln other than QU6 are valid in lpn.

  • 7.13 Show that if φ ⇒⊿J{1, , k}, |J m+n j J φ j and J{1, , k}, | J m jJ φj are propositional tautologies, then in any structure M = (W, 1, ), the sets [[φ1]]M, , [[φm]]M must cover W m times and [[φ]]M m + n times. Now, using (2.13), show that QU8 is sound in lpn.

  • 7.14 Prove the soundness of the axioms systems given in Theorem 7.5.1 with respect to the appropriate class of structures.

  • *7.15 This exercise shows that a formula in RLn is satisfiable in possn iff it is satisfiable in totn with respect to the e semantics. A very similar argument can be used to prove the same result for rankn instead of possn. These results prove Theorem 7.5.3.

    1. Show that if a formula is satisfiable in a possibility structure, it is satisfiable in one where the possibility of all worlds is positive. More precisely, given a structure M = (W, POSS1,,POSSn, π), let M = (W, POSS1,,POSSn, π), where POSSw,i = (Ww,i, Possw,i), Ww,i = {w Ww,i: Possw,i(w) > 0}, and POSSw, i (W) = Possw, i(w) for w Ww, i. Show that for all formulas φ and all w W, (M, w) φ iff (M, w) φ.

    2. Given a possibility structure M = (W, POSS1, , POSSn, π) such that Possw, i (w)> 0 for all agents i and worlds w, w with w Ww, i, construct a preferential structure M = (W, O1,, On,π) totn by setting Oi(w,i) = (Ww,i, w,i), where w w, i w iff Possw, i(w) Possw, i(w′′). Show that, for all subsets U, V Ww, i, Possw, i(U) Possw, i(V) iff U ew, i V. (Note that this would not be true without the assumption that Possw, i(w) > 0 for all w Ww, i. For if Possw, i(w) = 0, then Poss({w}) = Poss() although ew, i {w}.) Then show that (M, w) φ iff (M, w) φ for all formulas φ RLn. (Note that this argument works even if ww, i is infinite.)

    3. This part of the exercise shows that if a formula in RLn is satisfied in a preferential structure in tctn, it is also satisfied in some possibility structure. Given φ RLn, let p1, , pn be the primitive propositions that appear in φ. Suppose that (M, w) φ for some preferential structure M = (W, 1, , n, π) totn. For a world w W, define the formula φw to be of the form q1 qn, where qi is pi if (M, w) pi and pi otherwise. Note that (M, w) φw. Show that there exists a possibility measure Possw, i on ww, i such that Possw, i(w)> 0 for all w Ww, i on Possw, i(w) Possw, i(w) iff [[M]]φw Ww, i ew, i [[M]]φw ww, i. (The key point is that since there are only finitely many possible sets of the form [[M]]φw Ww, i, the range of Possw, i is finite, even if Ww, i is infinite; thus it is easy to define Possw, i. Let M = (W, POSS1,,POSSn, π) be the possibility structure such that POSSi(w) = (Ww,i, Possw,i). Show that (M, w) ψ iff (M, w) ψ for all subformulas ψ of φ and worlds w W. In particular, it follows that (M, w) φ, so φ is satisfied in M.

    Since (a) and (b) together show that if a formula is satisfiable in a possibility structure, it is satisfiable in a preferential structure in totn, and (c) shows that if a formula is satisfiable in a preferential structure in totn, then it is satisfiable in a possibility structure. It follows that a formula is valid in possibility structures iff it is valid in totally ordered preferential structures.

  • 7.16 Show that the same formulas in the language RLn are valid in each of rankn, possn, and totn (using the e semantics).

  • 7.17 Show that (i(p)>i( p) i(q)>i( q)) i(p)>i( q) is not provable in AXRLTs. (Hint: If it were provable in AXRLTs, it would be valid in possn and rankn.)

  • *7.18 Show that there are formulas valid in probn, beln, and lpn that are not provable in AXRLTs.

  • 7.19 Suppose that φ is an i-likelihood formula. Show that φ Ki φ is provable from KP2 and S5n.

  • 7.20 Show that KP1 and KP2 (together with Prop and MP) imply KP3.

  • 7.21 Show that KP1, KP2, and KP3 are valid in structures in K,measn that satisfy CONS, SDP, and UNIF, respectively.

  • 7.22 Suppose that X is a random variable that takes on only countably many values. Show that if Alice and Bob have a common prior on a (finite or) countable set of worlds, then it cannot be common knowledge that the expected value of X is 1/2 according to Alice and 2/3 according to Bob.

  • *7.23 This exercise considers the axiom CP2 and a generalization of it for n agents.

    1. Show that CP2 is valid in structures in K,meas2 satisfying CP.

    2. Consider the following axiom:

      • CPn. If φ1, , φm are pairwise mutually exclusive formulas and aij, i = 1, , n, j = 1, , m, are rational numbers such taht Σni=1 aij= 0, for j = 1,, m, then

    1. Show that CP2 is equivalent to the axiom that results from CPn when n = 2. (This justifies using the same name for both.)

    2. Show that CPn is valid in structures in K,measn satisfying CP.

  • 7.24 Construct a concrete example showing that CP2 does not hold without the requirement that C(w) have positive prior probability for each world w W.

  • 7.25 Use (5.12) together with ideas similar to those of Exercise 5.20 to show that a formula f En is equivalent (in structures in beln, probn, and possn to a formula f En such that, e is applied only to propositional formulas in f.

  • 7.26 Construct two structures in lpn that agree on all formulas in QUn but disagree on the formula ei(p + q) > 1/2.

  • 7.27 Given linear propositional gambles γ1 and γ2, this exercise considers how to construct gambles γ1 γ2 and γ1 γ2 such that XMγ1 γ2 = XMγ1 XMγ2, and XMγ1 γ2 = XMγ1 γ2 in all belief structures M.

    Assume without loss of generality that γ1 and γ2 involve the same propositional formulas, say φ1, , φm, so that γ1 = a1φ1 + + amφm and γ2 = b1φ1 + + bmφm. (It is always possible to ensure that γ1 and γ2 involve the same propositional formulas by adding "dummy" terms of the form 0ψ to each sum.) Define a family ρA of propositional formulas indexed by A {1, , m} by taking ρA = i A φi (j A φj). Thus, ρA is true exactly if the φis for i A are true and the other φjs are false. Note that the formulas ρA are pairwise mutually exclusive. Define the real numbers aA, bA for A {1, , n} by taking aA = iA ai and bA = iA bi. Define γ′1 = A{1, , n} aAρA and γ′ A{1, , n} bAρA.

    1. Show that XMγi = XMγ′i for i = 1, 2, for all belief structures M.

    2. Define γ1 γ2 = A{1, , n} max(aA, bA)ρA. Show that XMγ1 γ2 = XMγ1 XMγ2.

    3. Define γ1 γ2 = A{1, , n} min(aA, bA)ρA. Show that XMγ1 γ2 = XMγ1 XMγ2.

    4. Show that if γ1 and γ2 are the propositional formulas φ1 and φ2, respectively, then γ1 γ2 is a gamble equivalent to the propositional formula φ1 φ2, and γ1 γ2 is a gamble equivalent to the propositional formula φ1 φ2. This justifies the use of and for max and min in the context of random variables.

  • 7.28 Show that if φ1, , φm are pairwise mutually exclusive, a1 am, and b1 bm, γ1 = a1φ1 + + amφm, and γ2 = b1φ1 + + bmφm, then in all structures M, the gambles XMγ1 and XMγ2 are comonotonic.




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