10267
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{CTLind}%
|
|
4 |
%
|
10878
|
5 |
\isamarkupsubsection{CTL Revisited%
|
10395
|
6 |
}
|
10267
|
7 |
%
|
|
8 |
\begin{isamarkuptext}%
|
|
9 |
\label{sec:CTL-revisited}
|
10283
|
10 |
The purpose of this section is twofold: we want to demonstrate
|
|
11 |
some of the induction principles and heuristics discussed above and we want to
|
|
12 |
show how inductive definitions can simplify proofs.
|
10267
|
13 |
In \S\ref{sec:CTL} we gave a fairly involved proof of the correctness of a
|
10795
|
14 |
model checker for CTL\@. In particular the proof of the
|
10267
|
15 |
\isa{infinity{\isacharunderscore}lemma} on the way to \isa{AF{\isacharunderscore}lemma{\isadigit{2}}} is not as
|
|
16 |
simple as one might intuitively expect, due to the \isa{SOME} operator
|
10283
|
17 |
involved. Below we give a simpler proof of \isa{AF{\isacharunderscore}lemma{\isadigit{2}}}
|
|
18 |
based on an auxiliary inductive definition.
|
10267
|
19 |
|
|
20 |
Let us call a (finite or infinite) path \emph{\isa{A}-avoiding} if it does
|
|
21 |
not touch any node in the set \isa{A}. Then \isa{AF{\isacharunderscore}lemma{\isadigit{2}}} says
|
|
22 |
that if no infinite path from some state \isa{s} is \isa{A}-avoiding,
|
|
23 |
then \isa{s\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}}. We prove this by inductively defining the set
|
|
24 |
\isa{Avoid\ s\ A} of states reachable from \isa{s} by a finite \isa{A}-avoiding path:
|
|
25 |
% Second proof of opposite direction, directly by well-founded induction
|
|
26 |
% on the initial segment of M that avoids A.%
|
|
27 |
\end{isamarkuptext}%
|
|
28 |
\isacommand{consts}\ Avoid\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}state\ {\isasymRightarrow}\ state\ set\ {\isasymRightarrow}\ state\ set{\isachardoublequote}\isanewline
|
|
29 |
\isacommand{inductive}\ {\isachardoublequote}Avoid\ s\ A{\isachardoublequote}\isanewline
|
|
30 |
\isakeyword{intros}\ {\isachardoublequote}s\ {\isasymin}\ Avoid\ s\ A{\isachardoublequote}\isanewline
|
|
31 |
\ \ \ \ \ \ \ {\isachardoublequote}{\isasymlbrakk}\ t\ {\isasymin}\ Avoid\ s\ A{\isacharsemicolon}\ t\ {\isasymnotin}\ A{\isacharsemicolon}\ {\isacharparenleft}t{\isacharcomma}u{\isacharparenright}\ {\isasymin}\ M\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ u\ {\isasymin}\ Avoid\ s\ A{\isachardoublequote}%
|
|
32 |
\begin{isamarkuptext}%
|
|
33 |
It is easy to see that for any infinite \isa{A}-avoiding path \isa{f}
|
|
34 |
with \isa{f\ {\isadigit{0}}\ {\isasymin}\ Avoid\ s\ A} there is an infinite \isa{A}-avoiding path
|
|
35 |
starting with \isa{s} because (by definition of \isa{Avoid}) there is a
|
|
36 |
finite \isa{A}-avoiding path from \isa{s} to \isa{f\ {\isadigit{0}}}.
|
|
37 |
The proof is by induction on \isa{f\ {\isadigit{0}}\ {\isasymin}\ Avoid\ s\ A}. However,
|
|
38 |
this requires the following
|
|
39 |
reformulation, as explained in \S\ref{sec:ind-var-in-prems} above;
|
|
40 |
the \isa{rule{\isacharunderscore}format} directive undoes the reformulation after the proof.%
|
|
41 |
\end{isamarkuptext}%
|
|
42 |
\isacommand{lemma}\ ex{\isacharunderscore}infinite{\isacharunderscore}path{\isacharbrackleft}rule{\isacharunderscore}format{\isacharbrackright}{\isacharcolon}\isanewline
|
|
43 |
\ \ {\isachardoublequote}t\ {\isasymin}\ Avoid\ s\ A\ \ {\isasymLongrightarrow}\isanewline
|
|
44 |
\ \ \ {\isasymforall}f{\isasymin}Paths\ t{\isachardot}\ {\isacharparenleft}{\isasymforall}i{\isachardot}\ f\ i\ {\isasymnotin}\ A{\isacharparenright}\ {\isasymlongrightarrow}\ {\isacharparenleft}{\isasymexists}p{\isasymin}Paths\ s{\isachardot}\ {\isasymforall}i{\isachardot}\ p\ i\ {\isasymnotin}\ A{\isacharparenright}{\isachardoublequote}\isanewline
|
|
45 |
\isacommand{apply}{\isacharparenleft}erule\ Avoid{\isachardot}induct{\isacharparenright}\isanewline
|
|
46 |
\ \isacommand{apply}{\isacharparenleft}blast{\isacharparenright}\isanewline
|
|
47 |
\isacommand{apply}{\isacharparenleft}clarify{\isacharparenright}\isanewline
|
|
48 |
\isacommand{apply}{\isacharparenleft}drule{\isacharunderscore}tac\ x\ {\isacharequal}\ {\isachardoublequote}{\isasymlambda}i{\isachardot}\ case\ i\ of\ {\isadigit{0}}\ {\isasymRightarrow}\ t\ {\isacharbar}\ Suc\ i\ {\isasymRightarrow}\ f\ i{\isachardoublequote}\ \isakeyword{in}\ bspec{\isacharparenright}\isanewline
|
|
49 |
\isacommand{apply}{\isacharparenleft}simp{\isacharunderscore}all\ add{\isacharcolon}Paths{\isacharunderscore}def\ split{\isacharcolon}nat{\isachardot}split{\isacharparenright}\isanewline
|
|
50 |
\isacommand{done}%
|
|
51 |
\begin{isamarkuptext}%
|
|
52 |
\noindent
|
|
53 |
The base case (\isa{t\ {\isacharequal}\ s}) is trivial (\isa{blast}).
|
|
54 |
In the induction step, we have an infinite \isa{A}-avoiding path \isa{f}
|
|
55 |
starting from \isa{u}, a successor of \isa{t}. Now we simply instantiate
|
|
56 |
the \isa{{\isasymforall}f{\isasymin}Paths\ t} in the induction hypothesis by the path starting with
|
|
57 |
\isa{t} and continuing with \isa{f}. That is what the above $\lambda$-term
|
10878
|
58 |
expresses. Simplification shows that this is a path starting with \isa{t}
|
|
59 |
and that the instantiated induction hypothesis implies the conclusion.
|
10267
|
60 |
|
11196
|
61 |
Now we come to the key lemma. Assuming that no infinite \isa{A}-avoiding
|
11277
|
62 |
path starts from \isa{s}, we want to show \isa{s\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}}. For the
|
|
63 |
inductive proof this must be generalized to the statement that every point \isa{t}
|
|
64 |
``between'' \isa{s} and \isa{A}, i.e.\ all of \isa{Avoid\ s\ A},
|
11196
|
65 |
is contained in \isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}}:%
|
10267
|
66 |
\end{isamarkuptext}%
|
|
67 |
\isacommand{lemma}\ Avoid{\isacharunderscore}in{\isacharunderscore}lfp{\isacharbrackleft}rule{\isacharunderscore}format{\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharbrackright}{\isacharcolon}\isanewline
|
|
68 |
\ \ {\isachardoublequote}{\isasymforall}p{\isasymin}Paths\ s{\isachardot}\ {\isasymexists}i{\isachardot}\ p\ i\ {\isasymin}\ A\ {\isasymLongrightarrow}\ t\ {\isasymin}\ Avoid\ s\ A\ {\isasymlongrightarrow}\ t\ {\isasymin}\ lfp{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}%
|
|
69 |
\begin{isamarkuptxt}%
|
|
70 |
\noindent
|
11196
|
71 |
The proof is by induction on the ``distance'' between \isa{t} and \isa{A}. Remember that \isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}\ {\isacharequal}\ A\ {\isasymunion}\ M{\isasyminverse}\ {\isacharbackquote}{\isacharbackquote}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}}.
|
|
72 |
If \isa{t} is already in \isa{A}, then \isa{t\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}} is
|
|
73 |
trivial. If \isa{t} is not in \isa{A} but all successors are in
|
|
74 |
\isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}} (induction hypothesis), then \isa{t\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}} is
|
|
75 |
again trivial.
|
|
76 |
|
|
77 |
The formal counterpart of this proof sketch is a well-founded induction
|
|
78 |
w.r.t.\ \isa{M} restricted to (roughly speaking) \isa{Avoid\ s\ A\ {\isacharminus}\ A}:
|
10267
|
79 |
\begin{isabelle}%
|
11196
|
80 |
\ \ \ \ \ {\isacharbraceleft}{\isacharparenleft}y{\isacharcomma}\ x{\isacharparenright}{\isachardot}\ {\isacharparenleft}x{\isacharcomma}\ y{\isacharparenright}\ {\isasymin}\ M\ {\isasymand}\ x\ {\isasymin}\ Avoid\ s\ A\ {\isasymand}\ x\ {\isasymnotin}\ A{\isacharbraceright}%
|
10267
|
81 |
\end{isabelle}
|
11277
|
82 |
As we shall see presently, the absence of infinite \isa{A}-avoiding paths
|
10267
|
83 |
starting from \isa{s} implies well-foundedness of this relation. For the
|
|
84 |
moment we assume this and proceed with the induction:%
|
|
85 |
\end{isamarkuptxt}%
|
11196
|
86 |
\isacommand{apply}{\isacharparenleft}subgoal{\isacharunderscore}tac\ {\isachardoublequote}wf{\isacharbraceleft}{\isacharparenleft}y{\isacharcomma}x{\isacharparenright}{\isachardot}\ {\isacharparenleft}x{\isacharcomma}y{\isacharparenright}\ {\isasymin}\ M\ {\isasymand}\ x\ {\isasymin}\ Avoid\ s\ A\ {\isasymand}\ x\ {\isasymnotin}\ A{\isacharbraceright}{\isachardoublequote}{\isacharparenright}\isanewline
|
10267
|
87 |
\ \isacommand{apply}{\isacharparenleft}erule{\isacharunderscore}tac\ a\ {\isacharequal}\ t\ \isakeyword{in}\ wf{\isacharunderscore}induct{\isacharparenright}\isanewline
|
|
88 |
\ \isacommand{apply}{\isacharparenleft}clarsimp{\isacharparenright}%
|
|
89 |
\begin{isamarkuptxt}%
|
|
90 |
\noindent
|
10878
|
91 |
\begin{isabelle}%
|
11196
|
92 |
\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}t{\isachardot}\ {\isasymlbrakk}{\isasymforall}p{\isasymin}Paths\ s{\isachardot}\ {\isasymexists}i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharsemicolon}\ t\ {\isasymin}\ Avoid\ s\ A{\isacharsemicolon}\isanewline
|
|
93 |
\isaindent{\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}t{\isachardot}\ \ \ \ }{\isasymforall}y{\isachardot}\ {\isacharparenleft}t{\isacharcomma}\ y{\isacharparenright}\ {\isasymin}\ M\ {\isasymand}\ t\ {\isasymnotin}\ A\ {\isasymlongrightarrow}\isanewline
|
|
94 |
\isaindent{\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}t{\isachardot}\ \ \ \ {\isasymforall}y{\isachardot}\ }y\ {\isasymin}\ Avoid\ s\ A\ {\isasymlongrightarrow}\ y\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}{\isasymrbrakk}\isanewline
|
|
95 |
\isaindent{\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}t{\isachardot}\ }{\isasymLongrightarrow}\ t\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}\isanewline
|
10878
|
96 |
\ {\isadigit{2}}{\isachardot}\ {\isasymforall}p{\isasymin}Paths\ s{\isachardot}\ {\isasymexists}i{\isachardot}\ p\ i\ {\isasymin}\ A\ {\isasymLongrightarrow}\isanewline
|
11196
|
97 |
\isaindent{\ {\isadigit{2}}{\isachardot}\ }wf\ {\isacharbraceleft}{\isacharparenleft}y{\isacharcomma}\ x{\isacharparenright}{\isachardot}\ {\isacharparenleft}x{\isacharcomma}\ y{\isacharparenright}\ {\isasymin}\ M\ {\isasymand}\ x\ {\isasymin}\ Avoid\ s\ A\ {\isasymand}\ x\ {\isasymnotin}\ A{\isacharbraceright}%
|
10878
|
98 |
\end{isabelle}
|
|
99 |
Now the induction hypothesis states that if \isa{t\ {\isasymnotin}\ A}
|
10267
|
100 |
then all successors of \isa{t} that are in \isa{Avoid\ s\ A} are in
|
11196
|
101 |
\isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}}. Unfolding \isa{lfp} in the conclusion of the first
|
|
102 |
subgoal once, we have to prove that \isa{t} is in \isa{A} or all successors
|
|
103 |
of \isa{t} are in \isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}}: if \isa{t} is not in \isa{A},
|
|
104 |
the second
|
10267
|
105 |
\isa{Avoid}-rule implies that all successors of \isa{t} are in
|
|
106 |
\isa{Avoid\ s\ A} (because we also assume \isa{t\ {\isasymin}\ Avoid\ s\ A}), and
|
|
107 |
hence, by the induction hypothesis, all successors of \isa{t} are indeed in
|
|
108 |
\isa{lfp\ {\isacharparenleft}af\ A{\isacharparenright}}. Mechanically:%
|
|
109 |
\end{isamarkuptxt}%
|
11196
|
110 |
\ \isacommand{apply}{\isacharparenleft}subst\ lfp{\isacharunderscore}unfold{\isacharbrackleft}OF\ mono{\isacharunderscore}af{\isacharbrackright}{\isacharparenright}\isanewline
|
|
111 |
\ \isacommand{apply}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}\ add{\isacharcolon}\ af{\isacharunderscore}def{\isacharparenright}\isanewline
|
10267
|
112 |
\ \isacommand{apply}{\isacharparenleft}blast\ intro{\isacharcolon}Avoid{\isachardot}intros{\isacharparenright}%
|
|
113 |
\begin{isamarkuptxt}%
|
|
114 |
Having proved the main goal we return to the proof obligation that the above
|
10878
|
115 |
relation is indeed well-founded. This is proved by contradiction: if
|
|
116 |
the relation is not well-founded then there exists an infinite \isa{A}-avoiding path all in \isa{Avoid\ s\ A}, by theorem
|
10267
|
117 |
\isa{wf{\isacharunderscore}iff{\isacharunderscore}no{\isacharunderscore}infinite{\isacharunderscore}down{\isacharunderscore}chain}:
|
|
118 |
\begin{isabelle}%
|
|
119 |
\ \ \ \ \ wf\ r\ {\isacharequal}\ {\isacharparenleft}{\isasymnot}\ {\isacharparenleft}{\isasymexists}f{\isachardot}\ {\isasymforall}i{\isachardot}\ {\isacharparenleft}f\ {\isacharparenleft}Suc\ i{\isacharparenright}{\isacharcomma}\ f\ i{\isacharparenright}\ {\isasymin}\ r{\isacharparenright}{\isacharparenright}%
|
|
120 |
\end{isabelle}
|
|
121 |
From lemma \isa{ex{\isacharunderscore}infinite{\isacharunderscore}path} the existence of an infinite
|
10878
|
122 |
\isa{A}-avoiding path starting in \isa{s} follows, contradiction.%
|
10267
|
123 |
\end{isamarkuptxt}%
|
|
124 |
\isacommand{apply}{\isacharparenleft}erule\ contrapos{\isacharunderscore}pp{\isacharparenright}\isanewline
|
|
125 |
\isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}wf{\isacharunderscore}iff{\isacharunderscore}no{\isacharunderscore}infinite{\isacharunderscore}down{\isacharunderscore}chain{\isacharparenright}\isanewline
|
|
126 |
\isacommand{apply}{\isacharparenleft}erule\ exE{\isacharparenright}\isanewline
|
|
127 |
\isacommand{apply}{\isacharparenleft}rule\ ex{\isacharunderscore}infinite{\isacharunderscore}path{\isacharparenright}\isanewline
|
|
128 |
\isacommand{apply}{\isacharparenleft}auto\ simp\ add{\isacharcolon}Paths{\isacharunderscore}def{\isacharparenright}\isanewline
|
|
129 |
\isacommand{done}%
|
|
130 |
\begin{isamarkuptext}%
|
11196
|
131 |
The \isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}} modifier of the \isa{rule{\isacharunderscore}format} directive in the
|
|
132 |
statement of the lemma means
|
10971
|
133 |
that the assumption is left unchanged --- otherwise the \isa{{\isasymforall}p} is turned
|
10267
|
134 |
into a \isa{{\isasymAnd}p}, which would complicate matters below. As it is,
|
|
135 |
\isa{Avoid{\isacharunderscore}in{\isacharunderscore}lfp} is now
|
|
136 |
\begin{isabelle}%
|
10696
|
137 |
\ \ \ \ \ {\isasymlbrakk}{\isasymforall}p{\isasymin}Paths\ s{\isachardot}\ {\isasymexists}i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharsemicolon}\ t\ {\isasymin}\ Avoid\ s\ A{\isasymrbrakk}\ {\isasymLongrightarrow}\ t\ {\isasymin}\ lfp\ {\isacharparenleft}af\ A{\isacharparenright}%
|
10267
|
138 |
\end{isabelle}
|
|
139 |
The main theorem is simply the corollary where \isa{t\ {\isacharequal}\ s},
|
|
140 |
in which case the assumption \isa{t\ {\isasymin}\ Avoid\ s\ A} is trivially true
|
10845
|
141 |
by the first \isa{Avoid}-rule. Isabelle confirms this:%
|
10267
|
142 |
\end{isamarkuptext}%
|
10855
|
143 |
\isacommand{theorem}\ AF{\isacharunderscore}lemma{\isadigit{2}}{\isacharcolon}\ \ {\isachardoublequote}{\isacharbraceleft}s{\isachardot}\ {\isasymforall}p\ {\isasymin}\ Paths\ s{\isachardot}\ {\isasymexists}\ i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharbraceright}\ {\isasymsubseteq}\ lfp{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}\isanewline
|
10267
|
144 |
\isacommand{by}{\isacharparenleft}auto\ elim{\isacharcolon}Avoid{\isacharunderscore}in{\isacharunderscore}lfp\ intro{\isacharcolon}Avoid{\isachardot}intros{\isacharparenright}\isanewline
|
|
145 |
\isanewline
|
|
146 |
\end{isabellebody}%
|
|
147 |
%%% Local Variables:
|
|
148 |
%%% mode: latex
|
|
149 |
%%% TeX-master: "root"
|
|
150 |
%%% End:
|