22 % |
22 % |
23 \isamarkupchapter{Proofs% |
23 \isamarkupchapter{Proofs% |
24 } |
24 } |
25 \isamarkuptrue% |
25 \isamarkuptrue% |
26 % |
26 % |
|
27 \begin{isamarkuptext}% |
|
28 Proof commands perform transitions of Isar/VM machine |
|
29 configurations, which are block-structured, consisting of a stack of |
|
30 nodes with three main components: logical proof context, current |
|
31 facts, and open goals. Isar/VM transitions are \emph{typed} |
|
32 according to the following three different modes of operation: |
|
33 |
|
34 \begin{descr} |
|
35 |
|
36 \item [\isa{{\isachardoublequote}proof{\isacharparenleft}prove{\isacharparenright}{\isachardoublequote}}] means that a new goal has just been |
|
37 stated that is now to be \emph{proven}; the next command may refine |
|
38 it by some proof method, and enter a sub-proof to establish the |
|
39 actual result. |
|
40 |
|
41 \item [\isa{{\isachardoublequote}proof{\isacharparenleft}state{\isacharparenright}{\isachardoublequote}}] is like a nested theory mode: the |
|
42 context may be augmented by \emph{stating} additional assumptions, |
|
43 intermediate results etc. |
|
44 |
|
45 \item [\isa{{\isachardoublequote}proof{\isacharparenleft}chain{\isacharparenright}{\isachardoublequote}}] is intermediate between \isa{{\isachardoublequote}proof{\isacharparenleft}state{\isacharparenright}{\isachardoublequote}} and \isa{{\isachardoublequote}proof{\isacharparenleft}prove{\isacharparenright}{\isachardoublequote}}: existing facts (i.e.\ |
|
46 the contents of the special ``\indexref{}{fact}{this}\mbox{\isa{this}}'' register) have been |
|
47 just picked up in order to be used when refining the goal claimed |
|
48 next. |
|
49 |
|
50 \end{descr} |
|
51 |
|
52 The proof mode indicator may be read as a verb telling the writer |
|
53 what kind of operation may be performed next. The corresponding |
|
54 typings of proof commands restricts the shape of well-formed proof |
|
55 texts to particular command sequences. So dynamic arrangements of |
|
56 commands eventually turn out as static texts of a certain structure. |
|
57 \Appref{ap:refcard} gives a simplified grammar of the overall |
|
58 (extensible) language emerging that way.% |
|
59 \end{isamarkuptext}% |
|
60 \isamarkuptrue% |
|
61 % |
|
62 \isamarkupsection{Context elements \label{sec:proof-context}% |
|
63 } |
|
64 \isamarkuptrue% |
|
65 % |
|
66 \begin{isamarkuptext}% |
|
67 \begin{matharray}{rcl} |
|
68 \indexdef{}{command}{fix}\mbox{\isa{\isacommand{fix}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
69 \indexdef{}{command}{assume}\mbox{\isa{\isacommand{assume}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
70 \indexdef{}{command}{presume}\mbox{\isa{\isacommand{presume}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
71 \indexdef{}{command}{def}\mbox{\isa{\isacommand{def}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
72 \end{matharray} |
|
73 |
|
74 The logical proof context consists of fixed variables and |
|
75 assumptions. The former closely correspond to Skolem constants, or |
|
76 meta-level universal quantification as provided by the Isabelle/Pure |
|
77 logical framework. Introducing some \emph{arbitrary, but fixed} |
|
78 variable via ``\mbox{\isa{\isacommand{fix}}}~\isa{x}'' results in a local value |
|
79 that may be used in the subsequent proof as any other variable or |
|
80 constant. Furthermore, any result \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymphi}{\isacharbrackleft}x{\isacharbrackright}{\isachardoublequote}} exported from |
|
81 the context will be universally closed wrt.\ \isa{x} at the |
|
82 outermost level: \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymAnd}x{\isachardot}\ {\isasymphi}{\isacharbrackleft}x{\isacharbrackright}{\isachardoublequote}} (this is expressed in normal |
|
83 form using Isabelle's meta-variables). |
|
84 |
|
85 Similarly, introducing some assumption \isa{{\isasymchi}} has two effects. |
|
86 On the one hand, a local theorem is created that may be used as a |
|
87 fact in subsequent proof steps. On the other hand, any result |
|
88 \isa{{\isachardoublequote}{\isasymchi}\ {\isasymturnstile}\ {\isasymphi}{\isachardoublequote}} exported from the context becomes conditional wrt.\ |
|
89 the assumption: \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymchi}\ {\isasymLongrightarrow}\ {\isasymphi}{\isachardoublequote}}. Thus, solving an enclosing goal |
|
90 using such a result would basically introduce a new subgoal stemming |
|
91 from the assumption. How this situation is handled depends on the |
|
92 version of assumption command used: while \mbox{\isa{\isacommand{assume}}} |
|
93 insists on solving the subgoal by unification with some premise of |
|
94 the goal, \mbox{\isa{\isacommand{presume}}} leaves the subgoal unchanged in order |
|
95 to be proved later by the user. |
|
96 |
|
97 Local definitions, introduced by ``\mbox{\isa{\isacommand{def}}}~\isa{{\isachardoublequote}x\ {\isasymequiv}\ t{\isachardoublequote}}'', are achieved by combining ``\mbox{\isa{\isacommand{fix}}}~\isa{x}'' with |
|
98 another version of assumption that causes any hypothetical equation |
|
99 \isa{{\isachardoublequote}x\ {\isasymequiv}\ t{\isachardoublequote}} to be eliminated by the reflexivity rule. Thus, |
|
100 exporting some result \isa{{\isachardoublequote}x\ {\isasymequiv}\ t\ {\isasymturnstile}\ {\isasymphi}{\isacharbrackleft}x{\isacharbrackright}{\isachardoublequote}} yields \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymphi}{\isacharbrackleft}t{\isacharbrackright}{\isachardoublequote}}. |
|
101 |
|
102 \begin{rail} |
|
103 'fix' (vars + 'and') |
|
104 ; |
|
105 ('assume' | 'presume') (props + 'and') |
|
106 ; |
|
107 'def' (def + 'and') |
|
108 ; |
|
109 def: thmdecl? \\ name ('==' | equiv) term termpat? |
|
110 ; |
|
111 \end{rail} |
|
112 |
|
113 \begin{descr} |
|
114 |
|
115 \item [\mbox{\isa{\isacommand{fix}}}~\isa{x}] introduces a local variable |
|
116 \isa{x} that is \emph{arbitrary, but fixed.} |
|
117 |
|
118 \item [\mbox{\isa{\isacommand{assume}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}} and \mbox{\isa{\isacommand{presume}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}] introduce a local fact \isa{{\isachardoublequote}{\isasymphi}\ {\isasymturnstile}\ {\isasymphi}{\isachardoublequote}} by |
|
119 assumption. Subsequent results applied to an enclosing goal (e.g.\ |
|
120 by \indexref{}{command}{show}\mbox{\isa{\isacommand{show}}}) are handled as follows: \mbox{\isa{\isacommand{assume}}} expects to be able to unify with existing premises in the |
|
121 goal, while \mbox{\isa{\isacommand{presume}}} leaves \isa{{\isasymphi}} as new subgoals. |
|
122 |
|
123 Several lists of assumptions may be given (separated by |
|
124 \indexref{}{keyword}{and}\mbox{\isa{\isakeyword{and}}}; the resulting list of current facts consists |
|
125 of all of these concatenated. |
|
126 |
|
127 \item [\mbox{\isa{\isacommand{def}}}~\isa{{\isachardoublequote}x\ {\isasymequiv}\ t{\isachardoublequote}}] introduces a local |
|
128 (non-polymorphic) definition. In results exported from the context, |
|
129 \isa{x} is replaced by \isa{t}. Basically, ``\mbox{\isa{\isacommand{def}}}~\isa{{\isachardoublequote}x\ {\isasymequiv}\ t{\isachardoublequote}}'' abbreviates ``\mbox{\isa{\isacommand{fix}}}~\isa{x}~\mbox{\isa{\isacommand{assume}}}~\isa{{\isachardoublequote}x\ {\isasymequiv}\ t{\isachardoublequote}}'', with the resulting |
|
130 hypothetical equation solved by reflexivity. |
|
131 |
|
132 The default name for the definitional equation is \isa{x{\isacharunderscore}def}. |
|
133 Several simultaneous definitions may be given at the same time. |
|
134 |
|
135 \end{descr} |
|
136 |
|
137 The special name \indexref{}{fact}{prems}\mbox{\isa{prems}} refers to all assumptions of the |
|
138 current context as a list of theorems. This feature should be used |
|
139 with great care! It is better avoided in final proof texts.% |
|
140 \end{isamarkuptext}% |
|
141 \isamarkuptrue% |
|
142 % |
|
143 \isamarkupsection{Facts and forward chaining% |
|
144 } |
|
145 \isamarkuptrue% |
|
146 % |
|
147 \begin{isamarkuptext}% |
|
148 \begin{matharray}{rcl} |
|
149 \indexdef{}{command}{note}\mbox{\isa{\isacommand{note}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
150 \indexdef{}{command}{then}\mbox{\isa{\isacommand{then}}} & : & \isartrans{proof(state)}{proof(chain)} \\ |
|
151 \indexdef{}{command}{from}\mbox{\isa{\isacommand{from}}} & : & \isartrans{proof(state)}{proof(chain)} \\ |
|
152 \indexdef{}{command}{with}\mbox{\isa{\isacommand{with}}} & : & \isartrans{proof(state)}{proof(chain)} \\ |
|
153 \indexdef{}{command}{using}\mbox{\isa{\isacommand{using}}} & : & \isartrans{proof(prove)}{proof(prove)} \\ |
|
154 \indexdef{}{command}{unfolding}\mbox{\isa{\isacommand{unfolding}}} & : & \isartrans{proof(prove)}{proof(prove)} \\ |
|
155 \end{matharray} |
|
156 |
|
157 New facts are established either by assumption or proof of local |
|
158 statements. Any fact will usually be involved in further proofs, |
|
159 either as explicit arguments of proof methods, or when forward |
|
160 chaining towards the next goal via \mbox{\isa{\isacommand{then}}} (and variants); |
|
161 \mbox{\isa{\isacommand{from}}} and \mbox{\isa{\isacommand{with}}} are composite forms |
|
162 involving \mbox{\isa{\isacommand{note}}}. The \mbox{\isa{\isacommand{using}}} elements |
|
163 augments the collection of used facts \emph{after} a goal has been |
|
164 stated. Note that the special theorem name \indexref{}{fact}{this}\mbox{\isa{this}} refers |
|
165 to the most recently established facts, but only \emph{before} |
|
166 issuing a follow-up claim. |
|
167 |
|
168 \begin{rail} |
|
169 'note' (thmdef? thmrefs + 'and') |
|
170 ; |
|
171 ('from' | 'with' | 'using' | 'unfolding') (thmrefs + 'and') |
|
172 ; |
|
173 \end{rail} |
|
174 |
|
175 \begin{descr} |
|
176 |
|
177 \item [\mbox{\isa{\isacommand{note}}}~\isa{{\isachardoublequote}a\ {\isacharequal}\ b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub n{\isachardoublequote}}] |
|
178 recalls existing facts \isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ b\isactrlsub n{\isachardoublequote}}, binding |
|
179 the result as \isa{a}. Note that attributes may be involved as |
|
180 well, both on the left and right hand sides. |
|
181 |
|
182 \item [\mbox{\isa{\isacommand{then}}}] indicates forward chaining by the current |
|
183 facts in order to establish the goal to be claimed next. The |
|
184 initial proof method invoked to refine that will be offered the |
|
185 facts to do ``anything appropriate'' (see also |
|
186 \secref{sec:proof-steps}). For example, method \indexref{}{method}{rule}\mbox{\isa{rule}} |
|
187 (see \secref{sec:pure-meth-att}) would typically do an elimination |
|
188 rather than an introduction. Automatic methods usually insert the |
|
189 facts into the goal state before operation. This provides a simple |
|
190 scheme to control relevance of facts in automated proof search. |
|
191 |
|
192 \item [\mbox{\isa{\isacommand{from}}}~\isa{b}] abbreviates ``\mbox{\isa{\isacommand{note}}}~\isa{b}~\mbox{\isa{\isacommand{then}}}''; thus \mbox{\isa{\isacommand{then}}} is |
|
193 equivalent to ``\mbox{\isa{\isacommand{from}}}~\isa{this}''. |
|
194 |
|
195 \item [\mbox{\isa{\isacommand{with}}}~\isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub n{\isachardoublequote}}] |
|
196 abbreviates ``\mbox{\isa{\isacommand{from}}}~\isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub n\ {\isasymAND}\ this{\isachardoublequote}}''; thus the forward chaining is from earlier facts together |
|
197 with the current ones. |
|
198 |
|
199 \item [\mbox{\isa{\isacommand{using}}}~\isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub n{\isachardoublequote}}] augments |
|
200 the facts being currently indicated for use by a subsequent |
|
201 refinement step (such as \indexref{}{command}{apply}\mbox{\isa{\isacommand{apply}}} or \indexref{}{command}{proof}\mbox{\isa{\isacommand{proof}}}). |
|
202 |
|
203 \item [\mbox{\isa{\isacommand{unfolding}}}~\isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub n{\isachardoublequote}}] is |
|
204 structurally similar to \mbox{\isa{\isacommand{using}}}, but unfolds definitional |
|
205 equations \isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}\ b\isactrlsub n{\isachardoublequote}} throughout the goal state |
|
206 and facts. |
|
207 |
|
208 \end{descr} |
|
209 |
|
210 Forward chaining with an empty list of theorems is the same as not |
|
211 chaining at all. Thus ``\mbox{\isa{\isacommand{from}}}~\isa{nothing}'' has no |
|
212 effect apart from entering \isa{{\isachardoublequote}prove{\isacharparenleft}chain{\isacharparenright}{\isachardoublequote}} mode, since |
|
213 \indexref{}{fact}{nothing}\mbox{\isa{nothing}} is bound to the empty list of theorems. |
|
214 |
|
215 Basic proof methods (such as \indexref{}{method}{rule}\mbox{\isa{rule}}) expect multiple |
|
216 facts to be given in their proper order, corresponding to a prefix |
|
217 of the premises of the rule involved. Note that positions may be |
|
218 easily skipped using something like \mbox{\isa{\isacommand{from}}}~\isa{{\isachardoublequote}{\isacharunderscore}\ {\isasymAND}\ a\ {\isasymAND}\ b{\isachardoublequote}}, for example. This involves the trivial rule |
|
219 \isa{{\isachardoublequote}PROP\ {\isasympsi}\ {\isasymLongrightarrow}\ PROP\ {\isasympsi}{\isachardoublequote}}, which is bound in Isabelle/Pure as |
|
220 ``\indexref{}{fact}{\_}\mbox{\isa{{\isacharunderscore}}}'' (underscore). |
|
221 |
|
222 Automated methods (such as \mbox{\isa{simp}} or \mbox{\isa{auto}}) just |
|
223 insert any given facts before their usual operation. Depending on |
|
224 the kind of procedure involved, the order of facts is less |
|
225 significant here.% |
|
226 \end{isamarkuptext}% |
|
227 \isamarkuptrue% |
|
228 % |
|
229 \isamarkupsection{Goal statements \label{sec:goals}% |
|
230 } |
|
231 \isamarkuptrue% |
|
232 % |
|
233 \begin{isamarkuptext}% |
|
234 \begin{matharray}{rcl} |
|
235 \indexdef{}{command}{lemma}\mbox{\isa{\isacommand{lemma}}} & : & \isartrans{local{\dsh}theory}{proof(prove)} \\ |
|
236 \indexdef{}{command}{theorem}\mbox{\isa{\isacommand{theorem}}} & : & \isartrans{local{\dsh}theory}{proof(prove)} \\ |
|
237 \indexdef{}{command}{corollary}\mbox{\isa{\isacommand{corollary}}} & : & \isartrans{local{\dsh}theory}{proof(prove)} \\ |
|
238 \indexdef{}{command}{have}\mbox{\isa{\isacommand{have}}} & : & \isartrans{proof(state) ~|~ proof(chain)}{proof(prove)} \\ |
|
239 \indexdef{}{command}{show}\mbox{\isa{\isacommand{show}}} & : & \isartrans{proof(state) ~|~ proof(chain)}{proof(prove)} \\ |
|
240 \indexdef{}{command}{hence}\mbox{\isa{\isacommand{hence}}} & : & \isartrans{proof(state)}{proof(prove)} \\ |
|
241 \indexdef{}{command}{thus}\mbox{\isa{\isacommand{thus}}} & : & \isartrans{proof(state)}{proof(prove)} \\ |
|
242 \indexdef{}{command}{print\_statement}\mbox{\isa{\isacommand{print{\isacharunderscore}statement}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isarkeep{theory~|~proof} \\ |
|
243 \end{matharray} |
|
244 |
|
245 From a theory context, proof mode is entered by an initial goal |
|
246 command such as \mbox{\isa{\isacommand{lemma}}}, \mbox{\isa{\isacommand{theorem}}}, or |
|
247 \mbox{\isa{\isacommand{corollary}}}. Within a proof, new claims may be |
|
248 introduced locally as well; four variants are available here to |
|
249 indicate whether forward chaining of facts should be performed |
|
250 initially (via \indexref{}{command}{then}\mbox{\isa{\isacommand{then}}}), and whether the final result |
|
251 is meant to solve some pending goal. |
|
252 |
|
253 Goals may consist of multiple statements, resulting in a list of |
|
254 facts eventually. A pending multi-goal is internally represented as |
|
255 a meta-level conjunction (printed as \isa{{\isachardoublequote}{\isacharampersand}{\isacharampersand}{\isachardoublequote}}), which is usually |
|
256 split into the corresponding number of sub-goals prior to an initial |
|
257 method application, via \indexref{}{command}{proof}\mbox{\isa{\isacommand{proof}}} |
|
258 (\secref{sec:proof-steps}) or \indexref{}{command}{apply}\mbox{\isa{\isacommand{apply}}} |
|
259 (\secref{sec:tactic-commands}). The \indexref{}{method}{induct}\mbox{\isa{induct}} method |
|
260 covered in \secref{sec:cases-induct} acts on multiple claims |
|
261 simultaneously. |
|
262 |
|
263 Claims at the theory level may be either in short or long form. A |
|
264 short goal merely consists of several simultaneous propositions |
|
265 (often just one). A long goal includes an explicit context |
|
266 specification for the subsequent conclusion, involving local |
|
267 parameters and assumptions. Here the role of each part of the |
|
268 statement is explicitly marked by separate keywords (see also |
|
269 \secref{sec:locale}); the local assumptions being introduced here |
|
270 are available as \indexref{}{fact}{assms}\mbox{\isa{assms}} in the proof. Moreover, there |
|
271 are two kinds of conclusions: \indexdef{}{element}{shows}\mbox{\isa{\isakeyword{shows}}} states several |
|
272 simultaneous propositions (essentially a big conjunction), while |
|
273 \indexdef{}{element}{obtains}\mbox{\isa{\isakeyword{obtains}}} claims several simultaneous simultaneous |
|
274 contexts of (essentially a big disjunction of eliminated parameters |
|
275 and assumptions, cf.\ \secref{sec:obtain}). |
|
276 |
|
277 \begin{rail} |
|
278 ('lemma' | 'theorem' | 'corollary') target? (goal | longgoal) |
|
279 ; |
|
280 ('have' | 'show' | 'hence' | 'thus') goal |
|
281 ; |
|
282 'print\_statement' modes? thmrefs |
|
283 ; |
|
284 |
|
285 goal: (props + 'and') |
|
286 ; |
|
287 longgoal: thmdecl? (contextelem *) conclusion |
|
288 ; |
|
289 conclusion: 'shows' goal | 'obtains' (parname? case + '|') |
|
290 ; |
|
291 case: (vars + 'and') 'where' (props + 'and') |
|
292 ; |
|
293 \end{rail} |
|
294 |
|
295 \begin{descr} |
|
296 |
|
297 \item [\mbox{\isa{\isacommand{lemma}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}] enters proof mode with |
|
298 \isa{{\isasymphi}} as main goal, eventually resulting in some fact \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymphi}{\isachardoublequote}} to be put back into the target context. An additional |
|
299 \railnonterm{context} specification may build up an initial proof |
|
300 context for the subsequent claim; this includes local definitions |
|
301 and syntax as well, see the definition of \mbox{\isa{contextelem}} in |
|
302 \secref{sec:locale}. |
|
303 |
|
304 \item [\mbox{\isa{\isacommand{theorem}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}} and \mbox{\isa{\isacommand{corollary}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}] are essentially the same as \mbox{\isa{\isacommand{lemma}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}, but the facts are internally marked as |
|
305 being of a different kind. This discrimination acts like a formal |
|
306 comment. |
|
307 |
|
308 \item [\mbox{\isa{\isacommand{have}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}] claims a local goal, |
|
309 eventually resulting in a fact within the current logical context. |
|
310 This operation is completely independent of any pending sub-goals of |
|
311 an enclosing goal statements, so \mbox{\isa{\isacommand{have}}} may be freely |
|
312 used for experimental exploration of potential results within a |
|
313 proof body. |
|
314 |
|
315 \item [\mbox{\isa{\isacommand{show}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}}] is like \mbox{\isa{\isacommand{have}}}~\isa{{\isachardoublequote}a{\isacharcolon}\ {\isasymphi}{\isachardoublequote}} plus a second stage to refine some pending |
|
316 sub-goal for each one of the finished result, after having been |
|
317 exported into the corresponding context (at the head of the |
|
318 sub-proof of this \mbox{\isa{\isacommand{show}}} command). |
|
319 |
|
320 To accommodate interactive debugging, resulting rules are printed |
|
321 before being applied internally. Even more, interactive execution |
|
322 of \mbox{\isa{\isacommand{show}}} predicts potential failure and displays the |
|
323 resulting error as a warning beforehand. Watch out for the |
|
324 following message: |
|
325 |
|
326 %FIXME proper antiquitation |
|
327 \begin{ttbox} |
|
328 Problem! Local statement will fail to solve any pending goal |
|
329 \end{ttbox} |
|
330 |
|
331 \item [\mbox{\isa{\isacommand{hence}}}] abbreviates ``\mbox{\isa{\isacommand{then}}}~\mbox{\isa{\isacommand{have}}}'', i.e.\ claims a local goal to be proven by forward |
|
332 chaining the current facts. Note that \mbox{\isa{\isacommand{hence}}} is also |
|
333 equivalent to ``\mbox{\isa{\isacommand{from}}}~\isa{this}~\mbox{\isa{\isacommand{have}}}''. |
|
334 |
|
335 \item [\mbox{\isa{\isacommand{thus}}}] abbreviates ``\mbox{\isa{\isacommand{then}}}~\mbox{\isa{\isacommand{show}}}''. Note that \mbox{\isa{\isacommand{thus}}} is also equivalent to |
|
336 ``\mbox{\isa{\isacommand{from}}}~\isa{this}~\mbox{\isa{\isacommand{show}}}''. |
|
337 |
|
338 \item [\mbox{\isa{\isacommand{print{\isacharunderscore}statement}}}~\isa{a}] prints facts from the |
|
339 current theory or proof context in long statement form, according to |
|
340 the syntax for \mbox{\isa{\isacommand{lemma}}} given above. |
|
341 |
|
342 \end{descr} |
|
343 |
|
344 Any goal statement causes some term abbreviations (such as |
|
345 \indexref{}{variable}{?thesis}\mbox{\isa{{\isacharquery}thesis}}) to be bound automatically, see also |
|
346 \secref{sec:term-abbrev}. Furthermore, the local context of a |
|
347 (non-atomic) goal is provided via the \indexref{}{case}{rule\_context}\mbox{\isa{rule{\isacharunderscore}context}} case. |
|
348 |
|
349 The optional case names of \indexref{}{element}{obtains}\mbox{\isa{\isakeyword{obtains}}} have a twofold |
|
350 meaning: (1) during the of this claim they refer to the the local |
|
351 context introductions, (2) the resulting rule is annotated |
|
352 accordingly to support symbolic case splits when used with the |
|
353 \indexref{}{method}{cases}\mbox{\isa{cases}} method (cf. \secref{sec:cases-induct}). |
|
354 |
|
355 \medskip |
|
356 |
|
357 \begin{warn} |
|
358 Isabelle/Isar suffers theory-level goal statements to contain |
|
359 \emph{unbound schematic variables}, although this does not conform |
|
360 to the aim of human-readable proof documents! The main problem |
|
361 with schematic goals is that the actual outcome is usually hard to |
|
362 predict, depending on the behavior of the proof methods applied |
|
363 during the course of reasoning. Note that most semi-automated |
|
364 methods heavily depend on several kinds of implicit rule |
|
365 declarations within the current theory context. As this would |
|
366 also result in non-compositional checking of sub-proofs, |
|
367 \emph{local goals} are not allowed to be schematic at all. |
|
368 Nevertheless, schematic goals do have their use in Prolog-style |
|
369 interactive synthesis of proven results, usually by stepwise |
|
370 refinement via emulation of traditional Isabelle tactic scripts |
|
371 (see also \secref{sec:tactic-commands}). In any case, users |
|
372 should know what they are doing. |
|
373 \end{warn}% |
|
374 \end{isamarkuptext}% |
|
375 \isamarkuptrue% |
|
376 % |
|
377 \isamarkupsection{Initial and terminal proof steps \label{sec:proof-steps}% |
|
378 } |
|
379 \isamarkuptrue% |
|
380 % |
|
381 \begin{isamarkuptext}% |
|
382 \begin{matharray}{rcl} |
|
383 \indexdef{}{command}{proof}\mbox{\isa{\isacommand{proof}}} & : & \isartrans{proof(prove)}{proof(state)} \\ |
|
384 \indexdef{}{command}{qed}\mbox{\isa{\isacommand{qed}}} & : & \isartrans{proof(state)}{proof(state) ~|~ theory} \\ |
|
385 \indexdef{}{command}{by}\mbox{\isa{\isacommand{by}}} & : & \isartrans{proof(prove)}{proof(state) ~|~ theory} \\ |
|
386 \indexdef{}{command}{..}\mbox{\isa{\isacommand{{\isachardot}{\isachardot}}}} & : & \isartrans{proof(prove)}{proof(state) ~|~ theory} \\ |
|
387 \indexdef{}{command}{.}\mbox{\isa{\isacommand{{\isachardot}}}} & : & \isartrans{proof(prove)}{proof(state) ~|~ theory} \\ |
|
388 \indexdef{}{command}{sorry}\mbox{\isa{\isacommand{sorry}}} & : & \isartrans{proof(prove)}{proof(state) ~|~ theory} \\ |
|
389 \end{matharray} |
|
390 |
|
391 Arbitrary goal refinement via tactics is considered harmful. |
|
392 Structured proof composition in Isar admits proof methods to be |
|
393 invoked in two places only. |
|
394 |
|
395 \begin{enumerate} |
|
396 |
|
397 \item An \emph{initial} refinement step \indexref{}{command}{proof}\mbox{\isa{\isacommand{proof}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}} reduces a newly stated goal to a number |
|
398 of sub-goals that are to be solved later. Facts are passed to |
|
399 \isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}} for forward chaining, if so indicated by \isa{{\isachardoublequote}proof{\isacharparenleft}chain{\isacharparenright}{\isachardoublequote}} mode. |
|
400 |
|
401 \item A \emph{terminal} conclusion step \indexref{}{command}{qed}\mbox{\isa{\isacommand{qed}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}} is intended to solve remaining goals. No facts are |
|
402 passed to \isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}}. |
|
403 |
|
404 \end{enumerate} |
|
405 |
|
406 The only other (proper) way to affect pending goals in a proof body |
|
407 is by \indexref{}{command}{show}\mbox{\isa{\isacommand{show}}}, which involves an explicit statement of |
|
408 what is to be solved eventually. Thus we avoid the fundamental |
|
409 problem of unstructured tactic scripts that consist of numerous |
|
410 consecutive goal transformations, with invisible effects. |
|
411 |
|
412 \medskip As a general rule of thumb for good proof style, initial |
|
413 proof methods should either solve the goal completely, or constitute |
|
414 some well-understood reduction to new sub-goals. Arbitrary |
|
415 automatic proof tools that are prone leave a large number of badly |
|
416 structured sub-goals are no help in continuing the proof document in |
|
417 an intelligible manner. |
|
418 |
|
419 Unless given explicitly by the user, the default initial method is |
|
420 ``\indexref{}{method}{rule}\mbox{\isa{rule}}'', which applies a single standard elimination |
|
421 or introduction rule according to the topmost symbol involved. |
|
422 There is no separate default terminal method. Any remaining goals |
|
423 are always solved by assumption in the very last step. |
|
424 |
|
425 \begin{rail} |
|
426 'proof' method? |
|
427 ; |
|
428 'qed' method? |
|
429 ; |
|
430 'by' method method? |
|
431 ; |
|
432 ('.' | '..' | 'sorry') |
|
433 ; |
|
434 \end{rail} |
|
435 |
|
436 \begin{descr} |
|
437 |
|
438 \item [\mbox{\isa{\isacommand{proof}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}}] refines the goal by |
|
439 proof method \isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}}; facts for forward chaining are |
|
440 passed if so indicated by \isa{{\isachardoublequote}proof{\isacharparenleft}chain{\isacharparenright}{\isachardoublequote}} mode. |
|
441 |
|
442 \item [\mbox{\isa{\isacommand{qed}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}}] refines any remaining |
|
443 goals by proof method \isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}} and concludes the |
|
444 sub-proof by assumption. If the goal had been \isa{{\isachardoublequote}show{\isachardoublequote}} (or |
|
445 \isa{{\isachardoublequote}thus{\isachardoublequote}}), some pending sub-goal is solved as well by the rule |
|
446 resulting from the result \emph{exported} into the enclosing goal |
|
447 context. Thus \isa{{\isachardoublequote}qed{\isachardoublequote}} may fail for two reasons: either \isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}} fails, or the resulting rule does not fit to any |
|
448 pending goal\footnote{This includes any additional ``strong'' |
|
449 assumptions as introduced by \mbox{\isa{\isacommand{assume}}}.} of the enclosing |
|
450 context. Debugging such a situation might involve temporarily |
|
451 changing \mbox{\isa{\isacommand{show}}} into \mbox{\isa{\isacommand{have}}}, or weakening the |
|
452 local context by replacing occurrences of \mbox{\isa{\isacommand{assume}}} by |
|
453 \mbox{\isa{\isacommand{presume}}}. |
|
454 |
|
455 \item [\mbox{\isa{\isacommand{by}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}\ m\isactrlsub {\isadigit{2}}{\isachardoublequote}}] is a |
|
456 \emph{terminal proof}\index{proof!terminal}; it abbreviates |
|
457 \mbox{\isa{\isacommand{proof}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}}~\isa{{\isachardoublequote}qed{\isachardoublequote}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{2}}{\isachardoublequote}}, but with backtracking across both methods. Debugging |
|
458 an unsuccessful \mbox{\isa{\isacommand{by}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}\ m\isactrlsub {\isadigit{2}}{\isachardoublequote}} |
|
459 command can be done by expanding its definition; in many cases |
|
460 \mbox{\isa{\isacommand{proof}}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}} (or even \isa{{\isachardoublequote}apply{\isachardoublequote}}~\isa{{\isachardoublequote}m\isactrlsub {\isadigit{1}}{\isachardoublequote}}) is already sufficient to see the |
|
461 problem. |
|
462 |
|
463 \item [``\mbox{\isa{\isacommand{{\isachardot}{\isachardot}}}}''] is a \emph{default |
|
464 proof}\index{proof!default}; it abbreviates \mbox{\isa{\isacommand{by}}}~\isa{{\isachardoublequote}rule{\isachardoublequote}}. |
|
465 |
|
466 \item [``\mbox{\isa{\isacommand{{\isachardot}}}}''] is a \emph{trivial |
|
467 proof}\index{proof!trivial}; it abbreviates \mbox{\isa{\isacommand{by}}}~\isa{{\isachardoublequote}this{\isachardoublequote}}. |
|
468 |
|
469 \item [\mbox{\isa{\isacommand{sorry}}}] is a \emph{fake proof}\index{proof!fake} |
|
470 pretending to solve the pending claim without further ado. This |
|
471 only works in interactive development, or if the \verb|quick_and_dirty| flag is enabled (in ML). Facts emerging from fake |
|
472 proofs are not the real thing. Internally, each theorem container |
|
473 is tainted by an oracle invocation, which is indicated as ``\isa{{\isachardoublequote}{\isacharbrackleft}{\isacharbang}{\isacharbrackright}{\isachardoublequote}}'' in the printed result. |
|
474 |
|
475 The most important application of \mbox{\isa{\isacommand{sorry}}} is to support |
|
476 experimentation and top-down proof development. |
|
477 |
|
478 \end{descr}% |
|
479 \end{isamarkuptext}% |
|
480 \isamarkuptrue% |
|
481 % |
|
482 \isamarkupsection{Fundamental methods and attributes \label{sec:pure-meth-att}% |
|
483 } |
|
484 \isamarkuptrue% |
|
485 % |
|
486 \begin{isamarkuptext}% |
|
487 The following proof methods and attributes refer to basic logical |
|
488 operations of Isar. Further methods and attributes are provided by |
|
489 several generic and object-logic specific tools and packages (see |
|
490 \chref{ch:gen-tools} and \chref{ch:hol}). |
|
491 |
|
492 \begin{matharray}{rcl} |
|
493 \indexdef{}{method}{-}\mbox{\isa{{\isacharminus}}} & : & \isarmeth \\ |
|
494 \indexdef{}{method}{fact}\mbox{\isa{fact}} & : & \isarmeth \\ |
|
495 \indexdef{}{method}{assumption}\mbox{\isa{assumption}} & : & \isarmeth \\ |
|
496 \indexdef{}{method}{this}\mbox{\isa{this}} & : & \isarmeth \\ |
|
497 \indexdef{}{method}{rule}\mbox{\isa{rule}} & : & \isarmeth \\ |
|
498 \indexdef{}{method}{iprover}\mbox{\isa{iprover}} & : & \isarmeth \\[0.5ex] |
|
499 \indexdef{}{attribute}{intro}\mbox{\isa{intro}} & : & \isaratt \\ |
|
500 \indexdef{}{attribute}{elim}\mbox{\isa{elim}} & : & \isaratt \\ |
|
501 \indexdef{}{attribute}{dest}\mbox{\isa{dest}} & : & \isaratt \\ |
|
502 \indexdef{}{attribute}{rule}\mbox{\isa{rule}} & : & \isaratt \\[0.5ex] |
|
503 \indexdef{}{attribute}{OF}\mbox{\isa{OF}} & : & \isaratt \\ |
|
504 \indexdef{}{attribute}{of}\mbox{\isa{of}} & : & \isaratt \\ |
|
505 \indexdef{}{attribute}{where}\mbox{\isa{where}} & : & \isaratt \\ |
|
506 \end{matharray} |
|
507 |
|
508 \begin{rail} |
|
509 'fact' thmrefs? |
|
510 ; |
|
511 'rule' thmrefs? |
|
512 ; |
|
513 'iprover' ('!' ?) (rulemod *) |
|
514 ; |
|
515 rulemod: ('intro' | 'elim' | 'dest') ((('!' | () | '?') nat?) | 'del') ':' thmrefs |
|
516 ; |
|
517 ('intro' | 'elim' | 'dest') ('!' | () | '?') nat? |
|
518 ; |
|
519 'rule' 'del' |
|
520 ; |
|
521 'OF' thmrefs |
|
522 ; |
|
523 'of' insts ('concl' ':' insts)? |
|
524 ; |
|
525 'where' ((name | var | typefree | typevar) '=' (type | term) * 'and') |
|
526 ; |
|
527 \end{rail} |
|
528 |
|
529 \begin{descr} |
|
530 |
|
531 \item [``\mbox{\isa{{\isacharminus}}}'' (minus)] does nothing but insert the |
|
532 forward chaining facts as premises into the goal. Note that command |
|
533 \indexref{}{command}{proof}\mbox{\isa{\isacommand{proof}}} without any method actually performs a single |
|
534 reduction step using the \indexref{}{method}{rule}\mbox{\isa{rule}} method; thus a plain |
|
535 \emph{do-nothing} proof step would be ``\mbox{\isa{\isacommand{proof}}}~\isa{{\isachardoublequote}{\isacharminus}{\isachardoublequote}}'' rather than \mbox{\isa{\isacommand{proof}}} alone. |
|
536 |
|
537 \item [\mbox{\isa{fact}}~\isa{{\isachardoublequote}a\isactrlsub {\isadigit{1}}\ {\isasymdots}\ a\isactrlsub n{\isachardoublequote}}] composes |
|
538 some fact from \isa{{\isachardoublequote}a\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ a\isactrlsub n{\isachardoublequote}} (or implicitly from |
|
539 the current proof context) modulo unification of schematic type and |
|
540 term variables. The rule structure is not taken into account, i.e.\ |
|
541 meta-level implication is considered atomic. This is the same |
|
542 principle underlying literal facts (cf.\ \secref{sec:syn-att}): |
|
543 ``\mbox{\isa{\isacommand{have}}}~\isa{{\isachardoublequote}{\isasymphi}{\isachardoublequote}}~\mbox{\isa{\isacommand{by}}}~\isa{fact}'' is |
|
544 equivalent to ``\mbox{\isa{\isacommand{note}}}~\verb|`|\isa{{\isasymphi}}\verb|`|'' provided that \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymphi}{\isachardoublequote}} is an instance of some known |
|
545 \isa{{\isachardoublequote}{\isasymturnstile}\ {\isasymphi}{\isachardoublequote}} in the proof context. |
|
546 |
|
547 \item [\mbox{\isa{assumption}}] solves some goal by a single assumption |
|
548 step. All given facts are guaranteed to participate in the |
|
549 refinement; this means there may be only 0 or 1 in the first place. |
|
550 Recall that \mbox{\isa{\isacommand{qed}}} (\secref{sec:proof-steps}) already |
|
551 concludes any remaining sub-goals by assumption, so structured |
|
552 proofs usually need not quote the \mbox{\isa{assumption}} method at |
|
553 all. |
|
554 |
|
555 \item [\mbox{\isa{this}}] applies all of the current facts directly as |
|
556 rules. Recall that ``\mbox{\isa{\isacommand{{\isachardot}}}}'' (dot) abbreviates ``\mbox{\isa{\isacommand{by}}}~\isa{this}''. |
|
557 |
|
558 \item [\mbox{\isa{rule}}~\isa{{\isachardoublequote}a\isactrlsub {\isadigit{1}}\ {\isasymdots}\ a\isactrlsub n{\isachardoublequote}}] applies some |
|
559 rule given as argument in backward manner; facts are used to reduce |
|
560 the rule before applying it to the goal. Thus \mbox{\isa{rule}} |
|
561 without facts is plain introduction, while with facts it becomes |
|
562 elimination. |
|
563 |
|
564 When no arguments are given, the \mbox{\isa{rule}} method tries to pick |
|
565 appropriate rules automatically, as declared in the current context |
|
566 using the \mbox{\isa{intro}}, \mbox{\isa{elim}}, \mbox{\isa{dest}} |
|
567 attributes (see below). This is the default behavior of \mbox{\isa{\isacommand{proof}}} and ``\mbox{\isa{\isacommand{{\isachardot}{\isachardot}}}}'' (double-dot) steps (see |
|
568 \secref{sec:proof-steps}). |
|
569 |
|
570 \item [\mbox{\isa{iprover}}] performs intuitionistic proof search, |
|
571 depending on specifically declared rules from the context, or given |
|
572 as explicit arguments. Chained facts are inserted into the goal |
|
573 before commencing proof search; ``\mbox{\isa{iprover}}\isa{{\isachardoublequote}{\isacharbang}{\isachardoublequote}}'' |
|
574 means to include the current \mbox{\isa{prems}} as well. |
|
575 |
|
576 Rules need to be classified as \mbox{\isa{intro}}, \mbox{\isa{elim}}, or \mbox{\isa{dest}}; here the ``\isa{{\isachardoublequote}{\isacharbang}{\isachardoublequote}}'' indicator |
|
577 refers to ``safe'' rules, which may be applied aggressively (without |
|
578 considering back-tracking later). Rules declared with ``\isa{{\isachardoublequote}{\isacharquery}{\isachardoublequote}}'' are ignored in proof search (the single-step \mbox{\isa{rule}} |
|
579 method still observes these). An explicit weight annotation may be |
|
580 given as well; otherwise the number of rule premises will be taken |
|
581 into account here. |
|
582 |
|
583 \item [\mbox{\isa{intro}}, \mbox{\isa{elim}}, and \mbox{\isa{dest}}] |
|
584 declare introduction, elimination, and destruct rules, to be used |
|
585 with the \mbox{\isa{rule}} and \mbox{\isa{iprover}} methods. Note that |
|
586 the latter will ignore rules declared with ``\isa{{\isachardoublequote}{\isacharquery}{\isachardoublequote}}'', while |
|
587 ``\isa{{\isachardoublequote}{\isacharbang}{\isachardoublequote}}'' are used most aggressively. |
|
588 |
|
589 The classical reasoner (see \secref{sec:classical}) introduces its |
|
590 own variants of these attributes; use qualified names to access the |
|
591 present versions of Isabelle/Pure, i.e.\ \mbox{\isa{Pure{\isachardot}intro}}. |
|
592 |
|
593 \item [\mbox{\isa{rule}}~\isa{del}] undeclares introduction, |
|
594 elimination, or destruct rules. |
|
595 |
|
596 \item [\mbox{\isa{OF}}~\isa{{\isachardoublequote}a\isactrlsub {\isadigit{1}}\ {\isasymdots}\ a\isactrlsub n{\isachardoublequote}}] applies some |
|
597 theorem to all of the given rules \isa{{\isachardoublequote}a\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ a\isactrlsub n{\isachardoublequote}} |
|
598 (in parallel). This corresponds to the \verb|"op MRS"| operation in |
|
599 ML, but note the reversed order. Positions may be effectively |
|
600 skipped by including ``\isa{{\isacharunderscore}}'' (underscore) as argument. |
|
601 |
|
602 \item [\mbox{\isa{of}}~\isa{{\isachardoublequote}t\isactrlsub {\isadigit{1}}\ {\isasymdots}\ t\isactrlsub n{\isachardoublequote}}] performs |
|
603 positional instantiation of term variables. The terms \isa{{\isachardoublequote}t\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ t\isactrlsub n{\isachardoublequote}} are substituted for any schematic |
|
604 variables occurring in a theorem from left to right; ``\isa{{\isacharunderscore}}'' (underscore) indicates to skip a position. Arguments following |
|
605 a ``\mbox{\isa{\isakeyword{concl}}}\isa{{\isachardoublequote}{\isacharcolon}{\isachardoublequote}}'' specification refer to positions |
|
606 of the conclusion of a rule. |
|
607 |
|
608 \item [\mbox{\isa{where}}~\isa{{\isachardoublequote}x\isactrlsub {\isadigit{1}}\ {\isacharequal}\ t\isactrlsub {\isadigit{1}}\ {\isasymAND}\ {\isasymdots}\ x\isactrlsub n\ {\isacharequal}\ t\isactrlsub n{\isachardoublequote}}] performs named instantiation of schematic |
|
609 type and term variables occurring in a theorem. Schematic variables |
|
610 have to be specified on the left-hand side (e.g.\ \isa{{\isachardoublequote}{\isacharquery}x{\isadigit{1}}{\isachardot}{\isadigit{3}}{\isachardoublequote}}). |
|
611 The question mark may be omitted if the variable name is a plain |
|
612 identifier without index. As type instantiations are inferred from |
|
613 term instantiations, explicit type instantiations are seldom |
|
614 necessary. |
|
615 |
|
616 \end{descr}% |
|
617 \end{isamarkuptext}% |
|
618 \isamarkuptrue% |
|
619 % |
|
620 \isamarkupsection{Term abbreviations \label{sec:term-abbrev}% |
|
621 } |
|
622 \isamarkuptrue% |
|
623 % |
|
624 \begin{isamarkuptext}% |
|
625 \begin{matharray}{rcl} |
|
626 \indexdef{}{command}{let}\mbox{\isa{\isacommand{let}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
627 \indexdef{}{keyword}{is}\mbox{\isa{\isakeyword{is}}} & : & syntax \\ |
|
628 \end{matharray} |
|
629 |
|
630 Abbreviations may be either bound by explicit \mbox{\isa{\isacommand{let}}}~\isa{{\isachardoublequote}p\ {\isasymequiv}\ t{\isachardoublequote}} statements, or by annotating assumptions or |
|
631 goal statements with a list of patterns ``\isa{{\isachardoublequote}{\isacharparenleft}{\isasymIS}\ p\isactrlsub {\isadigit{1}}\ {\isasymdots}\ p\isactrlsub n{\isacharparenright}{\isachardoublequote}}''. In both cases, higher-order matching is invoked to |
|
632 bind extra-logical term variables, which may be either named |
|
633 schematic variables of the form \isa{{\isacharquery}x}, or nameless dummies |
|
634 ``\mbox{\isa{{\isacharunderscore}}}'' (underscore). Note that in the \mbox{\isa{\isacommand{let}}} |
|
635 form the patterns occur on the left-hand side, while the \mbox{\isa{\isakeyword{is}}} patterns are in postfix position. |
|
636 |
|
637 Polymorphism of term bindings is handled in Hindley-Milner style, |
|
638 similar to ML. Type variables referring to local assumptions or |
|
639 open goal statements are \emph{fixed}, while those of finished |
|
640 results or bound by \mbox{\isa{\isacommand{let}}} may occur in \emph{arbitrary} |
|
641 instances later. Even though actual polymorphism should be rarely |
|
642 used in practice, this mechanism is essential to achieve proper |
|
643 incremental type-inference, as the user proceeds to build up the |
|
644 Isar proof text from left to right. |
|
645 |
|
646 \medskip Term abbreviations are quite different from local |
|
647 definitions as introduced via \mbox{\isa{\isacommand{def}}} (see |
|
648 \secref{sec:proof-context}). The latter are visible within the |
|
649 logic as actual equations, while abbreviations disappear during the |
|
650 input process just after type checking. Also note that \mbox{\isa{\isacommand{def}}} does not support polymorphism. |
|
651 |
|
652 \begin{rail} |
|
653 'let' ((term + 'and') '=' term + 'and') |
|
654 ; |
|
655 \end{rail} |
|
656 |
|
657 The syntax of \mbox{\isa{\isakeyword{is}}} patterns follows \railnonterm{termpat} |
|
658 or \railnonterm{proppat} (see \secref{sec:term-decls}). |
|
659 |
|
660 \begin{descr} |
|
661 |
|
662 \item [\mbox{\isa{\isacommand{let}}}~\isa{{\isachardoublequote}p\isactrlsub {\isadigit{1}}\ {\isacharequal}\ t\isactrlsub {\isadigit{1}}\ {\isasymAND}\ {\isasymdots}\ p\isactrlsub n\ {\isacharequal}\ t\isactrlsub n{\isachardoublequote}}] binds any text variables in patterns \isa{{\isachardoublequote}p\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ p\isactrlsub n{\isachardoublequote}} by simultaneous higher-order matching |
|
663 against terms \isa{{\isachardoublequote}t\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ t\isactrlsub n{\isachardoublequote}}. |
|
664 |
|
665 \item [\isa{{\isachardoublequote}{\isacharparenleft}{\isasymIS}\ p\isactrlsub {\isadigit{1}}\ {\isasymdots}\ p\isactrlsub n{\isacharparenright}{\isachardoublequote}}] resembles \mbox{\isa{\isacommand{let}}}, but matches \isa{{\isachardoublequote}p\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ p\isactrlsub n{\isachardoublequote}} against the |
|
666 preceding statement. Also note that \mbox{\isa{\isakeyword{is}}} is not a |
|
667 separate command, but part of others (such as \mbox{\isa{\isacommand{assume}}}, |
|
668 \mbox{\isa{\isacommand{have}}} etc.). |
|
669 |
|
670 \end{descr} |
|
671 |
|
672 Some \emph{implicit} term abbreviations\index{term abbreviations} |
|
673 for goals and facts are available as well. For any open goal, |
|
674 \indexref{}{variable}{thesis}\mbox{\isa{thesis}} refers to its object-level statement, |
|
675 abstracted over any meta-level parameters (if present). Likewise, |
|
676 \indexref{}{variable}{this}\mbox{\isa{this}} is bound for fact statements resulting from |
|
677 assumptions or finished goals. In case \mbox{\isa{this}} refers to |
|
678 an object-logic statement that is an application \isa{{\isachardoublequote}f\ t{\isachardoublequote}}, then |
|
679 \isa{t} is bound to the special text variable ``\mbox{\isa{{\isasymdots}}}'' |
|
680 (three dots). The canonical application of this convenience are |
|
681 calculational proofs (see \secref{sec:calculation}).% |
|
682 \end{isamarkuptext}% |
|
683 \isamarkuptrue% |
|
684 % |
|
685 \isamarkupsection{Block structure% |
|
686 } |
|
687 \isamarkuptrue% |
|
688 % |
|
689 \begin{isamarkuptext}% |
|
690 \begin{matharray}{rcl} |
|
691 \indexdef{}{command}{next}\mbox{\isa{\isacommand{next}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
692 \indexdef{}{command}{\{}\mbox{\isa{\isacommand{{\isacharbraceleft}}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
693 \indexdef{}{command}{\}}\mbox{\isa{\isacommand{{\isacharbraceright}}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
694 \end{matharray} |
|
695 |
|
696 While Isar is inherently block-structured, opening and closing |
|
697 blocks is mostly handled rather casually, with little explicit |
|
698 user-intervention. Any local goal statement automatically opens |
|
699 \emph{two} internal blocks, which are closed again when concluding |
|
700 the sub-proof (by \mbox{\isa{\isacommand{qed}}} etc.). Sections of different |
|
701 context within a sub-proof may be switched via \mbox{\isa{\isacommand{next}}}, |
|
702 which is just a single block-close followed by block-open again. |
|
703 The effect of \mbox{\isa{\isacommand{next}}} is to reset the local proof context; |
|
704 there is no goal focus involved here! |
|
705 |
|
706 For slightly more advanced applications, there are explicit block |
|
707 parentheses as well. These typically achieve a stronger forward |
|
708 style of reasoning. |
|
709 |
|
710 \begin{descr} |
|
711 |
|
712 \item [\mbox{\isa{\isacommand{next}}}] switches to a fresh block within a |
|
713 sub-proof, resetting the local context to the initial one. |
|
714 |
|
715 \item [\mbox{\isa{\isacommand{{\isacharbraceleft}}}} and \mbox{\isa{\isacommand{{\isacharbraceright}}}}] explicitly open and close |
|
716 blocks. Any current facts pass through ``\mbox{\isa{\isacommand{{\isacharbraceleft}}}}'' |
|
717 unchanged, while ``\mbox{\isa{\isacommand{{\isacharbraceright}}}}'' causes any result to be |
|
718 \emph{exported} into the enclosing context. Thus fixed variables |
|
719 are generalized, assumptions discharged, and local definitions |
|
720 unfolded (cf.\ \secref{sec:proof-context}). There is no difference |
|
721 of \mbox{\isa{\isacommand{assume}}} and \mbox{\isa{\isacommand{presume}}} in this mode of |
|
722 forward reasoning --- in contrast to plain backward reasoning with |
|
723 the result exported at \mbox{\isa{\isacommand{show}}} time. |
|
724 |
|
725 \end{descr}% |
|
726 \end{isamarkuptext}% |
|
727 \isamarkuptrue% |
|
728 % |
|
729 \isamarkupsection{Emulating tactic scripts \label{sec:tactic-commands}% |
|
730 } |
|
731 \isamarkuptrue% |
|
732 % |
|
733 \begin{isamarkuptext}% |
|
734 The Isar provides separate commands to accommodate tactic-style |
|
735 proof scripts within the same system. While being outside the |
|
736 orthodox Isar proof language, these might come in handy for |
|
737 interactive exploration and debugging, or even actual tactical proof |
|
738 within new-style theories (to benefit from document preparation, for |
|
739 example). See also \secref{sec:tactics} for actual tactics, that |
|
740 have been encapsulated as proof methods. Proper proof methods may |
|
741 be used in scripts, too. |
|
742 |
|
743 \begin{matharray}{rcl} |
|
744 \indexdef{}{command}{apply}\mbox{\isa{\isacommand{apply}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof(prove)}{proof(prove)} \\ |
|
745 \indexdef{}{command}{apply\_end}\mbox{\isa{\isacommand{apply{\isacharunderscore}end}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
746 \indexdef{}{command}{done}\mbox{\isa{\isacommand{done}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof(prove)}{proof(state)} \\ |
|
747 \indexdef{}{command}{defer}\mbox{\isa{\isacommand{defer}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof}{proof} \\ |
|
748 \indexdef{}{command}{prefer}\mbox{\isa{\isacommand{prefer}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof}{proof} \\ |
|
749 \indexdef{}{command}{back}\mbox{\isa{\isacommand{back}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof}{proof} \\ |
|
750 \end{matharray} |
|
751 |
|
752 \begin{rail} |
|
753 ( 'apply' | 'apply\_end' ) method |
|
754 ; |
|
755 'defer' nat? |
|
756 ; |
|
757 'prefer' nat |
|
758 ; |
|
759 \end{rail} |
|
760 |
|
761 \begin{descr} |
|
762 |
|
763 \item [\mbox{\isa{\isacommand{apply}}}~\isa{m}] applies proof method \isa{m} |
|
764 in initial position, but unlike \mbox{\isa{\isacommand{proof}}} it retains |
|
765 ``\isa{{\isachardoublequote}proof{\isacharparenleft}prove{\isacharparenright}{\isachardoublequote}}'' mode. Thus consecutive method |
|
766 applications may be given just as in tactic scripts. |
|
767 |
|
768 Facts are passed to \isa{m} as indicated by the goal's |
|
769 forward-chain mode, and are \emph{consumed} afterwards. Thus any |
|
770 further \mbox{\isa{\isacommand{apply}}} command would always work in a purely |
|
771 backward manner. |
|
772 |
|
773 \item [\mbox{\isa{\isacommand{apply{\isacharunderscore}end}}}~\isa{{\isachardoublequote}m{\isachardoublequote}}] applies proof method |
|
774 \isa{m} as if in terminal position. Basically, this simulates a |
|
775 multi-step tactic script for \mbox{\isa{\isacommand{qed}}}, but may be given |
|
776 anywhere within the proof body. |
|
777 |
|
778 No facts are passed to \mbox{\isa{m}} here. Furthermore, the static |
|
779 context is that of the enclosing goal (as for actual \mbox{\isa{\isacommand{qed}}}). Thus the proof method may not refer to any assumptions |
|
780 introduced in the current body, for example. |
|
781 |
|
782 \item [\mbox{\isa{\isacommand{done}}}] completes a proof script, provided that |
|
783 the current goal state is solved completely. Note that actual |
|
784 structured proof commands (e.g.\ ``\mbox{\isa{\isacommand{{\isachardot}}}}'' or \mbox{\isa{\isacommand{sorry}}}) may be used to conclude proof scripts as well. |
|
785 |
|
786 \item [\mbox{\isa{\isacommand{defer}}}~\isa{n} and \mbox{\isa{\isacommand{prefer}}}~\isa{n}] shuffle the list of pending goals: \mbox{\isa{\isacommand{defer}}} puts off |
|
787 sub-goal \isa{n} to the end of the list (\isa{{\isachardoublequote}n\ {\isacharequal}\ {\isadigit{1}}{\isachardoublequote}} by |
|
788 default), while \mbox{\isa{\isacommand{prefer}}} brings sub-goal \isa{n} to the |
|
789 front. |
|
790 |
|
791 \item [\mbox{\isa{\isacommand{back}}}] does back-tracking over the result |
|
792 sequence of the latest proof command. Basically, any proof command |
|
793 may return multiple results. |
|
794 |
|
795 \end{descr} |
|
796 |
|
797 Any proper Isar proof method may be used with tactic script commands |
|
798 such as \mbox{\isa{\isacommand{apply}}}. A few additional emulations of actual |
|
799 tactics are provided as well; these would be never used in actual |
|
800 structured proofs, of course.% |
|
801 \end{isamarkuptext}% |
|
802 \isamarkuptrue% |
|
803 % |
|
804 \isamarkupsection{Omitting proofs% |
|
805 } |
|
806 \isamarkuptrue% |
|
807 % |
|
808 \begin{isamarkuptext}% |
|
809 \begin{matharray}{rcl} |
|
810 \indexdef{}{command}{oops}\mbox{\isa{\isacommand{oops}}} & : & \isartrans{proof}{theory} \\ |
|
811 \end{matharray} |
|
812 |
|
813 The \mbox{\isa{\isacommand{oops}}} command discontinues the current proof |
|
814 attempt, while considering the partial proof text as properly |
|
815 processed. This is conceptually quite different from ``faking'' |
|
816 actual proofs via \indexref{}{command}{sorry}\mbox{\isa{\isacommand{sorry}}} (see |
|
817 \secref{sec:proof-steps}): \mbox{\isa{\isacommand{oops}}} does not observe the |
|
818 proof structure at all, but goes back right to the theory level. |
|
819 Furthermore, \mbox{\isa{\isacommand{oops}}} does not produce any result theorem |
|
820 --- there is no intended claim to be able to complete the proof |
|
821 anyhow. |
|
822 |
|
823 A typical application of \mbox{\isa{\isacommand{oops}}} is to explain Isar proofs |
|
824 \emph{within} the system itself, in conjunction with the document |
|
825 preparation tools of Isabelle described in \cite{isabelle-sys}. |
|
826 Thus partial or even wrong proof attempts can be discussed in a |
|
827 logically sound manner. Note that the Isabelle {\LaTeX} macros can |
|
828 be easily adapted to print something like ``\isa{{\isachardoublequote}{\isasymdots}{\isachardoublequote}}'' instead of |
|
829 the keyword ``\mbox{\isa{\isacommand{oops}}}''. |
|
830 |
|
831 \medskip The \mbox{\isa{\isacommand{oops}}} command is undo-able, unlike |
|
832 \indexref{}{command}{kill}\mbox{\isa{\isacommand{kill}}} (see \secref{sec:history}). The effect is to |
|
833 get back to the theory just before the opening of the proof.% |
|
834 \end{isamarkuptext}% |
|
835 \isamarkuptrue% |
|
836 % |
|
837 \isamarkupsection{Generalized elimination \label{sec:obtain}% |
|
838 } |
|
839 \isamarkuptrue% |
|
840 % |
|
841 \begin{isamarkuptext}% |
|
842 \begin{matharray}{rcl} |
|
843 \indexdef{}{command}{obtain}\mbox{\isa{\isacommand{obtain}}} & : & \isartrans{proof(state)}{proof(prove)} \\ |
|
844 \indexdef{}{command}{guess}\mbox{\isa{\isacommand{guess}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isartrans{proof(state)}{proof(prove)} \\ |
|
845 \end{matharray} |
|
846 |
|
847 Generalized elimination means that additional elements with certain |
|
848 properties may be introduced in the current context, by virtue of a |
|
849 locally proven ``soundness statement''. Technically speaking, the |
|
850 \mbox{\isa{\isacommand{obtain}}} language element is like a declaration of |
|
851 \mbox{\isa{\isacommand{fix}}} and \mbox{\isa{\isacommand{assume}}} (see also see |
|
852 \secref{sec:proof-context}), together with a soundness proof of its |
|
853 additional claim. According to the nature of existential reasoning, |
|
854 assumptions get eliminated from any result exported from the context |
|
855 later, provided that the corresponding parameters do \emph{not} |
|
856 occur in the conclusion. |
|
857 |
|
858 \begin{rail} |
|
859 'obtain' parname? (vars + 'and') 'where' (props + 'and') |
|
860 ; |
|
861 'guess' (vars + 'and') |
|
862 ; |
|
863 \end{rail} |
|
864 |
|
865 The derived Isar command \mbox{\isa{\isacommand{obtain}}} is defined as follows |
|
866 (where \isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ b\isactrlsub k{\isachardoublequote}} shall refer to (optional) |
|
867 facts indicated for forward chaining). |
|
868 \begin{matharray}{l} |
|
869 \isa{{\isachardoublequote}{\isasymlangle}using\ b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub k{\isasymrangle}{\isachardoublequote}}~~\mbox{\isa{\isacommand{obtain}}}~\isa{{\isachardoublequote}x\isactrlsub {\isadigit{1}}\ {\isasymdots}\ x\isactrlsub m\ {\isasymWHERE}\ a{\isacharcolon}\ {\isasymphi}\isactrlsub {\isadigit{1}}\ {\isasymdots}\ {\isasymphi}\isactrlsub n\ \ {\isasymlangle}proof{\isasymrangle}\ {\isasymequiv}{\isachardoublequote}} \\[1ex] |
|
870 \quad \mbox{\isa{\isacommand{have}}}~\isa{{\isachardoublequote}{\isasymAnd}thesis{\isachardot}\ {\isacharparenleft}{\isasymAnd}x\isactrlsub {\isadigit{1}}\ {\isasymdots}\ x\isactrlsub m{\isachardot}\ {\isasymphi}\isactrlsub {\isadigit{1}}\ {\isasymLongrightarrow}\ {\isasymdots}\ {\isasymphi}\isactrlsub n\ {\isasymLongrightarrow}\ thesis{\isacharparenright}\ {\isasymLongrightarrow}\ thesis{\isachardoublequote}} \\ |
|
871 \quad \mbox{\isa{\isacommand{proof}}}~\isa{succeed} \\ |
|
872 \qquad \mbox{\isa{\isacommand{fix}}}~\isa{thesis} \\ |
|
873 \qquad \mbox{\isa{\isacommand{assume}}}~\isa{{\isachardoublequote}that\ {\isacharbrackleft}Pure{\isachardot}intro{\isacharquery}{\isacharbrackright}{\isacharcolon}\ {\isasymAnd}x\isactrlsub {\isadigit{1}}\ {\isasymdots}\ x\isactrlsub m{\isachardot}\ {\isasymphi}\isactrlsub {\isadigit{1}}\ {\isasymLongrightarrow}\ {\isasymdots}\ {\isasymphi}\isactrlsub n\ {\isasymLongrightarrow}\ thesis{\isachardoublequote}} \\ |
|
874 \qquad \mbox{\isa{\isacommand{then}}}~\mbox{\isa{\isacommand{show}}}~\isa{thesis} \\ |
|
875 \quad\qquad \mbox{\isa{\isacommand{apply}}}~\isa{{\isacharminus}} \\ |
|
876 \quad\qquad \mbox{\isa{\isacommand{using}}}~\isa{{\isachardoublequote}b\isactrlsub {\isadigit{1}}\ {\isasymdots}\ b\isactrlsub k\ \ {\isasymlangle}proof{\isasymrangle}{\isachardoublequote}} \\ |
|
877 \quad \mbox{\isa{\isacommand{qed}}} \\ |
|
878 \quad \mbox{\isa{\isacommand{fix}}}~\isa{{\isachardoublequote}x\isactrlsub {\isadigit{1}}\ {\isasymdots}\ x\isactrlsub m{\isachardoublequote}}~\mbox{\isa{\isacommand{assume}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}\ a{\isacharcolon}\ {\isasymphi}\isactrlsub {\isadigit{1}}\ {\isasymdots}\ {\isasymphi}\isactrlsub n{\isachardoublequote}} \\ |
|
879 \end{matharray} |
|
880 |
|
881 Typically, the soundness proof is relatively straight-forward, often |
|
882 just by canonical automated tools such as ``\mbox{\isa{\isacommand{by}}}~\isa{simp}'' or ``\mbox{\isa{\isacommand{by}}}~\isa{blast}''. Accordingly, the |
|
883 ``\isa{that}'' reduction above is declared as simplification and |
|
884 introduction rule. |
|
885 |
|
886 In a sense, \mbox{\isa{\isacommand{obtain}}} represents at the level of Isar |
|
887 proofs what would be meta-logical existential quantifiers and |
|
888 conjunctions. This concept has a broad range of useful |
|
889 applications, ranging from plain elimination (or introduction) of |
|
890 object-level existential and conjunctions, to elimination over |
|
891 results of symbolic evaluation of recursive definitions, for |
|
892 example. Also note that \mbox{\isa{\isacommand{obtain}}} without parameters acts |
|
893 much like \mbox{\isa{\isacommand{have}}}, where the result is treated as a |
|
894 genuine assumption. |
|
895 |
|
896 An alternative name to be used instead of ``\isa{that}'' above may |
|
897 be given in parentheses. |
|
898 |
|
899 \medskip The improper variant \mbox{\isa{\isacommand{guess}}} is similar to |
|
900 \mbox{\isa{\isacommand{obtain}}}, but derives the obtained statement from the |
|
901 course of reasoning! The proof starts with a fixed goal \isa{thesis}. The subsequent proof may refine this to anything of the |
|
902 form like \isa{{\isachardoublequote}{\isasymAnd}x\isactrlsub {\isadigit{1}}\ {\isasymdots}\ x\isactrlsub m{\isachardot}\ {\isasymphi}\isactrlsub {\isadigit{1}}\ {\isasymLongrightarrow}\ {\isasymdots}\ {\isasymphi}\isactrlsub n\ {\isasymLongrightarrow}\ thesis{\isachardoublequote}}, but must not introduce new subgoals. The |
|
903 final goal state is then used as reduction rule for the obtain |
|
904 scheme described above. Obtained parameters \isa{{\isachardoublequote}x\isactrlsub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ x\isactrlsub m{\isachardoublequote}} are marked as internal by default, which prevents the |
|
905 proof context from being polluted by ad-hoc variables. The variable |
|
906 names and type constraints given as arguments for \mbox{\isa{\isacommand{guess}}} |
|
907 specify a prefix of obtained parameters explicitly in the text. |
|
908 |
|
909 It is important to note that the facts introduced by \mbox{\isa{\isacommand{obtain}}} and \mbox{\isa{\isacommand{guess}}} may not be polymorphic: any |
|
910 type-variables occurring here are fixed in the present context!% |
|
911 \end{isamarkuptext}% |
|
912 \isamarkuptrue% |
|
913 % |
|
914 \isamarkupsection{Calculational reasoning \label{sec:calculation}% |
|
915 } |
|
916 \isamarkuptrue% |
|
917 % |
|
918 \begin{isamarkuptext}% |
|
919 \begin{matharray}{rcl} |
|
920 \indexdef{}{command}{also}\mbox{\isa{\isacommand{also}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
921 \indexdef{}{command}{finally}\mbox{\isa{\isacommand{finally}}} & : & \isartrans{proof(state)}{proof(chain)} \\ |
|
922 \indexdef{}{command}{moreover}\mbox{\isa{\isacommand{moreover}}} & : & \isartrans{proof(state)}{proof(state)} \\ |
|
923 \indexdef{}{command}{ultimately}\mbox{\isa{\isacommand{ultimately}}} & : & \isartrans{proof(state)}{proof(chain)} \\ |
|
924 \indexdef{}{command}{print\_trans\_rules}\mbox{\isa{\isacommand{print{\isacharunderscore}trans{\isacharunderscore}rules}}}\isa{{\isachardoublequote}\isactrlsup {\isacharasterisk}{\isachardoublequote}} & : & \isarkeep{theory~|~proof} \\ |
|
925 \mbox{\isa{trans}} & : & \isaratt \\ |
|
926 \mbox{\isa{sym}} & : & \isaratt \\ |
|
927 \mbox{\isa{symmetric}} & : & \isaratt \\ |
|
928 \end{matharray} |
|
929 |
|
930 Calculational proof is forward reasoning with implicit application |
|
931 of transitivity rules (such those of \isa{{\isachardoublequote}{\isacharequal}{\isachardoublequote}}, \isa{{\isachardoublequote}{\isasymle}{\isachardoublequote}}, |
|
932 \isa{{\isachardoublequote}{\isacharless}{\isachardoublequote}}). Isabelle/Isar maintains an auxiliary fact register |
|
933 \indexref{}{fact}{calculation}\mbox{\isa{calculation}} for accumulating results obtained by |
|
934 transitivity composed with the current result. Command \mbox{\isa{\isacommand{also}}} updates \mbox{\isa{calculation}} involving \mbox{\isa{this}}, while |
|
935 \mbox{\isa{\isacommand{finally}}} exhibits the final \mbox{\isa{calculation}} by |
|
936 forward chaining towards the next goal statement. Both commands |
|
937 require valid current facts, i.e.\ may occur only after commands |
|
938 that produce theorems such as \mbox{\isa{\isacommand{assume}}}, \mbox{\isa{\isacommand{note}}}, or some finished proof of \mbox{\isa{\isacommand{have}}}, \mbox{\isa{\isacommand{show}}} etc. The \mbox{\isa{\isacommand{moreover}}} and \mbox{\isa{\isacommand{ultimately}}} |
|
939 commands are similar to \mbox{\isa{\isacommand{also}}} and \mbox{\isa{\isacommand{finally}}}, |
|
940 but only collect further results in \mbox{\isa{calculation}} without |
|
941 applying any rules yet. |
|
942 |
|
943 Also note that the implicit term abbreviation ``\isa{{\isachardoublequote}{\isasymdots}{\isachardoublequote}}'' has |
|
944 its canonical application with calculational proofs. It refers to |
|
945 the argument of the preceding statement. (The argument of a curried |
|
946 infix expression happens to be its right-hand side.) |
|
947 |
|
948 Isabelle/Isar calculations are implicitly subject to block structure |
|
949 in the sense that new threads of calculational reasoning are |
|
950 commenced for any new block (as opened by a local goal, for |
|
951 example). This means that, apart from being able to nest |
|
952 calculations, there is no separate \emph{begin-calculation} command |
|
953 required. |
|
954 |
|
955 \medskip The Isar calculation proof commands may be defined as |
|
956 follows:\footnote{We suppress internal bookkeeping such as proper |
|
957 handling of block-structure.} |
|
958 |
|
959 \begin{matharray}{rcl} |
|
960 \mbox{\isa{\isacommand{also}}}\isa{{\isachardoublequote}\isactrlsub {\isadigit{0}}{\isachardoublequote}} & \equiv & \mbox{\isa{\isacommand{note}}}~\isa{{\isachardoublequote}calculation\ {\isacharequal}\ this{\isachardoublequote}} \\ |
|
961 \mbox{\isa{\isacommand{also}}}\isa{{\isachardoublequote}\isactrlsub n\isactrlsub {\isacharplus}\isactrlsub {\isadigit{1}}{\isachardoublequote}} & \equiv & \mbox{\isa{\isacommand{note}}}~\isa{{\isachardoublequote}calculation\ {\isacharequal}\ trans\ {\isacharbrackleft}OF\ calculation\ this{\isacharbrackright}{\isachardoublequote}} \\[0.5ex] |
|
962 \mbox{\isa{\isacommand{finally}}} & \equiv & \mbox{\isa{\isacommand{also}}}~\mbox{\isa{\isacommand{from}}}~\isa{calculation} \\[0.5ex] |
|
963 \mbox{\isa{\isacommand{moreover}}} & \equiv & \mbox{\isa{\isacommand{note}}}~\isa{{\isachardoublequote}calculation\ {\isacharequal}\ calculation\ this{\isachardoublequote}} \\ |
|
964 \mbox{\isa{\isacommand{ultimately}}} & \equiv & \mbox{\isa{\isacommand{moreover}}}~\mbox{\isa{\isacommand{from}}}~\isa{calculation} \\ |
|
965 \end{matharray} |
|
966 |
|
967 \begin{rail} |
|
968 ('also' | 'finally') ('(' thmrefs ')')? |
|
969 ; |
|
970 'trans' (() | 'add' | 'del') |
|
971 ; |
|
972 \end{rail} |
|
973 |
|
974 \begin{descr} |
|
975 |
|
976 \item [\mbox{\isa{\isacommand{also}}}~\isa{{\isachardoublequote}{\isacharparenleft}a\isactrlsub {\isadigit{1}}\ {\isasymdots}\ a\isactrlsub n{\isacharparenright}{\isachardoublequote}}] |
|
977 maintains the auxiliary \mbox{\isa{calculation}} register as follows. |
|
978 The first occurrence of \mbox{\isa{\isacommand{also}}} in some calculational |
|
979 thread initializes \mbox{\isa{calculation}} by \mbox{\isa{this}}. Any |
|
980 subsequent \mbox{\isa{\isacommand{also}}} on the same level of block-structure |
|
981 updates \mbox{\isa{calculation}} by some transitivity rule applied to |
|
982 \mbox{\isa{calculation}} and \mbox{\isa{this}} (in that order). Transitivity |
|
983 rules are picked from the current context, unless alternative rules |
|
984 are given as explicit arguments. |
|
985 |
|
986 \item [\mbox{\isa{\isacommand{finally}}}~\isa{{\isachardoublequote}{\isacharparenleft}a\isactrlsub {\isadigit{1}}\ {\isasymdots}\ a\isactrlsub n{\isacharparenright}{\isachardoublequote}}] |
|
987 maintaining \mbox{\isa{calculation}} in the same way as \mbox{\isa{\isacommand{also}}}, and concludes the current calculational thread. The final |
|
988 result is exhibited as fact for forward chaining towards the next |
|
989 goal. Basically, \mbox{\isa{\isacommand{finally}}} just abbreviates \mbox{\isa{\isacommand{also}}}~\mbox{\isa{\isacommand{from}}}~\mbox{\isa{calculation}}. Typical idioms for |
|
990 concluding calculational proofs are ``\mbox{\isa{\isacommand{finally}}}~\mbox{\isa{\isacommand{show}}}~\isa{{\isacharquery}thesis}~\mbox{\isa{\isacommand{{\isachardot}}}}'' and ``\mbox{\isa{\isacommand{finally}}}~\mbox{\isa{\isacommand{have}}}~\isa{{\isasymphi}}~\mbox{\isa{\isacommand{{\isachardot}}}}''. |
|
991 |
|
992 \item [\mbox{\isa{\isacommand{moreover}}} and \mbox{\isa{\isacommand{ultimately}}}] are |
|
993 analogous to \mbox{\isa{\isacommand{also}}} and \mbox{\isa{\isacommand{finally}}}, but collect |
|
994 results only, without applying rules. |
|
995 |
|
996 \item [\mbox{\isa{\isacommand{print{\isacharunderscore}trans{\isacharunderscore}rules}}}] prints the list of |
|
997 transitivity rules (for calculational commands \mbox{\isa{\isacommand{also}}} and |
|
998 \mbox{\isa{\isacommand{finally}}}) and symmetry rules (for the \mbox{\isa{symmetric}} operation and single step elimination patters) of the |
|
999 current context. |
|
1000 |
|
1001 \item [\mbox{\isa{trans}}] declares theorems as transitivity rules. |
|
1002 |
|
1003 \item [\mbox{\isa{sym}}] declares symmetry rules, as well as |
|
1004 \mbox{\isa{Pure{\isachardot}elim{\isacharquery}}} rules. |
|
1005 |
|
1006 \item [\mbox{\isa{symmetric}}] resolves a theorem with some rule |
|
1007 declared as \mbox{\isa{sym}} in the current context. For example, |
|
1008 ``\mbox{\isa{\isacommand{assume}}}~\isa{{\isachardoublequote}{\isacharbrackleft}symmetric{\isacharbrackright}{\isacharcolon}\ x\ {\isacharequal}\ y{\isachardoublequote}}'' produces a |
|
1009 swapped fact derived from that assumption. |
|
1010 |
|
1011 In structured proof texts it is often more appropriate to use an |
|
1012 explicit single-step elimination proof, such as ``\mbox{\isa{\isacommand{assume}}}~\isa{{\isachardoublequote}x\ {\isacharequal}\ y{\isachardoublequote}}~\mbox{\isa{\isacommand{then}}}~\mbox{\isa{\isacommand{have}}}~\isa{{\isachardoublequote}y\ {\isacharequal}\ x{\isachardoublequote}}~\mbox{\isa{\isacommand{{\isachardot}{\isachardot}}}}''. |
|
1013 |
|
1014 \end{descr}% |
|
1015 \end{isamarkuptext}% |
|
1016 \isamarkuptrue% |
|
1017 % |
27 \isadelimtheory |
1018 \isadelimtheory |
28 % |
1019 % |
29 \endisadelimtheory |
1020 \endisadelimtheory |
30 % |
1021 % |
31 \isatagtheory |
1022 \isatagtheory |