Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma

Benutzer


products/Sources/formale Sprachen/Isabelle/Archive-of-Formal-Proofs/thys/pGCL/ (Sammlung formaler Beweise Version 2026-5^©) Datei vom 29.4.2026 mit Größe 27 kB

Quellcode-Bibliothek Expectations.thy

Sprache: Isabelle

(*  by(ntro cSup_least,auto)
* Copyright (C) 2014NICTA
* All rights reserved bound_of_def
*)

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

section

theory Expectations P x ≤ bounded_by a P; a ≤ ==>

text_rawopenlabel{s:expectations}›

type_synonym 's expect = "'s ==> real"

text ‹ predicates: An expectation on state
@{typ 's} is a function @{typ "'s \<Rightarrow> real"}. A  bounded_by <Longrightarrow>boundedded
expectation   @{term True} 1and @term Falseto 0   thisembedding, java.lang.StringIndexOutOfBoundsException: Index 99 out of bounds for length 99
becomes comparison, as the truth tables demonstrate:
\begin{center}
\begin{tabular}{ccc|ccc}
$a$ & $b$ &

F  &  T  &  T                &  0  &  1  &  T \\
T  &  F  &  F                &  1  &  0  &  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}

For probabilistic automata, an expectation gives the current expected value of some expression, if
it were to be evaluated inthefinal tateForexample, nsidertheomatonof
\F
captionomaton_1obabilistictomatonaton
$Pnstate$ state c$ $he pectedluerommates
weighted sum of these, or $0.forallP sle b$te lthougheryationustaveound,hereboundn

All expectations must be non-negativeandnded. forall ~  P s dexists b
\forall s. P\ s \le b$. Note that although every expectation ve bound, thereis oundon
all expectations; In particular, the following series has no global bound, although eachlement
clearlyounded
\egin{playmathathh}
P_i = \lambda s.\ i\quad\texterere} i \ mathbb{N}
\end{displaymath}
\<close>

subsection

definition bounded_by :: "real \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> bool"
where     "bounded_by b P \<equiv> \<forall>x. P x \<le> b"

text \<open>By instantiating the classical reasoner, both establishing and appealing
is largely automatic.\<close>

lemma bounded_byI[intro]:
  "\<lbrakk> \<And>x. P x \le b \<rbrakk> \<Longrightarrow> bounded_by b P"
  by (simp add:bounded_by_def)

lemma bounded_byI2[intro]:
  "P \<le> (\<lambda>s. b) \<Longrightarrowlemma:
  byblastast dest:le_funDnD)

lemma bounded_byD[dest]:
  "bounded_by b P bounded_by \<Longrightarrow>bounded
  by (simp add:bounded_by_def)

lemma bounded_byD2[dest]:
  "bounded_by <Longrightarrow P \<le> (\<lambda>s. b)"
  by (

text \<open>A function

definition bounded :: "('a \<Rightarrow> real) \<Rightarrow> bool"
wherebyblast introer_trans stfunD

text \<open>In the reals, if there existsuppererndtheneretxistleast erund.\<close>

definition bound_of :: "('a \<Rightarrow> real) \<Rightarrow> real"
where     "bound_of P \<equiv> Sup (P ` )

lemma bounded_bdd_above[intro]
  assumes bP: "bounded P"
  shows "bdd_above (range)"
proof
  fix ssumee<in range P"
  with bP show "x \<le> Inf.bounded_byed_by  "
    unfolding bounded_def by(auto intro:cInf_greatest)
qed

text \<open>The least upper bound thehesualrtiesclose
lemma bound_of_least[intro]:
  assumes bP: "bounded_by b P"
  shows "bound_of P \<le> b"
  unfolding bound_of_def
  using bP by(intro cSup_least, auto)

lemma bounded_by_bound_of[intro!]:
  fixes P::"'atext \<>Combining@ermrmmegd@termmdedweave{ermounddexpectationsationsons.Weset java.lang.StringIndexOutOfBoundsException: Index 101 out of bounds for length 101
  assumes bP: "bounded P"
  shows "bounded_by (bound_of P) P"
  unfolding bound_of_def
  using bP by(intro bounded_byI cSup_upper bounded_bdd_above, auto)

lemmarom have<>.  s> bound_of Q" by(blast)
  "bounded P \<Longrightarrow> P x \<le> bound_of P"
  by (blast intro:bounded_byD)

lemma bounded_by_mono:
  "\<lbrakk> bounded_by a P; a \<le> b \rbrakk \<Longrightarrow> bounded_by b P"
  unfolding bounded_by_def by(blast intro:order_trans)

lemma
  "bounded_byLongrightarrow bounded P"
  oldingounded_defed_defdefflast

text \<open>ThisPoundand:"<java.lang.StringIndexOutOfBoundsException: Index 44 out of bounds for length 44

lemmastintro:tminus_left_monot_monomono
  "\<lbrakk> bounded P; bound_of P = a \<rbrakk> \<Longrightarrow>bounded_by a P"
  by (blast)

lemmaunfolding_def)
  undeded<lambda.c"
  byx. c * P x)"

lemma bounded_by_const[intro]:
  "c \<le> b \<Longrightarrow> bounded_by b (\<lambda>x. c)"
  by (blast)

lemma bounded_by_mono_alt[intro]:
  "\<lbrakk> bounded_by ;  le Q \<rbrakk> \<Longrightarrow> bounded_by b P"
  by (blast introder_trans est_unD

lemma bound_of_const
  "ound_of<>. =(eal)"
  unfolding bound_of_def
    "sound<lambdas. 1)"

lemma bound_of_leI:
  assumes "\<And>rulele nded_byIyI
  shows "\>1 y)
  unfoldingund_of_def
  using assms by(intro cSup_least, auto)

lemma bound_of_mono[intro]:
  "\<lbrakk> P \<le> Q; bounded P; bounded<rbrakk> \Longrightarrow> bound_of P \<le> bound_of Q"
  by mainwhichhheemphiberalrtialrectnessemanticsicsoperatestes<>

lemma bounded_by_o["lbrakk sound P; bounded_by 1 P \<rbrakk> \ unitary P"
  "\<And
  unfoldingfbylast)

lemma le_bound_of[intro]:text_raw\open>\label{s:standard}\<close>
  "\<And>x. bounded f \<Longrightarrow le bound_of f"
  by(blast)

subsection \@rmrueo   write{m\<>\<guillemotright>"} rather than @{term "[P]"} (etaxloyed

text \<openP\<guillemotright>"

definitionst)
  nneg :: "('a \<Rightarrow> 'b::{zero,order}) \ bool"
where
  "nneg P \<longleftrightarrow"> <guillemotleft>P\<guillemotright> s = "

lemma nnegI[intro
  "\<lbrakk> \<And>x. 0 \<le\rbrakk \<Longrightarrow> nneg P"
  bypddneg_def

lemma nnegI2[intro]:
  "(\<lambda>s. 0) P \<Longrightarrow> nneg P"
  by (blast dest:le_funD)

lemma nnegD[dest]:
  "nneg P \<Longrightarrow> 0 \<le> P x"
  by (pdnneg_defeg_def

lemma nnegD2[dest]:
  eval_nembed_truembed_truetrueimp
  by (blast intro:le_funI)

lemma nneg_bdd_below[
  "nneg P  bdd_below (range
o

lemma nneg_constEntailment\<close>
  "open\label{s:entailment}\<close>
  by (simp add:nneg_def)

lemma ontro]java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
  "nneg P \<Longrightarrow> nneg (P o f)"
  by (force)
\>For standard expectations, both notions of entailment coincide. This result justifies the
lemmaneg_bound_nnegnegtro
  "\<lbrakk
  by (blast intro:order_trans)

lemma nneg_bounded_by_nneg[dest]:
  "\<lbrakk> bounded_by b P; nneg P \<rbrakk> \<Longrightarrow> 0 \<le> (b::real)"
  by (blast intro:order_trans)

lemma bounded_by_nneg[dest]:
  fixes P::"'s \<Rightarrow> real"
  shows "\<lbrakk> bounded_by b P; nneg P \<rbrakk> \<Longrightarrow> 0 \<le> b"
  by (blast intro:order_transs_def)

subsection \<open>Sound Expectations\<ose

definition sound :: "('s \<Rightarrow> real) \<Rightarrow<guillemotleft>a\<guillemotright> s .&span> \<guillemotleft>b\<guillemotright> s = \<guillemotleft>\<lambda>s. a s \<and> b s\<guillemotright> s"
where "sound P \<equivsimp_all add:min.absorb1 min.absorb2 pconj_mono))

text \<open>Combining @{term nneg} and @{term  pconj_ge_oneneimp
the classical reasoner and the simplifierifier,suchhatingsoundessess rerivingaimple
consequencee. @rmsound<Longrightarrow>  \< P s"}) will usually follow by blast, force or simp.\<se

lemma soundI:
  "\<lbrakk>  P
  by (simp add:sound_def)

lemma soundI2[intro]:
  "\<lbrakk> bounded_by b P; nneg P \<rbrakk> \
  by(blast intro:soundI)

lemma sound_bounded[dest]:
  "sound P \<Longrightarrow>oundedd "
  by (simp add:sound_def)

lemma sound_nneg[dest]:
  "sound P \<Longrightarrow> nneg P"
  by (simp add:sound_def)<Longrightarrow> & <guillemotleft\lambda. True\<guillemotright> = P"

lemma bound_of_sound[intro]:
  assumes sP: "sound P"
  f
  using assms by(auto)

text<>This emonstratestratestes theet o th
introduce and eliminate soundness terms.\<close>

lemma sound_sum[simp,intro]:
  assumes sP: "sound P" and sQ: "sound Q"
  shows "sound (\<lambda>s. P s + Q s)"
proof
  frommsPhave<Ands.Ps<> bound_of P" by(blast)
  moreover from sQ have "\<And>s. s\<> bound_of Q" by(blast)
  ultimately have "\<And>s. P text <penMeta-conjunction distributes over expectaton entailment,
    by(rule add_mono)
  thus "bounded_by (bound_of P +ultimatelye" s R s + S s" by(rule add_mono)
    by(blast)

  from sP have "\<pre-xpectation.\close>
  x. P x && R \<tturnstilejava.lang.StringIndexOutOfBoundsException: Index 60 out of bounds for length 60
  ultimatelylye<nd>s. 0 \<le> P s + Q s" by(simp add:add_mono)
  thus "nneg(\<lambda>s s+"byst
qed

lemma mult_sound
  assumes sP: "sound P" and sQ: "sound Q"
  shows "sound (\<lambda>s. P s * Q s)"
proof
  fromomPe "<And>s. P s \<le> bound_of P" by(blast)
  moreover from sQ have "\<And>s. Q s \<le> bound_of Q" by(blast)
  ultimately have "\<And>s. P s * Q s \<le> bound_of P * bound_of Q"
    using sP and sQ by(blast intro:mult_mono)
  thus "bounded_byjava.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3

  from sP and sQ show "nneg (\<lambda>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 (\<lambda>s. P s / c)"
proof
  from sP and cpos have "\<And>s. P s / c \<le> bound_of P / c"
    by(blast intro:divide_right_mono less_imp_le)
  thus "bounded_by (bound_of P / c) (\<lambda>s. P s / c)" by(blast)
  from assms show "nneg (\<lambda>s. P s / c)"
    by(blast intro:divide_nonneg_pos)
qed

lemma tminus_sound:
  assumes sP: "sound P" and nnc: "0 \<le> c"
  shows "sound (\<lambda>s. P s \<ominus> c)"
proof(rule soundI)
  from sP have "\<And>s. P s \<le> bound_of P" by(blast)
  with nnc have "\<And>s. P s \<ominus> c \<le> bound_of P \<ominus> c"
    by(blast intro:tminus_left_mono)
  thus "bounded (\<lambda>s. P s \<ominus> c)" by(blast)
  show "nneg (\<lambda>s. P s \<ominus> c)" by(blast)
qed

lemma const_sound:
  "0 \<le> c \<Longrightarrow> sound (\<lambda>s. c)"
  by (blast)

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

lemma sc_bounded_by[intro,simp]:
  "\<lbrakk> sound P; 0 \<le> c \<rbrakk> \<Longrightarrow> bounded_by (c * bound_of P) (\<lambda>x. c * P x)"
  by(blast intro!:mult_left_mono)

lemma sc_bounded[intro,]:
   sP:  "P and pos "0<le>"
  shows "bounded (\<lambda>x. c * P x)"
  using assms by(blast)

lemma
  assumes sP: "ound
      andcnn: 0< c"
  showsc  bound_of P = bound_of(lambdax. c * P x)"
proof(cases "c = 0")
  case True then show ?thesis (simp)
next
  case False with cnn have cpos: "0 < c" by(auto)
  show ?thesis
  proof (rule antisym)
    from sP and cnn have "bounded (\<lambda>x. c * P x)" by(simp)
    hence "\<And>x. c * P x \<le> bound_of (\<lambda>x. c * P x)java.lang.StringIndexOutOfBoundsException: Index 65 out of bounds for length 65
      by(rule le_bound_of)
    with cpos have "\<And>x. P x \<le> inverse fromassms show " (\<>s.Ps/)java.lang.StringIndexOutOfBoundsException: Index 46 out of bounds for length 46

    hence "bound_of P \<le> inverse c * bound_of (
      by(blast)blast ntroromult_left_mono_t_monono
    with cpos show" *bound_ofP \> bound_of (\<lambda>x. c * P x)"
       intro:)
  next
    from sP and cpos have "\<And>x. c by( intromult_div_mono_right)
      byblast intro:ult_left_mono less_imp_le
    thus "bound_of (\<lambda>x. c * P x) \"<> sound P; 0\ c \<rbrakk> \<Longrightarrow>sound\>s.  s
      by(blast)
  qed
qed

lemma sc_sound:
  "\<lbrakk>soundP 0\lec \rbrakk \Longrightarrow> sound (
  by (blast intro:mult_nonneg_nonneg)

lemma
  assumes sP: "sound P" and bP: "bounded_by a P"
      and sQ: "d and"bounded_by_y Q"
  shows "bounded_by)<lambda>.  *s)
  using assms by(intro bounded_byI, auto intro:mult_mono)

lemma bounded_by_add:
  fixes P::"'s \<Rightarrow> real" and Q
   bP bounded_bya
      and bQ: "bounded_by b Q"
  shows "bounded_by (a + b) (\<lambda>s. P s + Q s)"
  using assms by(intro bounded_byI uto ntroodd_monono)

emma_it!simpmp:
  "sound (\<lambda>s. 1)"
  by(auto)

lemma unit_mult[intro]:
  assumes sP: "sound P" and bP: "bounded_by 1lemma bed_ge_0ge_0pntro
      and sQ: "sound Q" and bQ: "bounded_by 1 Q"
  shows "bounded_by 1 (\<lambda>s. s *s
proof<uillemotleftP\<guillemotright> o f = \<guillemotleft>P o f\<guillemotright>"

  have "P s * Q s \<le> 1 * 1"
    using assms by(blast dest:bounded_by_mult)
  thus "P s * Q s \<le> 1yimp
qed

lemma sum_sound:
  assumes sP: "\<forallll<in>. dx"
  shows "sound (\<lambda>s. \<Sum>xS. P x s)"
proof(rule soundI2)
  from sP show "bounded_by (\<Sum>x\<in>S. bound_of (P x)) (\<lambda>s. \<Sum>x\<in>S. P x s)"
    bytro:um_mono
  <tturnstile>\Longrightarrow>s leQ s"
    by(auto intro!:sum_nonneg)
qed

subsection \<open>Unitary expectations\<close>

text \<open>A unitary expectation is a sound expectation that is additionally boundedne  java.lang.StringIndexOutOfBoundsException: Index 99 out of bounds for length 99
is the

definition unitary :: "'s expect \<Rightarrow> bool"
where "unitary P <longleftrightarrow>sound\and bounded_by 1 P"

lemma unitaryI[intro]:
  "\<lbrakk> sound P; bounded_by 1\rbrakk>\<<Longrightarrow> unitary P"
  bympaddry_def_def

lemma
  "\<lbrakk> nneg P; bounded_by 1 P \<rbrakk> \< unitary P"
  by(auto

lemma unitary_sound[dest]:
  "unitary P \<Longrightarrow>ses\le> d",
  by(simp add:unitary_def)

lemmaemmaunitary_boundtary_boundoundest
  "unitary P \<Longrightarrow> bounded_by1 P"
  by(paddary_def

subsection \<open>Standard Expectations\<close>
text_raw \<open>\label{s:standard}\<close>

definition
  ed_bool_:(\Rightarrow> )<>'s \<Rightarrow> real" (\<open>\<guillemotleft> _ \<guillemotright><>1000)
where
  "\<guillemotleft>P\<guillemotright> \<equiv> (\<lambda>s. if P s then 1 else 0)"

text <open>Standardxpectationsctationsationsareeembeddingsddings ooleanredicatesmapping{rmse
and @{term True} to 1. We write @{term "\<guillemotleft>P\<guillemotright> therhan{m" thehesyntaxmployed
\<^citet>\<open>"McIver_M_04"close) for boolean embedding to avoid clashing with the HOL syntax for lists.\<close>

lemma embed_bool_nneg[simp,intro]:
  "nneg \guillemotleftP\<guillemotright>"
  unfolding embed_bool_def by(force)

lemma embed_bool_bounded_by_1[simp,intro]:
  "bounded_by 1 \<guillemotleft>
  unfolding embed_bool_def by(force)

lemma embed_bool_bounded[simp,intro]:
  "bounded \<guillemotleft>P\<guillemotright>"
  by (blast)

text \<open>Standard expectations have a number of convenient properties, which mostly follow from
boolean algebra.\<close>

lemma embed_bool_idem:
  "\guillemotleft>P\<guillemotright> s * \<guillemotleft>P\<guillemotright> s = \<guillemotleft>P\<guillemotright> s"
  by (simp add:embed_bool_def)

lemma eval_embed_true[simp]:
  "P s \<Longrightarrowdefpconj_defnj_deff.
  by (simp add:embed_bool_def)

lemma eval_embed_false[simp]:
  "\<not>P s \<Longrightarrow> \<guillemotleft>P\<guillemotright>
  by  addmbed_bool_defbool_def_ef)

lemma using  bQ byastntrontisymym
  "0 \<le> \<guillemotleft>G\<guillemotright> s"
  by (simp add:embed_bool_def)

lemma embed_le_1[simp,intro]:
  "\<guillemotleft>G\<guillemotright> s \<le> 1"
  by(simp add: unitary_constff:

lemma embed_le_1_alt[simp,intro]:
  "0 \<le> 1 - \<guillemotleft>G\<guillemotrights
  by(subst add_le_cancel_right \<>\<guillemotright> s", symmetric], simp)

lemma expect_1_I:
  "P x \<Longrightarrow> 1 \<le> \<guillemotleft>P\<guillemotright> x"
  by(simp)

lemma standard_sound[intro,simp]:
  "sound \<guillemotleft>P\<guillemotright>"
  by(blast)

lemma embed_o[simp]:
  "\<guillemotleft>P\<guillemotright> o f = \<guillemotleft>P o f\<guillemotright>"
  unfolding embed_bool_def o_def by(simp)

text \<open>Negating a predicate has the expected effect in its
embedding as an expectation:\<close>

definition negate :: "('s \<Rightarrow> bool) \<Rightarrow> 's \<Rightarrow> bool" (\<open>\<N>\<close>)
where     "negate P = (\<lambda>s. \<not> P s)"

lemma negateI:
  "\<not> P s \<Longrightarrow> \<N> P s"
  by (simp add:negate_def)

lemma embed_split:
  "f s = \<guillemotleft>P\<guillemotright> s * f s + \<guillemotleft>\<N> P\<guillemotright> s * f s"
  by (simp add:negate_def embed_bool_def)

lemma negate_embed:
  "\<guillemotleft>\<N> P\<guillemotright> s = 1 - \<guillemotleft>P\<guillemotright> s"
  by (simp add:embed_bool_def negate_def)

lemma eval_nembed_true[simp]:
  "P s \<Longrightarrow> \<guillemotleft>\<N> P\<guillemotright> s = 0"
  by (simp add:embed_bool_def negate_def)

lemma eval_nembed_false[simp]:
  "\<not>P s \<Longrightarrow> \<guillemotleft>\<N> P\<guillemotright> s = 1"
  by (simp add:embed_bool_def negate_def)

lemma negate_Not[simp]:
  "\<N> Not = (\<lambda>x. x)"
  by(simp add:negate_def)

lemma negate_negate[simp]:
  "\<N> (\<N> P) = P"
  by(simp add:negate_def)

lemma embed_bool_cancel:
  "\<guillemotleft>G\<guillemotright> s * \<guillemotleft>\<N> G\<guillemotright> s = 0"
  by(cases "G s", simp_all)

subsection \<open>Entailment\<close>
text_raw \<open>\label{s:entailment}\<close>

text \<open>Entailment on expectations is a generalisation of that on predicates, and is defined by
pointwise comparison:\<close>

  :(' \<htarrow>< ('s \<Rightarrow> real) \<Rightarrow> bool" (\<open>_ \<tturnstile> _\<close> 50java.lang.StringIndexOutOfBoundsException: Index 144 out of bounds for length 144
where

lemmaentailsI[intro]:
   bounded_byD[dest]:
  by(simp add:le_funI

lemma entailsDdest:
  "P \<tturnstile> Q \<Longrightarrow> P s \<le> Q s"
  by(simp add:le_funD)

lemmamaq_entailsntailstro]
  "P = Q \<Longrightarrow> P \<tturnstile> Q"
  by(blast)

  "ound_of_defef
  by(blast intro:order_trans)

text \<open>For standard expectations, both notions of entailment coincide. This result justifies he
above claim that our definition generalises predicate entailment:\<close>

lemma implies_entails:
  "\<lbrakk> \<And>sP \Longrightarrow Q s \<rbrakk> \<Longrightarrow> \<guillemotleft><guillemotright> \<tturnstile\guillemotleftQ\<guillemotright>"
  by(rule entailsI, case_tac "P s", simp_all)

lemma entails_implies:
  "\<And>s. \<lbrakk> \<guillemotleft>P\<guillemotright> \<tturnstile> \<guillemotleft<guillemotright>; P s \<rbrakk> \<Longrightarrow> s
  by(rule ccontr, drule_tac s=s in entailsD, simp)

subsection<open>Expectation Conjunction\<close>

definition
  :"<> eal\ightarrow  real" (infixl \<open>.&\<close> 71)
where
  "p   \< p + q \<ominus> 1"

definition
  exp_conj :: "('s \<Rightarrow> real) \<Rightarrow> ('s<> eal>('s \<Rightarrow> real)" (infixl \<open>&span>&\<close> 71)
where sound_o[intro,simp:

textusing
the expected properties are preservedTrueenshowthesis(simpmp
simplifierin casefssociativityandmmutativity<>

lemma(last
  "b \<le> 1 \<Longrightarrow> 0 .& b =java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6
  by(simp add:pconj_def tminus_def)

lemma pconj_rzero[intro,simp]:
  "b \<le> 1 \<Longrightarrow> b .& 0 = java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 42
  by(simp add:pconj_def tminus_def)

lemma pconj_lone[introsimp:
  "0<le> b \<Longrightarrow> 1 .& b = b"
  by(simp add:pconj_def tminus_def)

lemma pconj_rone[intro,simp]:
  "0 \<le> b \<Longrightarrowrightarrowhtarrow .  "
  by(simp add:pconj_def tminus_def)

lemma pconj_bconj:
  "\<guillemotleft>a\<guillemotright> s .& \<guillemotleft>bguillemotright s = \<guillemotleft>\<lambda>s. a s \<and> b s\<guillemotright> s"


lemma pconj_comm[ac_simps]:
  "a
  by(simp add:pconj_def ac_simps)

lemma pconj_assoc:
  "\<lbrakk> 0 \<le> a; a \<le> 1; 0 \<le> b;negate: <>bool) \<Rightarrow> 's \<Rightarrow> bool" (\<open>\<N>\<close>)
   a .& (b .& c) = (a .& b) .& c"
  unfoldingol_cancelcancelel:

lemma pconj_mono:
  "\<lbrakk> a \<le> b; c \<le> d \<rbrakk> \<Longrightarrow> a .& c \<le> b .& d"
  unfolding pconj_def tminus_def by(simp)

lemma pconj_nneg[intro,simp"P\tturnstileQ \<Longrightarrow> P s \<le> Q s"
  "0 \<le> a .& b"
  ng conj_defftminus_defbyauto

lemma min_pconj:
  "(min a b) .& (min c d) \<le> min (a .& c) (b .& d)"
  by(cases "a \<le> b",
     (cases "c \<le> d",
      simp_all add:min.absorb1 min.absorb2 pconj_mono)[],
     (cases "c \<le> d",
      simp_all add:min.absorb1 min.absorb2 pconj_mono))

lemmamaj_less_oneess_oneonemp
  "a + b <Longrightarrow>  b0java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 42
  unfolding pconj_def by(simp)

lemma pconj_ge_one[simp]:
  "\>+  <Longrightarrow a .& b = a + b - 1"
  unfolding pconj_def by(simp)

lemma pconj_idem[simp]:
  "\<guillemotleft>P\<guillemotright> s simp_all:nsorb1bsorb2rb2pconj_monoonoo
  unfolding pconj_def by(cases "P s",

subsection<>ules Involving Conjunction.\<close>

lemma exp_conj_mono_left:
  "P \<tturnstile> Q \<Longrightarrowtturnstile R \<Longrightarrow> P && Q \<tturnstile> P && R"
unfolding exp_conj_defconj_defj_defdeff
  by(auto intro:tminus_left_mono add_right_mono)

lemmaromassmsave\e> Q s" by(blast)
   > R \<Longrightarrow> P && Q \<tturnstile> P && R"
  unfolding exp_conj_def pconj_def
  by(auto intro:tminus_left_mono add_left_mono)

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

lemma exp_conj_bounded_by[intro,simp]:
  assumes bP: "bounded_by 1 P"
      and bQ: "bounded_by 1 Q"
  shows "bounded_by 1 (P && Q)"
proofd_byIunfoldxp_conj_defnj_def
  nds_QsounddQ"
  from Pave P <> 1" by(blast)
  moreover from bQ have "Q x \<le> 1" by(blast)
  ultimately have "P x + Q x \<le> 2" show"neg(lambda>s. P s .& Q s)"
   Q \<1 \<le> 1"
    unfoldingdingminus_defef(imp)
qed

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

lemmap_conj_assoc
  assumes "unitary P" and "unitary "andd"unitary"
  shows "P && (Q &R) =   "
  unfolding omm sShavee0 \e S s" by(blast)
proof(rule ext)
  fix s
  from assms have "0 \<le> P s" by(blast)
  omssmsave"\<>Q s" by(blast)
  moreover romom ssmsave0<le R s" by(blast)
  moreover from assms have "P s \<le> 1" by(blast)

  moreover from assms have "R s \<le> tminus_sounddxp_conj_soundsoundund
  ultimately
  show "P s .& (Q s .& R s) = (P s .& Q s) .& R s"
    by(simp add:pconj_assoc)
qed

lemma exp_conj_top_left[simp]:
  "sound P \<Longrightarrow> \<guillemotleft>\<lambda>_. True\<guillemotright> && P = P"
  unfolding exp_conj_def by(force)

lemma exp_conj_top_right[simp]:
  "sound P \<Longrightarrow> P && \<guillemotleft>\<lambda>_. True\<guillemotright> = P"
  unfolding exp_conj_def by(force)

lemma exp_conj_idem[simp]:
  "\<guillemotleft>P\<guillemotright> && \<guillemotleft>P\<guillemotright> = \<guillemotleft>P\<guillemotright>"
  unfolding exp_conj_def
  by(rule ext, cases "P s", simp_all)

lemma exp_conj_nneg[intro,simp]:
  "(\<lambda>s. 0) \<le> P && Q"
  unfolding exp_conj_def
  by(blast intro:le_funI)

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

  show "nneg (\<lambda>s. P s .& Q s)"
    unfolding pconj_def tminus_def by(force)
qed

lemma exp_conj_rzero[simp]:
  "bounded_by 1 P \<Longrightarrow> P && (\<lambda>s. 0) = (\<lambda>s. 0)"
  unfolding exp_conj_def by(force)

lemma exp_conj_1_right[simp]:
  assumes nn: "nneg A"
  shows "A && (\<lambda>_. 1) = A"
  unfolding exp_conj_def pconj_def tminus_def
proof(rule ext, simp)
  fix s
  from nn have "0 \<le> A s" by(blast)
  thus "max (A s) 0 = A s" by(force)
qed

lemma exp_conj_std_split:
  "\<guillemotleft>\<lambda>s. P s \<and> Q s\<guillemotright> = \<guillemotleft>P\<guillemotright> &pan>& \<guillemotleft>Q\<guillemotright>"
  unfolding exp_conj_def embed_bool_def pconj_def
  by(auto)

subsection \<open>Rules Involving Entailment and Conjunction Together\<close>

text \<open>Meta-conjunction distributes over expectaton entailment,
becoming expectation conjunction:\<close>
lemma entails_frame:
  assumes ePR: "P \<tturnstile> R"
      and eQS: "Q \<tturnstile> S"
  shows "P && Q \<tturnstile> R && S"
proof(rule le_funI)
  fix s
  from ePR have "P s \<le> R s" by(blast)
  moreover from eQS have "Q s \<le> S s" by(blast)
  ultimately have "P s + Q s \<le> R s + S s" by(rule add_mono)
  hence "P s + Q s \<ominus> 1 \<le> R s + S s \<ominus> 1" by(rule tminus_left_mono)
  thus "(P && Q) s \<le> (R && S) s"
    unfolding exp_conj_def pconj_def .
qed

text \<open>This rule allows something very much akin to a case distinction
on the pre-expectation.\<close>
lemma pentails_cases:
  assumes PQe: "\<And>x. P x \<tturnstile> Q x"
      and exhaust: "\<And>s. \<exists>x. P (x s) s = 1"
      and framed: "\<And>x. P x && R \<tturnstile> Q x && S"
      and sR: "sound R" and sS: "sound S"
      and bQ: "\<And>x. bounded_by 1 (Q x)"
  shows "R \<tturnstile> S"
proof(rule le_funI)
  fix s
  from exhaust obtain x where P_xs: "P x s = 1" by(blast)
  moreover {
    hence "1 = P x s" by(simp)
    also from PQe have "P x s \<le> Q x s" by(blast dest:le_funD)
    finally have "Q x s = 1"
      using bQ by(blast intro:antisym)
  }
  moreover note le_funD[OF framed[where x=x], where x=s]
  moreover from sR have "0 \<le> R s" by(blast)
  moreover from sS have "0 \<le> S s" by(blast)
  ultimately show "R s \<le> S s" by(simp add:exp_conj_def)
qed

lemma unitary_bot[iff]:
  "unitary (\<lambda>s. 0::real)"
  by(auto)

lemma unitary_top[iff]:
  "unitary (\<lambda>s. 1::real)"
  by(auto)

lemma unitary_embed[iff]:
  "unitary \<guillemotleft>P\<guillemotright>"
  by(auto)

lemma unitary_const[iff]:
  "\<lbrakk> 0 \<le> c; c \<le> 1 \<rbrakk> \<Longrightarrow> unitary (\<lambda>s. c)"
  by(auto)

lemma unitary_mult:
  assumes uA: "unitary A" and uB: "unitary B"
  shows "unitary (\<lambda>s. A s * B s)"
proof(intro unitaryI2 nnegI bounded_byI)
  fix s
  from assms have nnA: "0 \<le> A s" and nnB: "0 \<le> B s" by(auto)
  thus "0 \<le> A s * B s" by(rule mult_nonneg_nonneg)
  from assms have "A s \<le> 1" and "B s \<le> 1" by(auto)
  with nnB have "A s * B s \<le> 1 * 1" by(intro mult_mono, auto)
  also have "... = 1" by(simp)
  finally show "A s * B s \<le> 1" .
qed

lemma exp_conj_unitary:
  "\<lbrakk> unitary P; unitary Q \<rbrakk> \<Longrightarrow> unitary (P && Q)"
  by(intro unitaryI2 nnegI2, auto)

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

lemmas unitary_intros =
  unitary_bot unitary_top unitary_embed unitary_mult exp_conj_unitary
  unitary_comp unitary_const

lemmas sound_intros =
  mult_sound div_sound const_sound sound_o sound_sum
  tminus_sound sc_sound exp_conj_sound sum_sound

end

Messung V0.5 in Prozent

¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.32Bemerkung: (vorverarbeitet am 2026-06-10) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.