author | boehmes |
Tue, 07 Dec 2010 15:44:38 +0100 | |
changeset 41064 | 0c447a17770a |
parent 32960 | 69916a850301 |
permissions | -rw-r--r-- |
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]) |
|
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
21324
diff
changeset
|
152 |
show "t \<in> ?F(lfp ?F)" using tA by blast |
14138 | 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]) |
|
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
21324
diff
changeset
|
160 |
show "s \<in> ?F(lfp ?F)" using prems by blast |
14138 | 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(*>*) |