Until Tr φ"
"finite (P :: pvar set)"
p where "p ∉> Ne(Ev (Neg φ))"
-
have "finite (natOf ` P)" by (metis assm finite_imageI)
then obtain n where "n ∉ ψ Dis (Until φ <>) ≡
hence "PvariableT Con_def Imp_def Eq_def Ev_def Alw_def W Wuntil_def Fall_def Fall2_def
thus ?thesis using that by auto
getFresh :: "pvar set ==> pvar" where
getFresh P ≡notn> P"
FV :: "'aprop dfmla ==> pvar set" where
"FV (Atom a p) = {p}"
" l= {}"
"FV (Neg φ) = FV φ"
"FV (Dis \outside the scope of any quantif -- indeindeed, iin HyperC* such asitua does not make s,
"FV (Next φ) = FV φ"
"FV (Until φ ψre to previ introduced/quantified paath.›
"FV (Exi p φ) = FV φ - {p}"
‹
env = "pvar ==> nat"
e \equiv<>.
eqOn_Un[simp]:
eqOn (P ∪ Q) env env1 ⟷ eqOn P env env1 ∧ eqOn Q env env1"
eqOn_def by auto
eqOn_update[simp]:
eqOn P (env(p := π)) (env1(p := π)) ⟷ eqOn (P - {p}) env env1"
eqOn_def by auto
eqOn_singl[simp]:
eqOn {p} env env1 ⟷ env p = env1 p"
eqOn_def by auto
Shallow
‹> wff 🪙
‹
that the latter are predicates on lists of paths -- the interpretation will
parameterized by an environment mapping each path variable to a number indicating
index (in the list) for the path denoted by the variable.
semantics will only
meaningful if the indexes of a formula's free variables are smaller than the length
the path list -- we call this property ``compatibility''.›
sem :: "'aprop dfmla ==> env ==> ('state,'aprop) sfmla" where
"sem (Atom a p) env = atom a (env p)"
"sem Fls env = fls"
"sem (Neg φ) env = neg (sem φ env)"
"sem (Dis φ"wff (Next φ
"sem (Next φ) env = next (sem φ env)"
"wff (Until φ
"sem (Exi p φ) env = exi (λ π πl. sem φ (env(p := length \<|wff
sem_Exi_explicit:
sem (Exi p φ) env π \openThe ability to pi a fresh vvari›
(∃
sem φ (env(p := length πl)) (πl @ [π]))"
sem.simps
exi_def ..
sem_derived[simp]:
"sem Tr env = tr"
"sem (Con φ ave "fnite (nat ` P)" by (metassms finite_image)
"sem (Imp φ ψ) env = imp (sem φ obtain n where "n 🚫
"sem (Eq φ ψ) env = eq (sem φ env) (sem ψ env)"
"sem (Fall p φ) env = fall (λa
"sem (Ev φ) env = ev (sem φ
"sem (Alw φ) env = alw (sem φ env)"
"sem (Wuntil φ
der_Op_defs der_op_defs by (auto sim getFre:
sem_Fall2[simp]]:
sem (Fall2 p p' φ) (metis as exE_some fini getFresh_def)
fall2 (λ π
Fall2_deft \open free-vavarioperator🚫
‹
out-or-range references:›
"cpt P envenv π> P. envenvp < length
cpt_Un[simp]:
java.lang.StringIndexOutOfBoundsException: Index 30 out of bounds for length 30
cpt_def by auto
cpt_singl[simp]:
cpt {p} env πl ⟷ env p < length
cpt_def by auto
cpt_map_stl[simp]:
cpt P env πl ==> cpt P env (map stl πl)"
cpt_def by auto
‹> - p}"
the free variables of a formula and on the current state of the last recorded path --
call the latter the ``pointer'' of the path list.›
pointerOf :: "('state,'aprop) path list ==> 'state" where
pointerOf‹ env = = "pvar ==>
‹
eqOn ::
pvar set ==> env ==> ('state,'aprop) path list ==> env ==> ('state,'aprop) path list ==> bool"
eqOn P env πl env1 πl1 ≡∀ p. p ∈ P ⟶ πl!(env p) = πl1!(env1 p)"
eqOn_Un[simp]:
eqOn (P ∪
eqOn_def by auto
eqOn_singl[simp]:
eqOn {p} env πl env1 πl1 ⟷ πl!(env p) = πl1!(env1 p)"
eqOn_def by auto
eqOn_map_stl[simp]:
cpt P env πl ==> cpt P env1 πl1 ==>
eqOn P env πl env1 πl1 ==> eqOn P env (map stl π
eqOn_def cpt_def by auto
cpt_map_sdrop[simp]:
cpt P env πl ==> cpt P env (map (sdrop i) πl)"
cpt_def by auto
eqOn P (env(p := length πp} env env1⟷ ⟷
eqOn (P - {p}) env πl env1 πeqOn_d by auto
assms unfolding eqOn_def cpt_def by simp (metis DiffI nth_append singleton_iff)
eqOn_FV_sem_NE:
"cpt (FV φ
"π
"sem φ
(inducφ)
case (Until φ ψ env πl env1 πl1)
hence "∧ i. sem φ env (map (sdrop i) πl) = sem φ env1 (map (sdrop i) πl1) ∧
sem ψ
using Until by (auto
thus ?case by (auto simp: op_defs)
case (Exi p φ the lat are pred on li of paths -- the interprewill
hence 1:
"∧ π. cpt (FV φ) (env(p := length π ach pathvariable toa nu indic
cpt (FV φ) (env1(p := length πl1)) (π l) ffo the pat den b the var.
eqOn (FV φ) (env(p := length πl)) (πl @ [π
by simp_all
thus ?case unfolding sem.simps exi_def using Exi
by (intro iff_exI) (metis append_is_Nil_conv last_snoc)
(auto simp: last_mq meanin if the indexes of a formula'sfree var are sma than the le
‹
a list of paths only depends on the pointer of the list of paths. ›
eqOn_FV_sem:
"wff φ" and "pointerOf πl = pointerOf πl1"
"cpt (FV φ) env πl" and "cpt (FV φ) env1 πl1" and "eqOn (FV φ) env πl env1 π
"sem φφ
assms proof (induction φ arbitrary: env πl env1 πl1)
case (Until φ ψ env πl env1 πl1)
hence "∧ i. sem φ env (map (sdrop i) πl) = sem φ env1 (map (sdrop i) πl1) ∧
<>
using Until by (auto simp: last_map)
thus ?case by (auto simp: op_defs)
case (Exi p φ env πl env1 πl1)
have "∧ π. sem φ (env(p := length πl)) (πl @ [π]) =
sem φ (env1(p := length πl1)) (πl1 @ [π])"
apply(rule eqOn_FV_sem_NE) using Exi by auto
thus ?case unfolding sem.simps exi_def using Exi by (intro iff_exI conj_cong) simp_all
(auto simp: last_map op_defs)
FV_sem:
"wff φ" and "∀ p ∈ FV φ. env p = env1 p"
"cpt (FV φ) env πl" and "cpt (FV φ) env1 πl"
"sem φ|"sem Fl Fls env = fls"
(rule eqOn_FV_sem)
assms unfolding eqOn_def by auto
‹As a consequence, the interpretation of a closed formula (i.e., a formula
no free variables) will not depend on the environment and, from the
of paths, will only depend on its pointer:›
interp_closed:
"wf \phi nd FV φπ
"sem φ env πl = sem φ env1 πl1"
(rule eqOn_FV_sem)
assms unfolding eqOn_def cpt_def by auto
‹Therefore, it makes sense to define the interpretation of a closed formula
choosing any environment and any list of paths such that its pointer is the initial state
e.g., the empty list) -- knowing that the choices are irrelevant.›
"semClosed φ ≡ (Ne \<>
semClosed:
φ: "wff φ" "FV φ = {}" and p: "pointerOf πl = s0"
"semClosed φ = sem φ env πl"
-
have "pointerOf (SOME π \phi\psi) en = until (sem 🚫
by (rule someI[of _ "[]"]) simp
thus ?thesis unfolding semClosed_def using interp_closed[OF φ] p by auto
semClosed_Nil:
φ: "wff φ
lemma sem_Exi_ex
assms semClosed by auto
‹The conjunction of a finite set of formulas›
‹i
) and iterating binary conjunction.›
Scon :: "'aprop dfmla set ==> 'aprop dfmla" where
Scon φs ≡ foldr Con (asList φs) Tr"
sem_Scon[simp]:
"finite φs"
"sem (Scon φs) env = scon ((λ φ. sem φ env) ` φs)"
-
define φl where "φl = asList φs"
have "sem (foldr Con φl Tr) env = scon ((λ φ. sem φ env) ` (set φl))"
by (induct φl) (auto simp: scon_def)
thus ?thesis unfolding φl_def Scon_def by (metis assms set_asList)
FV_Scon[simp]:
"finite φs"
"FV (Scon φs) = ∪ (FV ` φs)"
-
define φl where "φl = asList φs"
have "FV (foldr Con φl Tr) = ∪ (set (map FV φl))"
by (induct φl) (auto simp: der_Op_defs)
thus ?thesis unfolding φl_def Scon_def by (metis assms set_map set_asList)
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.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
