doc-src/TutorialI/ToyList/ToyList.thy
changeset 9723 a977245dfc8a
parent 9541 d17c0b34d5c8
child 9792 bbefb6ce5cb2
equal deleted inserted replaced
9722:a5f86aed785b 9723:a977245dfc8a
   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);