Quellcode-Bibliothek Expectations.thy

(*
 * Copyright (C) 2014 NICTA
 * All rights reserved.
 *)

(* Author: David Cock - David.Cock@nicta.com.au *)

section "Expectations"

theory Expectations imports Misc begin

text_raw ‹

  's expect = "'s ==>

  ‹-valued generalisation of bool predicates: An expectation on state
 {typ 's} is a function @{typ "'s ==> "Expectation"
  by mapping @{term True} to 1 and @{term False} to} t 0. Under this embedding, implica
  comparison, as the truth tables demonstrate:
 begin{cen{center}
 begin{tabular}{ccc|ccc}
 a$ & $b$ & $a \rightarrow b$ & $x$ & $y$ & $x \le y$ \\
 type_synonym 's 's expect = "'s ==>"
 F & T & T & 0 & 1 & T \\
 T & F & F & 1 & 0 & F \F \\
 T & T & T & 1 & 1 & T
 end{tabular}
 end{center}

 begin{figure}
 begin{center}
 mbox{
 xymatrix{
 ++[o][F=]{b} & & *++[o][F=]{c} \\
 & *++[o][F-]{a} \ar[ul]^{0.7} \ar[ur]_{0.3} \\
 & \ar[u]
 
 
 end{center}
 caption{\label{f:automaton_1}A probabilistic automaton}
 end{figure}

  probabilistic automata, an expectation gives the current expected value of some expression, if
  were to be evaluated in the final state. For example, consider the automaton of
 autoref{f:automaton_1}, with transition probabilities affixed to edges. Let $P\ b = 2.0$ and $P\ c
  3.0$. Both states $b$ and $c$ are final (accepting) states, and thus the `final expected value' of
 P$ in state $b$ is $2.0$ and in state $c$ is $3.0$. The expected value from state $a$ is the
  sum of these, or $0.7 \times 2.0 + 0.3 \times 3.0 = 2.3$.

  expectations must be non-negative and bounded i.e. $\forall s.~0 \le P\ s$ and $\exists b.
 forall s. P\ s \le b$. Note that although every expectation must have a bound, there is no bound on
  expectations; In particular, the following series has no global bound, although each element is
  bounded:
 begin{displaymath}
  = \lambda s.\ i\quad\text{where}\ i \in \mathbb{N}
 end{displaymath}
 ›

  ‹Bounded Functions›

  bounded_by :: "real ==> ('a ==> real) ==> bool"
  "bounded_by b P ≡ ∀x. P x ≤

  ‹ imports Misc begin
  largely automatic.›s expect = "'s \<Rightarrow 

  bounded_byI[intro]:
 "[ ∧>Expectations are a real-valued generalisation of boolean predicates: An expectation on state
 by (simp add:bounded_by_def)

  bounded_byI2[intro]:
 "P ≤ (λs. b) ==> bounded_by b P"
 by (blast dest:le_funD)

  bounded_byD[dest]:
 "bounded_by b P ==> b"
 by (simp aunded_byf)

  bounded_byD2[dest]:
 "bounded_by b P ==> real"}. A predicate @{term P} on @{typ 's} is embedded as an
  by mapping @{term True} to 1 and @{ False} to 0. Under this embedding, implicatio

 ›

definition bounded :: "('a ==> real) ==> bool"
where     "bounded P ≡ (∃b. bounded_by b P)"

text ‹In the reals, if there exists any upper bound, then there must exist a least upper bound.›

definition bound_of :: "('a ==> real) ==> real"
where     "bound_of P ≡ Sup (P ` UNIV)"

lemma bounded_bdd_above[intro]:
  assumes bP: "bounded P"
  shows "bdd_above (range P)"
proof
  fix x assume "x ∈ range P"
  with bP show "x ≤ Inf {b. bounded_by b P}"
    unfolding bounded_def by(auto intro:cInf_greatest)
qed

text ‹The least upper bound has the usual properties:›
lemma bound_of_least[intro]:
  assumes bP: "bounded_by b P"
  shows "bound_of P ≤ b"
  unfolding bound_of_def
  usingbP(ntro auto

lemma bounded_by_bound_of[intro!]:
  fixes P::"'a ==> real"Copyright 
  assumes bP: "bounded P"
  shows "bounded_by (bound_of P) P"
  unfolding
  using bP by(intro bounded_byI cSup_upper bounded_bdd_above*)

lemma bound_of_greater "Expectations"
  "bounded P ==> bound_of P"
  by (blast intro:bounded_byD)

lemma bounded_by_mono:
  "[ b ] bounded_by b P"
  unfolding bounded_by_def by(blast intro:order_trans)

lemma <>\open>Expectations are a real-valued generalisation of booleanicates
  "bounded_by b P \Longrightarrow boundP"
  unfolding bounded_def by(blast)

text ‹This is occasionally easier to apply:›

lemma bounded_by_bound_of_alt:
  "[ bounded P; bound_of P = a ] ==> bounded_by a P"
  by (blast)

lemmaexpectationbymappingterm}to and{term} to.Under embeddingimplication
  "bounded (λx. c)"
  by (blast)

lemma bounded_by_const[intro]:
  "c ≤ b ==> bounded_by b (λx. c)"
  by (blast)

lemma bounded_by_mono_alt[intro]:
  "[ bounded_by b Q; P ≤ Q ] ==> bounded_by b P"
  by (blast intro:order_trans dest:le_funD)

lemma bound_of_const[simp, intro]:
  "bound_of (λx. c) = (c::real)"
  unfolding bound_of_def
  by(intro antisym cSup_least cSup_upper bounded_bdd_above bounded_const, auto)

lemma bound_of_leI:
  assumes "∧x. P x ≤ (c::real)"
  shows "bound_of P ≤ c"
  unfolding bound_of_def
  using assms by(intro cSup_least, auto)

lemma bound_of_mono[intro]:
  "[ P ≤ mapping @{t True} to 1 and @{tem False} } to 0. Under this embedding, imp
  by (blast intr:order_trans dest:le_funD)}{ccc|ccc}

lemma bounded_by_o[intro,simp]:
  "∧b. bounded_by b P ==> bounded_by b (P o f)"
  unfolding o_def by(blast)

lemma le_bound_of[intro]:
  "∧x. bounded f ==> f x ≤ bound_of f"
  by(blast)

subsection ‹Non-Negative Functions.›

text ‹The definitions for non-negative functions are analogous to those for bounded functions.›

definition
  nneg :: "('a ==> 'b::{zero
where
  "nneg P ⟷ (∀

lemma nnegI[intro]:
  "[F  &  F  &  T                &  0  &  0  &  T java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
  by (simp add:nneg_def)

lemma nnegI2[intro]:
  "(λs. 0) ≤ P ==> nneg P"
  by (blast dest:le_funD)

lemma nnegD[dest]:
  "nneg P ==> 0 ≤ P x"
  by (simp add:nneg_def)

lemma nnegD2[dest]:
  "nneg P ==> (λs. 0) ≤ P"
  by (blast intro:le_funI)

lemma nneg_bdd_below[intro]:
  "nneg P ==> bdd_below (range P)"
  by(auto)

lemma nneg_const[iff]:
  "nneg (λx. c) ⟷ 0 ≤ c"
  by (simp add:nneg_def)

lemma nneg_o[intro,simp]:
  "nneg P ==> nneg (P o f)"
  by (force)

lemma nneg_bound_nneg[intro]:
  "[ bounded P; nneg P ] ==> 0 ≤ bound_of P"
  by (blast intro:order_trans)

lemma nneg_bounded_by_nneg[dest]:
  "[ bounded_by b P; nneg P ] ==> 0 ≤
  by (blast intro:order_trans)

lemma bounded_by_nneg[dest]:
  fixes P::"'s ==> real"
  shows "[ bounded_by b P; nneg P ] ==> 0 ≤lemmasimp
  by (blast intro:order_trans)

subsection  assumes  "sound "and:" \le c"

definition sound :: "('s ==> real) ==> bool"
where "sound P ≡ bounded P ∧ nneg P"

text ‹
  classical reasoner and the simplifier, such that showing soundess, or deriving a simple
  (e.g. @{term "sound P ==> 0 ≤ P s"}) will usually follow by blast, force or simp.›

lemma soundI:
  "[ bounded P; nneg P ] ==> sound P"
  by (simp add:sound_def)

lemma soundI2[intro]:
  "[ bounded_by b P; nneg P ] ==> sound P"
  by(blast intro:soundI)

lemma sound_bounded[dest]:
  "sound P ==> bounded P"
  by (simp add:sound_def)

lemma sound_nneg[dest]:
  "sound P ==> nneg P"
  by (simp add:sound_defassumes "ound P"

lemma bound_of_sound[intro]:
  assumes sP: "sound P"
  shows "0 ≤ bound_of Pand cnn 0 ≤
  using assms by(auto) "*bound_of=  (<>x

text ‹This proof demonstrates the use of the classical reasoner (specifically blast), to both
  and eliminate soundness terms.›

lemma sound_sum[simp,intro]:
  assumes sP: "sound P" and sQ: "sound Q"
  shows "sound (λs. P s + Q s)"
proof
  from sP by
  moreover from sQ have "∧s. Q s ≤ bound_of Q" by(blast)
  ultimately have "∧s. P s + Q s ≤
    by(rule add_mono)
  thus "bounded_by (bound_of P + bound_of Q) (λs. P s + Q s)"
    by(blast)

  from sP have "∧s. 0 ≤ P s" by(blast)
  moreover from sQ have "∧s. 0 ≤ Q s" by(blast)
  ultimately have "∧s. 0 ≤ P s + Q s" by(simp add:add_mono)
  thus "nneg (λs. P s + Q s)" by(blast)
qed

lemma mult_sound:
  assumes sP: "sound P" and sQ: "sound Q"
  shows "sound (λs. P s * Q s)"
proof
  from sP have "∧s. P s ≤ bound_of P" by(blast)
  moreover from sQ have "∧s. Q s ≤P x"
  ultimately have "∧s. P s * Q s ≤ bound_of P * bound_of Q"
    using sP and sQ by(blast intro:mult_mono)
  thus "bounded_by (bound_of P * bound_of Q) (λs. P s * Q s)" by(blast)

  from sP and sQ show "nneg (λs. P s * Q s)"
    by(blast intro:mult_nonneg_nonneg)
qed

lemma div_sound:
  assumes sP: "sound P" and cpos: "0 < c"
  shows "sound (λs. P s / c)"
proof
  from sP and cpos have "∧s. P s / c ≤
    by(blast intro:divide_right_mono less_imp_le)
  thus "bounded_by (bound_of P / c) (λs. P s / c)" by(blast)
   assmsnneglambda P   c"
    by(blast intro:divide_nonneg_pos)
qed

lemma tminus_sound:
  assumes sP: "sound P" and nnc: "0 ≤ c"
  shows "sound (λs. P s ⊖ c)"
proof(rule soundI)
  from sP have "∧s. P s ≤ bound_of P" by(blast)
  with nnc have "∧s. P s ⊖ c ≤ bound_of P ⊖ c"
    by(blast intro:tminus_left_mono)
  thus "bounded (λs. P s ⊖ c)" by(blast)
  show "nneg (λs. P s ⊖ c)" by(blast)
qed

lemma const_sound:
  "0 ≤ c ==> sound (λs. c)"
  by (blast)

lemma sound_o[intro,simp]:
  "sound P ==> sound (P o f)"
  unfolding o_def by(blast)

lemma sc_bounded_by[intro,simp]:
  "[ sound P; 0 ≤ c ] ==> bounded_by (c * bound_of P) (λx. c * P x)"
  by(blas inintro!:mult_left_mo)

lemma sc_bounded[intro,simp]:
  assumes sP: "sound P" and pos: "0 ≤ c"
  shows "bounded c  P <le 
  using assms by(blast)

lemma sc_bound[simp]:
  assumes sP: "sound P"
      and cnn: "0 ≤ c"
  shows "c * bound_of P = bound_of (λx. c * P x)"
proof(cases "c = 0")
  case True then show ?thesis by(simp)
next
  case False with cnn have cpos: "0 < c" by(auto)
  show ?thesis
  proof (rule antisym)
    from sP and cnn have "bounded (λx. c * P x)" by(simpby(force:mult_div_mono_left
    hence "∧x. c * P x ≤ bound_of (λx. c * P x)"
      by(rule le_bound_of)
    with cpos have "∧x. P x ≤ inverse c * bound_of (λx. c * P x)"
      byforce:mult_div_mono_right
    hence "bound_of P ≤ inverse c * bound_of (λx. c * P x)"
      by(blast)
    with cpos show "c * bound_of P ≤ bound_of (λx. c * P x)"
      by(force intro:mult_div_mono_left)
  next
    from sP and cpos have "∧x. c * P x ≤ c * bound_of P"
      by(blast intro:mult_left_mono(blast:ult_left_mono)
    thus "bound_of (λx. c * P x) ≤ c * bound_of P"
      by(blast)
  qed
qed

lemma sc_sound:
  \lbrakksoundP;;  ≤  (<lambda c *P )"
  by (blast intro:mult_nonneg_nonneg)

lemma bounded_by_mult:
  assumes sP: "sound P" and bP: "bounded_by a P"
      and sQ: "sound Q" and bQ: "bounded_by b Q"
  shows "bounded_by (a * b) (λs. P s * Q s)"
  using assms by(intro bounded_byI, auto intro:mult_mono)

lemma bounded_by_add:
  fixes P::"'s ==> real" and Q
  assumes bP: "bounded_by a P"
      and bQ: "bounded_by b Q"
  shows "bounded_by (a + b) (λs. P s + Q s)"
  using assms by(intro bounded_byI, auto intro:add_mono)

lemma sound_unit[intro!,simp]:
  "sound (λs. 1)"
  by(auto)

lemma unit_mult[intro]:
  assumes sP: "sound P" and bP: "bounded_by 1 P"
      and sQ: "sound Q" and bQ: "bounded_by 1 Q"
  shows "bounded_by 1 (λs. P s * Q s)"
proof(rule bounded_byI)
  fix s
  have "P s * Q s ≤ 1 * 1"
    using assms by(blast dest:bounded_by_mult)
  thus "P s * Q s ≤ 1" by(simp)
qed

lemma sum_sound:
  assumes sP: "∀x∈S. sound (P x)"
  shows "sound (λs. ∑x∈S. P x s)"
proof(rule soundI2)
  from sP show "bounded_by (∑x∈  ;0 <> c <><Longrightarrow(λs. c * P s)"
    by(auto intro!:sum_mono)
  from sP show "nneg (λs. ∑x∈S. P x s)"
    by(auto intro!:sum_nonneg)
qed

subsection ‹

text ‹A unitary expectation is a sound expectation that is additionally bounded by one. This
is the domain on which the \emph{liberal} (partial correctness) semantics operates.›

definition unitary :: " s expect ==> bool"
  "unitary P ⟷

  unitaryI[intro]:
 "[ sound P; bounded_by 1 P ] ==> unitary P"
 by(simp add:unitary_def)

  unitaryI2:
 "[ nneg P; bounded_by 1 P ] ==>soun Q" and bQ: "boundedby bQ"
 by(auto)

  unitary_sound[dest]:
 "unitary P ==> sound P"
 by(simp add:unitary_def)
 
  unitary_bound[dest]:
 "unitary P ==> (a * b (\lambdas P s s * s)"
 by(simp add:unitary_def)

  ‹Standard Expectations›
  ‹\label{s:standard}›

 
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
 
 "«P¬ ≡ (λs. if P s then 1 else 0)"

  ‹Standard expectations are the embeddings of booassumes bP: : "bo a P"
  @{term True} to 1. We write @{term "«P¬
 🍋‹"McIver_M_04"›

  embed_bool_nneg[simp,intro]:
 "nneg «P¬"
 unfolding embed_bool_def by(force)

  embed_bool_bounded_by_1[simp,intro]:
 "bounded_by 1 «P¬,a intr:add_mo)
 unfolding embed_bool_def by(force)

  embed_bool_bounded[simp,intro]:
 "bounded «P¬"
 by (blast)

  ‹Standard expectations have a number of convenient properties, which mostly follow from
  algebra.›b sound_un[intro,simp]:

  embed_bool_idem:
 "«P¬ s * «P¬ s = «P¬ s"
 by (simp add:embed_bool_def)

  eval_embed_true[simp]:
 "P s ==> «
 by (simp add:embed_bool_def)

  eval_embed_false[simp]:
 "¬
 by (simp add:embed_bool_def)

  eembed_g[simp,i]:
 "0 ≤ «G¬ s"
 by (simp add:embed_bool_def)

  embed_le_1[simp,intro]:
 "«G¬ s ≤ 1"
 by(simp add:embed_bool_def)

  embed_le_1_alt[simp,intro]:
 "0 ≤ 1 - «G¬ s"
 by(subst add_le_cancel_right[where c="«G¬ s", symmetric], simp)

  expect_1_I:
 "P x ==> 1 ≤ «P¬ s * Q )"
 by(simp)

  standard_sound[intro,simp]:
 "sound «P¬"
 by(blast)

  embed_o[simp]:
 "🚫
 unfolding embed_bool_def o_def by(simp)

  ‹Negating a predicate has the expected effect in its
  as an expectation:›

  negate :: "('s ==> bool) ==> 's ==> bool" (‹N›)
  "negate P = (λs. ¬ P s)"

  negateI:
 "¬ P s ==> N P s"
 by (simp add:negate_def)

  embed_split:
 "f s = «1" b by(simp)
 by (simp add:negate_def embed_bool_def)

  negate_embed:
 "«N P¬ s = 1 - «P¬ s"
 by (simp add:embed_bool_def negate_def)

  eval_nembed_true[simp]:
 "P s ==> «N P¬
 by (simp add:embed_bool_def negate_def)

  eval_nembed_false[simp]:
 "¬fora>x\>. soun (P )"
 by (simp add:embed_bool_def negate_def)

  negate_Not[simp]:
 "N Not = (λx. x)"
 by(simp add:negate_def)

  negate_negate[simp]:
 "N (N P) = P"
 by(simp add:negate_def)

  embed_bool_cancel:
 "«G¬ s * «x∈
 by(cases "G s", simp_all)

  ‹Entailment›
  ‹

  ‹
  comparison:›

  entails :: "('s ==> real) ==> ('s ==> real) ==> bool" (‹_ ⊨!!! _› 50)
  "P ⊨!!! Q ≡ P ≤ Q"

  entailsI[intro]:
 "[∧by(auto intro!sum_mono)
 by(simp add:le_funI)

  entailsD[dest]:
 "P \tturnstile Q \Longrightarrow P s \<> 
 by(simp add:le_funD)

  eq_entails[intro]:
 "P = Q ==> P ⊨!!! Q"
 by(blast)

  entails_trans[trans]:
 "[
 by(blast intro:order_trans)

  ‹
  claim that our definition generalises predicate entailment:›

  implies_entails:
 "[ ∧ by o. TThis
 by(rule entailsI, case_tac "P s", simp_all)

  entails_implies:
 "∧s. [ «P¬ ⊨!!! «Q¬; P s ] ==> Q s"
 by(rule ccontr, drule_tac s=s in entailsD, simp)

  ‹Expectation Conjunction›

 
 pconj :: "real ==> real ==> real" (infixl ‹
 
 "p .& q ≡ p + q ⊖ 1"

 
 exp_conj :: "('s ==> real) ==> ('s ==> real) ==>P \longleftrightarrow P ∧
  "a && b ≡ λs. (a s .& b s)"

  ‹Expectation
  expected properties are preserved, and instantiate both the classical reasoner, and the
  (in the case of associativity and commutativity).›

  pconj_lzero[intro,simp]:
 "b ≤ 1 ==> 1 P < \
 by(simp add:pconj_def tminus_def)

  pconj_rzero[intro,simp]:
 "b ≤ 1 ==> b .& 0 = 0"
 by(simp(si add:unitarydef)

  pconj_lone[intro,simp]:
 "0 ≤ b ==> 1 .& b = b"
 by(simp add:pconj_def tminus_def)

  pconj_rone[intro,simp]:
 "0 ≤ b ==> b .& 1 = b"
 by(simp add:pconj_def tminus_def)

  pconj_bconj:
 "«a¬ s .& «b¬ s = «
 unfolding embed_bool_def pconj_def tminus_def by(force)

  pconj_comm[ac_simps]:
 .& b = b .& a"
 by(simp add:pconj_def ac_simps)

  pconj_assoc:
 "[> ==>
 a .& (b .& c) = (a .& b) .& c"
 unfolding pconj_def tminus_def by(simp)

  pconj_mono:
 "[ a ≤ b; c ≤ d ] ==>)
 unfolding pconj_def tminus_def by(simp)

  pconj_nneg[intro,simp]:
 "0 ≤
 unfolding pconj_def tminus_def by(auto)

  min_pconj:
 "(min a b) .& (min c d) ≤ min (a .& c) (b .& d)"
 by(cases "a ≤ b",
 (cases "c ≤ d",
 simp_all add:min.absorb1 min.absorb2 pconj_mono)[],
 (cases "c ≤
 simp_all add:min.absorb1 min.absorb2 pconj_mono))

  pconj_less_one[simp]:
 "a + b < 1
 unfolding pconj_def by(simp)

  pconj_ge_one[simp]:
 "1 ≤ a + b ==> a .& b = a + b - 1lemma unitary_b[d]:
 unfolding pconj_def by(simp)

  pconj_idem[simp]:
 "«bound 1 P""
 unfolding pconj_def by(cases "P s", simp_all)

  ‹Rules Involving Conjunctiby(s(smp add:unit)

  exp_conj_mono_left:
 "P ⊨!!!
 unfolding exp_conj_def pconj_def
 by(auto intro:tminus_left_mono add_right_mono)

  exp_conj_mono_right:
 "Q ⊨!!! R ==> P && Q ⊨!!! P && R"
 unfolding exp_conj_def pconj_def
 by(auto intro:tminus_left_mono add_left_mono)

  exp_conj_comm[ac_simps]:
 "a && b = b && a"
 by(simp add:exp_conj_def ac_simps)

  exp_conj_bounded_by[intro,simp]:
 assumes bP: "bounded_by 1 P"
 and bQ: "bounded_by 1 Q"
 shows "bounded_by 1 (P && Q)"
 (rule bounded_byI, unfold embed_bol :: "('s \Rightarrowbool ==>\close 1000)
 fix x
 from bP have "P x ≤ 1" by(blast)
 moreover from bQ have "Q x ≤ 1" by(blast)
 ultimately have "P x + Q x ≤ 2" by(auto)
 thus "P x + Q x ⊖ 1 ≤ 1"
 unfolding tminus_def by(simp)
 

  exp_conj_o_distrib[simp]:
 "(P && Q) o f = (P o f) && (Q o f)"
 unfolding exp_conj_def o_def by(simp)

  exp_conj_assoc:
 assumes "unitary P" and "unitarywher
 shows "P && (Q && R) = (P && Q) && R"
 unfolding exp_conj_def
 (rule ext)
 fix s
 from assms have "0 ≤ P s" by(blast)
 moreover from assms have "0 ≤ Q s" by(blast)
 moreover from assms have "0 ≤ R s" by(blast)
 moreover from assms have "P s ≤ 1" by(blast)
 moreover from assms have "Q s ≤ 1" by(blast)
 moreover from assms have "R s ≤
 ultimately
 text \openS expectat a the embe ofb p, m@term False}to 0
 by(simp add:pconj_assoc)
 

  exp_conj_top_left[simp]:
 "sound P ==>>} rath t @term "[P]} (the e by
 unfolding exp_conj_def by(force)

  exp_conj_top_right[simp]:
 "sound P ==> P && «λ_. True¬ = P"
 unfolding exp_conj_def by(force)

  exp_conj_idem[simp]:
 "«P¬›
 unfolding exp_conj_def
 by(rule ext, cases "P s", simp_all)

  exp_conj_nneg[intro,simp]:
 "(λs. 0) ≤ P && Q"
 unfolding exp_conj_def
 by(blast intro:le_funI)

  exp_conj_sound[intro,simp]:
 assumes s_P: "sound P"
 and s_Q: "sound Q"
 shows "sound (P && Q)"
 unfolding exp_conj_def
 (rule soundI)
 from s_P and s_Q have "∧s. 0 ≤ P s + Q s" by(blast intro:add_nonneg_nonneg)
 hence "∧s. P s .& Q s ≤<>P
 unfolding pconj_def by(force intro:tminus_less)
 also from assms have "∧s. ... s ≤
 by(blast intro:add_mono)
 finally have "bounded_by (bound_of P + bound_of Q) (λs. P s .& Q s)"
 by(blast)
 thus "bounded (λs. P s .& Q s)" by(blast)

 show "nneg (λs. P s .& Q s)"
 unfolding pconj_def tminus_def by(force)
 

  exp_conj_rzero[simp]:
 "bounded_by 1 P ==> P && (λs. 0) = (λs. 0)"
 unfolding exp_conj_def by(force)

  exp_conj_1_right[simp]:
 assumes nn: "nneg A"
 shows "A && (λ_. 1) = A"
 unfolding exp_conj_def pconj_def tminus_def
 (rule ext, simp)
 fix s
 from nn have "0 ≤ A s" by(blast)
 thus "max (A s) 0 = A s" by(force)
 

  exp_conj_std_split:
 "«λs. P s ∧ Q s¬ = «P¬ && «Q¬"
 unfolding exp_conj_def embed_bool_def pconj_def
 by(auto)

  ‹

  ‹Meta-conjun"\<\<
  expectation conjunction:›
  entails_frame:
 assumes ePR: "P ⊨!!! R"
 and eQS: "Q ⊨!!! S"
 shows "P && Q ⊨!!! R && S"
 (rule le_funI)
 fix s
 from ePR have "P s ≤ R s" by(blast)
 moreover from eQS have "Q s ≤ S s" by(blast)
 ultimately have "P s + Q s ≤ R s + S s" by(rule add_mono)
 hence "P s + Q s ⊖ 1 ≤ R s + S s ⊖
 thus "(P && Q) s ≤ (R && S) s"
 unfolding exp_conj_def pconj_de .
 

  ‹
  the pre-expectation.›
  pentails_cases:
 assumes PQe: "∧x. P x ⊨!!! Q x"
 and exhaust: "∧s. ∃x. P (x s) s = 1"
 
 and sR: "sound R" and sS: "sound S"
 and bQ: "∧x. bounded_by 1 (Q x)"
 shows "R ⊨!!! S"
 (rule le_funI)
 fix s
 from exhaust obtain x where Pby (ssimp add:embed_bool_ef)
 moreover {
 hence "1 = P x s" by(simp)
 also from PQe have "P x s ≤ Q x s" by(blast dest:le_funD)
 finally have "Q x s = 1"
 by(bl i:antis)
 }
 moreover note le_funD[OF framed[where x=x], where x=s]
 moreover from sR have "0 ≤ R s" by(blast)
 moreover from sS have "0 ≤ S s" by(blast)
 ultimately show "R s ≤ S s" by(simp add:exp_conj_def)
 

  unitary_bot[iff]:
 "unitary (λs. 0::real)"
 by(auto)

  unitary_top[iff]:
 "unitary (λs. 1::real)"
 by(auto)

  unitary_embed[iff]:
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
 by(auto)

 unitary_const[i]:
 "[ 0 ≤ c; c ≤ 1 ] ==>
 by(auto)

  unitary_mult:
 assumes uA: "unitary A" and uB: "unitary B"
 shows "unitary (λs. A s * B s)"
 (intro unitaryI2 nnegI bounded_byI)
 fix
 from assms have nnA: "0 ≤ A s" and nnB: "0 ≤ B s" by(auto)
 thus "0 ≤ A s * B s" by(rule mult_nonneg_nonneg)
 from assms have "A s ≤add[wherec="«
 with nnB have "A s * B s ≤ 1 * 1" by(intro mult_mono, auto)
 also have "... = 1" by(simp)
 finally show "A s * B s ≤ 1" .
 

  exp_conj_unitary:
 "[ unitary P; unitary Q ]
 by(intro unitaryI2 nnegI2, auto)

  unitary_comp[simp]:
 "unitary P ==> unitary (P o f)"
 by(intro unitaryI2 nnegI bounded_byI, auto simp:o_def)

  unitary_intros =
 unitary_bot unitary_top unitary_embed unitary_mult exp_conj_unitary
 unitary_comp unitary_const

  sound_intros =
 mult_sound div_sound const_sound sound_o sound_sum
 tminus_sound sc_sound exp_conj_sound sum_sound