lemma alphaFrameRes: and s>': "x ♯ν(FAssert Ψ and F :: "'a::fs_name frame" and y :: name
assumes"y ♯
shows "(x)>\[(x, y)] ∙ proof(cases "x = y") byp thus ?thesis bywith next assume"x ≠ with \<open show ?thesis by(perm_simp add: frame.inject alpha calc_atm fresh_left) qed
lemma frameChainAppend: next fixes from `\not>(x ♯ν(FAssert Ψ: "x ∈⟩ and ec and F :: "'a::fs_name frame"
showslparrν*(xvecyvecF = (*xvec)ν*yvec)" byinduct xvec) au
lemma frameChainEqLength: fixes xec : ame lit and Ψ :: "'a::fs_namesharp yvec'` EQ' have"⟨⟩yvec', ([(x, y)] ∙" and yvec :: "name list" and Ψ' :: "'a::fs_name"
assumes
shows"length xvec = length yvec" proof - obtain n where"n = length xvec" auto
th proof(induct n arbitraryx♯ xvec yvec'` S have"x ♯ p" case(0 xvec yvec Ψ Ψef from‹
moreover with ‹ y` `x 🚫 p` `y ♯ p` S `distinctPerm p`
have "sinPmxy)#) by ip
ultimately show ?case by simp
next
case(Suc n xvec yvec Ψ Ψ
from ‹ Ψ Ψ`
obtain x xvec' where "xvec = x#xvec'" and "length xvec' = n"
by(case_tac xvec) auto
from ‹ = ⟨'⟩‹
obtain y yvec' where "⟨(x#xvec'), Ψ⟩ = ⟨(y#yvec'), Ψ'⟩"
and "yvec = y#yvec'"
by(case_tac yvec) auto
hence EQ: "(νx) > Ψ" by simp
by simp
have IH: "∧xvec yvec Ψ Ψ `ecx#xv' `ye=#yec'
by fact
show ?case
proof(case_tac "x = y")
assume "x = y"
with EQ have "⟨xvec', Ψ⟩ = ⟨yvec', Ψ'⟩"
by(simp add: alpha frame.inject)
with IH ‹
by blast
with ‹
show ?case by simp
ext
assume "x ≠ y"
with EQ have "⟨xvec', Ψ
by(simp add: alpha frame.inject)
hence "⟨xvec', Ψ⟩)
by(simp add: eqvts)
with IH ‹
by blast
hence "length xvec' = length yvec'"
by simp
with ‹
show ?case by simp
qed
qed
frameEqFresh:
fixes F :: "('a::fs_name) frame"
and G :: "'a frame"
and x :: name
and y :: name
shows "Ψ = Ψ'"
-
obtain n where "n = length xvec" by auto
with assms show ?thesis
proof(induct n arbitrary: xvec yvec Ψ Ψ')
case(0 xvec yvec Ψ Ψ')
from ‹0 = length xvec› have "xvec = []" by auto
moreover with ‹⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩› have "yvec = []"
by(case_tac yvec) auto
ultimately show ?case using ‹⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩›
by(simp add: frame.inject)
next
case(Suc n xvec yvec Ψ Ψ')
from ‹Suc n = length xvec›
obtain x xvec' where "xvec = x#xvec'" and "length xvec' = n"
by(case_tac xvec) auto
from ‹⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩›‹xvec = x # xvec'›
obtain y yvec' where "⟨(x#xvec'), Ψ⟩ = ⟨(y#yvec'), Ψ'⟩"
and "yvec = y#yvec'"
by(case_tac yvec) auto
hence EQ: "(νx)(ν*xvec')(FAssert Ψ) = (νy)(ν*yvec')(FAssert Ψ')"
by simp
have IH: "∧xvec yvec Ψ Ψ'. [⟨xvec, (Ψ::'a)⟩ = ⟨yvec, (Ψ'::'a)⟩; supp Ψ = ({}::name set); n = length xvec]==> Ψ = Ψ'"
by fact
show ?case
proof(case_tac "x = y")
assume "x = y"
with EQ have "⟨∠
by(simp add: alpha frame.inject)
with IH ‹length xvec' = n›‹supp Ψ = {}› show ?case
by simp
next
assume "x ≠ y"
with EQ have "⟨xvec', Ψ⟩ = [(x, y)] ∙⟨yvec', Ψ'⟩"
by(simp add: alpha frame.inject)
hence "⟨xvec', Ψ⟩ = ⟨([(x, y) case Nil
by(simp add: eqvts)
with IH ‹
by(simp add: eqvts)
moreover with ‹supp Ψ = {}›
by simp
hence "x ♯ ([(x, y)] ∙ Ψ')" and "y ♯ ([(x, y)] ∙ Ψ')"
with ‹x ≠ y› have "x ♯ Ψ'" and "y ♯ Ψ'"
by(simp add: fresh_left calc_atm)+
ultimately show ?case by simp
qed
qed
frameChainEq:
fixes xvec :: "name list"
and Ψ :: "'a::fs_name"
and yvec :: "name list"
and Ψ' :: "'a::fs_name"
assumes "⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩"
and "xvec ♯* yvec"
obtains p where "(set p) ⊆ (set xvec) × set (yvec)" and "distinctPerm p" and "Ψ' = p ∙ Ψ"
-
assume "∧p. [set p ⊆ set xvec × set yvec; distinctPerm p; Ψ' = p ∙ Ψ]==> thesis"
moreover obtain n where "n = length xvec" by auto
with assms have "∃p. (set p) ⊆ (set xvec) × set (yvec) ∧ distinctPerm p ∧ Ψ' = p∙ Ψ"
proof(induct n arbitrary: xvec yvec Ψ Ψ')
case(0 xvec yvec Ψ Ψ')
have Eq: "⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩" by fact
from ‹0 = length xvec› have "xvec = []" by auto
moreover with Eq have "yvec = []"
by(case_tac yvec) auto
ultimately show ?case using Eq
by(simp add: frame.inject)
next
case(Suc n xvec yvec Ψ Ψ')
from ‹Suc n = length xvec›
obtain x xvec' where "xvec = x#xvec'" and "length xvec' = n"
by(case_tac xvec) auto
from ‹⟨xvec from \< \
obtain y yvec' where "⟨(x#xvec'), Ψ⟩ = ⟨(y#yvec'), Ψ'⟩"
and "yvec = y#yvec'"
by(case_tac yvec) auto
hence EQ: "(νx)(ν*xvec')(FAssert Ψ) = (νy)(ν*yvec')(FAssert Ψ')"
by simp
from ‹xvec = x#xvec'›‹yvec=y#yvec'›‹xvec ♯* yvec›
have "x ≠ y" and "xvec' ♯* yvec'" and "x ♯ yvec'" and "y ♯ xvec'"
by auto
have IH: "∧xvec yvec Ψ Ψ'. [⟨xvec, (Ψ::'a)⟩ = ⟨yvec, (Ψ'::'a)⟩; xvec ♯* yvec; n = length xvec]==> ∃p. (set p) ⊆ (set xvec) × (set yvec) ∧ distinctPerm p ∧ Ψ' = p ∙ Ψ"
by fact
from EQ ‹x ≠ y› have EQ': "⟨xvec', Ψ⟩ = ([(x, y)] ∙⟨yvec', Ψ'⟩)"
and xFreshΨ': "x ♯(ν*yvec')(FAssert Ψ')"
by(simp add: frame.inject alpha)+
show ?case
proof(case_tac "x ♯⟨xvec', Ψ⟩")
assume "x ♯⟨xvec', Ψ⟩"
with EQ have "y ♯⟨yvec', Ψ'⟩"
by(rule frameEqFresh)
with xFreshΨ' EQ' have "⟨xvec', Ψ⟩ = ⟨yvec', Ψ'⟩"
by(simp)
with ‹xvec' ♯
obtain p where S: "(set p) ⊆ (set xvec') × (set yvec')" and "distinctPerm p" and "Ψ' = p ∙ Ψ"
by blast
from S have "(set p) ⊆ set(x#xvec') × set(y#yvec')" by auto
with ‹xvec = x#xvec'›‹yvec=y#yvec'›‹distinctPerm p›‹Ψ' = p ∙ Ψ›
show ?case by blast
next
assume "¬(x ♯(ν*xvec')(FAssert Ψ))"
hence xSuppΨ: "x ∈ supp(⟨xvec', Ψ⟩)"
by(simp add: fresh_def)
with EQ have "y ∈ supp (⟨yvec', Ψ'⟩)"
by(rule frameEqSupp)
hence "y ♯ yvec'"
by(induct yvec') (auto simp add: frame.supp abs_supp)
with ‹x ♯ yvec'› EQ' have "⟨xvec', Ψ⟩ = ⟨yvec', ([(x, y)] ∙ Ψ')⟩"
by(simp add: eqvts)
with ‹
obtain p where S: "(set p) ⊆p where "(set p) ⊆ set (p ∙ xvec)" and "disti"and "yvec = p ∙p \bulletΨ"
by blast
from xSupp\<>
by(induct xvec') (auto simp add: frame.supp abs_supp)
with ‹p. (set p) ⊆ set (yvec) ∧ yvec = p ∙ Ψ' = p ∙
apply(induct p)
by(auto simp add: name_list_supp) (auto simp add: fresh_def)
from S have "(set ((x, y)#p)) ⊆🚫
by force
moreover from ‹')
have "distinctPerm((x,y)#p)" by simp
moreover from ‹‹‹‹
by(simp add: eqvts calc_atm freshChainSimps)
moreover from ‹([(x, y)] ∙ Ψ') = p ∙ Ψ›
have "([(x, y)] ∙ [(x, y)] ∙ Ψ') = [(x, y)] ∙ p ∙ Ψ0 = length xvec› have "xvec = []" by auto
imp dd:pt_bj)
hence "Ψ' = ((x, y)#p) ∙
ultimately show ?case using ‹
ylst
qed
qed
ultimately show ?thesis by blast
frameChainEq'':
fixes xvec :: "name list
and Ψ :: "'a::fs_name"
and "name llis
and Ψ' :: "'a::fs_name"
assumes "⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩"
obtains p where "(set p) ⊆F, \Psi^>F∠" (simp a frameinj)
-
assume "∧p. [set p ⊆ set xvec × set yvec; Ψ' = p ∙ Ψ]==> thesis"
moreover obtain n where "n = length xvec" by auto
with assms have "∃p. (set p) ⊆ (set xvec) × set (yvec) ∧ Ψ' = p ∙ Ψ"
proof(induct n arbitrary: xvec yvec Ψ Ψ')
case(0 xvec yvec Ψ Ψcase_tac y yvec) auto
Eq: "⟨> = ⟨>" by fact
from `0 = length xvec` have "xvec = []" by auto
moreover with Eq have "yvec = []"
by(case_tac yvec) auto
ultimately show ?case using Eq
by(simp add: frame.inject)
next
case(Suc n xvec yvec Ψ Ψ')
from `Suc n = length xvec`
obtain x xvec' where "xvec = x#xvec'" and "length xvec' = n"
by(case_tac xvec) auto
from `⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩` `xvec = x # xvec'`
obtain y yvec' where "⟨(x#xvec'), Ψ⟩ = ⟨(y#yvec'), Ψ'⟩"
and "yvec = y#yvec'"
by(case_tac yvec) auto
hence EQ: "(νx)(ν*xvec')(FAssert Ψ) = (νy)(ν*yvec')(FAssert Ψ')"
by simp
have IH: "∧xvec yvec Ψ Ψ'. [⟨xvec, (Ψ::'a)⟩ = ⟨yvec, (Ψ'::'a)⟩; n = length xvec]==> ∃ (set xvec) \times (set yvec) ∧∙
by fact
show ?case
proof(cases "x=y")
case True
from EQ `x = y` have "⟨xvec', Ψ⟩ = ⟨yvec', Ψ'⟩" by(simp add: alpha frame.inject)
then obtain p where S: "set p ⊆ set xvec' × set yvec'" and "Ψ' = p ∙ Ψ" using `length xvec' = n` IH
by blast
from S have "set((x, y)#p) ⊆ set(x#xvec') × set (y#yvec')" by auto
moreover from `x = y` `Ψ' = p ∙ Ψ` have "Ψ' = ((x, y)#p) ∙ Ψ" by auto
ultimately show ?thesis using `xvec = x#xvec'` `yvec = y#yvec'` by blast
next
case False
from EQ `x ≠ y` have EQ': "⟨xvec', Ψ⟩ = ([(x, y)] ∙⟨yvec', Ψ'⟩)"
and xFreshΨνΨ
by(simp add: frame.inject alpha)+
show ?thesis
proof(cases "x ♯⟨xvec', Ψ⟩")
case True
from EQ `x ♯⟨xvec', Ψ⟩` have "y ♯⟨yvec', Ψ'⟩"
by(rule frameEqFresh)
with xFreshΨ' EQ' have "⟨xvec', Ψ⟩ = ⟨yvec', Ψ'⟩"
by(simp)
with `length xvec' = n` IH
obtain p where S: "(set p) ⊆ (set xvec') × (set yvec')" and "Ψ' = p ∙ Ψ"
by blast
from S have "(set p) ⊆ set(x#xvec') × set(y#yvec')" by auto
with `xvec = x#xvec'` `yvec=y#yvec'` `Ψ' = p ∙ Ψ`
show ?thesis by blast
next
case False
from `¬(x ♯(ν*xvec')(FAssert Ψauto
by(simp add: fresh_def)
with EQ have "y "y \<>
by(rule frameEqSupp)
hence "y ♯ yvec'"
by(induct yvec') (auto simp add: frame.supp abs_supp)
with `x ♯ yvec'` EQ' have "⟨xvec', Ψ⟩ = ⟨yvec', ([(x, y)] ∙ Ψ')⟩"
by(simp add: eqvts)
with by simp+
obtain p where S: "(set p) ⊆yve>. 🚫 p \andyvec = p \<>
by blast
from xSuppΨ have "x ♯ xvec'"
by(induct xvec') (auto simp add: frame.supp abs_supp)
with `x ♯ yvec'` `y ♯ xvec'` `y ♯ yvec'` S have "x ♯ p" and "y ♯ p"
apply(induct p)
by(auto simp add: name_list_supp) (auto simp add: fresh_def)
from S have "(set ((x, y)#p)) ⊆ (set(x#xvec')) × (set(y#yvec'))"
by force
moreover from `x ≠ y` `x ♯ p` `y ♯ p` S `distinctPerm p`
have "distinctPerm((x,y)#p)" by simp
moreover from `x ♯ p` `y ♯ p` `x ♯ xvec'` `y ♯ xvec'` have "y#(p ∙ xvec') = ((x, y)#p) ∙ (x#xvec')"
by(simp add: eqvts calc_atm freshChainSimps)
moreover from `([(x, y)] ∙ Ψ') = p ∙ Ψ`
have "([(x, y)] ∙ [(x, y)] ∙ Ψ') = [(x, y)] ∙ p ∙ Ψ"
by(simp add: pt_bij)
hence "Ψ' = ((x, y)#p) ∙ Ψ" by simp
ultimately show ?case using `xvec=x#xvec'` `yvec=y#yvec'`
by blast
qed
qed
ultimately show ?thesis by blast
*) lemma frameChainEq': fixes xvec :: "name list" and Ψ :: "'a::fs_name" and yvec :: "name list" and Ψ' :: "'a::fs_name"
obtains p where"(set p) ⊆ (set xvec) × set (p ∙ xvec)"and"distinctPerm p"and"yvec = p ∙ xvec"and"Ψ' = p ∙ Ψ" proof - assume java.lang.NullPointerException moreover obtain n where "n = length xvec" by auto with assms have "∃p. (set p) ⊆ (set xvec) × set (yvec) ∧ distinctPerm p ∧ yvec = p ∙ xvec ∧ Ψ' = p ∙ Ψ" proof(induct n arbitrary: xvec yvec Ψ Ψ') case(0 xvec yvec Ψ Ψ') have Eq: "⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩" by fact from ‹0 = length xvec› have "xvec = []" by auto moreover with Eq have "yvec = []" by(case_tac yvec) auto ultimately show ?case using Eq by(simp add: frame.inject) next case(Suc n xvec yvec Ψ Ψ') from ‹Suc n = length xvec› obtain x xvec' where "xvec = x#xvec'" and "length xvec' = n" by(case_tac xvec) auto from ‹⟨xvec, Ψ⟩ = ⟨yvec, Ψ'⟩›‹xvec = x # xvec'› obtain y yvec' where "⟨(x#xvec'), Ψ⟩ = ⟨(y#yvec'), Ψ'⟩" and "yvec = y#yvec'" by(case_tac yvec) auto hence EQ: "\lparr\nux<parrnu)lparr>νy)nuyvec<rparrFAssert<>')" by simp from ‹xvec = x#xvec'›‹yvec=y#yvec'›‹xvec ♯* yvec› have "x ≠ y" and "xvec' ♯* yvec'" and "x ♯ yvec'" and "y ♯ xvec'" by auto from ‹distinct xvec›‹distinct yvec›‹xvec=x#xvec'›‹yvec=y#yvec'› have "x ♯ xvec'" and "y ♯ yvec'" and "distinct xvec'" and "distinct yvec'" by simp+ have IH: "∧xvec yvec Ψ Ψ'. [⟨xvec, (Ψ::'a)⟩ = ⟨yvec, (Ψ'::'a)⟩; xvec ♯* yvec; distinct xvec; distinct yvec; n = length xvec]==>∃p. (set p) ⊆ (set xvec) × (set yvec) ∧ distinctPerm p ∧ yvec = p ∙ xvec ∧ Ψ' = p ∙ Ψ" by fact from EQ ‹x ≠ y›‹x ♯ yvec'›‹y ♯ yvec'› have "⟨xvec', Ψ⟩ = ⟨yvec', ([(x, y)] ∙ Ψ')⟩" by(simp add: frame.inject alpha eqvts) with ‹xvec' ♯* yvec'›‹distinct xvec'›‹distinct yvec'›‹length xvec' = n› IH obtain p where S: "(set p) ⊆ (set xvec') × (set yvec')" and "distinctPerm p" and "yvec' = p ∙ xvec'" and "[(x, y)] ∙ Ψ' = p ∙ Ψ" by metis from S have "set((x, y)#p) ⊆ set(x#xvec') × set(y#yvec')" by auto moreover from ‹x ♯ xvec'›‹x ♯ yvec'›‹y ♯>x \sharp'> <open>x \yvec'🚫 apply(induct p) by(auto simp add: name_list_supp) (auto simp add: fresh_def)
with S ‹distinctPerm p›‹x ≠ y› have "distinctPerm((x, y)#p)" by auto moreover from ‹yvec' = p ∙ xvec'›‹x ♯ p›‹apply(iduct p p by(simp add: freshChainSimps calc_atm) moreover from ‹([(x, y)] ∙ Ψ') = p ∙ Ψ› have " [(x, y)] ∙ [(x, y)] ∙ Ψ') = [(x, y)] ∙ p ∙ Ψ"
by(simp add: pt_bij)
hence "Ψ' = ((x, y)#p) ∙ Ψ"
by simp
ultimately show ?case using ‹xvec=x#xvec'›‹yvec=y#yvec'›
by blast
qed
ultimately show ?thesis by blast
frameEq[simp]:
fixes AF :: "name list"
and Ψ :: "'a::fs_name"
and Ψ' :: 'a
shows "⟨AF, Ψ⟩ = ⟨ε, Ψ'⟩ = (AF = [] ∧> xvec'›> \<>x)#p) \bullet (
and "⟨ε, Ψ'⟩ = ⟨AF, Ψ⟩ = (AF = [] ∧ Ψ = Ψ')"
-
{
assume "⟨AF, Ψ⟩ = ⟨ε, Ψ'⟩"
hence A: "⟨AF, Ψ⟩ = ⟨[], Ψ'⟩" by simp
hence "length AF = length ([]::name list)"
by(rule frameChainEqLength)
with A have "AF = []" and "Ψ = Ψ'" by(auto simp add: frame.inject)
}
thus "⟨AF, Ψ⟩ = ⟨ε, Ψ'⟩ = (AF = [] ∧ Ψ = Ψ')"
and "⟨ε, Ψ'⟩ = ⟨AF, Ψ⟩ = (AF = [] ∧ Ψ = Ψ')"
by auto
distinctFrame:
fixes AF :: "name list"
and ΨF :: "'a::fs_name"
and C :: "'b::fs_name"
assumes "AF♯* C"
obtains AF' where "⟨AF, ΨF⟩ = ⟨AF', ΨF⟩" and "distinct AF'" and "AF' ♯* C"
-
assume "∧AF'. [⟨AF, Ψ)= <>
moreover from assms have "∃AF'. ⟨AF, ΨF⟩ = ⟨AF', ΨF⟩∧ distinct AF' ∧ AbulletΨy)∙
proof(induct AF)
case Nil
thus ?case by simp
next
A^s>F)
then obtain AF' where Eq: "⟨AF, ΨF⟩ = ⟨AF', ΨF⟩" and "distinct AF'" and "AF' ♯* C" by force
from \openaAA\^subF \sharp>* C by si+
show ?case
proof(case_tac "a ♯⟨AF', ΨF⟩")
assume "a ♯⟨AF', ΨF⟩"
obtain b::name where "b ♯ AF'" and "b ♯ ΨF" and "b ♯ C" by(generate_fresh "name", auto)
java.lang.NullPointerException
java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 13 ∠⟨ \<>\
moreover from ‹b ♯ ΨF› have "… = (νb)([(a, b)] ∙(ν*AF')(FAssert ΨF))"
by(force intro: alphaFrameRes simp add: frameResChainFresh)
ultimately show ?thesis using ‹a ♯⟨AF', ΨF⟩›‹b ♯ ΨF›
by(simp add: frameResChainFresh)
qed
moreover from ‹distinct AF'›‹b ♯ AF'› have "distinct(b#AF')" by simp
moreover from ‹AF' ♯* C›‹b ♯ C› have "(b#AF') ♯* C"
ultimately show ?case by blast
next
from Eq have "⟨(a#A: 'a
moreover assume "¬(a ♯⟨
hence "a ♯
by(induct AF') (auto simp add: supp_list_nil supp_list_cons supp_atm frame.supp abs_supp)
with ‹distinct AF'› have "distinct(a#AF')" by simp
moreover from ‹AF' ♯* C›‹a ♯ C› have "(a#AF') ♯* C" by simp+
ultimately show ?case by blast
qed
qed
ultimately show ?thesis using ‹ "\<angle\<>
by blast
freshFrame:
fixes F :: "('a::fs_name) frame"
and C :: "'b ::fs_name"
obtains AF ΨF where "F = ⟨AF, ΨF⟩" and "distinct AF" and "AF♯* C"
-
assume "∧AF ΨF. [F = ⟨AF, ΨF⟩; distinct AF; AF♯* C]==> thesis"
moreover have "∃AF ΨF. F = ⟨AF, ΨF⟩∧ AF♯* C"
proof(nominal_induct F avoiding: C rule: frame.strong_induct)
case(FAssert ΨF)
have "FAssert ΨF = ⟨[], ΨF⟩" by simp
moreover have "([]::name list) ♯* C" by simp
ultimately show ?case by force
next
case(FRes a F) ‹F =⟨F, \<Psi\⟩\close>
obtain AF ΨF where "F = ⟨AF, ΨF⟩" and "AF♯* C"
by blast
with ‹a ♯ C› have "(νa)F = (ν*(a#AF))(FAssert ΨF)" and "(a#AF) ♯* C"
by simp+
thus ?case by blast
qed
ultimately show ?thesis
by(auto, rule_tac distinctFrame) auto
assertionAux =
fixes SCompose :: "'b::fs_name ==> 'b ==> 'b" (infixr ‹⊗› 80)
and SImp <A^
and SBottom :: 'b (‹⊥› 90)
and SChanEq :: "'a::fs_name ==> 'a ==> 'c" (‹_ ↔ _› [80, 80] 80)
assumes statEqvt[eqvt]: "∧p::name prm. p ∙ (Ψ ⊨ Φ) = (p ∙ Ψ) ⊨ (p ∙ Φ)"
and statEqvt'[eqvt]: "∧p::name prm. p ∙ (Ψ ⊗ Ψ') = (p ∙ Ψ) ⊗ (p ∙ Ψ')"
and statEqvt''[eqvt]: "∧p::name prm. p ∙ (M ↔ N) = (p ∙ M) ↔ (p ∙ N)"
and permBottom[eqvt]: "∧p::name prm. (p ∙ SBottom) = SBottom"
statClosed:
fixes Ψ :: 'b
and φ :: 'c
p : "name prm"
frameImpAlphaEnt:
fixes A "F ⟨<>\ \^F:: 'b
and AF' :: "name list"
and ΨF' :: 'b
and φ :: 'c
assumes "⟨AF, ΨF⟩ = ⟨AF', ΨF'⟩"
and "AF♯* φ"
and "AF' ♯* φ"
and "ΨF' ⊨ φ"
shows "ΨF⊨ φ"
-
java.lang.NullPointerException
obtain n where "n = length AF" by blast
java.lang.NullPointerException
have "length AF = length AF'"
by(rule frameChainEqLength)
ultimately show ?thesis using assms
proof(induqed
case(zero AF AF' ΨF')
thus ?case by(auto simp add: frame.inject)
next
case(Suc n AF AF' ΨF')
from ‹
obtain x xs where "AF = x#xs" and "n = length xs"
by(case_tac AF) auto
from ‹⟨AF, ΨF⟩ = ⟨AF', ΨF'⟩›‹AF = x # xs›
obtain y ys where "⟨(x#xs), ΨF⟩ = ⟨(y#ys), ΨF'⟩" and "AF' = y#ys"
by(case_tac AF') auto
hence EQ: "(νx)(F)
by simp
from ‹
have "length xs = length ys" and "xs ♯* φ" and "ys ♯* φ" and "x ♯ φ
by auto
have IH: "∧xs ys ΨF'. [the obtain A<r> = ⟨PsiF'" and "A🚫
by fact
show ?case
proof(case_tac "x = y")
assume "x = y"
h "\<>xs: alpha frame.ininject)
with IH ‹n = length xs›‹length xs = length ys›‹xs ♯* φ›‹ys ♯* φ›‹ΨF' ⊨ φ› o(F) C<have
show ?case by blast
next
assume "x ≠ y"
with EQ have "⟨xs, ΨF⟩ = [(x, y)] ∙⟨ys, ΨF'⟩" by(simp add: alpha frame.inject)
hence "⟨xs, ΨF⟩ = ⟨([(x, y)] ∙
moreover from ‹length xs = length ys› have "length xs = length([(x, y)] ∙ ys)"
by auto
\<openys] ∙) ♯>)"
by(simp add: fresh_star_bij)
with ‹x ♯ φ›‹y ♯ φ› have "([(x, y)] ∙ ys) ♯* φ"
by simp
moreover with ‹ΨF' ⊨ φ› have "([(x, y)] ∙ ΨF') ⊨ ([(x, y)] ∙ φ)"
by(simp add: statClosed)
with ‹x ♯ φ›‹y ♯ φ› have "([(x, y)] ∙ ΨF') ⊨ φ"
by simp
ultimately show ?case using IH ‹n = length xs›‹xs ♯* φ›
by blast
qed
qed
"mergeFrame (FAssert Ψ) G = insertAssertion G Ψ"
"x ♯ G ==> mergeFrame ((νx)F) G = (νmoreov have "∃<langleA^sub>F⟩♯
(finite_guess add: fsCompose)+
(rule TrueI)+
(simp add: abs_fresh)
(simp add: fs_name1)
(rule supports_fresh[of "supp G"])
(force simp add: perm_fun_def eqvts fresh_def[symmetric] supports_def)
(simp add: fs_name1)
(simp add: fresh_def[symmetric])
(fresh_guess)+
mergeFrame (infixr ‹⊗F› 80)
frameBottomJudge (‹⊥F›) where "⊥F≡ (FAssert SBottom)"
mergeFrameEqvt[eqvt]:
fixes p :: "name prm"
and F :: "'b frame"
and G :: "'b frame"
shows "p ∙
(nominal_induct F avoiding: p G rule: frame.strong_induct)
(auto simp add: at_prm_fresh[OF at_name_inst]
pt_fresh_perm_app[OF pt_name_inst, OF at_name_inst] eqvts)
extractFrameEqvt[eqvt]:
fixes p :: "name prm"
and P :: "('a, 'b, 'c) psi"
and I :: "('a, 'b, 'c) input"
and C :: "('a, 'b, 'c) psiCase"
shows "p ∙ (extractFrame P) = extractFrame (p ∙ P)"
and "p ∙ (extractFrame' I) = extractFrame' (p ∙ I)"
and "p ∙ (extractFrame'' C) = extractFrame'' (p ∙ C)"
(nominal_induct P and I and C avoiding: p rule: psi_input_psiCase.strong_inducts)
(auto simp add: at_prm_fresh[OF at_name_inst] eqvts permBottom
pt_fresh_perm_app[OF pt_name_inst, OF at_name_inst])
insertAssertionFresh[intro]:
fixes F :: "'b frame"
and Ψ :: 'b
and x :: name
assumes "x ♯ F"
and "x ♯ Ψ"
shows "x ♯ (insertAssertion F Ψ)"
assms
(nominal_induct F avoiding: x Ψ SBott :: b ‹
(auto simp add: abs_fresh)
insertAssertionFreshChain[ntro]:
fixes F :: "'b frame"
and Ψ :: 'b
and xvec :: "name list"
and Xs :: "name set"
shows "[xvec ♯* F; xvec ♯* Ψ]==> xvec ♯* (insertAssertion F Ψ)"
and "[Xs ♯* F; Xs ♯* Ψ]==> Xs ♯* (insertAssertion F Ψ)"
(auto simp add: fresh_star_def)
mergeFrameFresh[intro]:
fixes F :: "'b frame"
and G :: assumassumes statEqvt[eqvt]: : "\And::nname prm p \<>
and x :: name
shows "[x ♯ F; x ♯ G]==> x ♯ (mergeFrame F G)"
(nominal_induct F avoiding: x G rule: frame.strong_induct)
(auto simp add: abs_fresh)
mergeFrameFreshChain[intro]:
fixes F :: "'b frame"
and G :: "'b frame"
and xvec :: "name list"
and Xs :: "name set"
shows "[♯ (mergeFrameF G)"
and "[Xs ♯* F; Xs ♯* G]==> Xs ♯* (mergeFrame F G)"
(auto simp add: fresh_star_def)
extractFrameFresh:
fixes P :: "('a, 'b, 'c) psi"
and I :: "('a, 'b, 'c) input"
and C :: "('a, 'b, 'c) psiCase"
and x :: name
shows "x ♯ P ==> x ♯ extractFrame P"
and "x ♯I"
and "x ♯ C ==> x ♯ extractFrame'' C"
(nominal_induct P and I and C avoiding: x rule: psi_input_psiCase.strong_inducts)
(auto simp add: abs_fresh)
extractFrameFreshChain:
fixes P :: "('a, 'b, 'c) psi"
and I :: "('a, 'b, 'c) input"
and C :: "('a, 'b, 'c) psiCase"
and xvec :: "name list"
and Xs :: "name set"
shows "xvec ♯* P ==> xvec ♯* extractFrame P"
and "xvec ♯* I ==> xvec ♯* extractFrame' I"
and "xvec ♯* C ==> xvec ♯* extractFrame'' C"
and "Xs ♯* P ==> Xs ♯* extractFrame P"
and "XXs ♯" and perm[e[eqvt] "<>:
and "Xs ♯* C ==> Xs ♯* extractFrame'' C"
(auto simp add: fresh_star_def intro: extractFrameFresh)
guardedFrameSupp[simp]:
fixes P :: "('a, 'b, 'c) psi"
and I :: "('a, 'b, 'c) input"
and C :: "('a, 'b, 'c) psiCase"
and x :: name
shows "guarded P ==> x ♯ (extractFrame P)"lemstatClos:
and "guarded' I ==> x ♯ (extractFrame' I)"
and "guarded'' C ==> x ♯ (extractFrame'' C)"
(nominal_induct P and I and C arbitrary: x rule: psi_input_psiCase.strong_inducts)
(auto simp add: frameResChainFresh abs_fresh)
frameResChainFresh':
fixes xvec :: "name list"
and yvec :: "name list"
and F :: "'b frame"
shows "(xvec ♯* ((ν*yvec)F)) = (∀x ∈ set xvec. x ∈ set yvec ∨ x ♯fin{y. and inf {y. ?P(y)}"
(simp add: frameResChainFresh fres
frameChainFresh[simp]:
fixes xvec :: "name list"
and Ψ :: 'b
and Xs :: "name set"
frameImpResPres:
fixes F :: "'b frame"
and G :: "'b frame"
and x :: name
assumes "F ↪F G"
shows "(>F ↪F (rparr>G""
(auto simp add: FrameStatImp_def)
fix φ::'c
obtain AF ΨF where Feq: "F = ⟨AF, ΨF⟩" and "AF♯* (x, φ)"
by(rule freshFrame)
from ‹AF♯* (x, φ)› '
obtain y where "y ♯ AF" and "y ♯ F" and "y ♯ G"
and "x ≠ y" and "y ♯ φ"
by(enerate_fresh "name", auto)
assume "(νx)F ⊨F φ"
with ‹y ♯
with Feq ‹x ♯ AF›‹
with ‹
by(force intro: frameImpI dest: frameImpE simp del: frameResChain.simps)
hence "([(x, y)] ∙⟨
by(rule frameImpClosed)
with ‹x ♯ AF›‹y ♯ AF› Feq have "F ⊨: 'a
by(simp add: eqvts)
with ‹F ↪F G› have "G \<turnstile
obtain AG Ψ
(rufreshFram)
from ‹
java.lang.NullPointerException
by(rule frameImpClosed)
with Geq ‹
with ‹y ♯ φ :: "ame l"
by(force intro: frameImpI dest: frameImpE simp del: frameResChain.simps)
with ‹y ♯ G›‹x ♯ AG›‹y ♯ AG›
by(subst alphaFrameRes) (fastforce simp add: eqvts)+
frameResPres:
fixes F :: "'b frame"
and G :: "'b frame"
and x :: name
x \noteq"
show ?thesis
proof(auto simp add: FrameStatImp_def)
fix φ::'c
obtain AF ΨF where Feq: "F = ⟨Aadd: supp permBottom)
freshFrame)
then have "x ♯ AF" and "y ♯ AF" and "AF♯*and N : 'a
java.lang.NullPointerException
by(generate_fresh "name") auto
obtain y'::name where "y' ≠ x" and "y' ≠ y" and "y' ≠ x'" and "y' ♯ F" and "y' ♯ φ" and "y' ♯ AF"
by(generate_fresh "name") auto
java.lang.NullPointerException
moreover from ‹
by(rule_tac alphaFrameRes) (simp add: abs_fresh fresh_left)
moreover with ‹y' ≠ x'›‹y' ≠
by(simp add: eqvts calc_atm)
A "\<lparr\\lparrν(lparr>ν>F\\)∙
using Feq ‹x ♯ AF›
by(simp add: eqvts)
from ‹
by(simp add: alphaFrameRes)
moreover from ‹y' ♯ F›‹y' ≠ x›‹y' ≠ x'› have "… = (νy')([(y, y')] ∙
)simp ad: ab fr)
moreover with ‹
by(simp add: eqvts calc_atm)
moreover with ‹
have "… = (νy')((νx')([(x, x')] ∙ [(y, y')] ∙ F))"
apply(simp add: eqvts)
by(subst perm_compose) (simp add: calc_atm)
ultimately have B: "(νy)((νx)F)= (νy')((νx')((ν*AF)(FAs and p :: "name pr
using Feq ‹x ♯ AF›‹x' ♯ AF›‹
:)
>\\>›* φ›
have "⟨(x'#y'#AF), [(x, x')] ∙ [(y, y')] ∙ ΨF⟩⊨F φ = ⟨(y'#x'#AF), [(x, x')] ∙ [(y, y')] ∙ ΨF⟩⊨F φ"
by(force dest: frameImpE intro: frameImpI simp del: frameResChain.simps)
java.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21
by simp
moreover assume "((νx)((νy)F)) ⊨F φ"
ultimately show "((νy)((νx)F)) ⊨F φ" by simp
qed
frameResComm:
fixes x :: name
and y :: name
and F :: "'b frame"
insertAssertionE:
fixes F :: "('b::fs_name) frame"
and Ψ :: 'b
and Ψ' :: 'b
and AF :: "name list"
assumes "insertAssertion F Ψ = ⟨AF, Ψ'⟩"
and "AF♯* F"
and "AF♯* Ψ"
and "distinct AF"
obtains ΨF where "F = ⟨AF, ΨF⟩" and "Ψ' = Ψ ⊗ ΨF"
-
assume A: "∧ΨF. [F = ⟨AF, ΨF⟩; Ψ' = Ψ ⊗ ΨF]==> thesis"
from assms have "∃ΨF. F = ⟨AF, ΨF⟩∧ Ψ' = Ψ ⊗ ΨF"
proof(nominal_induct F avoiding: Ψ A>"
case(FAssert Ψ AF Ψ')
thus ?case by auto
next
case(FRes x F Ψ AF Ψ')
from ‹insertAssertion (( assms
obtain y AF' where "AF = y#AF'" by(induct AF) auto
with ‹
have A: "insertAssertion F Ψ = ⟨:
by(simp add: frame.inject alpha eqvts)
java.lang.NullPointerException
from ‹distinct AF›‹AF = y#AF'› have "y ♯ ::: 'b
from ‹
apply -
apply(auto simp add: abs_fresh)
apply(hypsubst_thin)
apply(subst fresh_star_def)
apply(erule rev_mp)
apply(subst fresh_star_def)
apply(clarify)
apply(erule_tac x=xa in ballE)
apply(simp add: abs_fresh)
apply auto
by(simp add: fresh_def name_list_supp)
java.lang.NullPointerException
from ‹
with ‹x ♯ Ψ›‹y ♯ Ψ› have "([(x, y)] ∙ AF') ♯* Ψ" by simp
with ‹ ‹([(x, y)] ∙ AF') ♯* F›‹
obtain ΨF where Feq: "F = ⟨AF', ΨF⟩" and Ψeq: "([(x, y)] ∙ Ψ') = Ψ: 'b
by force
from Feq have "(νx)F = ⟨(x#AF'), ΨF⟩" by(simp add: frame.inject)
hence "([(x, y)] ∙(νx)F) = [(x, y)] ∙⟨(x#AF'), ΨF⟩" by simp
hence "(νx)F = ⟨AF, [(x, y)] ∙ ΨF⟩" using ‹y ♯ F›‹
ad: eq calc_atm alph
moreover from Ψeq have "[(x, y)] ∙ ([(x, y)] ∙ Ψ') = [(x, y)] ∙ (Ψ ⊗ a
by simp
with \open>x ♯♯ "\Psi>' Ψ> ([(xy)]∙su>F)" by( add: eqvt
ultimately show ?case
by blast
qed
with A show ?thesis
by blast
mergeFrameE:
fixes F :: "'b frame"
and G :: "'b frame"
and AFG :: "name list"
and ΨFG :: 'b
assumes "mergeFrame F G = ⟨AFG, ΨFG⟩"
and "distinct AFG"
and "AFG♯* F"
and "AFG♯* G"
obtains AF ΨF AG ΨG where "AFG = AF@AG" and "ΨFG = ΨF⊗ ΨG" and "F = ⟨AF, ΨF⟩" and "G = ⟨AG, ΨG⟩" and "AF♯* ΨG" and "AG♯* ΨF"
assume A: "∧AF AG ΨF ΨG. [AFG = AF@AG; Ψ
java.lang.NullPointerException
proof(nominal_induct F avoiding: G AFG ΨFG rule: frame.strong_induct)
case(FAssert Ψ G AFG ΨFG)
thus ?case
apply auto
apply(rule_tac x="[]" in exI)
by(drule_tac insertAssertionE) auto
next
java.lang.NullPointerException
from ‹mergeFrame ((ν "Ψ
obtain y AFG' where "AFG = y#AFG'" by(induct AFG) auto
with ‹AFG♯* ((>)≃
by(auto simp add: supp_list_cons fresh_star_def fresh_def name_list_supp abs_supp frame.supp)
from ‹AFG = y#AFG'›‹
java.lang.NullPointerException
apply(auto simp add: abs_fresh frameResChainFreshSet)
apply(hypsubst_thin)
by(induct AFG') (auto simp add: abs_fresh)
from ‹
with ‹
have "mergeFrame F G = ⟨AFG', [(x, y)] ∙ ΨFG⟩"
by(simp add: frame.inject alpha eqvts)
with ‹p :: "nam prm" ‹∧G AFG ΨFG. [mergeFrame F G = ⟨A<> >) ↪'))"
obtain AF ΨF AG ΨG where "AFG' = AF@AG" and "([(x, y)] ∙ ΨFG) = ΨF⊗ ΨG" and FrF: "F = ⟨AF, ΨF⟩" and FrG: "G = ⟨AG, ΨG⟩" and "AF♯* ΨG" and "AG♯
by metis
from ‹
moreover from ‹AFG' = AF@AG›‹y ♯ AFG'›
with ‹y ♯ G›
by auto
from 🪙[x, yy)] \<> ^sub>G) [(x, y)] ∙⊗G)"
by simp
with ‹x ♯ ΨG›‹y ♯ ΨG› have "ΨFG = ([(x, y)] ∙ ΨF) ⊗ ΨG" by(simp add: eqvts)
moreover from FrF have "([(x, y)] ∙ F) = [(x, y)] ∙⟨AF, ΨF⟩" by simp
with ‹x ♯ AF›‹y ♯ AF› have "([(x, y)] ∙ F) = ⟨AF, [(x, y)] ∙ ΨF⟩" by(simp add: eqvts)
hence "(νy)([(x, y)] ∙ F) = ⟨(y#AF), [(x, y)] ∙ ΨF⟩" by(simp add: frame.inject)
with ‹y ♯ F› have "(νx)F = ⟨(y#AF), [(x, y)] ∙ ΨF⟩" by(simp add: alphaFrameRes)
moreover with ‹AG♯* ΨF› have "([(x, y)] ∙ AG) ♯* ([(x, y)] ∙ ΨF)" by(simp add: pt_fresh_star_bij[OF pt_name_inst, OF at_name_inst])
with ‹x ♯ AG›‹y ♯ AG› have "AG♯* ([(x, y)] ∙ ΨF)" by simp
moreover from ‹AF♯* ΨG›
ultimately show ?case using FrG
by blast
qed
with A show ?thesis by blast
mergeFrameRes1[simp]:
fixes AF :: "name list"
and ΨF :: 'b
and x :: name
and AG :: "name list"
and ΨG :: 'b
assumes "AF♯
and "AF♯* AG"
and "x ♯ AF"
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
and "AG♯* ΨF"
frameChanEqTrans:
fixes F :: "'b frame"
and M :: 'a
and N :: 'a
assumes "F ⊨F M ↔ N"
and "F ⊨F N ↔ L"
shows "F ⊨F M ↔ L"
-
obtain AF ΨF where "F = ⟨AF, ΨF⟩" and "A\<^>F
by(rule freshFrame)
with assms show ?thesis
by(force dest: frameImpE intro: frameImpI chanEqTrans)
*) lemma frameIntAssociativity: fixes AF :: "name list" and Ψ :: 'b and Ψ' :: 'b and Ψ'' :: 'b
lemma frameCommutativity: fixes F :: "'b frame" and G :: "'b frame"
shows"F ⊗F G ≃F G ⊗F F" proof - obtain AF ΨFwhere"F = ⟨AF, ΨF⟩"and"AF♯* G" by(rule freshFrame) moreoverobtainA" =⟨Psi^sub<>" a "A<^sub" and "F" by(rule_tac C="(AF, ΨF)" in freshFrame) auto moreover from ‹AF♯* G›‹G = ⟨AG, ΨG⟩›‹AG♯* AF› have "AF♯* ΨG" by auto ultimately show ?thesis by auto (metis FrameStatEqTrans frameChainAppend frameResChainComm frameIntCommutativity) qed lemma frameScopeExt: fixes x :: name and F :: "'b frame" and G :: "'b frame"
assumes "x ♯ F"
shows "(νx)(F ⊗F G) ≃F F ⊗F ((νx)G)" proof - have "(νx)(F ⊗F G) ≃F(νx)(G ⊗F F)" by(metis frameResPres frameCommutativity) with ‹x ♯ F› have "(νx)(F ⊗F G) ≃F ((νx)G) ⊗F F" by simp moreover have "((νx)G) ⊗F F ≃F F ⊗F ((νx)G)" by(rule frameCommutativity) ultimately show ?thesis by(rule FrameStatEqTrans) qed
lemma insertDoubleAssertionStatEq: fixes F :: "'b frame" and Ψ :: 'b and Ψ' :: 'b
shows "insertAssertion(insertAssertion F Ψ) Ψ' ≃F (insertAssertion F) (Ψ ⊗ proof - obtain AF ΨFwhere"F = ⟨AF, ΨF⟩"and"AF♯* Ψ"and"AF♯* Ψ'"and"AF♯* (Ψ ⊗ Ψ')" by(rule_tac C="(Ψ, Ψ')"in freshFrame) auto thus ?thesis by auto (metis frameIntComposition qed
lemma guardedStatEq: fixes P : "'a, ', ''c) psi" and I :: "('a, 'b, 'c) input" and C :: "('a, 'b, 'c) psiCase" and AP :: "name list" and ΨP :: 'b
shows"[guarded P; extractFrame P = ⟨AP, ΨP⟩]==> ΨP≃⊥∧ supp ΨP = ({}::name set)" and"[guarded' I; extractFrame' I = ⟨AP, ΨP⟩]==> ΨP≃⊥ and "[guarded'' C; extractFrame'' C = ⟨AP, ΨP⟩]==> ΨP≃⊥∧ supp ΨP = ({}::name set)" proof(nominal_induct P and I and C arbitrary: AP ΨP rule: psi_input_psiCase.strong_inducts) case(PsiNil AP ΨP) thus ?case by simp next case(Output M N P AP ΨP) thus ?case by simp next case(Input M In AP ΨP) thus ?case by simp next case(Case psiCase AP ΨP) thus ?case by simp next case(Par P Q A><>* \phi from ‹guarded(P ∥ Q)› have "guarded P" and "guarded Q" by simp+ obtain AP ΨP where FrP: "extractFrame P = ⟨AP, ΨP⟩" and "AP♯* Q" by(rule freshFrame) obtain AQ ΨQ where FrQ: "extractFrame Q = ⟨AQ, ΨQ⟩" and "AQ♯* AP" and "AQ♯* ΨP" by(rule_tac C"A<^>,
from‹AP♯* Q› FrQ ‹AQ♯* AP›have"AP♯* ΨQ"by(drule_tac extractFrameFreshChain) auto with‹AQ♯* AP›‹AQ♯* ΨP› FrP FrQ ‹extractFrame(P ∥have "length xs = length ys" and "xs ♯>* φ♯\sharp> φ
by auto
with ulti
by blast
moreover from ‹ ni
by(metis Composition Identity Associativity Commutativity AssertionStatEqTrans)
ultimately show ?case using ‹supp ΨP = {}›‹supp ΨQ = {}› compSupp
by blast
java.lang.NullPointerException
from ‹guarded((νx)P)› have "guarded P" by simp
moreover obtain AP ΨP where FrP: "extractFrame P = ⟨AP, ΨP⟩" by(rule freshFrame)
java.lang.NullPointerException
ultimately have "ΨP≃⊥" and "supp ΨP = ({}::name set)" by auto
from FrP ‹extractFrame((νx)P)
with ‹supp ΨP = {}› have "ΨP = ΨxP" by(auto simp del: frameResChain.simps)
with ‹
by simp
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.
Suchen
