doc-src/TutorialI/Misc/document/simp.tex
author nipkow
Wed, 11 Oct 2000 10:44:42 +0200
changeset 10187 0376cccd9118
parent 10171 59d6633835fa
child 10362 c6b197ccf1f1
permissions -rw-r--r--
*** empty log message ***
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9924
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
     1
%
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
     2
\begin{isabellebody}%
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
     3
\def\isabellecontext{simp}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     4
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     5
\isamarkupsubsubsection{Simplification rules}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     6
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     7
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     8
\indexbold{simplification rule}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
     9
To facilitate simplification, theorems can be declared to be simplification
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    10
rules (with the help of the attribute \isa{{\isacharbrackleft}simp{\isacharbrackright}}\index{*simp
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    11
  (attribute)}), in which case proofs by simplification make use of these
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    12
rules automatically. In addition the constructs \isacommand{datatype} and
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    13
\isacommand{primrec} (and a few others) invisibly declare useful
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    14
simplification rules. Explicit definitions are \emph{not} declared
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    15
simplification rules automatically!
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    16
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    17
Not merely equations but pretty much any theorem can become a simplification
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    18
rule. The simplifier will try to make sense of it.  For example, a theorem
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    19
\isa{{\isasymnot}\ P} is automatically turned into \isa{P\ {\isacharequal}\ False}. The details
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    20
are explained in \S\ref{sec:SimpHow}.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    21
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    22
The simplification attribute of theorems can be turned on and off as follows:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    23
\begin{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    24
\isacommand{declare} \textit{theorem-name}\isa{{\isacharbrackleft}simp{\isacharbrackright}}\\
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    25
\isacommand{declare} \textit{theorem-name}\isa{{\isacharbrackleft}simp\ del{\isacharbrackright}}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    26
\end{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    27
As a rule of thumb, equations that really simplify (like \isa{rev\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs} and \isa{xs\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ xs}) should be made simplification
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    28
rules.  Those of a more specific nature (e.g.\ distributivity laws, which
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    29
alter the structure of terms considerably) should only be used selectively,
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    30
i.e.\ they should not be default simplification rules.  Conversely, it may
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    31
also happen that a simplification rule needs to be disabled in certain
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    32
proofs.  Frequent changes in the simplification status of a theorem may
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    33
indicate a badly designed theory.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    34
\begin{warn}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    35
  Simplification may not terminate, for example if both $f(x) = g(x)$ and
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    36
  $g(x) = f(x)$ are simplification rules. It is the user's responsibility not
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    37
  to include simplification rules that can lead to nontermination, either on
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    38
  their own or in combination with other simplification rules.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    39
\end{warn}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    40
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    41
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    42
\isamarkupsubsubsection{The simplification method}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    43
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    44
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    45
\index{*simp (method)|bold}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    46
The general format of the simplification method is
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    47
\begin{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    48
\isa{simp} \textit{list of modifiers}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    49
\end{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    50
where the list of \emph{modifiers} helps to fine tune the behaviour and may
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    51
be empty. Most if not all of the proofs seen so far could have been performed
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    52
with \isa{simp} instead of \isa{auto}, except that \isa{simp} attacks
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    53
only the first subgoal and may thus need to be repeated---use
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    54
\isaindex{simp_all} to simplify all subgoals.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    55
Note that \isa{simp} fails if nothing changes.%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    56
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    57
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    58
\isamarkupsubsubsection{Adding and deleting simplification rules}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    59
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    60
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    61
If a certain theorem is merely needed in a few proofs by simplification,
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    62
we do not need to make it a global simplification rule. Instead we can modify
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    63
the set of simplification rules used in a simplification step by adding rules
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    64
to it and/or deleting rules from it. The two modifiers for this are
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    65
\begin{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    66
\isa{add{\isacharcolon}} \textit{list of theorem names}\\
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    67
\isa{del{\isacharcolon}} \textit{list of theorem names}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    68
\end{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    69
In case you want to use only a specific list of theorems and ignore all
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    70
others:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    71
\begin{quote}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    72
\isa{only{\isacharcolon}} \textit{list of theorem names}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    73
\end{quote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    74
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    75
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    76
\isamarkupsubsubsection{Assumptions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    77
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    78
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    79
\index{simplification!with/of assumptions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    80
By default, assumptions are part of the simplification process: they are used
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    81
as simplification rules and are simplified themselves. For example:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    82
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    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
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
    84
\isacommand{apply}\ simp\isanewline
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
    85
\isacommand{done}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    86
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    87
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    88
The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    89
simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    90
conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    91
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    92
In some cases this may be too much of a good thing and may lead to
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    93
nontermination:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    94
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    95
\isacommand{lemma}\ {\isachardoublequote}{\isasymforall}x{\isachardot}\ f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    96
\begin{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    97
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    98
cannot be solved by an unmodified application of \isa{simp} because the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
    99
simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}} extracted from the assumption
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   100
does not terminate. Isabelle notices certain simple forms of
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   101
nontermination but not this one. The problem can be circumvented by
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   102
explicitly telling the simplifier to ignore the assumptions:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   103
\end{isamarkuptxt}%
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   104
\isacommand{apply}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   105
\isacommand{done}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   106
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   107
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   108
There are three options that influence the treatment of assumptions:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   109
\begin{description}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   110
\item[\isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}}]\indexbold{*no_asm}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   111
 means that assumptions are completely ignored.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   112
\item[\isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}simp{\isacharparenright}}]\indexbold{*no_asm_simp}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   113
 means that the assumptions are not simplified but
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   114
  are used in the simplification of the conclusion.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   115
\item[\isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}use{\isacharparenright}}]\indexbold{*no_asm_use}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   116
 means that the assumptions are simplified but are not
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   117
  used in the simplification of each other or the conclusion.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   118
\end{description}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   119
Neither \isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}simp{\isacharparenright}} nor \isa{{\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}use{\isacharparenright}} allow to simplify
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   120
the above problematic subgoal.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   121
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   122
Note that only one of the above options is allowed, and it must precede all
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   123
other arguments.%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   124
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   125
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   126
\isamarkupsubsubsection{Rewriting with definitions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   127
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   128
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   129
\index{simplification!with definitions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   130
Constant definitions (\S\ref{sec:ConstDefinitions}) can
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   131
be used as simplification rules, but by default they are not.  Hence the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   132
simplifier does not expand them automatically, just as it should be:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   133
definitions are introduced for the purpose of abbreviating complex
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   134
concepts. Of course we need to expand the definitions initially to derive
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   135
enough lemmas that characterize the concept sufficiently for us to forget the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   136
original definition. For example, given%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   137
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   138
\isacommand{constdefs}\ exor\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}bool\ {\isasymRightarrow}\ bool\ {\isasymRightarrow}\ bool{\isachardoublequote}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   139
\ \ \ \ \ \ \ \ \ {\isachardoublequote}exor\ A\ B\ {\isasymequiv}\ {\isacharparenleft}A\ {\isasymand}\ {\isasymnot}B{\isacharparenright}\ {\isasymor}\ {\isacharparenleft}{\isasymnot}A\ {\isasymand}\ B{\isacharparenright}{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   140
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   141
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   142
we may want to prove%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   143
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   144
\isacommand{lemma}\ {\isachardoublequote}exor\ A\ {\isacharparenleft}{\isasymnot}A{\isacharparenright}{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   145
\begin{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   146
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   147
Typically, the opening move consists in \emph{unfolding} the definition(s), which we need to
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   148
get started, but nothing else:\indexbold{*unfold}\indexbold{definition!unfolding}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   149
\end{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   150
\isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}exor{\isacharunderscore}def{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   151
\begin{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   152
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   153
In this particular case, the resulting goal
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   154
\begin{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   155
~1.~A~{\isasymand}~{\isasymnot}~{\isasymnot}~A~{\isasymor}~{\isasymnot}~A~{\isasymand}~{\isasymnot}~A%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   156
\end{isabelle}
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   157
can be proved by simplification. Thus we could have proved the lemma outright by%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   158
\end{isamarkuptxt}%
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   159
\isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ exor{\isacharunderscore}def{\isacharparenright}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   160
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   161
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   162
Of course we can also unfold definitions in the middle of a proof.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   163
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   164
You should normally not turn a definition permanently into a simplification
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   165
rule because this defeats the whole purpose of an abbreviation.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   166
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   167
\begin{warn}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   168
  If you have defined $f\,x\,y~\isasymequiv~t$ then you can only expand
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   169
  occurrences of $f$ with at least two arguments. Thus it is safer to define
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   170
  $f$~\isasymequiv~\isasymlambda$x\,y.\;t$.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   171
\end{warn}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   172
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   173
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   174
\isamarkupsubsubsection{Simplifying let-expressions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   175
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   176
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   177
\index{simplification!of let-expressions}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   178
Proving a goal containing \isaindex{let}-expressions almost invariably
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   179
requires the \isa{let}-con\-structs to be expanded at some point. Since
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   180
\isa{let}-\isa{in} is just syntactic sugar for a predefined constant
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   181
(called \isa{Let}), expanding \isa{let}-constructs means rewriting with
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   182
\isa{Let{\isacharunderscore}def}:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   183
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   184
\isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequote}\isanewline
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   185
\isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   186
\isacommand{done}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   187
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   188
If, in a particular context, there is no danger of a combinatorial explosion
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   189
of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   190
default:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   191
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   192
\isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   193
\isamarkupsubsubsection{Conditional equations}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   194
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   195
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   196
So far all examples of rewrite rules were equations. The simplifier also
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   197
accepts \emph{conditional} equations, for example%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   198
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   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
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   200
\isacommand{apply}{\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   201
\isacommand{done}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   202
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   203
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   204
Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   205
sequence of methods. Assuming that the simplification rule
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   206
\isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   207
is present as well,%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   208
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   209
\isacommand{lemma}\ {\isachardoublequote}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ hd{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ rev\ xs{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   210
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   211
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   212
is proved by plain simplification:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   213
the conditional equation \isa{hd{\isacharunderscore}Cons{\isacharunderscore}tl} above
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   214
can simplify \isa{hd\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl\ {\isacharparenleft}rev\ xs{\isacharparenright}} to \isa{rev\ xs}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   215
because the corresponding precondition \isa{rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   216
simplifies to \isa{xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}, which is exactly the local
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   217
assumption of the subgoal.%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   218
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   219
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   220
\isamarkupsubsubsection{Automatic case splits}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   221
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   222
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   223
\indexbold{case splits}\index{*split|(}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   224
Goals containing \isa{if}-expressions are usually proved by case
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   225
distinction on the condition of the \isa{if}. For example the goal%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   226
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   227
\isacommand{lemma}\ {\isachardoublequote}{\isasymforall}xs{\isachardot}\ if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   228
\begin{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   229
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   230
can be split into
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   231
\begin{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   232
~1.~{\isasymforall}xs.~(xs~=~[]~{\isasymlongrightarrow}~rev~xs~=~[])~{\isasymand}~(xs~{\isasymnoteq}~[]~{\isasymlongrightarrow}~rev~xs~{\isasymnoteq}~[])
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   233
\end{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   234
by a degenerate form of simplification%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   235
\end{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   236
\isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}\ split{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   237
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   238
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   239
where no simplification rules are included (\isa{only{\isacharcolon}} is followed by the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   240
empty list of theorems) but the rule \isaindexbold{split_if} for
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   241
splitting \isa{if}s is added (via the modifier \isa{split{\isacharcolon}}). Because
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   242
case-splitting on \isa{if}s is almost always the right proof strategy, the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   243
simplifier performs it automatically. Try \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   244
on the initial goal above.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   245
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   246
This splitting idea generalizes from \isa{if} to \isaindex{case}:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   247
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   248
\isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}case\ xs\ of\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymRightarrow}\ zs\ {\isacharbar}\ y{\isacharhash}ys\ {\isasymRightarrow}\ y{\isacharhash}{\isacharparenleft}ys{\isacharat}zs{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ xs{\isacharat}zs{\isachardoublequote}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   249
\begin{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   250
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   251
becomes
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   252
\begin{isabelle}\makeatother
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   253
~1.~(xs~=~[]~{\isasymlongrightarrow}~zs~=~xs~@~zs)~{\isasymand}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   254
~~~~({\isasymforall}a~list.~xs~=~a~\#~list~{\isasymlongrightarrow}~a~\#~list~@~zs~=~xs~@~zs)
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   255
\end{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   256
by typing%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   257
\end{isamarkuptxt}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   258
\isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   259
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   260
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   261
In contrast to \isa{if}-expressions, the simplifier does not split
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   262
\isa{case}-expressions by default because this can lead to nontermination
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   263
in case of recursive datatypes. Again, if the \isa{only{\isacharcolon}} modifier is
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   264
dropped, the above goal is solved,%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   265
\end{isamarkuptext}%
10171
59d6633835fa *** empty log message ***
nipkow
parents: 9933
diff changeset
   266
\isacommand{apply}{\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   267
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   268
\noindent%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   269
which \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not do.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   270
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   271
In general, every datatype $t$ comes with a theorem
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   272
$t$\isa{{\isachardot}split} which can be declared to be a \bfindex{split rule} either
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   273
locally as above, or by giving it the \isa{split} attribute globally:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   274
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   275
\isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split{\isacharbrackright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   276
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   277
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   278
The \isa{split} attribute can be removed with the \isa{del} modifier,
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   279
either locally%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   280
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   281
\isacommand{apply}{\isacharparenleft}simp\ split\ del{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   282
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   283
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   284
or globally:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   285
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   286
\isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split\ del{\isacharbrackright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   287
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   288
The above split rules intentionally only affect the conclusion of a
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   289
subgoal.  If you want to split an \isa{if} or \isa{case}-expression in
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   290
the assumptions, you have to apply \isa{split{\isacharunderscore}if{\isacharunderscore}asm} or
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   291
$t$\isa{{\isachardot}split{\isacharunderscore}asm}:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   292
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   293
\isacommand{lemma}\ {\isachardoublequote}if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ ys\ {\isachartilde}{\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ ys\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}{\isacharequal}{\isachargreater}\ xs\ {\isacharat}\ ys\ {\isachartilde}{\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   294
\isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}\ split{\isacharcolon}\ split{\isacharunderscore}if{\isacharunderscore}asm{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   295
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   296
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   297
In contrast to splitting the conclusion, this actually creates two
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   298
separate subgoals (which are solved by \isa{simp{\isacharunderscore}all}):
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   299
\begin{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   300
\ \isadigit{1}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   301
\ \isadigit{2}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ \mbox{xs}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   302
\end{isabelle}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   303
If you need to split both in the assumptions and the conclusion,
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   304
use $t$\isa{{\isachardot}splits} which subsumes $t$\isa{{\isachardot}split} and
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   305
$t$\isa{{\isachardot}split{\isacharunderscore}asm}. Analogously, there is \isa{if{\isacharunderscore}splits}.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   306
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   307
\begin{warn}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   308
  The simplifier merely simplifies the condition of an \isa{if} but not the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   309
  \isa{then} or \isa{else} parts. The latter are simplified only after the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   310
  condition reduces to \isa{True} or \isa{False}, or after splitting. The
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   311
  same is true for \isaindex{case}-expressions: only the selector is
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   312
  simplified at first, until either the expression reduces to one of the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   313
  cases or it is split.
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   314
\end{warn}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   315
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   316
\index{*split|)}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   317
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   318
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   319
\isamarkupsubsubsection{Arithmetic}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   320
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   321
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   322
\index{arithmetic}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   323
The simplifier routinely solves a small class of linear arithmetic formulae
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   324
(over type \isa{nat} and other numeric types): it only takes into account
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   325
assumptions and conclusions that are (possibly negated) (in)equalities
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   326
(\isa{{\isacharequal}}, \isasymle, \isa{{\isacharless}}) and it only knows about addition. Thus%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   327
\end{isamarkuptext}%
10187
0376cccd9118 *** empty log message ***
nipkow
parents: 10171
diff changeset
   328
\isacommand{lemma}\ {\isachardoublequote}{\isasymlbrakk}\ {\isasymnot}\ m\ {\isacharless}\ n{\isacharsemicolon}\ m\ {\isacharless}\ n{\isacharplus}{\isadigit{1}}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ m\ {\isacharequal}\ n{\isachardoublequote}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   329
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   330
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   331
is proved by simplification, whereas the only slightly more complex%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   332
\end{isamarkuptext}%
10187
0376cccd9118 *** empty log message ***
nipkow
parents: 10171
diff changeset
   333
\isacommand{lemma}\ {\isachardoublequote}{\isasymnot}\ m\ {\isacharless}\ n\ {\isasymand}\ m\ {\isacharless}\ n{\isacharplus}{\isadigit{1}}\ {\isasymLongrightarrow}\ m\ {\isacharequal}\ n{\isachardoublequote}%
9933
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   334
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   335
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   336
is not proved by simplification and requires \isa{arith}.%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   337
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   338
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   339
\isamarkupsubsubsection{Tracing}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   340
%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   341
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   342
\indexbold{tracing the simplifier}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   343
Using the simplifier effectively may take a bit of experimentation.  Set the
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   344
\isaindexbold{trace_simp} \rmindex{flag} to get a better idea of what is going
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   345
on:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   346
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   347
\isacommand{ML}\ {\isachardoublequote}set\ trace{\isacharunderscore}simp{\isachardoublequote}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   348
\isacommand{lemma}\ {\isachardoublequote}rev\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   349
\isacommand{apply}{\isacharparenleft}simp{\isacharparenright}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   350
\begin{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   351
\noindent
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   352
produces the trace
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   353
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   354
\begin{ttbox}\makeatother
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   355
Applying instance of rewrite rule:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   356
rev (?x1 \# ?xs1) == rev ?xs1 @ [?x1]
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   357
Rewriting:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   358
rev [x] == rev [] @ [x]
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   359
Applying instance of rewrite rule:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   360
rev [] == []
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   361
Rewriting:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   362
rev [] == []
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   363
Applying instance of rewrite rule:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   364
[] @ ?y == ?y
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   365
Rewriting:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   366
[] @ [x] == [x]
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   367
Applying instance of rewrite rule:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   368
?x3 \# ?t3 = ?t3 == False
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   369
Rewriting:
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   370
[x] = [] == False
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   371
\end{ttbox}
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   372
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   373
In more complicated cases, the trace can be quite lenghty, especially since
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   374
invocations of the simplifier are often nested (e.g.\ when solving conditions
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   375
of rewrite rules). Thus it is advisable to reset it:%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   376
\end{isamarkuptext}%
9feb1e0c4cb3 *** empty log message ***
nipkow
parents: 9924
diff changeset
   377
\isacommand{ML}\ {\isachardoublequote}reset\ trace{\isacharunderscore}simp{\isachardoublequote}\isanewline
9924
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
   378
\end{isabellebody}%
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
   379
%%% Local Variables:
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
   380
%%% mode: latex
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
   381
%%% TeX-master: "root"
3370f6aa3200 updated;
wenzelm
parents: 9911
diff changeset
   382
%%% End: