135 \isa{xs}. |
135 \isa{xs}. |
136 |
136 |
137 The name and the simplification attribute are optional. |
137 The name and the simplification attribute are optional. |
138 \end{itemize} |
138 \end{itemize} |
139 Isabelle's response is to print |
139 Isabelle's response is to print |
140 \begin{isabellepar}% |
140 \begin{isabelle} |
141 proof(prove):~step~0\isanewline |
141 proof(prove):~step~0\isanewline |
142 \isanewline |
142 \isanewline |
143 goal~(theorem~rev\_rev):\isanewline |
143 goal~(theorem~rev\_rev):\isanewline |
144 rev~(rev~xs)~=~xs\isanewline |
144 rev~(rev~xs)~=~xs\isanewline |
145 ~1.~rev~(rev~xs)~=~xs |
145 ~1.~rev~(rev~xs)~=~xs |
146 \end{isabellepar}% |
146 \end{isabelle} |
147 The first three lines tell us that we are 0 steps into the proof of |
147 The first three lines tell us that we are 0 steps into the proof of |
148 theorem \isa{rev_rev}; for compactness reasons we rarely show these |
148 theorem \isa{rev_rev}; for compactness reasons we rarely show these |
149 initial lines in this tutorial. The remaining lines display the current |
149 initial lines in this tutorial. The remaining lines display the current |
150 proof state. |
150 proof state. |
151 Until we have finished a proof, the proof state always looks like this: |
151 Until we have finished a proof, the proof state always looks like this: |
152 \begin{isabellepar}% |
152 \begin{isabelle} |
153 $G$\isanewline |
153 $G$\isanewline |
154 ~1.~$G\sb{1}$\isanewline |
154 ~1.~$G\sb{1}$\isanewline |
155 ~~\vdots~~\isanewline |
155 ~~\vdots~~\isanewline |
156 ~$n$.~$G\sb{n}$ |
156 ~$n$.~$G\sb{n}$ |
157 \end{isabellepar}% |
157 \end{isabelle} |
158 where $G$ |
158 where $G$ |
159 is the overall goal that we are trying to prove, and the numbered lines |
159 is the overall goal that we are trying to prove, and the numbered lines |
160 contain the subgoals $G\sb{1}$, \dots, $G\sb{n}$ that we need to prove to |
160 contain the subgoals $G\sb{1}$, \dots, $G\sb{n}$ that we need to prove to |
161 establish $G$. At \isa{step 0} there is only one subgoal, which is |
161 establish $G$. At \isa{step 0} there is only one subgoal, which is |
162 identical with the overall goal. Normally $G$ is constant and only serves as |
162 identical with the overall goal. Normally $G$ is constant and only serves as |
173 This tells Isabelle to perform induction on variable \isa{xs}. The suffix |
173 This tells Isabelle to perform induction on variable \isa{xs}. The suffix |
174 \isa{tac} stands for ``tactic'', a synonym for ``theorem proving function''. |
174 \isa{tac} stands for ``tactic'', a synonym for ``theorem proving function''. |
175 By default, induction acts on the first subgoal. The new proof state contains |
175 By default, induction acts on the first subgoal. The new proof state contains |
176 two subgoals, namely the base case (\isa{Nil}) and the induction step |
176 two subgoals, namely the base case (\isa{Nil}) and the induction step |
177 (\isa{Cons}): |
177 (\isa{Cons}): |
178 \begin{isabellepar}% |
178 \begin{isabelle} |
179 ~1.~rev~(rev~[])~=~[]\isanewline |
179 ~1.~rev~(rev~[])~=~[]\isanewline |
180 ~2.~{\isasymAnd}a~list.~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev(a~\#~list))~=~a~\#~list% |
180 ~2.~{\isasymAnd}a~list.~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev(a~\#~list))~=~a~\#~list% |
181 \end{isabellepar}% |
181 \end{isabelle} |
182 |
182 |
183 The induction step is an example of the general format of a subgoal: |
183 The induction step is an example of the general format of a subgoal: |
184 \begin{isabellepar}% |
184 \begin{isabelle} |
185 ~$i$.~{\indexboldpos{\isasymAnd}{$IsaAnd}}$x\sb{1}$~\dots~$x\sb{n}$.~{\it assumptions}~{\isasymLongrightarrow}~{\it conclusion} |
185 ~$i$.~{\indexboldpos{\isasymAnd}{$IsaAnd}}$x\sb{1}$~\dots~$x\sb{n}$.~{\it assumptions}~{\isasymLongrightarrow}~{\it conclusion} |
186 \end{isabellepar}% |
186 \end{isabelle} |
187 The prefix of bound variables \isasymAnd$x\sb{1}$~\dots~$x\sb{n}$ can be |
187 The prefix of bound variables \isasymAnd$x\sb{1}$~\dots~$x\sb{n}$ can be |
188 ignored most of the time, or simply treated as a list of variables local to |
188 ignored most of the time, or simply treated as a list of variables local to |
189 this subgoal. Their deeper significance is explained in \S\ref{sec:PCproofs}. |
189 this subgoal. Their deeper significance is explained in \S\ref{sec:PCproofs}. |
190 The {\it assumptions} are the local assumptions for this subgoal and {\it |
190 The {\it assumptions} are the local assumptions for this subgoal and {\it |
191 conclusion} is the actual proposition to be proved. Typical proof steps |
191 conclusion} is the actual proposition to be proved. Typical proof steps |
206 This command tells Isabelle to apply a proof strategy called |
206 This command tells Isabelle to apply a proof strategy called |
207 \isa{auto} to all subgoals. Essentially, \isa{auto} tries to |
207 \isa{auto} to all subgoals. Essentially, \isa{auto} tries to |
208 ``simplify'' the subgoals. In our case, subgoal~1 is solved completely (thanks |
208 ``simplify'' the subgoals. In our case, subgoal~1 is solved completely (thanks |
209 to the equation \isa{rev [] = []}) and disappears; the simplified version |
209 to the equation \isa{rev [] = []}) and disappears; the simplified version |
210 of subgoal~2 becomes the new subgoal~1: |
210 of subgoal~2 becomes the new subgoal~1: |
211 \begin{isabellepar}% |
211 \begin{isabelle} |
212 ~1.~\dots~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev~list~@~a~\#~[])~=~a~\#~list |
212 ~1.~\dots~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev~list~@~a~\#~[])~=~a~\#~list |
213 \end{isabellepar}% |
213 \end{isabelle} |
214 In order to simplify this subgoal further, a lemma suggests itself. |
214 In order to simplify this subgoal further, a lemma suggests itself. |
215 *} |
215 *} |
216 (*<*) |
216 (*<*) |
217 oops |
217 oops |
218 (*>*) |
218 (*>*) |
219 |
219 |
220 text{* |
220 subsubsection{*First lemma: \texttt{rev(xs \at~ys) = (rev ys) \at~(rev xs)}*} |
221 \subsubsection*{First lemma: \texttt{rev(xs \at~ys) = (rev ys) \at~(rev xs)}} |
221 |
222 |
222 text{* |
223 After abandoning the above proof attempt\indexbold{abandon |
223 After abandoning the above proof attempt\indexbold{abandon |
224 proof}\indexbold{proof!abandon} (at the shell level type |
224 proof}\indexbold{proof!abandon} (at the shell level type |
225 \isacommand{oops}\indexbold{*oops}) we start a new proof: |
225 \isacommand{oops}\indexbold{*oops}) we start a new proof: |
226 *} |
226 *} |
227 |
227 |
245 *} |
245 *} |
246 |
246 |
247 apply(auto); |
247 apply(auto); |
248 |
248 |
249 txt{* |
249 txt{* |
250 \begin{isabellepar}% |
250 \begin{isabelle} |
251 ~1.~rev~ys~=~rev~ys~@~[]\isanewline |
251 ~1.~rev~ys~=~rev~ys~@~[]\isanewline |
252 ~2. \dots |
252 ~2. \dots |
253 \end{isabellepar}% |
253 \end{isabelle} |
254 Again, we need to abandon this proof attempt and prove another simple lemma first. |
254 Again, we need to abandon this proof attempt and prove another simple lemma first. |
255 In the future the step of abandoning an incomplete proof before embarking on |
255 In the future the step of abandoning an incomplete proof before embarking on |
256 the proof of a lemma usually remains implicit. |
256 the proof of a lemma usually remains implicit. |
257 *} |
257 *} |
258 (*<*) |
258 (*<*) |
259 oops |
259 oops |
260 (*>*) |
260 (*>*) |
261 |
261 |
262 text{* |
262 subsubsection{*Second lemma: \texttt{xs \at~[] = xs}*} |
263 \subsubsection*{Second lemma: \texttt{xs \at~[] = xs}} |
263 |
264 |
264 text{* |
265 This time the canonical proof procedure |
265 This time the canonical proof procedure |
266 *} |
266 *} |
267 |
267 |
268 lemma app_Nil2 [simp]: "xs @ [] = xs"; |
268 lemma app_Nil2 [simp]: "xs @ [] = xs"; |
269 apply(induct_tac xs); |
269 apply(induct_tac xs); |
270 apply(auto); |
270 apply(auto); |
271 |
271 |
272 txt{* |
272 txt{* |
273 \noindent |
273 \noindent |
274 leads to the desired message \isa{No subgoals!}: |
274 leads to the desired message \isa{No subgoals!}: |
275 \begin{isabellepar}% |
275 \begin{isabelle} |
276 xs~@~[]~=~xs\isanewline |
276 xs~@~[]~=~xs\isanewline |
277 No~subgoals! |
277 No~subgoals! |
278 \end{isabellepar}% |
278 \end{isabelle} |
279 |
279 |
280 We still need to confirm that the proof is now finished: |
280 We still need to confirm that the proof is now finished: |
281 *} |
281 *} |
282 |
282 |
283 . |
283 . |
300 |
300 |
301 txt{* |
301 txt{* |
302 \noindent |
302 \noindent |
303 we find that this time \isa{auto} solves the base case, but the |
303 we find that this time \isa{auto} solves the base case, but the |
304 induction step merely simplifies to |
304 induction step merely simplifies to |
305 \begin{isabellepar} |
305 \begin{isabelle} |
306 ~1.~{\isasymAnd}a~list.\isanewline |
306 ~1.~{\isasymAnd}a~list.\isanewline |
307 ~~~~~~~rev~(list~@~ys)~=~rev~ys~@~rev~list~{\isasymLongrightarrow}\isanewline |
307 ~~~~~~~rev~(list~@~ys)~=~rev~ys~@~rev~list~{\isasymLongrightarrow}\isanewline |
308 ~~~~~~~(rev~ys~@~rev~list)~@~a~\#~[]~=~rev~ys~@~rev~list~@~a~\#~[] |
308 ~~~~~~~(rev~ys~@~rev~list)~@~a~\#~[]~=~rev~ys~@~rev~list~@~a~\#~[] |
309 \end{isabellepar}% |
309 \end{isabelle} |
310 Now we need to remember that \isa{\at} associates to the right, and that |
310 Now we need to remember that \isa{\at} associates to the right, and that |
311 \isa{\#} and \isa{\at} have the same priority (namely the \isa{65} |
311 \isa{\#} and \isa{\at} have the same priority (namely the \isa{65} |
312 in their \isacommand{infixr} annotation). Thus the conclusion really is |
312 in their \isacommand{infixr} annotation). Thus the conclusion really is |
313 \begin{isabellepar}% |
313 \begin{isabelle} |
314 ~~~~~(rev~ys~@~rev~list)~@~(a~\#~[])~=~rev~ys~@~(rev~list~@~(a~\#~[]))% |
314 ~~~~~(rev~ys~@~rev~list)~@~(a~\#~[])~=~rev~ys~@~(rev~list~@~(a~\#~[]))% |
315 \end{isabellepar}% |
315 \end{isabelle} |
316 and the missing lemma is associativity of \isa{\at}. |
316 and the missing lemma is associativity of \isa{\at}. |
317 |
317 *} |
318 \subsubsection*{Third lemma: \texttt{(xs \at~ys) \at~zs = xs \at~(ys \at~zs)}} |
318 (*<*)oops(*>*) |
319 |
319 |
|
320 subsubsection{*Third lemma: \texttt{(xs \at~ys) \at~zs = xs \at~(ys \at~zs)}*} |
|
321 |
|
322 text{* |
320 Abandoning the previous proof, the canonical proof procedure |
323 Abandoning the previous proof, the canonical proof procedure |
321 *} |
324 *} |
322 |
325 |
323 |
|
324 txt_raw{*\begin{comment}*} |
|
325 oops |
|
326 text_raw{*\end{comment}*} |
|
327 |
|
328 lemma app_assoc [simp]: "(xs @ ys) @ zs = xs @ (ys @ zs)"; |
326 lemma app_assoc [simp]: "(xs @ ys) @ zs = xs @ (ys @ zs)"; |
329 apply(induct_tac xs); |
327 apply(induct_tac xs); |
330 by(auto); |
328 by(auto); |
331 |
329 |
332 text{* |
330 text{* |
333 \noindent |
331 \noindent |
334 succeeds without further ado. |
332 succeeds without further ado. |
335 |
|
336 Now we can go back and prove the first lemma |
333 Now we can go back and prove the first lemma |
337 *} |
334 *} |
338 |
335 |
339 lemma rev_app [simp]: "rev(xs @ ys) = (rev ys) @ (rev xs)"; |
336 lemma rev_app [simp]: "rev(xs @ ys) = (rev ys) @ (rev xs)"; |
340 apply(induct_tac xs); |
337 apply(induct_tac xs); |