21324
|
1 |
(*<*)theory Sets imports Main begin(*>*)
|
13262
|
2 |
|
|
3 |
section{*Sets, Functions and Relations*}
|
|
4 |
|
|
5 |
subsection{*Set Notation*}
|
|
6 |
|
|
7 |
text{*
|
|
8 |
\begin{center}
|
|
9 |
\begin{tabular}{ccc}
|
|
10 |
@{term "A \<union> B"} & @{term "A \<inter> B"} & @{term "A - B"} \\
|
|
11 |
@{term "a \<in> A"} & @{term "b \<notin> A"} \\
|
|
12 |
@{term "{a,b}"} & @{text "{x. P x}"} \\
|
|
13 |
@{term "\<Union> M"} & @{text "\<Union>a \<in> A. F a"}
|
|
14 |
\end{tabular}
|
|
15 |
\end{center}*}
|
|
16 |
(*<*)term "A \<union> B" term "A \<inter> B" term "A - B"
|
|
17 |
term "a \<in> A" term "b \<notin> A"
|
|
18 |
term "{a,b}" term "{x. P x}"
|
|
19 |
term "\<Union> M" term "\<Union>a \<in> A. F a"(*>*)
|
|
20 |
|
13489
|
21 |
|
13262
|
22 |
subsection{*Some Functions*}
|
|
23 |
|
|
24 |
text{*
|
|
25 |
\begin{tabular}{l}
|
|
26 |
@{thm id_def}\\
|
|
27 |
@{thm o_def[no_vars]}\\
|
|
28 |
@{thm image_def[no_vars]}\\
|
|
29 |
@{thm vimage_def[no_vars]}
|
|
30 |
\end{tabular}*}
|
|
31 |
(*<*)thm id_def o_def[no_vars] image_def[no_vars] vimage_def[no_vars](*>*)
|
|
32 |
|
13489
|
33 |
|
13262
|
34 |
subsection{*Some Relations*}
|
|
35 |
|
|
36 |
text{*
|
|
37 |
\begin{tabular}{l}
|
|
38 |
@{thm Id_def}\\
|
|
39 |
@{thm converse_def[no_vars]}\\
|
|
40 |
@{thm Image_def[no_vars]}\\
|
|
41 |
@{thm rtrancl_refl[no_vars]}\\
|
14138
|
42 |
@{thm rtrancl_into_rtrancl[no_vars]}
|
13262
|
43 |
\end{tabular}*}
|
|
44 |
(*<*)thm Id_def
|
14138
|
45 |
thm converse_def[no_vars] Image_def[no_vars]
|
13262
|
46 |
thm relpow.simps[no_vars]
|
14138
|
47 |
thm rtrancl.intros[no_vars](*>*)
|
13262
|
48 |
|
13489
|
49 |
|
13262
|
50 |
subsection{*Wellfoundedness*}
|
|
51 |
|
|
52 |
text{*
|
|
53 |
\begin{tabular}{l}
|
|
54 |
@{thm wf_def[no_vars]}\\
|
|
55 |
@{thm wf_iff_no_infinite_down_chain[no_vars]}
|
|
56 |
\end{tabular}*}
|
|
57 |
(*<*)thm wf_def[no_vars]
|
|
58 |
thm wf_iff_no_infinite_down_chain[no_vars](*>*)
|
|
59 |
|
13489
|
60 |
|
13262
|
61 |
subsection{*Fixed Point Operators*}
|
|
62 |
|
|
63 |
text{*
|
|
64 |
\begin{tabular}{l}
|
|
65 |
@{thm lfp_def[no_vars]}\\
|
|
66 |
@{thm lfp_unfold[no_vars]}\\
|
|
67 |
@{thm lfp_induct[no_vars]}
|
|
68 |
\end{tabular}*}
|
14138
|
69 |
(*<*)thm lfp_def[no_vars] gfp_def[no_vars]
|
|
70 |
thm lfp_unfold[no_vars]
|
|
71 |
thm lfp_induct[no_vars](*>*)
|
13262
|
72 |
|
13489
|
73 |
|
13262
|
74 |
subsection{*Case Study: Verified Model Checking*}
|
|
75 |
|
|
76 |
typedecl state
|
|
77 |
|
|
78 |
consts M :: "(state \<times> state)set"
|
|
79 |
|
|
80 |
typedecl atom
|
|
81 |
|
|
82 |
consts L :: "state \<Rightarrow> atom set"
|
|
83 |
|
|
84 |
datatype formula = Atom atom
|
13489
|
85 |
| Neg formula
|
|
86 |
| And formula formula
|
|
87 |
| AX formula
|
|
88 |
| EF formula
|
13262
|
89 |
|
|
90 |
consts valid :: "state \<Rightarrow> formula \<Rightarrow> bool" ("(_ \<Turnstile> _)" [80,80] 80)
|
|
91 |
|
|
92 |
primrec
|
|
93 |
"s \<Turnstile> Atom a = (a \<in> L s)"
|
|
94 |
"s \<Turnstile> Neg f = (\<not>(s \<Turnstile> f))"
|
|
95 |
"s \<Turnstile> And f g = (s \<Turnstile> f \<and> s \<Turnstile> g)"
|
|
96 |
"s \<Turnstile> AX f = (\<forall>t. (s,t) \<in> M \<longrightarrow> t \<Turnstile> f)"
|
|
97 |
"s \<Turnstile> EF f = (\<exists>t. (s,t) \<in> M\<^sup>* \<and> t \<Turnstile> f)"
|
|
98 |
|
|
99 |
consts mc :: "formula \<Rightarrow> state set"
|
|
100 |
primrec
|
|
101 |
"mc(Atom a) = {s. a \<in> L s}"
|
|
102 |
"mc(Neg f) = -mc f"
|
|
103 |
"mc(And f g) = mc f \<inter> mc g"
|
|
104 |
"mc(AX f) = {s. \<forall>t. (s,t) \<in> M \<longrightarrow> t \<in> mc f}"
|
|
105 |
"mc(EF f) = lfp(\<lambda>T. mc f \<union> (M\<inverse> `` T))"
|
|
106 |
|
|
107 |
lemma mono_ef: "mono(\<lambda>T. A \<union> (M\<inverse> `` T))"
|
|
108 |
apply(rule monoI)
|
|
109 |
apply blast
|
|
110 |
done
|
|
111 |
|
|
112 |
lemma EF_lemma:
|
|
113 |
"lfp(\<lambda>T. A \<union> (M\<inverse> `` T)) = {s. \<exists>t. (s,t) \<in> M\<^sup>* \<and> t \<in> A}"
|
|
114 |
apply(rule equalityI)
|
|
115 |
thm lfp_lowerbound
|
|
116 |
apply(rule lfp_lowerbound)
|
|
117 |
apply(blast intro: rtrancl_trans)
|
|
118 |
apply(rule subsetI)
|
|
119 |
apply clarsimp
|
|
120 |
apply(erule converse_rtrancl_induct)
|
|
121 |
thm lfp_unfold[OF mono_ef]
|
|
122 |
apply(subst lfp_unfold[OF mono_ef])
|
|
123 |
apply(blast)
|
|
124 |
apply(subst lfp_unfold[OF mono_ef])
|
|
125 |
apply(blast)
|
|
126 |
done
|
|
127 |
|
|
128 |
theorem "mc f = {s. s \<Turnstile> f}"
|
|
129 |
apply(induct_tac f)
|
|
130 |
apply(auto simp add: EF_lemma)
|
|
131 |
done
|
|
132 |
|
14138
|
133 |
text{*Preview of coming attractions: a structured proof of the
|
|
134 |
@{thm[source]EF_lemma}.*}
|
|
135 |
lemma EF_lemma:
|
|
136 |
"lfp(\<lambda>T. A \<union> (M\<inverse> `` T)) = {s. \<exists>t. (s,t) \<in> M\<^sup>* \<and> t \<in> A}"
|
|
137 |
(is "lfp ?F = ?R")
|
|
138 |
proof
|
|
139 |
show "lfp ?F \<subseteq> ?R"
|
|
140 |
proof (rule lfp_lowerbound)
|
|
141 |
show "?F ?R \<subseteq> ?R" by(blast intro: rtrancl_trans)
|
|
142 |
qed
|
|
143 |
next
|
|
144 |
show "?R \<subseteq> lfp ?F"
|
|
145 |
proof
|
|
146 |
fix s assume "s \<in> ?R"
|
|
147 |
then obtain t where st: "(s,t) \<in> M\<^sup>*" and tA: "t \<in> A" by blast
|
|
148 |
from st show "s \<in> lfp ?F"
|
|
149 |
proof (rule converse_rtrancl_induct)
|
|
150 |
show "t \<in> lfp ?F"
|
|
151 |
proof (subst lfp_unfold[OF mono_ef])
|
|
152 |
show "t \<in> ?F(lfp ?F)" using tA by blast
|
|
153 |
qed
|
|
154 |
next
|
|
155 |
fix s s'
|
|
156 |
assume ss': "(s,s') \<in> M" and s't: "(s',t) \<in> M\<^sup>*"
|
|
157 |
and IH: "s' \<in> lfp ?F"
|
|
158 |
show "s \<in> lfp ?F"
|
|
159 |
proof (subst lfp_unfold[OF mono_ef])
|
|
160 |
show "s \<in> ?F(lfp ?F)" using prems by blast
|
|
161 |
qed
|
|
162 |
qed
|
|
163 |
qed
|
|
164 |
qed
|
|
165 |
|
13262
|
166 |
text{*
|
|
167 |
\begin{exercise}
|
|
168 |
@{term AX} has a dual operator @{term EN}\footnote{We cannot use the customary @{text EX}
|
|
169 |
as that is the \textsc{ascii}-equivalent of @{text"\<exists>"}}
|
|
170 |
(``there exists a next state such that'') with the intended semantics
|
|
171 |
@{prop[display]"(s \<Turnstile> EN f) = (EX t. (s,t) : M & t \<Turnstile> f)"}
|
|
172 |
Fortunately, @{term"EN f"} can already be expressed as a PDL formula. How?
|
|
173 |
|
|
174 |
Show that the semantics for @{term EF} satisfies the following recursion equation:
|
|
175 |
@{prop[display]"(s \<Turnstile> EF f) = (s \<Turnstile> f | s \<Turnstile> EN(EF f))"}
|
|
176 |
\end{exercise}*}
|
|
177 |
(*<*)end(*>*)
|