equal
deleted
inserted
replaced
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 |