122 \begin{isamarkuptext}% |
122 \begin{isamarkuptext}% |
123 \index{simplification!with/of assumptions} |
123 \index{simplification!with/of assumptions} |
124 By default, assumptions are part of the simplification process: they are used |
124 By default, assumptions are part of the simplification process: they are used |
125 as simplification rules and are simplified themselves. For example:% |
125 as simplification rules and are simplified themselves. For example:% |
126 \end{isamarkuptext}% |
126 \end{isamarkuptext}% |
127 \isamarkupfalse% |
127 \isamarkuptrue% |
128 \isacommand{lemma}\ {\isachardoublequote}{\isasymlbrakk}\ xs\ {\isacharat}\ zs\ {\isacharequal}\ ys\ {\isacharat}\ xs{\isacharsemicolon}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ ys\ {\isacharequal}\ zs{\isachardoublequote}\isanewline |
128 \isacommand{lemma}\isamarkupfalse% |
129 % |
129 \ {\isachardoublequoteopen}{\isasymlbrakk}\ xs\ {\isacharat}\ zs\ {\isacharequal}\ ys\ {\isacharat}\ xs{\isacharsemicolon}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ ys\ {\isacharequal}\ zs{\isachardoublequoteclose}\isanewline |
130 \isadelimproof |
130 % |
131 % |
131 \isadelimproof |
132 \endisadelimproof |
132 % |
133 % |
133 \endisadelimproof |
134 \isatagproof |
134 % |
135 \isamarkupfalse% |
135 \isatagproof |
136 \isacommand{apply}\ simp\isanewline |
136 \isacommand{apply}\isamarkupfalse% |
137 \isamarkupfalse% |
137 \ simp\isanewline |
138 \isacommand{done}% |
138 \isacommand{done}\isamarkupfalse% |
139 \endisatagproof |
139 % |
140 {\isafoldproof}% |
140 \endisatagproof |
141 % |
141 {\isafoldproof}% |
142 \isadelimproof |
142 % |
143 % |
143 \isadelimproof |
144 \endisadelimproof |
144 % |
145 \isamarkuptrue% |
145 \endisadelimproof |
146 % |
146 % |
147 \begin{isamarkuptext}% |
147 \begin{isamarkuptext}% |
148 \noindent |
148 \noindent |
149 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn |
149 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn |
150 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the |
150 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the |
151 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}. |
151 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}. |
152 |
152 |
153 In some cases, using the assumptions can lead to nontermination:% |
153 In some cases, using the assumptions can lead to nontermination:% |
154 \end{isamarkuptext}% |
154 \end{isamarkuptext}% |
155 \isamarkupfalse% |
155 \isamarkuptrue% |
156 \isacommand{lemma}\ {\isachardoublequote}{\isasymforall}x{\isachardot}\ f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}% |
156 \isacommand{lemma}\isamarkupfalse% |
157 \isadelimproof |
157 \ {\isachardoublequoteopen}{\isasymforall}x{\isachardot}\ f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}% |
158 % |
158 \isadelimproof |
159 \endisadelimproof |
159 % |
160 % |
160 \endisadelimproof |
161 \isatagproof |
161 % |
162 \isamarkuptrue% |
162 \isatagproof |
163 % |
163 % |
164 \begin{isamarkuptxt}% |
164 \begin{isamarkuptxt}% |
165 \noindent |
165 \noindent |
166 An unmodified application of \isa{simp} loops. The culprit is the |
166 An unmodified application of \isa{simp} loops. The culprit is the |
167 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}}, which is extracted from |
167 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}}, which is extracted from |
168 the assumption. (Isabelle notices certain simple forms of |
168 the assumption. (Isabelle notices certain simple forms of |
169 nontermination but not this one.) The problem can be circumvented by |
169 nontermination but not this one.) The problem can be circumvented by |
170 telling the simplifier to ignore the assumptions:% |
170 telling the simplifier to ignore the assumptions:% |
171 \end{isamarkuptxt}% |
171 \end{isamarkuptxt}% |
172 \isamarkupfalse% |
172 \isamarkuptrue% |
173 \isacommand{apply}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline |
173 \isacommand{apply}\isamarkupfalse% |
174 \isamarkupfalse% |
174 {\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline |
175 \isacommand{done}% |
175 \isacommand{done}\isamarkupfalse% |
176 \endisatagproof |
176 % |
177 {\isafoldproof}% |
177 \endisatagproof |
178 % |
178 {\isafoldproof}% |
179 \isadelimproof |
179 % |
180 % |
180 \isadelimproof |
181 \endisadelimproof |
181 % |
182 \isamarkuptrue% |
182 \endisadelimproof |
183 % |
183 % |
184 \begin{isamarkuptext}% |
184 \begin{isamarkuptext}% |
185 \noindent |
185 \noindent |
186 Three modifiers influence the treatment of assumptions: |
186 Three modifiers influence the treatment of assumptions: |
187 \begin{description} |
187 \begin{description} |
225 proofs more robust: if the definition has to be changed, |
225 proofs more robust: if the definition has to be changed, |
226 only the proofs of the abstract properties will be affected. |
226 only the proofs of the abstract properties will be affected. |
227 |
227 |
228 For example, given% |
228 For example, given% |
229 \end{isamarkuptext}% |
229 \end{isamarkuptext}% |
230 \isamarkupfalse% |
230 \isamarkuptrue% |
231 \isacommand{constdefs}\ xor\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}bool\ {\isasymRightarrow}\ bool\ {\isasymRightarrow}\ bool{\isachardoublequote}\isanewline |
231 \isacommand{constdefs}\isamarkupfalse% |
232 \ \ \ \ \ \ \ \ \ {\isachardoublequote}xor\ A\ B\ {\isasymequiv}\ {\isacharparenleft}A\ {\isasymand}\ {\isasymnot}B{\isacharparenright}\ {\isasymor}\ {\isacharparenleft}{\isasymnot}A\ {\isasymand}\ B{\isacharparenright}{\isachardoublequote}\isamarkuptrue% |
232 \ xor\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}bool\ {\isasymRightarrow}\ bool\ {\isasymRightarrow}\ bool{\isachardoublequoteclose}\isanewline |
233 % |
233 \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}xor\ A\ B\ {\isasymequiv}\ {\isacharparenleft}A\ {\isasymand}\ {\isasymnot}B{\isacharparenright}\ {\isasymor}\ {\isacharparenleft}{\isasymnot}A\ {\isasymand}\ B{\isacharparenright}{\isachardoublequoteclose}% |
234 \begin{isamarkuptext}% |
234 \begin{isamarkuptext}% |
235 \noindent |
235 \noindent |
236 we may want to prove% |
236 we may want to prove% |
237 \end{isamarkuptext}% |
237 \end{isamarkuptext}% |
238 \isamarkupfalse% |
238 \isamarkuptrue% |
239 \isacommand{lemma}\ {\isachardoublequote}xor\ A\ {\isacharparenleft}{\isasymnot}A{\isacharparenright}{\isachardoublequote}% |
239 \isacommand{lemma}\isamarkupfalse% |
240 \isadelimproof |
240 \ {\isachardoublequoteopen}xor\ A\ {\isacharparenleft}{\isasymnot}A{\isacharparenright}{\isachardoublequoteclose}% |
241 % |
241 \isadelimproof |
242 \endisadelimproof |
242 % |
243 % |
243 \endisadelimproof |
244 \isatagproof |
244 % |
245 \isamarkuptrue% |
245 \isatagproof |
246 % |
246 % |
247 \begin{isamarkuptxt}% |
247 \begin{isamarkuptxt}% |
248 \noindent |
248 \noindent |
249 Typically, we begin by unfolding some definitions: |
249 Typically, we begin by unfolding some definitions: |
250 \indexbold{definitions!unfolding}% |
250 \indexbold{definitions!unfolding}% |
251 \end{isamarkuptxt}% |
251 \end{isamarkuptxt}% |
252 \isamarkupfalse% |
252 \isamarkuptrue% |
253 \isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}\isamarkuptrue% |
253 \isacommand{apply}\isamarkupfalse% |
254 % |
254 {\isacharparenleft}simp\ only{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}% |
255 \begin{isamarkuptxt}% |
255 \begin{isamarkuptxt}% |
256 \noindent |
256 \noindent |
257 In this particular case, the resulting goal |
257 In this particular case, the resulting goal |
258 \begin{isabelle}% |
258 \begin{isabelle}% |
259 \ {\isadigit{1}}{\isachardot}\ A\ {\isasymand}\ {\isasymnot}\ {\isasymnot}\ A\ {\isasymor}\ {\isasymnot}\ A\ {\isasymand}\ {\isasymnot}\ A% |
259 \ {\isadigit{1}}{\isachardot}\ A\ {\isasymand}\ {\isasymnot}\ {\isasymnot}\ A\ {\isasymor}\ {\isasymnot}\ A\ {\isasymand}\ {\isasymnot}\ A% |
260 \end{isabelle} |
260 \end{isabelle} |
261 can be proved by simplification. Thus we could have proved the lemma outright by% |
261 can be proved by simplification. Thus we could have proved the lemma outright by% |
262 \end{isamarkuptxt}% |
262 \end{isamarkuptxt}% |
263 % |
263 \isamarkuptrue% |
264 \endisatagproof |
264 \isamarkupfalse% |
265 {\isafoldproof}% |
265 % |
266 % |
266 \endisatagproof |
267 \isadelimproof |
267 {\isafoldproof}% |
268 % |
268 % |
269 \endisadelimproof |
269 \isadelimproof |
270 % |
270 % |
271 \isadelimproof |
271 \endisadelimproof |
272 % |
272 \isamarkupfalse% |
273 \endisadelimproof |
273 % |
274 % |
274 \isadelimproof |
275 \isatagproof |
275 % |
276 \isamarkupfalse% |
276 \endisadelimproof |
277 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}% |
277 % |
278 \endisatagproof |
278 \isatagproof |
279 {\isafoldproof}% |
279 \isacommand{apply}\isamarkupfalse% |
280 % |
280 {\isacharparenleft}simp\ add{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}\isamarkupfalse% |
281 \isadelimproof |
281 % |
282 % |
282 \endisatagproof |
283 \endisadelimproof |
283 {\isafoldproof}% |
284 \isamarkuptrue% |
284 % |
|
285 \isadelimproof |
|
286 % |
|
287 \endisadelimproof |
285 % |
288 % |
286 \begin{isamarkuptext}% |
289 \begin{isamarkuptext}% |
287 \noindent |
290 \noindent |
288 Of course we can also unfold definitions in the middle of a proof. |
291 Of course we can also unfold definitions in the middle of a proof. |
289 |
292 |
312 \isa{let}-con\-structs to be expanded at some point. Since |
315 \isa{let}-con\-structs to be expanded at some point. Since |
313 \isa{let}\ldots\isa{=}\ldots\isa{in}{\ldots} is just syntactic sugar for |
316 \isa{let}\ldots\isa{=}\ldots\isa{in}{\ldots} is just syntactic sugar for |
314 the predefined constant \isa{Let}, expanding \isa{let}-constructs |
317 the predefined constant \isa{Let}, expanding \isa{let}-constructs |
315 means rewriting with \tdx{Let_def}:% |
318 means rewriting with \tdx{Let_def}:% |
316 \end{isamarkuptext}% |
319 \end{isamarkuptext}% |
317 \isamarkupfalse% |
320 \isamarkuptrue% |
318 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequote}\isanewline |
321 \isacommand{lemma}\isamarkupfalse% |
319 % |
322 \ {\isachardoublequoteopen}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequoteclose}\isanewline |
320 \isadelimproof |
323 % |
321 % |
324 \isadelimproof |
322 \endisadelimproof |
325 % |
323 % |
326 \endisadelimproof |
324 \isatagproof |
327 % |
325 \isamarkupfalse% |
328 \isatagproof |
326 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline |
329 \isacommand{apply}\isamarkupfalse% |
327 \isamarkupfalse% |
330 {\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline |
328 \isacommand{done}% |
331 \isacommand{done}\isamarkupfalse% |
329 \endisatagproof |
332 % |
330 {\isafoldproof}% |
333 \endisatagproof |
331 % |
334 {\isafoldproof}% |
332 \isadelimproof |
335 % |
333 % |
336 \isadelimproof |
334 \endisadelimproof |
337 % |
335 \isamarkuptrue% |
338 \endisadelimproof |
336 % |
339 % |
337 \begin{isamarkuptext}% |
340 \begin{isamarkuptext}% |
338 If, in a particular context, there is no danger of a combinatorial explosion |
341 If, in a particular context, there is no danger of a combinatorial explosion |
339 of nested \isa{let}s, you could even simplify with \isa{Let{\isacharunderscore}def} by |
342 of nested \isa{let}s, you could even simplify with \isa{Let{\isacharunderscore}def} by |
340 default:% |
343 default:% |
341 \end{isamarkuptext}% |
344 \end{isamarkuptext}% |
342 \isamarkupfalse% |
345 \isamarkuptrue% |
343 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}\isamarkuptrue% |
346 \isacommand{declare}\isamarkupfalse% |
344 % |
347 \ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}% |
345 \isamarkupsubsection{Conditional Simplification Rules% |
348 \isamarkupsubsection{Conditional Simplification Rules% |
346 } |
349 } |
347 \isamarkuptrue% |
350 \isamarkuptrue% |
348 % |
351 % |
349 \begin{isamarkuptext}% |
352 \begin{isamarkuptext}% |
350 \index{conditional simplification rules}% |
353 \index{conditional simplification rules}% |
351 So far all examples of rewrite rules were equations. The simplifier also |
354 So far all examples of rewrite rules were equations. The simplifier also |
352 accepts \emph{conditional} equations, for example% |
355 accepts \emph{conditional} equations, for example% |
353 \end{isamarkuptext}% |
356 \end{isamarkuptext}% |
354 \isamarkupfalse% |
357 \isamarkuptrue% |
355 \isacommand{lemma}\ hd{\isacharunderscore}Cons{\isacharunderscore}tl{\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ \ {\isasymLongrightarrow}\ \ hd\ xs\ {\isacharhash}\ tl\ xs\ {\isacharequal}\ xs{\isachardoublequote}\isanewline |
358 \isacommand{lemma}\isamarkupfalse% |
356 % |
359 \ hd{\isacharunderscore}Cons{\isacharunderscore}tl{\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequoteopen}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ \ {\isasymLongrightarrow}\ \ hd\ xs\ {\isacharhash}\ tl\ xs\ {\isacharequal}\ xs{\isachardoublequoteclose}\isanewline |
357 \isadelimproof |
360 % |
358 % |
361 \isadelimproof |
359 \endisadelimproof |
362 % |
360 % |
363 \endisadelimproof |
361 \isatagproof |
364 % |
362 \isamarkupfalse% |
365 \isatagproof |
363 \isacommand{apply}{\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline |
366 \isacommand{apply}\isamarkupfalse% |
364 \isamarkupfalse% |
367 {\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline |
365 \isacommand{done}% |
368 \isacommand{done}\isamarkupfalse% |
366 \endisatagproof |
369 % |
367 {\isafoldproof}% |
370 \endisatagproof |
368 % |
371 {\isafoldproof}% |
369 \isadelimproof |
372 % |
370 % |
373 \isadelimproof |
371 \endisadelimproof |
374 % |
372 \isamarkuptrue% |
375 \endisadelimproof |
373 % |
376 % |
374 \begin{isamarkuptext}% |
377 \begin{isamarkuptext}% |
375 \noindent |
378 \noindent |
376 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a |
379 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a |
377 sequence of methods. Assuming that the simplification rule |
380 sequence of methods. Assuming that the simplification rule |
378 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}} |
381 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}} |
379 is present as well, |
382 is present as well, |
380 the lemma below is proved by plain simplification:% |
383 the lemma below is proved by plain simplification:% |
381 \end{isamarkuptext}% |
384 \end{isamarkuptext}% |
382 \isamarkupfalse% |
385 \isamarkuptrue% |
383 \isacommand{lemma}\ {\isachardoublequote}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ hd{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ rev\ xs{\isachardoublequote}% |
386 \isacommand{lemma}\isamarkupfalse% |
384 \isadelimproof |
387 \ {\isachardoublequoteopen}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ hd{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ rev\ xs{\isachardoublequoteclose}% |
385 % |
388 \isadelimproof |
386 \endisadelimproof |
389 % |
387 % |
390 \endisadelimproof |
388 \isatagproof |
391 % |
389 % |
392 \isatagproof |
390 \endisatagproof |
393 \isamarkupfalse% |
391 {\isafoldproof}% |
394 % |
392 % |
395 \endisatagproof |
393 \isadelimproof |
396 {\isafoldproof}% |
394 % |
397 % |
395 \endisadelimproof |
398 \isadelimproof |
396 \isamarkuptrue% |
399 % |
|
400 \endisadelimproof |
397 % |
401 % |
398 \begin{isamarkuptext}% |
402 \begin{isamarkuptext}% |
399 \noindent |
403 \noindent |
400 The conditional equation \isa{hd{\isacharunderscore}Cons{\isacharunderscore}tl} above |
404 The conditional equation \isa{hd{\isacharunderscore}Cons{\isacharunderscore}tl} above |
401 can simplify \isa{hd\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl\ {\isacharparenleft}rev\ xs{\isacharparenright}} to \isa{rev\ xs} |
405 can simplify \isa{hd\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl\ {\isacharparenleft}rev\ xs{\isacharparenright}} to \isa{rev\ xs} |
413 \label{sec:AutoCaseSplits}\indexbold{case splits}% |
417 \label{sec:AutoCaseSplits}\indexbold{case splits}% |
414 Goals containing \isa{if}-expressions\index{*if expressions!splitting of} |
418 Goals containing \isa{if}-expressions\index{*if expressions!splitting of} |
415 are usually proved by case |
419 are usually proved by case |
416 distinction on the boolean condition. Here is an example:% |
420 distinction on the boolean condition. Here is an example:% |
417 \end{isamarkuptext}% |
421 \end{isamarkuptext}% |
418 \isamarkupfalse% |
422 \isamarkuptrue% |
419 \isacommand{lemma}\ {\isachardoublequote}{\isasymforall}xs{\isachardot}\ if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}% |
423 \isacommand{lemma}\isamarkupfalse% |
420 \isadelimproof |
424 \ {\isachardoublequoteopen}{\isasymforall}xs{\isachardot}\ if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}% |
421 % |
425 \isadelimproof |
422 \endisadelimproof |
426 % |
423 % |
427 \endisadelimproof |
424 \isatagproof |
428 % |
425 \isamarkuptrue% |
429 \isatagproof |
426 % |
430 % |
427 \begin{isamarkuptxt}% |
431 \begin{isamarkuptxt}% |
428 \noindent |
432 \noindent |
429 The goal can be split by a special method, \methdx{split}:% |
433 The goal can be split by a special method, \methdx{split}:% |
430 \end{isamarkuptxt}% |
434 \end{isamarkuptxt}% |
431 \isamarkupfalse% |
435 \isamarkuptrue% |
432 \isacommand{apply}{\isacharparenleft}split\ split{\isacharunderscore}if{\isacharparenright}\isamarkuptrue% |
436 \isacommand{apply}\isamarkupfalse% |
433 % |
437 {\isacharparenleft}split\ split{\isacharunderscore}if{\isacharparenright}% |
434 \begin{isamarkuptxt}% |
438 \begin{isamarkuptxt}% |
435 \noindent |
439 \noindent |
436 \begin{isabelle}% |
440 \begin{isabelle}% |
437 \ {\isadigit{1}}{\isachardot}\ {\isasymforall}xs{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}% |
441 \ {\isadigit{1}}{\isachardot}\ {\isasymforall}xs{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}% |
438 \end{isabelle} |
442 \end{isabelle} |
443 on the initial goal above. |
447 on the initial goal above. |
444 |
448 |
445 This splitting idea generalizes from \isa{if} to \sdx{case}. |
449 This splitting idea generalizes from \isa{if} to \sdx{case}. |
446 Let us simplify a case analysis over lists:\index{*list.split (theorem)}% |
450 Let us simplify a case analysis over lists:\index{*list.split (theorem)}% |
447 \end{isamarkuptxt}% |
451 \end{isamarkuptxt}% |
448 % |
452 \isamarkuptrue% |
449 \endisatagproof |
453 \isamarkupfalse% |
450 {\isafoldproof}% |
454 % |
451 % |
455 \endisatagproof |
452 \isadelimproof |
456 {\isafoldproof}% |
453 % |
457 % |
454 \endisadelimproof |
458 \isadelimproof |
455 \isamarkupfalse% |
459 % |
456 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}case\ xs\ of\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymRightarrow}\ zs\ {\isacharbar}\ y{\isacharhash}ys\ {\isasymRightarrow}\ y{\isacharhash}{\isacharparenleft}ys{\isacharat}zs{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ xs{\isacharat}zs{\isachardoublequote}\isanewline |
460 \endisadelimproof |
457 % |
461 \isacommand{lemma}\isamarkupfalse% |
458 \isadelimproof |
462 \ {\isachardoublequoteopen}{\isacharparenleft}case\ xs\ of\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymRightarrow}\ zs\ {\isacharbar}\ y{\isacharhash}ys\ {\isasymRightarrow}\ y{\isacharhash}{\isacharparenleft}ys{\isacharat}zs{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ xs{\isacharat}zs{\isachardoublequoteclose}\isanewline |
459 % |
463 % |
460 \endisadelimproof |
464 \isadelimproof |
461 % |
465 % |
462 \isatagproof |
466 \endisadelimproof |
463 \isamarkupfalse% |
467 % |
464 \isacommand{apply}{\isacharparenleft}split\ list{\isachardot}split{\isacharparenright}\isamarkuptrue% |
468 \isatagproof |
465 % |
469 \isacommand{apply}\isamarkupfalse% |
|
470 {\isacharparenleft}split\ list{\isachardot}split{\isacharparenright}% |
466 \begin{isamarkuptxt}% |
471 \begin{isamarkuptxt}% |
467 \begin{isabelle}% |
472 \begin{isabelle}% |
468 \ {\isadigit{1}}{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}\ {\isasymand}\isanewline |
473 \ {\isadigit{1}}{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}\ {\isasymand}\isanewline |
469 \isaindent{\ {\isadigit{1}}{\isachardot}\ }{\isacharparenleft}{\isasymforall}a\ list{\isachardot}\ xs\ {\isacharequal}\ a\ {\isacharhash}\ list\ {\isasymlongrightarrow}\ a\ {\isacharhash}\ list\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}% |
474 \isaindent{\ {\isadigit{1}}{\isachardot}\ }{\isacharparenleft}{\isasymforall}a\ list{\isachardot}\ xs\ {\isacharequal}\ a\ {\isacharhash}\ list\ {\isasymlongrightarrow}\ a\ {\isacharhash}\ list\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}% |
470 \end{isabelle} |
475 \end{isabelle} |
474 Instead, the simplifier has a modifier |
479 Instead, the simplifier has a modifier |
475 \isa{split}\index{*split (modifier)} |
480 \isa{split}\index{*split (modifier)} |
476 for adding splitting rules explicitly. The |
481 for adding splitting rules explicitly. The |
477 lemma above can be proved in one step by% |
482 lemma above can be proved in one step by% |
478 \end{isamarkuptxt}% |
483 \end{isamarkuptxt}% |
479 % |
484 \isamarkuptrue% |
480 \endisatagproof |
485 \isamarkupfalse% |
481 {\isafoldproof}% |
486 % |
482 % |
487 \endisatagproof |
483 \isadelimproof |
488 {\isafoldproof}% |
484 % |
489 % |
485 \endisadelimproof |
490 \isadelimproof |
486 % |
491 % |
487 \isadelimproof |
492 \endisadelimproof |
488 % |
493 \isamarkupfalse% |
489 \endisadelimproof |
494 % |
490 % |
495 \isadelimproof |
491 \isatagproof |
496 % |
492 \isamarkupfalse% |
497 \endisadelimproof |
493 \isacommand{apply}{\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}% |
498 % |
494 \endisatagproof |
499 \isatagproof |
495 {\isafoldproof}% |
500 \isacommand{apply}\isamarkupfalse% |
496 % |
501 {\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}\isamarkupfalse% |
497 \isadelimproof |
502 % |
498 % |
503 \endisatagproof |
499 \endisadelimproof |
504 {\isafoldproof}% |
500 \isamarkuptrue% |
505 % |
|
506 \isadelimproof |
|
507 % |
|
508 \endisadelimproof |
501 % |
509 % |
502 \begin{isamarkuptext}% |
510 \begin{isamarkuptext}% |
503 \noindent |
511 \noindent |
504 whereas \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not succeed. |
512 whereas \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not succeed. |
505 |
513 |
506 Every datatype $t$ comes with a theorem |
514 Every datatype $t$ comes with a theorem |
507 $t$\isa{{\isachardot}split} which can be declared to be a \bfindex{split rule} either |
515 $t$\isa{{\isachardot}split} which can be declared to be a \bfindex{split rule} either |
508 locally as above, or by giving it the \attrdx{split} attribute globally:% |
516 locally as above, or by giving it the \attrdx{split} attribute globally:% |
509 \end{isamarkuptext}% |
517 \end{isamarkuptext}% |
510 \isamarkupfalse% |
518 \isamarkuptrue% |
511 \isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split{\isacharbrackright}\isamarkuptrue% |
519 \isacommand{declare}\isamarkupfalse% |
512 % |
520 \ list{\isachardot}split\ {\isacharbrackleft}split{\isacharbrackright}% |
513 \begin{isamarkuptext}% |
521 \begin{isamarkuptext}% |
514 \noindent |
522 \noindent |
515 The \isa{split} attribute can be removed with the \isa{del} modifier, |
523 The \isa{split} attribute can be removed with the \isa{del} modifier, |
516 either locally% |
524 either locally% |
517 \end{isamarkuptext}% |
525 \end{isamarkuptext}% |
518 % |
526 \isamarkuptrue% |
519 \isadelimproof |
527 \isamarkupfalse% |
520 % |
528 % |
521 \endisadelimproof |
529 \isadelimproof |
522 % |
530 % |
523 \isatagproof |
531 \endisadelimproof |
524 \isamarkupfalse% |
532 % |
525 \isacommand{apply}{\isacharparenleft}simp\ split\ del{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}% |
533 \isatagproof |
526 \endisatagproof |
534 \isacommand{apply}\isamarkupfalse% |
527 {\isafoldproof}% |
535 {\isacharparenleft}simp\ split\ del{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}\isamarkupfalse% |
528 % |
536 % |
529 \isadelimproof |
537 \endisatagproof |
530 % |
538 {\isafoldproof}% |
531 \endisadelimproof |
539 % |
532 \isamarkuptrue% |
540 \isadelimproof |
|
541 % |
|
542 \endisadelimproof |
533 % |
543 % |
534 \begin{isamarkuptext}% |
544 \begin{isamarkuptext}% |
535 \noindent |
545 \noindent |
536 or globally:% |
546 or globally:% |
537 \end{isamarkuptext}% |
547 \end{isamarkuptext}% |
538 \isamarkupfalse% |
548 \isamarkuptrue% |
539 \isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split\ del{\isacharbrackright}\isamarkuptrue% |
549 \isacommand{declare}\isamarkupfalse% |
540 % |
550 \ list{\isachardot}split\ {\isacharbrackleft}split\ del{\isacharbrackright}% |
541 \begin{isamarkuptext}% |
551 \begin{isamarkuptext}% |
542 Polished proofs typically perform splitting within \isa{simp} rather than |
552 Polished proofs typically perform splitting within \isa{simp} rather than |
543 invoking the \isa{split} method. However, if a goal contains |
553 invoking the \isa{split} method. However, if a goal contains |
544 several \isa{if} and \isa{case} expressions, |
554 several \isa{if} and \isa{case} expressions, |
545 the \isa{split} method can be |
555 the \isa{split} method can be |
548 The split rules shown above are intended to affect only the subgoal's |
558 The split rules shown above are intended to affect only the subgoal's |
549 conclusion. If you want to split an \isa{if} or \isa{case}-expression |
559 conclusion. If you want to split an \isa{if} or \isa{case}-expression |
550 in the assumptions, you have to apply \tdx{split_if_asm} or |
560 in the assumptions, you have to apply \tdx{split_if_asm} or |
551 $t$\isa{{\isachardot}split{\isacharunderscore}asm}:% |
561 $t$\isa{{\isachardot}split{\isacharunderscore}asm}:% |
552 \end{isamarkuptext}% |
562 \end{isamarkuptext}% |
553 \isamarkupfalse% |
563 \isamarkuptrue% |
554 \isacommand{lemma}\ {\isachardoublequote}if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ else\ ys\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ xs\ {\isacharat}\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline |
564 \isacommand{lemma}\isamarkupfalse% |
555 % |
565 \ {\isachardoublequoteopen}if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ else\ ys\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ xs\ {\isacharat}\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}\isanewline |
556 \isadelimproof |
566 % |
557 % |
567 \isadelimproof |
558 \endisadelimproof |
568 % |
559 % |
569 \endisadelimproof |
560 \isatagproof |
570 % |
561 \isamarkupfalse% |
571 \isatagproof |
562 \isacommand{apply}{\isacharparenleft}split\ split{\isacharunderscore}if{\isacharunderscore}asm{\isacharparenright}\isamarkuptrue% |
572 \isacommand{apply}\isamarkupfalse% |
563 % |
573 {\isacharparenleft}split\ split{\isacharunderscore}if{\isacharunderscore}asm{\isacharparenright}% |
564 \begin{isamarkuptxt}% |
574 \begin{isamarkuptxt}% |
565 \noindent |
575 \noindent |
566 Unlike splitting the conclusion, this step creates two |
576 Unlike splitting the conclusion, this step creates two |
567 separate subgoals, which here can be solved by \isa{simp{\isacharunderscore}all}: |
577 separate subgoals, which here can be solved by \isa{simp{\isacharunderscore}all}: |
568 \begin{isabelle}% |
578 \begin{isabelle}% |
581 same is true for \sdx{case}-expressions: only the selector is |
591 same is true for \sdx{case}-expressions: only the selector is |
582 simplified at first, until either the expression reduces to one of the |
592 simplified at first, until either the expression reduces to one of the |
583 cases or it is split. |
593 cases or it is split. |
584 \end{warn}% |
594 \end{warn}% |
585 \end{isamarkuptxt}% |
595 \end{isamarkuptxt}% |
586 % |
596 \isamarkuptrue% |
587 \endisatagproof |
597 \isamarkupfalse% |
588 {\isafoldproof}% |
598 % |
589 % |
599 \endisatagproof |
590 \isadelimproof |
600 {\isafoldproof}% |
591 % |
601 % |
592 \endisadelimproof |
602 \isadelimproof |
593 \isamarkuptrue% |
603 % |
|
604 \endisadelimproof |
594 % |
605 % |
595 \isamarkupsubsection{Tracing% |
606 \isamarkupsubsection{Tracing% |
596 } |
607 } |
597 \isamarkuptrue% |
608 \isamarkuptrue% |
598 % |
609 % |
599 \begin{isamarkuptext}% |
610 \begin{isamarkuptext}% |
600 \indexbold{tracing the simplifier} |
611 \indexbold{tracing the simplifier} |
601 Using the simplifier effectively may take a bit of experimentation. Set the |
612 Using the simplifier effectively may take a bit of experimentation. Set the |
602 Proof General flag \pgmenu{Isabelle} $>$ \pgmenu{Settings} $>$ \pgmenu{Trace Simplifier} to get a better idea of what is going on:% |
613 Proof General flag \pgmenu{Isabelle} $>$ \pgmenu{Settings} $>$ \pgmenu{Trace Simplifier} to get a better idea of what is going on:% |
603 \end{isamarkuptext}% |
614 \end{isamarkuptext}% |
604 \isamarkupfalse% |
615 \isamarkuptrue% |
605 \isacommand{lemma}\ {\isachardoublequote}rev\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline |
616 \isacommand{lemma}\isamarkupfalse% |
606 % |
617 \ {\isachardoublequoteopen}rev\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}\isanewline |
607 \isadelimproof |
618 % |
608 % |
619 \isadelimproof |
609 \endisadelimproof |
620 % |
610 % |
621 \endisadelimproof |
611 \isatagproof |
622 % |
612 \isamarkupfalse% |
623 \isatagproof |
613 \isacommand{apply}{\isacharparenleft}simp{\isacharparenright}% |
624 \isacommand{apply}\isamarkupfalse% |
614 \endisatagproof |
625 {\isacharparenleft}simp{\isacharparenright}\isamarkupfalse% |
615 {\isafoldproof}% |
626 % |
616 % |
627 \endisatagproof |
617 \isadelimproof |
628 {\isafoldproof}% |
618 % |
629 % |
619 \endisadelimproof |
630 \isadelimproof |
620 \isamarkuptrue% |
631 % |
|
632 \endisadelimproof |
621 % |
633 % |
622 \begin{isamarkuptext}% |
634 \begin{isamarkuptext}% |
623 \noindent |
635 \noindent |
624 produces the following trace in Proof General's \pgmenu{Trace} buffer: |
636 produces the following trace in Proof General's \pgmenu{Trace} buffer: |
625 |
637 |