10122
|
1 |
(*<*)theory PDL = Base:(*>*)
|
9958
|
2 |
|
10122
|
3 |
subsection{*Propositional dynmic logic---PDL*}
|
9958
|
4 |
|
|
5 |
datatype ctl_form = Atom atom
|
|
6 |
| NOT ctl_form
|
|
7 |
| And ctl_form ctl_form
|
|
8 |
| AX ctl_form
|
|
9 |
| EF ctl_form;
|
|
10 |
|
|
11 |
consts valid :: "state \<Rightarrow> ctl_form \<Rightarrow> bool" ("(_ \<Turnstile> _)" [80,80] 80)
|
|
12 |
M :: "(state \<times> state)set";
|
|
13 |
|
|
14 |
primrec
|
|
15 |
"s \<Turnstile> Atom a = (a\<in>s)"
|
|
16 |
"s \<Turnstile> NOT f = (\<not>(s \<Turnstile> f))"
|
|
17 |
"s \<Turnstile> And f g = (s \<Turnstile> f \<and> s \<Turnstile> g)"
|
|
18 |
"s \<Turnstile> AX f = (\<forall>t. (s,t) \<in> M \<longrightarrow> t \<Turnstile> f)"
|
|
19 |
"s \<Turnstile> EF f = (\<exists>t. (s,t) \<in> M^* \<and> t \<Turnstile> f)";
|
|
20 |
|
|
21 |
consts mc :: "ctl_form \<Rightarrow> state set";
|
|
22 |
primrec
|
|
23 |
"mc(Atom a) = {s. a\<in>s}"
|
|
24 |
"mc(NOT f) = -mc f"
|
|
25 |
"mc(And f g) = mc f Int mc g"
|
|
26 |
"mc(AX f) = {s. \<forall>t. (s,t) \<in> M \<longrightarrow> t \<in> mc f}"
|
|
27 |
"mc(EF f) = lfp(\<lambda>T. mc f \<union> {s. \<exists>t. (s,t)\<in>M \<and> t\<in>T})";
|
|
28 |
|
|
29 |
lemma mono_lemma: "mono(\<lambda>T. A \<union> {s. \<exists>t. (s,t)\<in>M \<and> t\<in>T})";
|
|
30 |
apply(rule monoI);
|
|
31 |
by(blast);
|
|
32 |
|
|
33 |
lemma lfp_conv_EF:
|
|
34 |
"lfp(\<lambda>T. A \<union> {s. \<exists>t. (s,t)\<in>M \<and> t\<in>T}) = {s. \<exists>t. (s,t) \<in> M^* \<and> t \<in> A}";
|
|
35 |
apply(rule equalityI);
|
|
36 |
apply(rule subsetI);
|
|
37 |
apply(simp);
|
|
38 |
apply(erule Lfp.induct);
|
|
39 |
apply(rule mono_lemma);
|
|
40 |
apply(simp);
|
|
41 |
apply(blast intro: r_into_rtrancl rtrancl_trans);
|
|
42 |
apply(rule subsetI);
|
|
43 |
apply(simp);
|
|
44 |
apply(erule exE);
|
|
45 |
apply(erule conjE);
|
|
46 |
apply(erule_tac P = "t\<in>A" in rev_mp);
|
|
47 |
apply(erule converse_rtrancl_induct);
|
|
48 |
apply(rule ssubst[OF lfp_Tarski[OF mono_lemma]]);
|
|
49 |
apply(blast);
|
|
50 |
apply(rule ssubst[OF lfp_Tarski[OF mono_lemma]]);
|
|
51 |
by(blast);
|
|
52 |
|
|
53 |
theorem "mc f = {s. s \<Turnstile> f}";
|
|
54 |
apply(induct_tac f);
|
|
55 |
by(auto simp add:lfp_conv_EF);
|
|
56 |
|
|
57 |
end;
|