doc-src/TutorialI/Misc/document/simp.tex
changeset 10171 59d6633835fa
parent 9933 9feb1e0c4cb3
child 10187 0376cccd9118
equal deleted inserted replaced
10170:dfff821d2949 10171:59d6633835fa
    79 \index{simplification!with/of assumptions}
    79 \index{simplification!with/of assumptions}
    80 By default, assumptions are part of the simplification process: they are used
    80 By default, assumptions are part of the simplification process: they are used
    81 as simplification rules and are simplified themselves. For example:%
    81 as simplification rules and are simplified themselves. For example:%
    82 \end{isamarkuptext}%
    82 \end{isamarkuptext}%
    83 \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
    83 \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
    84 \isacommand{by}\ simp%
    84 \isacommand{apply}\ simp\isanewline
       
    85 \isacommand{done}%
    85 \begin{isamarkuptext}%
    86 \begin{isamarkuptext}%
    86 \noindent
    87 \noindent
    87 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn
    88 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn
    88 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the
    89 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the
    89 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}.
    90 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}.
    98 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}} extracted from the assumption
    99 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}} extracted from the assumption
    99 does not terminate. Isabelle notices certain simple forms of
   100 does not terminate. Isabelle notices certain simple forms of
   100 nontermination but not this one. The problem can be circumvented by
   101 nontermination but not this one. The problem can be circumvented by
   101 explicitly telling the simplifier to ignore the assumptions:%
   102 explicitly telling the simplifier to ignore the assumptions:%
   102 \end{isamarkuptxt}%
   103 \end{isamarkuptxt}%
   103 \isacommand{by}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}%
   104 \isacommand{apply}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline
       
   105 \isacommand{done}%
   104 \begin{isamarkuptext}%
   106 \begin{isamarkuptext}%
   105 \noindent
   107 \noindent
   106 There are three options that influence the treatment of assumptions:
   108 There are three options that influence the treatment of assumptions:
   107 \begin{description}
   109 \begin{description}
   108 \item[\isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}}]\indexbold{*no_asm}
   110 \item[\isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}}]\indexbold{*no_asm}
   150 \noindent
   152 \noindent
   151 In this particular case, the resulting goal
   153 In this particular case, the resulting goal
   152 \begin{isabelle}
   154 \begin{isabelle}
   153 ~1.~A~{\isasymand}~{\isasymnot}~{\isasymnot}~A~{\isasymor}~{\isasymnot}~A~{\isasymand}~{\isasymnot}~A%
   155 ~1.~A~{\isasymand}~{\isasymnot}~{\isasymnot}~A~{\isasymor}~{\isasymnot}~A~{\isasymand}~{\isasymnot}~A%
   154 \end{isabelle}
   156 \end{isabelle}
   155 can be proved by simplification. Thus we could have proved the lemma outright%
   157 can be proved by simplification. Thus we could have proved the lemma outright by%
   156 \end{isamarkuptxt}%
   158 \end{isamarkuptxt}%
   157 \isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ exor{\isacharunderscore}def{\isacharparenright}%
   159 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ exor{\isacharunderscore}def{\isacharparenright}%
   158 \begin{isamarkuptext}%
   160 \begin{isamarkuptext}%
   159 \noindent
   161 \noindent
   160 Of course we can also unfold definitions in the middle of a proof.
   162 Of course we can also unfold definitions in the middle of a proof.
   161 
   163 
   162 You should normally not turn a definition permanently into a simplification
   164 You should normally not turn a definition permanently into a simplification
   178 \isa{let}-\isa{in} is just syntactic sugar for a predefined constant
   180 \isa{let}-\isa{in} is just syntactic sugar for a predefined constant
   179 (called \isa{Let}), expanding \isa{let}-constructs means rewriting with
   181 (called \isa{Let}), expanding \isa{let}-constructs means rewriting with
   180 \isa{Let{\isacharunderscore}def}:%
   182 \isa{Let{\isacharunderscore}def}:%
   181 \end{isamarkuptext}%
   183 \end{isamarkuptext}%
   182 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequote}\isanewline
   184 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequote}\isanewline
   183 \isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}%
   185 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline
       
   186 \isacommand{done}%
   184 \begin{isamarkuptext}%
   187 \begin{isamarkuptext}%
   185 If, in a particular context, there is no danger of a combinatorial explosion
   188 If, in a particular context, there is no danger of a combinatorial explosion
   186 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by
   189 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by
   187 default:%
   190 default:%
   188 \end{isamarkuptext}%
   191 \end{isamarkuptext}%
   192 \begin{isamarkuptext}%
   195 \begin{isamarkuptext}%
   193 So far all examples of rewrite rules were equations. The simplifier also
   196 So far all examples of rewrite rules were equations. The simplifier also
   194 accepts \emph{conditional} equations, for example%
   197 accepts \emph{conditional} equations, for example%
   195 \end{isamarkuptext}%
   198 \end{isamarkuptext}%
   196 \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
   199 \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
   197 \isacommand{by}{\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}%
   200 \isacommand{apply}{\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline
       
   201 \isacommand{done}%
   198 \begin{isamarkuptext}%
   202 \begin{isamarkuptext}%
   199 \noindent
   203 \noindent
   200 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a
   204 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a
   201 sequence of methods. Assuming that the simplification rule
   205 sequence of methods. Assuming that the simplification rule
   202 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}}
   206 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}}
   257 In contrast to \isa{if}-expressions, the simplifier does not split
   261 In contrast to \isa{if}-expressions, the simplifier does not split
   258 \isa{case}-expressions by default because this can lead to nontermination
   262 \isa{case}-expressions by default because this can lead to nontermination
   259 in case of recursive datatypes. Again, if the \isa{only{\isacharcolon}} modifier is
   263 in case of recursive datatypes. Again, if the \isa{only{\isacharcolon}} modifier is
   260 dropped, the above goal is solved,%
   264 dropped, the above goal is solved,%
   261 \end{isamarkuptext}%
   265 \end{isamarkuptext}%
   262 \isacommand{by}{\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}%
   266 \isacommand{apply}{\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}%
   263 \begin{isamarkuptext}%
   267 \begin{isamarkuptext}%
   264 \noindent%
   268 \noindent%
   265 which \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not do.
   269 which \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not do.
   266 
   270 
   267 In general, every datatype $t$ comes with a theorem
   271 In general, every datatype $t$ comes with a theorem