diff -r 11aa41ed306d -r 1eced27ee0e1 doc-src/TutorialI/Inductive/document/AB.tex --- a/doc-src/TutorialI/Inductive/document/AB.tex Sun Aug 28 19:42:10 2005 +0200 +++ b/doc-src/TutorialI/Inductive/document/AB.tex Sun Aug 28 19:42:19 2005 +0200 @@ -7,6 +7,7 @@ \endisadelimtheory % \isatagtheory +\isamarkupfalse% % \endisatagtheory {\isafoldtheory}% @@ -14,7 +15,6 @@ \isadelimtheory % \endisadelimtheory -\isamarkuptrue% % \isamarkupsection{Case Study: A Context Free Grammar% } @@ -41,77 +41,77 @@ We start by fixing the alphabet, which consists only of \isa{a}'s and~\isa{b}'s:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{datatype}\ alfa\ {\isacharequal}\ a\ {\isacharbar}\ b\isamarkuptrue% -% +\isamarkuptrue% +\isacommand{datatype}\isamarkupfalse% +\ alfa\ {\isacharequal}\ a\ {\isacharbar}\ b% \begin{isamarkuptext}% \noindent For convenience we include the following easy lemmas as simplification rules:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x\ {\isasymnoteq}\ a{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharequal}\ b{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}x\ {\isasymnoteq}\ b{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharequal}\ a{\isacharparenright}{\isachardoublequote}\isanewline +\isamarkuptrue% +\isacommand{lemma}\isamarkupfalse% +\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}x\ {\isasymnoteq}\ a{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharequal}\ b{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}x\ {\isasymnoteq}\ b{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharequal}\ a{\isacharparenright}{\isachardoublequoteclose}\isanewline % \isadelimproof % \endisadelimproof % \isatagproof -\isamarkupfalse% -\isacommand{by}\ {\isacharparenleft}case{\isacharunderscore}tac\ x{\isacharcomma}\ auto{\isacharparenright}% +\isacommand{by}\isamarkupfalse% +\ {\isacharparenleft}case{\isacharunderscore}tac\ x{\isacharcomma}\ auto{\isacharparenright}% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% \noindent Words over this alphabet are of type \isa{alfa\ list}, and the three nonterminals are declared as sets of such words:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{consts}\ S\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}alfa\ list\ set{\isachardoublequote}\isanewline -\ \ \ \ \ \ \ A\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}alfa\ list\ set{\isachardoublequote}\isanewline -\ \ \ \ \ \ \ B\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}alfa\ list\ set{\isachardoublequote}\isamarkuptrue% -% +\isamarkuptrue% +\isacommand{consts}\isamarkupfalse% +\ S\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}alfa\ list\ set{\isachardoublequoteclose}\isanewline +\ \ \ \ \ \ \ A\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}alfa\ list\ set{\isachardoublequoteclose}\isanewline +\ \ \ \ \ \ \ B\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}alfa\ list\ set{\isachardoublequoteclose}% \begin{isamarkuptext}% \noindent The productions above are recast as a \emph{mutual} inductive definition\index{inductive definition!simultaneous} of \isa{S}, \isa{A} and~\isa{B}:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{inductive}\ S\ A\ B\isanewline +\isamarkuptrue% +\isacommand{inductive}\isamarkupfalse% +\ S\ A\ B\isanewline \isakeyword{intros}\isanewline -\ \ {\isachardoublequote}{\isacharbrackleft}{\isacharbrackright}\ {\isasymin}\ S{\isachardoublequote}\isanewline -\ \ {\isachardoublequote}w\ {\isasymin}\ A\ {\isasymLongrightarrow}\ b{\isacharhash}w\ {\isasymin}\ S{\isachardoublequote}\isanewline -\ \ {\isachardoublequote}w\ {\isasymin}\ B\ {\isasymLongrightarrow}\ a{\isacharhash}w\ {\isasymin}\ S{\isachardoublequote}\isanewline +\ \ {\isachardoublequoteopen}{\isacharbrackleft}{\isacharbrackright}\ {\isasymin}\ S{\isachardoublequoteclose}\isanewline +\ \ {\isachardoublequoteopen}w\ {\isasymin}\ A\ {\isasymLongrightarrow}\ b{\isacharhash}w\ {\isasymin}\ S{\isachardoublequoteclose}\isanewline +\ \ {\isachardoublequoteopen}w\ {\isasymin}\ B\ {\isasymLongrightarrow}\ a{\isacharhash}w\ {\isasymin}\ S{\isachardoublequoteclose}\isanewline \isanewline -\ \ {\isachardoublequote}w\ {\isasymin}\ S\ \ \ \ \ \ \ \ {\isasymLongrightarrow}\ a{\isacharhash}w\ \ \ {\isasymin}\ A{\isachardoublequote}\isanewline -\ \ {\isachardoublequote}{\isasymlbrakk}\ v{\isasymin}A{\isacharsemicolon}\ w{\isasymin}A\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ b{\isacharhash}v{\isacharat}w\ {\isasymin}\ A{\isachardoublequote}\isanewline +\ \ {\isachardoublequoteopen}w\ {\isasymin}\ S\ \ \ \ \ \ \ \ {\isasymLongrightarrow}\ a{\isacharhash}w\ \ \ {\isasymin}\ A{\isachardoublequoteclose}\isanewline +\ \ {\isachardoublequoteopen}{\isasymlbrakk}\ v{\isasymin}A{\isacharsemicolon}\ w{\isasymin}A\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ b{\isacharhash}v{\isacharat}w\ {\isasymin}\ A{\isachardoublequoteclose}\isanewline \isanewline -\ \ {\isachardoublequote}w\ {\isasymin}\ S\ \ \ \ \ \ \ \ \ \ \ \ {\isasymLongrightarrow}\ b{\isacharhash}w\ \ \ {\isasymin}\ B{\isachardoublequote}\isanewline -\ \ {\isachardoublequote}{\isasymlbrakk}\ v\ {\isasymin}\ B{\isacharsemicolon}\ w\ {\isasymin}\ B\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ a{\isacharhash}v{\isacharat}w\ {\isasymin}\ B{\isachardoublequote}\isamarkuptrue% -% +\ \ {\isachardoublequoteopen}w\ {\isasymin}\ S\ \ \ \ \ \ \ \ \ \ \ \ {\isasymLongrightarrow}\ b{\isacharhash}w\ \ \ {\isasymin}\ B{\isachardoublequoteclose}\isanewline +\ \ {\isachardoublequoteopen}{\isasymlbrakk}\ v\ {\isasymin}\ B{\isacharsemicolon}\ w\ {\isasymin}\ B\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ a{\isacharhash}v{\isacharat}w\ {\isasymin}\ B{\isachardoublequoteclose}% \begin{isamarkuptext}% \noindent First we show that all words in \isa{S} contain the same number of \isa{a}'s and \isa{b}'s. Since the definition of \isa{S} is by mutual induction, so is the proof: we show at the same time that all words in \isa{A} contain one more \isa{a} than \isa{b} and all words in \isa{B} contains one more \isa{b} than \isa{a}.% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{lemma}\ correctness{\isacharcolon}\isanewline -\ \ {\isachardoublequote}{\isacharparenleft}w\ {\isasymin}\ S\ {\isasymlongrightarrow}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}{\isacharparenright}\ \ \ \ \ {\isasymand}\isanewline +\isamarkuptrue% +\isacommand{lemma}\isamarkupfalse% +\ correctness{\isacharcolon}\isanewline +\ \ {\isachardoublequoteopen}{\isacharparenleft}w\ {\isasymin}\ S\ {\isasymlongrightarrow}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}{\isacharparenright}\ \ \ \ \ {\isasymand}\isanewline \ \ \ {\isacharparenleft}w\ {\isasymin}\ A\ {\isasymlongrightarrow}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}{\isacharparenright}\ {\isasymand}\isanewline -\ \ \ {\isacharparenleft}w\ {\isasymin}\ B\ {\isasymlongrightarrow}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}{\isacharparenright}{\isachardoublequote}% +\ \ \ {\isacharparenleft}w\ {\isasymin}\ B\ {\isasymlongrightarrow}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}{\isacharparenright}{\isachardoublequoteclose}% \isadelimproof % \endisadelimproof % \isatagproof -\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -120,15 +120,15 @@ The proof itself is by rule induction and afterwards automatic:% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{by}\ {\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}induct{\isacharcomma}\ auto{\isacharparenright}% +\isamarkuptrue% +\isacommand{by}\isamarkupfalse% +\ {\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}induct{\isacharcomma}\ auto{\isacharparenright}% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -164,16 +164,16 @@ to prove the desired lemma twice, once as stated above and once with the roles of \isa{a}'s and \isa{b}'s interchanged.% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{lemma}\ step{\isadigit{1}}{\isacharcolon}\ {\isachardoublequote}{\isasymforall}i\ {\isacharless}\ size\ w{\isachardot}\isanewline +\isamarkuptrue% +\isacommand{lemma}\isamarkupfalse% +\ step{\isadigit{1}}{\isacharcolon}\ {\isachardoublequoteopen}{\isasymforall}i\ {\isacharless}\ size\ w{\isachardot}\isanewline \ \ {\isasymbar}{\isacharparenleft}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ {\isacharparenleft}i{\isacharplus}{\isadigit{1}}{\isacharparenright}\ w{\isachardot}\ P\ x{\isacharbrackright}{\isacharparenright}{\isacharminus}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ {\isacharparenleft}i{\isacharplus}{\isadigit{1}}{\isacharparenright}\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharparenright}{\isacharparenright}\isanewline -\ \ \ {\isacharminus}\ {\isacharparenleft}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ P\ x{\isacharbrackright}{\isacharparenright}{\isacharminus}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharparenright}{\isacharparenright}{\isasymbar}\ {\isasymle}\ {\isadigit{1}}{\isachardoublequote}% +\ \ \ {\isacharminus}\ {\isacharparenleft}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ P\ x{\isacharbrackright}{\isacharparenright}{\isacharminus}int{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharparenright}{\isacharparenright}{\isasymbar}\ {\isasymle}\ {\isadigit{1}}{\isachardoublequoteclose}% \isadelimproof % \endisadelimproof % \isatagproof -\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -188,33 +188,33 @@ so trivial induction step. Since it is essentially just arithmetic, we do not discuss it.% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ w{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}auto\ simp\ add{\isacharcolon}\ abs{\isacharunderscore}if\ take{\isacharunderscore}Cons\ split{\isacharcolon}\ nat{\isachardot}split{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{done}% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}induct{\isacharunderscore}tac\ w{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}auto\ simp\ add{\isacharcolon}\ abs{\isacharunderscore}if\ take{\isacharunderscore}Cons\ split{\isacharcolon}\ nat{\isachardot}split{\isacharparenright}\isanewline +\isacommand{done}\isamarkupfalse% +% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% Finally we come to the above-mentioned lemma about cutting in half a word with two more elements of one sort than of the other sort:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{lemma}\ part{\isadigit{1}}{\isacharcolon}\isanewline -\ {\isachardoublequote}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{2}}\ {\isasymLongrightarrow}\isanewline -\ \ {\isasymexists}i{\isasymle}size\ w{\isachardot}\ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{1}}{\isachardoublequote}% +\isamarkuptrue% +\isacommand{lemma}\isamarkupfalse% +\ part{\isadigit{1}}{\isacharcolon}\isanewline +\ {\isachardoublequoteopen}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{2}}\ {\isasymLongrightarrow}\isanewline +\ \ {\isasymexists}i{\isasymle}size\ w{\isachardot}\ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{1}}{\isachardoublequoteclose}% \isadelimproof % \endisadelimproof % \isatagproof -\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -222,17 +222,17 @@ instantiated appropriately and with its first premise disposed of by lemma \isa{step{\isadigit{1}}}:% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}insert\ nat{\isadigit{0}}{\isacharunderscore}intermed{\isacharunderscore}int{\isacharunderscore}val{\isacharbrackleft}OF\ step{\isadigit{1}}{\isacharcomma}\ of\ {\isachardoublequote}P{\isachardoublequote}\ {\isachardoublequote}w{\isachardoublequote}\ {\isachardoublequote}{\isadigit{1}}{\isachardoublequote}{\isacharbrackright}{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{by}\ force% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}insert\ nat{\isadigit{0}}{\isacharunderscore}intermed{\isacharunderscore}int{\isacharunderscore}val{\isacharbrackleft}OF\ step{\isadigit{1}}{\isacharcomma}\ of\ {\isachardoublequoteopen}P{\isachardoublequoteclose}\ {\isachardoublequoteopen}w{\isachardoublequoteclose}\ {\isachardoublequoteopen}{\isadigit{1}}{\isachardoublequoteclose}{\isacharbrackright}{\isacharparenright}\isanewline +\isacommand{by}\isamarkupfalse% +\ force% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -240,27 +240,27 @@ Lemma \isa{part{\isadigit{1}}} tells us only about the prefix \isa{take\ i\ w}. An easy lemma deals with the suffix \isa{drop\ i\ w}:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{lemma}\ part{\isadigit{2}}{\isacharcolon}\isanewline -\ \ {\isachardoublequote}{\isasymlbrakk}size{\isacharbrackleft}x{\isasymin}take\ i\ w\ {\isacharat}\ drop\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\isanewline +\isamarkuptrue% +\isacommand{lemma}\isamarkupfalse% +\ part{\isadigit{2}}{\isacharcolon}\isanewline +\ \ {\isachardoublequoteopen}{\isasymlbrakk}size{\isacharbrackleft}x{\isasymin}take\ i\ w\ {\isacharat}\ drop\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\isanewline \ \ \ \ size{\isacharbrackleft}x{\isasymin}take\ i\ w\ {\isacharat}\ drop\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{2}}{\isacharsemicolon}\isanewline \ \ \ \ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}take\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{1}}{\isasymrbrakk}\isanewline -\ \ \ {\isasymLongrightarrow}\ size{\isacharbrackleft}x{\isasymin}drop\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}drop\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{1}}{\isachardoublequote}\isanewline +\ \ \ {\isasymLongrightarrow}\ size{\isacharbrackleft}x{\isasymin}drop\ i\ w{\isachardot}\ P\ x{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}drop\ i\ w{\isachardot}\ {\isasymnot}P\ x{\isacharbrackright}{\isacharplus}{\isadigit{1}}{\isachardoublequoteclose}\isanewline % \isadelimproof % \endisadelimproof % \isatagproof -\isamarkupfalse% -\isacommand{by}{\isacharparenleft}simp\ del{\isacharcolon}\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharparenright}% +\isacommand{by}\isamarkupfalse% +{\isacharparenleft}simp\ del{\isacharcolon}\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharparenright}% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -277,9 +277,9 @@ To dispose of trivial cases automatically, the rules of the inductive definition are declared simplification rules:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{declare}\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharbrackleft}simp{\isacharbrackright}\isamarkuptrue% -% +\isamarkuptrue% +\isacommand{declare}\isamarkupfalse% +\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharbrackleft}simp{\isacharbrackright}% \begin{isamarkuptext}% \noindent This could have been done earlier but was not necessary so far. @@ -288,17 +288,17 @@ \isa{a}'s and \isa{b}'s, then it is in \isa{S}, and similarly for \isa{A} and \isa{B}:% \end{isamarkuptext}% -\isamarkupfalse% -\isacommand{theorem}\ completeness{\isacharcolon}\isanewline -\ \ {\isachardoublequote}{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ \ \ \ \ {\isasymlongrightarrow}\ w\ {\isasymin}\ S{\isacharparenright}\ {\isasymand}\isanewline +\isamarkuptrue% +\isacommand{theorem}\isamarkupfalse% +\ completeness{\isacharcolon}\isanewline +\ \ {\isachardoublequoteopen}{\isacharparenleft}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ \ \ \ \ {\isasymlongrightarrow}\ w\ {\isasymin}\ S{\isacharparenright}\ {\isasymand}\isanewline \ \ \ {\isacharparenleft}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}\ {\isasymlongrightarrow}\ w\ {\isasymin}\ A{\isacharparenright}\ {\isasymand}\isanewline -\ \ \ {\isacharparenleft}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}\ {\isasymlongrightarrow}\ w\ {\isasymin}\ B{\isacharparenright}{\isachardoublequote}% +\ \ \ {\isacharparenleft}size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}b{\isacharbrackright}\ {\isacharequal}\ size{\isacharbrackleft}x{\isasymin}w{\isachardot}\ x{\isacharequal}a{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}\ {\isasymlongrightarrow}\ w\ {\isasymin}\ B{\isacharparenright}{\isachardoublequoteclose}% \isadelimproof % \endisadelimproof % \isatagproof -\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -307,8 +307,9 @@ merely appending a single letter at the front. Hence we induct on the length of \isa{w}, using the induction rule \isa{length{\isacharunderscore}induct}:% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ w\ rule{\isacharcolon}\ length{\isacharunderscore}induct{\isacharparenright}\isamarkuptrue% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}induct{\isacharunderscore}tac\ w\ rule{\isacharcolon}\ length{\isacharunderscore}induct{\isacharparenright}\isamarkupfalse% % \begin{isamarkuptxt}% \noindent @@ -320,10 +321,11 @@ The proof continues with a case distinction on \isa{w}, on whether \isa{w} is empty or not.% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}case{\isacharunderscore}tac\ w{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}simp{\isacharunderscore}all{\isacharparenright}\isamarkuptrue% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}case{\isacharunderscore}tac\ w{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}simp{\isacharunderscore}all{\isacharparenright}\isamarkupfalse% % \begin{isamarkuptxt}% \noindent @@ -338,15 +340,15 @@ After breaking the conjunction up into two cases, we can apply \isa{part{\isadigit{1}}} to the assumption that \isa{w} contains two more \isa{a}'s than \isa{b}'s.% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}rule\ conjI{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}clarify{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}frule\ part{\isadigit{1}}{\isacharbrackleft}of\ {\isachardoublequote}{\isasymlambda}x{\isachardot}\ x{\isacharequal}a{\isachardoublequote}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}clarify{\isacharparenright}\isamarkuptrue% -% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}rule\ conjI{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}clarify{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}frule\ part{\isadigit{1}}{\isacharbrackleft}of\ {\isachardoublequoteopen}{\isasymlambda}x{\isachardot}\ x{\isacharequal}a{\isachardoublequoteclose}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}clarify{\isacharparenright}% \begin{isamarkuptxt}% \noindent This yields an index \isa{i\ {\isasymle}\ length\ v} such that @@ -358,19 +360,19 @@ \ \ \ \ \ length\ {\isacharbrackleft}x{\isasymin}drop\ i\ v\ {\isachardot}\ x\ {\isacharequal}\ a{\isacharbrackright}\ {\isacharequal}\ length\ {\isacharbrackleft}x{\isasymin}drop\ i\ v\ {\isachardot}\ x\ {\isacharequal}\ b{\isacharbrackright}\ {\isacharplus}\ {\isadigit{1}}% \end{isabelle}% \end{isamarkuptxt}% -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}drule\ part{\isadigit{2}}{\isacharbrackleft}of\ {\isachardoublequote}{\isasymlambda}x{\isachardot}\ x{\isacharequal}a{\isachardoublequote}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline -\ \ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}assumption{\isacharparenright}\isamarkuptrue% -% +\isamarkuptrue% +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}drule\ part{\isadigit{2}}{\isacharbrackleft}of\ {\isachardoublequoteopen}{\isasymlambda}x{\isachardot}\ x{\isacharequal}a{\isachardoublequoteclose}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline +\ \ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}assumption{\isacharparenright}% \begin{isamarkuptxt}% \noindent Now it is time to decompose \isa{v} in the conclusion \isa{b\ {\isacharhash}\ v\ {\isasymin}\ A} into \isa{take\ i\ v\ {\isacharat}\ drop\ i\ v},% \end{isamarkuptxt}% -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}rule{\isacharunderscore}tac\ n{\isadigit{1}}{\isacharequal}i\ \isakeyword{and}\ t{\isacharequal}v\ \isakeyword{in}\ subst{\isacharbrackleft}OF\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharbrackright}{\isacharparenright}\isamarkuptrue% -% +\isamarkuptrue% +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}rule{\isacharunderscore}tac\ n{\isadigit{1}}{\isacharequal}i\ \isakeyword{and}\ t{\isacharequal}v\ \isakeyword{in}\ subst{\isacharbrackleft}OF\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharbrackright}{\isacharparenright}% \begin{isamarkuptxt}% \noindent (the variables \isa{n{\isadigit{1}}} and \isa{t} are the result of composing the @@ -378,45 +380,45 @@ after which the appropriate rule of the grammar reduces the goal to the two subgoals \isa{take\ i\ v\ {\isasymin}\ A} and \isa{drop\ i\ v\ {\isasymin}\ A}:% \end{isamarkuptxt}% -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharparenright}\isamarkuptrue% -% +\isamarkuptrue% +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharparenright}% \begin{isamarkuptxt}% Both subgoals follow from the induction hypothesis because both \isa{take\ i\ v} and \isa{drop\ i\ v} are shorter than \isa{w}:% \end{isamarkuptxt}% -\ \ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}force\ split\ add{\isacharcolon}\ nat{\isacharunderscore}diff{\isacharunderscore}split{\isacharparenright}\isamarkuptrue% -% +\isamarkuptrue% +\ \ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}force\ split\ add{\isacharcolon}\ nat{\isacharunderscore}diff{\isacharunderscore}split{\isacharparenright}% \begin{isamarkuptxt}% The case \isa{w\ {\isacharequal}\ b\ {\isacharhash}\ v} is proved analogously:% \end{isamarkuptxt}% -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}clarify{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}frule\ part{\isadigit{1}}{\isacharbrackleft}of\ {\isachardoublequote}{\isasymlambda}x{\isachardot}\ x{\isacharequal}b{\isachardoublequote}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}clarify{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}drule\ part{\isadigit{2}}{\isacharbrackleft}of\ {\isachardoublequote}{\isasymlambda}x{\isachardot}\ x{\isacharequal}b{\isachardoublequote}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}assumption{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}rule{\isacharunderscore}tac\ n{\isadigit{1}}{\isacharequal}i\ \isakeyword{and}\ t{\isacharequal}v\ \isakeyword{in}\ subst{\isacharbrackleft}OF\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharbrackright}{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{apply}{\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharparenright}\isanewline -\ \isamarkupfalse% -\isacommand{apply}{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj{\isacharparenright}\isanewline -\isamarkupfalse% -\isacommand{by}{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj\ split\ add{\isacharcolon}\ nat{\isacharunderscore}diff{\isacharunderscore}split{\isacharparenright}% +\isamarkuptrue% +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}clarify{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}frule\ part{\isadigit{1}}{\isacharbrackleft}of\ {\isachardoublequoteopen}{\isasymlambda}x{\isachardot}\ x{\isacharequal}b{\isachardoublequoteclose}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}clarify{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}drule\ part{\isadigit{2}}{\isacharbrackleft}of\ {\isachardoublequoteopen}{\isasymlambda}x{\isachardot}\ x{\isacharequal}b{\isachardoublequoteclose}{\isacharcomma}\ simplified{\isacharbrackright}{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}assumption{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}rule{\isacharunderscore}tac\ n{\isadigit{1}}{\isacharequal}i\ \isakeyword{and}\ t{\isacharequal}v\ \isakeyword{in}\ subst{\isacharbrackleft}OF\ append{\isacharunderscore}take{\isacharunderscore}drop{\isacharunderscore}id{\isacharbrackright}{\isacharparenright}\isanewline +\isacommand{apply}\isamarkupfalse% +{\isacharparenleft}rule\ S{\isacharunderscore}A{\isacharunderscore}B{\isachardot}intros{\isacharparenright}\isanewline +\ \isacommand{apply}\isamarkupfalse% +{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj{\isacharparenright}\isanewline +\isacommand{by}\isamarkupfalse% +{\isacharparenleft}force\ simp\ add{\isacharcolon}\ min{\isacharunderscore}less{\isacharunderscore}iff{\isacharunderscore}disj\ split\ add{\isacharcolon}\ nat{\isacharunderscore}diff{\isacharunderscore}split{\isacharparenright}% \endisatagproof {\isafoldproof}% % \isadelimproof % \endisadelimproof -\isamarkuptrue% % \begin{isamarkuptext}% We conclude this section with a comparison of our proof with @@ -443,12 +445,14 @@ are scrutinized formally.% \index{grammars!defining inductively|)}% \end{isamarkuptext}% +\isamarkuptrue% % \isadelimtheory % \endisadelimtheory % \isatagtheory +\isamarkupfalse% % \endisatagtheory {\isafoldtheory}%