src/Doc/IsarRef/Generic.thy
author wenzelm
Sun, 04 Nov 2012 19:05:34 +0100
changeset 50064 e08cc8b20564
parent 50063 7e491da6bcbd
child 50065 7c01dc2dcb8c
permissions -rw-r--r--
refurbished Simplifier examples;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     1
theory Generic
42651
e3fdb7c96be5 formal Base theory;
wenzelm
parents: 42626
diff changeset
     2
imports Base Main
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     3
begin
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     4
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     5
chapter {* Generic tools and packages \label{ch:gen-tools} *}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     6
42655
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
     7
section {* Configuration options \label{sec:config} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
     8
40291
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
     9
text {* Isabelle/Pure maintains a record of named configuration
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    10
  options within the theory or proof context, with values of type
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    11
  @{ML_type bool}, @{ML_type int}, @{ML_type real}, or @{ML_type
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    12
  string}.  Tools may declare options in ML, and then refer to these
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    13
  values (relative to the context).  Thus global reference variables
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    14
  are easily avoided.  The user may change the value of a
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    15
  configuration option by means of an associated attribute of the same
012ed4426fda support for real valued configuration options;
wenzelm
parents: 40255
diff changeset
    16
  name.  This form of context declaration works particularly well with
42655
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    17
  commands such as @{command "declare"} or @{command "using"} like
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    18
  this:
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    19
*}
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    20
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    21
declare [[show_main_goal = false]]
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    22
42655
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    23
notepad
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    24
begin
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    25
  note [[show_main_goal = true]]
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    26
end
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    27
eb95e2f3b218 updated configuration options -- no ML here;
wenzelm
parents: 42651
diff changeset
    28
text {* For historical reasons, some tools cannot take the full proof
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    29
  context into account and merely refer to the background theory.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    30
  This is accommodated by configuration options being declared as
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    31
  ``global'', which may not be changed within a local context.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    32
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    33
  \begin{matharray}{rcll}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    34
    @{command_def "print_configs"} & : & @{text "context \<rightarrow>"} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    35
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    36
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    37
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    38
    @{syntax name} ('=' ('true' | 'false' | @{syntax int} | @{syntax float} | @{syntax name}))?
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    39
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    40
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    41
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    42
  
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    43
  \item @{command "print_configs"} prints the available configuration
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    44
  options, with names, types, and current values.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    45
  
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    46
  \item @{text "name = value"} as an attribute expression modifies the
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    47
  named option, with the syntax of the value depending on the option's
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    48
  type.  For @{ML_type bool} the default value is @{text true}.  Any
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    49
  attempt to change a global option in a local context is ignored.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    50
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    51
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    52
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    53
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    54
27040
3d3e6e07b931 major reorganization of document structure;
wenzelm
parents: 26901
diff changeset
    55
section {* Basic proof tools *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    56
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    57
subsection {* Miscellaneous methods and attributes \label{sec:misc-meth-att} *}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    58
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    59
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    60
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    61
    @{method_def unfold} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    62
    @{method_def fold} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    63
    @{method_def insert} & : & @{text method} \\[0.5ex]
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    64
    @{method_def erule}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    65
    @{method_def drule}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    66
    @{method_def frule}@{text "\<^sup>*"} & : & @{text method} \\
43365
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
    67
    @{method_def intro} & : & @{text method} \\
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
    68
    @{method_def elim} & : & @{text method} \\
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    69
    @{method_def succeed} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
    70
    @{method_def fail} & : & @{text method} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    71
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    72
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    73
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    74
    (@@{method fold} | @@{method unfold} | @@{method insert}) @{syntax thmrefs}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    75
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    76
    (@@{method erule} | @@{method drule} | @@{method frule})
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    77
      ('(' @{syntax nat} ')')? @{syntax thmrefs}
43365
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
    78
    ;
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
    79
    (@@{method intro} | @@{method elim}) @{syntax thmrefs}?
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
    80
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    81
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    82
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    83
  
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    84
  \item @{method unfold}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{method fold}~@{text
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    85
  "a\<^sub>1 \<dots> a\<^sub>n"} expand (or fold back) the given definitions throughout
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    86
  all goals; any chained facts provided are inserted into the goal and
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    87
  subject to rewriting as well.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    88
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    89
  \item @{method insert}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} inserts theorems as facts
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    90
  into all goals of the proof state.  Note that current facts
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
    91
  indicated for forward chaining are ignored.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
    92
30397
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    93
  \item @{method erule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, @{method
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    94
  drule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, and @{method frule}~@{text
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    95
  "a\<^sub>1 \<dots> a\<^sub>n"} are similar to the basic @{method rule}
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    96
  method (see \secref{sec:pure-meth-att}), but apply rules by
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    97
  elim-resolution, destruct-resolution, and forward-resolution,
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    98
  respectively \cite{isabelle-implementation}.  The optional natural
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
    99
  number argument (default 0) specifies additional assumption steps to
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
   100
  be performed here.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   101
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   102
  Note that these methods are improper ones, mainly serving for
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   103
  experimentation and tactic script emulation.  Different modes of
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   104
  basic rule application are usually expressed in Isar at the proof
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   105
  language level, rather than via implicit proof state manipulations.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   106
  For example, a proper single-step elimination would be done using
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   107
  the plain @{method rule} method, with forward chaining of current
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   108
  facts.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   109
43365
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   110
  \item @{method intro} and @{method elim} repeatedly refine some goal
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   111
  by intro- or elim-resolution, after having inserted any chained
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   112
  facts.  Exactly the rules given as arguments are taken into account;
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   113
  this allows fine-tuned decomposition of a proof problem, in contrast
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   114
  to common automated tools.
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
   115
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   116
  \item @{method succeed} yields a single (unchanged) result; it is
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   117
  the identity of the ``@{text ","}'' method combinator (cf.\
28754
6f2e67a3dfaa moved section "Proof method expressions" to proof chapter;
wenzelm
parents: 27248
diff changeset
   118
  \secref{sec:proof-meth}).
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   119
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   120
  \item @{method fail} yields an empty result sequence; it is the
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   121
  identity of the ``@{text "|"}'' method combinator (cf.\
28754
6f2e67a3dfaa moved section "Proof method expressions" to proof chapter;
wenzelm
parents: 27248
diff changeset
   122
  \secref{sec:proof-meth}).
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   123
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   124
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   125
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   126
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   127
    @{attribute_def tagged} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   128
    @{attribute_def untagged} & : & @{text attribute} \\[0.5ex]
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   129
    @{attribute_def THEN} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   130
    @{attribute_def unfolded} & : & @{text attribute} \\
47497
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   131
    @{attribute_def folded} & : & @{text attribute} \\
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   132
    @{attribute_def abs_def} & : & @{text attribute} \\[0.5ex]
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   133
    @{attribute_def rotated} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   134
    @{attribute_def (Pure) elim_format} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   135
    @{attribute_def standard}@{text "\<^sup>*"} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   136
    @{attribute_def no_vars}@{text "\<^sup>*"} & : & @{text attribute} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   137
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   138
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   139
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   140
    @@{attribute tagged} @{syntax name} @{syntax name}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   141
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   142
    @@{attribute untagged} @{syntax name}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   143
    ;
48205
09c2a3d9aa22 discontinued obsolete attribute "COMP";
wenzelm
parents: 47967
diff changeset
   144
    @@{attribute THEN} ('[' @{syntax nat} ']')? @{syntax thmref}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   145
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   146
    (@@{attribute unfolded} | @@{attribute folded}) @{syntax thmrefs}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   147
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   148
    @@{attribute rotated} @{syntax int}?
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   149
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   150
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   151
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   152
28764
b65194fe4434 fixed/tuned syntax for attribute "tagged";
wenzelm
parents: 28761
diff changeset
   153
  \item @{attribute tagged}~@{text "name value"} and @{attribute
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   154
  untagged}~@{text name} add and remove \emph{tags} of some theorem.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   155
  Tags may be any list of string pairs that serve as formal comment.
28764
b65194fe4434 fixed/tuned syntax for attribute "tagged";
wenzelm
parents: 28761
diff changeset
   156
  The first string is considered the tag name, the second its value.
b65194fe4434 fixed/tuned syntax for attribute "tagged";
wenzelm
parents: 28761
diff changeset
   157
  Note that @{attribute untagged} removes any tags of the same name.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   158
48205
09c2a3d9aa22 discontinued obsolete attribute "COMP";
wenzelm
parents: 47967
diff changeset
   159
  \item @{attribute THEN}~@{text a} composes rules by resolution; it
09c2a3d9aa22 discontinued obsolete attribute "COMP";
wenzelm
parents: 47967
diff changeset
   160
  resolves with the first premise of @{text a} (an alternative
09c2a3d9aa22 discontinued obsolete attribute "COMP";
wenzelm
parents: 47967
diff changeset
   161
  position may be also specified).  See also @{ML_op "RS"} in
09c2a3d9aa22 discontinued obsolete attribute "COMP";
wenzelm
parents: 47967
diff changeset
   162
  \cite{isabelle-implementation}.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   163
  
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   164
  \item @{attribute unfolded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{attribute
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   165
  folded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} expand and fold back again the given
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   166
  definitions throughout a rule.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   167
47497
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   168
  \item @{attribute abs_def} turns an equation of the form @{prop "f x
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   169
  y \<equiv> t"} into @{prop "f \<equiv> \<lambda>x y. t"}, which ensures that @{method
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   170
  simp} or @{method unfold} steps always expand it.  This also works
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   171
  for object-logic equality.
c78c6e1ec75d document attribute "abs_def";
wenzelm
parents: 46706
diff changeset
   172
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   173
  \item @{attribute rotated}~@{text n} rotate the premises of a
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   174
  theorem by @{text n} (default 1).
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   175
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   176
  \item @{attribute (Pure) elim_format} turns a destruction rule into
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   177
  elimination rule format, by resolving with the rule @{prop "PROP A \<Longrightarrow>
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   178
  (PROP A \<Longrightarrow> PROP B) \<Longrightarrow> PROP B"}.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   179
  
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   180
  Note that the Classical Reasoner (\secref{sec:classical}) provides
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   181
  its own version of this operation.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   182
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   183
  \item @{attribute standard} puts a theorem into the standard form of
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   184
  object-rules at the outermost theory level.  Note that this
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   185
  operation violates the local proof context (including active
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   186
  locales).
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   187
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   188
  \item @{attribute no_vars} replaces schematic variables by free
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   189
  ones; this is mainly for tuning output of pretty printed theorems.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   190
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   191
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   192
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   193
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   194
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   195
subsection {* Low-level equational reasoning *}
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   196
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   197
text {*
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   198
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   199
    @{method_def subst} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   200
    @{method_def hypsubst} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   201
    @{method_def split} & : & @{text method} \\
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   202
  \end{matharray}
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   203
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   204
  @{rail "
42704
3f19e324ff59 tuned rail diagrams and layout;
wenzelm
parents: 42655
diff changeset
   205
    @@{method subst} ('(' 'asm' ')')? \\ ('(' (@{syntax nat}+) ')')? @{syntax thmref}
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   206
    ;
44094
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   207
    @@{method split} @{syntax thmrefs}
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   208
  "}
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   209
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   210
  These methods provide low-level facilities for equational reasoning
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   211
  that are intended for specialized applications only.  Normally,
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   212
  single step calculations would be performed in a structured text
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   213
  (see also \secref{sec:calculation}), while the Simplifier methods
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   214
  provide the canonical way for automated normalization (see
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   215
  \secref{sec:simplifier}).
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   216
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   217
  \begin{description}
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   218
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   219
  \item @{method subst}~@{text eq} performs a single substitution step
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   220
  using rule @{text eq}, which may be either a meta or object
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   221
  equality.
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   222
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   223
  \item @{method subst}~@{text "(asm) eq"} substitutes in an
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   224
  assumption.
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   225
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   226
  \item @{method subst}~@{text "(i \<dots> j) eq"} performs several
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   227
  substitutions in the conclusion. The numbers @{text i} to @{text j}
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   228
  indicate the positions to substitute at.  Positions are ordered from
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   229
  the top of the term tree moving down from left to right. For
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   230
  example, in @{text "(a + b) + (c + d)"} there are three positions
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   231
  where commutativity of @{text "+"} is applicable: 1 refers to @{text
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   232
  "a + b"}, 2 to the whole term, and 3 to @{text "c + d"}.
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   233
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   234
  If the positions in the list @{text "(i \<dots> j)"} are non-overlapping
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   235
  (e.g.\ @{text "(2 3)"} in @{text "(a + b) + (c + d)"}) you may
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   236
  assume all substitutions are performed simultaneously.  Otherwise
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   237
  the behaviour of @{text subst} is not specified.
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   238
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   239
  \item @{method subst}~@{text "(asm) (i \<dots> j) eq"} performs the
27071
614c045c5fd4 clarification of "subst" by Lucas Dixon;
wenzelm
parents: 27044
diff changeset
   240
  substitutions in the assumptions. The positions refer to the
614c045c5fd4 clarification of "subst" by Lucas Dixon;
wenzelm
parents: 27044
diff changeset
   241
  assumptions in order from left to right.  For example, given in a
614c045c5fd4 clarification of "subst" by Lucas Dixon;
wenzelm
parents: 27044
diff changeset
   242
  goal of the form @{text "P (a + b) \<Longrightarrow> P (c + d) \<Longrightarrow> \<dots>"}, position 1 of
614c045c5fd4 clarification of "subst" by Lucas Dixon;
wenzelm
parents: 27044
diff changeset
   243
  commutativity of @{text "+"} is the subterm @{text "a + b"} and
614c045c5fd4 clarification of "subst" by Lucas Dixon;
wenzelm
parents: 27044
diff changeset
   244
  position 2 is the subterm @{text "c + d"}.
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   245
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   246
  \item @{method hypsubst} performs substitution using some
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   247
  assumption; this only works for equations of the form @{text "x =
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   248
  t"} where @{text x} is a free or bound variable.
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   249
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   250
  \item @{method split}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} performs single-step case
44094
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   251
  splitting using the given rules.  Splitting is performed in the
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   252
  conclusion or some assumption of the subgoal, depending of the
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   253
  structure of the rule.
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   254
  
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   255
  Note that the @{method simp} method already involves repeated
44094
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   256
  application of split rules as declared in the current context, using
f7bbfdf4b4a7 updated documentation of method "split" according to e6a4bb832b46;
wenzelm
parents: 43367
diff changeset
   257
  @{attribute split}, for example.
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   258
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   259
  \end{description}
27044
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   260
*}
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   261
c4eaa7140532 moved subst/hypsubst to "Basic proof tools";
wenzelm
parents: 27040
diff changeset
   262
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   263
subsection {* Further tactic emulations \label{sec:tactics} *}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   264
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   265
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   266
  The following improper proof methods emulate traditional tactics.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   267
  These admit direct access to the goal state, which is normally
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   268
  considered harmful!  In particular, this may involve both numbered
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   269
  goal addressing (default 1), and dynamic instantiation within the
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   270
  scope of some subgoal.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   271
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   272
  \begin{warn}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   273
    Dynamic instantiations refer to universally quantified parameters
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   274
    of a subgoal (the dynamic context) rather than fixed variables and
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   275
    term abbreviations of a (static) Isar context.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   276
  \end{warn}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   277
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   278
  Tactic emulation methods, unlike their ML counterparts, admit
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   279
  simultaneous instantiation from both dynamic and static contexts.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   280
  If names occur in both contexts goal parameters hide locally fixed
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   281
  variables.  Likewise, schematic variables refer to term
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   282
  abbreviations, if present in the static context.  Otherwise the
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   283
  schematic variable is interpreted as a schematic variable and left
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   284
  to be solved by unification with certain parts of the subgoal.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   285
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   286
  Note that the tactic emulation proof methods in Isabelle/Isar are
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   287
  consistently named @{text foo_tac}.  Note also that variable names
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   288
  occurring on left hand sides of instantiations must be preceded by a
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   289
  question mark if they coincide with a keyword or contain dots.  This
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   290
  is consistent with the attribute @{attribute "where"} (see
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   291
  \secref{sec:pure-meth-att}).
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   292
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   293
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   294
    @{method_def rule_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   295
    @{method_def erule_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   296
    @{method_def drule_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   297
    @{method_def frule_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   298
    @{method_def cut_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   299
    @{method_def thin_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   300
    @{method_def subgoal_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   301
    @{method_def rename_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   302
    @{method_def rotate_tac}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   303
    @{method_def tactic}@{text "\<^sup>*"} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   304
    @{method_def raw_tactic}@{text "\<^sup>*"} & : & @{text method} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   305
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   306
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   307
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   308
    (@@{method rule_tac} | @@{method erule_tac} | @@{method drule_tac} |
42705
528a2ba8fa74 tuned some syntax names;
wenzelm
parents: 42704
diff changeset
   309
      @@{method frule_tac} | @@{method cut_tac} | @@{method thin_tac}) @{syntax goal_spec}? \\
42617
77d239840285 more precise rail diagrams;
wenzelm
parents: 42596
diff changeset
   310
    ( dynamic_insts @'in' @{syntax thmref} | @{syntax thmrefs} )
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   311
    ;
42705
528a2ba8fa74 tuned some syntax names;
wenzelm
parents: 42704
diff changeset
   312
    @@{method subgoal_tac} @{syntax goal_spec}? (@{syntax prop} +)
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   313
    ;
42705
528a2ba8fa74 tuned some syntax names;
wenzelm
parents: 42704
diff changeset
   314
    @@{method rename_tac} @{syntax goal_spec}? (@{syntax name} +)
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   315
    ;
42705
528a2ba8fa74 tuned some syntax names;
wenzelm
parents: 42704
diff changeset
   316
    @@{method rotate_tac} @{syntax goal_spec}? @{syntax int}?
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   317
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   318
    (@@{method tactic} | @@{method raw_tactic}) @{syntax text}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   319
    ;
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   320
42617
77d239840285 more precise rail diagrams;
wenzelm
parents: 42596
diff changeset
   321
    dynamic_insts: ((@{syntax name} '=' @{syntax term}) + @'and')
77d239840285 more precise rail diagrams;
wenzelm
parents: 42596
diff changeset
   322
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   323
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   324
\begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   325
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   326
  \item @{method rule_tac} etc. do resolution of rules with explicit
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   327
  instantiation.  This works the same way as the ML tactics @{ML
30397
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
   328
  res_inst_tac} etc. (see \cite{isabelle-implementation})
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   329
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   330
  Multiple rules may be only given if there is no instantiation; then
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   331
  @{method rule_tac} is the same as @{ML resolve_tac} in ML (see
30397
b6212ae21656 markup antiquotation options;
wenzelm
parents: 30168
diff changeset
   332
  \cite{isabelle-implementation}).
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   333
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   334
  \item @{method cut_tac} inserts facts into the proof state as
46706
877d57975427 updated cut_tac, without loose references to implementation manual;
wenzelm
parents: 46494
diff changeset
   335
  assumption of a subgoal; instantiations may be given as well.  Note
877d57975427 updated cut_tac, without loose references to implementation manual;
wenzelm
parents: 46494
diff changeset
   336
  that the scope of schematic variables is spread over the main goal
877d57975427 updated cut_tac, without loose references to implementation manual;
wenzelm
parents: 46494
diff changeset
   337
  statement and rule premises are turned into new subgoals.  This is
877d57975427 updated cut_tac, without loose references to implementation manual;
wenzelm
parents: 46494
diff changeset
   338
  in contrast to the regular method @{method insert} which inserts
877d57975427 updated cut_tac, without loose references to implementation manual;
wenzelm
parents: 46494
diff changeset
   339
  closed rule statements.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   340
46277
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   341
  \item @{method thin_tac}~@{text \<phi>} deletes the specified premise
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   342
  from a subgoal.  Note that @{text \<phi>} may contain schematic
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   343
  variables, to abbreviate the intended proposition; the first
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   344
  matching subgoal premise will be deleted.  Removing useless premises
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   345
  from a subgoal increases its readability and can make search tactics
aea65ff733b4 updated thin_tac;
wenzelm
parents: 46274
diff changeset
   346
  run faster.
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   347
46271
e1b5460f1725 updated subgoal_tac;
wenzelm
parents: 46262
diff changeset
   348
  \item @{method subgoal_tac}~@{text "\<phi>\<^sub>1 \<dots> \<phi>\<^sub>n"} adds the propositions
e1b5460f1725 updated subgoal_tac;
wenzelm
parents: 46262
diff changeset
   349
  @{text "\<phi>\<^sub>1 \<dots> \<phi>\<^sub>n"} as local premises to a subgoal, and poses the same
e1b5460f1725 updated subgoal_tac;
wenzelm
parents: 46262
diff changeset
   350
  as new subgoals (in the original context).
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   351
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   352
  \item @{method rename_tac}~@{text "x\<^sub>1 \<dots> x\<^sub>n"} renames parameters of a
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   353
  goal according to the list @{text "x\<^sub>1, \<dots>, x\<^sub>n"}, which refers to the
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   354
  \emph{suffix} of variables.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   355
46274
67139209b548 updated rotate_tac;
wenzelm
parents: 46271
diff changeset
   356
  \item @{method rotate_tac}~@{text n} rotates the premises of a
67139209b548 updated rotate_tac;
wenzelm
parents: 46271
diff changeset
   357
  subgoal by @{text n} positions: from right to left if @{text n} is
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   358
  positive, and from left to right if @{text n} is negative; the
46274
67139209b548 updated rotate_tac;
wenzelm
parents: 46271
diff changeset
   359
  default value is 1.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   360
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   361
  \item @{method tactic}~@{text "text"} produces a proof method from
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   362
  any ML text of type @{ML_type tactic}.  Apart from the usual ML
27223
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   363
  environment and the current proof context, the ML code may refer to
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   364
  the locally bound values @{ML_text facts}, which indicates any
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   365
  current facts used for forward-chaining.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   366
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   367
  \item @{method raw_tactic} is similar to @{method tactic}, but
27223
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   368
  presents the goal state in its raw internal form, where simultaneous
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   369
  subgoals appear as conjunction of the logical framework instead of
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   370
  the usual split into several subgoals.  While feature this is useful
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   371
  for debugging of complex method definitions, it should not never
8546e2407b31 method "tactic": only "facts" as bound value;
wenzelm
parents: 27209
diff changeset
   372
  appear in production theories.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   373
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   374
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   375
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   376
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   377
27040
3d3e6e07b931 major reorganization of document structure;
wenzelm
parents: 26901
diff changeset
   378
section {* The Simplifier \label{sec:simplifier} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   379
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   380
text {* The Simplifier performs conditional and unconditional
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   381
  rewriting and uses contextual information: rule declarations in the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   382
  background theory or local proof context are taken into account, as
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   383
  well as chained facts and subgoal premises (``local assumptions'').
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   384
  There are several general hooks that allow to modify the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   385
  simplification strategy, or incorporate other proof tools that solve
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   386
  sub-problems, produce rewrite rules on demand etc.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   387
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   388
  The default Simplifier setup of major object logics (HOL, HOLCF,
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   389
  FOL, ZF) makes the Simplifier ready for immediate use, without
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   390
  engaging into the internal structures.  Thus it serves as
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   391
  general-purpose proof tool with the main focus on equational
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   392
  reasoning, and a bit more than that.  *}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   393
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   394
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   395
subsection {* Simplification methods \label{sec:simp-meth} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   396
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   397
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   398
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   399
    @{method_def simp} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   400
    @{method_def simp_all} & : & @{text method} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   401
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   402
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   403
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   404
    (@@{method simp} | @@{method simp_all}) opt? (@{syntax simpmod} * )
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   405
    ;
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   406
40255
9ffbc25e1606 eliminated obsolete \_ escapes in rail environments;
wenzelm
parents: 35613
diff changeset
   407
    opt: '(' ('no_asm' | 'no_asm_simp' | 'no_asm_use' | 'asm_lr' ) ')'
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   408
    ;
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   409
    @{syntax_def simpmod}: ('add' | 'del' | 'only' | 'split' (() | 'add' | 'del') |
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   410
      'cong' (() | 'add' | 'del')) ':' @{syntax thmrefs}
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   411
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   412
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   413
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   414
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   415
  \item @{method simp} invokes the Simplifier on the first subgoal,
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   416
  after inserting chained facts as additional goal premises; further
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   417
  rule declarations may be included via @{text "(simp add: facts)"}.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   418
  The proof method fails if the subgoal remains unchanged after
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   419
  simplification.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   420
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   421
  Note that the original goal premises and chained facts are subject
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   422
  to simplification themselves, while declarations via @{text
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   423
  "add"}/@{text "del"} merely follow the policies of the object-logic
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   424
  to extract rewrite rules from theorems, without further
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   425
  simplification.  This may lead to slightly different behavior in
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   426
  either case, which might be required precisely like that in some
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   427
  boundary situations to perform the intended simplification step!
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   428
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   429
  \medskip The @{text only} modifier first removes all other rewrite
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   430
  rules, looper tactics (including split rules), congruence rules, and
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   431
  then behaves like @{text add}.  Implicit solvers remain, which means
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   432
  that trivial rules like reflexivity or introduction of @{text
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   433
  "True"} are available to solve the simplified subgoals, but also
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   434
  non-trivial tools like linear arithmetic in HOL.  The latter may
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   435
  lead to some surprise of the meaning of ``only'' in Isabelle/HOL
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   436
  compared to English!
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   437
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   438
  \medskip The @{text split} modifiers add or delete rules for the
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   439
  Splitter (see also \cite{isabelle-ref}), the default is to add.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   440
  This works only if the Simplifier method has been properly setup to
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   441
  include the Splitter (all major object logics such HOL, HOLCF, FOL,
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   442
  ZF do this already).
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   443
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   444
  \medskip The @{text cong} modifiers add or delete Simplifier
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   445
  congruence rules (see also \secref{sec:simp-rules}); the default is
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   446
  to add.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   447
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   448
  \item @{method simp_all} is similar to @{method simp}, but acts on
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   449
  all goals, working backwards from the last to the first one as usual
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   450
  in Isabelle.\footnote{The order is irrelevant for goals without
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   451
  schematic variables, so simplification might actually be performed
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   452
  in parallel here.}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   453
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   454
  Chained facts are inserted into all subgoals, before the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   455
  simplification process starts.  Further rule declarations are the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   456
  same as for @{method simp}.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   457
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   458
  The proof method fails if all subgoals remain unchanged after
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   459
  simplification.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   460
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   461
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   462
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   463
  By default the Simplifier methods above take local assumptions fully
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   464
  into account, using equational assumptions in the subsequent
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   465
  normalization process, or simplifying assumptions themselves.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   466
  Further options allow to fine-tune the behavior of the Simplifier
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   467
  in this respect, corresponding to a variety of ML tactics as
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   468
  follows.\footnote{Unlike the corresponding Isar proof methods, the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   469
  ML tactics do not insist in changing the goal state.}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   470
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   471
  \begin{center}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   472
  \small
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   473
  \begin{tabular}{|l|l|p{0.3\textwidth}|}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   474
  \hline
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   475
  Isar method & ML tactic & behavior \\\hline
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   476
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   477
  @{text "(simp (no_asm))"} & @{ML simp_tac} & assumptions are ignored
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   478
  completely \\\hline
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   479
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   480
  @{text "(simp (no_asm_simp))"} & @{ML asm_simp_tac} & assumptions
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   481
  are used in the simplification of the conclusion but are not
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   482
  themselves simplified \\\hline
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   483
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   484
  @{text "(simp (no_asm_use))"} & @{ML full_simp_tac} & assumptions
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   485
  are simplified but are not used in the simplification of each other
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   486
  or the conclusion \\\hline
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   487
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   488
  @{text "(simp)"} & @{ML asm_full_simp_tac} & assumptions are used in
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   489
  the simplification of the conclusion and to simplify other
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   490
  assumptions \\\hline
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   491
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   492
  @{text "(simp (asm_lr))"} & @{ML asm_lr_simp_tac} & compatibility
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   493
  mode: an assumption is only used for simplifying assumptions which
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   494
  are to the right of it \\\hline
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   495
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   496
  \end{tabular}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   497
  \end{center}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   498
50064
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   499
  %FIXME move?
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   500
  \medskip The Splitter package is usually configured to work as part
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   501
  of the Simplifier.  The effect of repeatedly applying @{ML
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   502
  split_tac} can be simulated by ``@{text "(simp only: split:
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   503
  a\<^sub>1 \<dots> a\<^sub>n)"}''.  There is also a separate @{text split}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   504
  method available for single-step case splitting.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   505
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   506
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   507
50064
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   508
subsubsection {* Examples *}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   509
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   510
text {* We consider basic algebraic simplifications in Isabelle/HOL.
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   511
  The rather trivial goal @{prop "0 + (x + 0) = x + 0 + 0"} looks like
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   512
  a good candidate to be solved by a single call of @{method simp}:
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   513
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   514
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   515
lemma "0 + (x + 0) = x + 0 + 0" apply simp? oops
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   516
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   517
text {* The above attempt \emph{fails}, because @{term "0"} and @{term
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   518
  "op +"} in the HOL library are declared as generic type class
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   519
  operations, without stating any algebraic laws yet.  More specific
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   520
  types are required to get access to certain standard simplifications
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   521
  of the theory context, e.g.\ like this: *}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   522
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   523
lemma fixes x :: nat shows "0 + (x + 0) = x + 0 + 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   524
lemma fixes x :: int shows "0 + (x + 0) = x + 0 + 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   525
lemma fixes x :: "'a :: monoid_add" shows "0 + (x + 0) = x + 0 + 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   526
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   527
text {*
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   528
  \medskip In many cases, assumptions of a subgoal are also needed in
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   529
  the simplification process.  For example:
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   530
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   531
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   532
lemma fixes x :: nat shows "x = 0 \<Longrightarrow> x + x = 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   533
lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" apply simp oops
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   534
lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" using assms by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   535
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   536
text {* As seen above, local assumptions that shall contribute to
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   537
  simplification need to be part of the subgoal already, or indicated
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   538
  explicitly for use by the subsequent method invocation.  Both too
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   539
  little or too much information can make simplification fail, for
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   540
  different reasons.
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   541
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   542
  In the next example the malicious assumption @{prop "\<And>x::nat. f x =
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   543
  g (f (g x))"} does not contribute to solve the problem, but makes
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   544
  the default @{method simp} method loop: the rewrite rule @{text "f
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   545
  ?x \<equiv> g (f (g ?x))"} extracted from the assumption does not
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   546
  terminate.  The Simplifier notices certain simple forms of
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   547
  nontermination, but not this one.  The problem can be solved
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   548
  nonetheless, by ignoring assumptions via special options as
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   549
  explained before:
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   550
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   551
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   552
lemma "(\<And>x::nat. f x = g (f (g x))) \<Longrightarrow> f 0 = f 0 + 0"
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   553
  by (simp (no_asm))
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   554
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   555
text {* The latter form is typical for long unstructured proof
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   556
  scripts, where the control over the goal content is limited.  In
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   557
  structured proofs it is usually better to avoid pushing too many
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   558
  facts into the goal state in the first place.  Assumptions in the
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   559
  Isar proof context do not intrude the reasoning if not used
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   560
  explicitly.  This is illustrated for a toplevel statement and a
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   561
  local proof body as follows:
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   562
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   563
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   564
lemma
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   565
  assumes "\<And>x::nat. f x = g (f (g x))"
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   566
  shows "f 0 = f 0 + 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   567
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   568
notepad
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   569
begin
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   570
  assume "\<And>x::nat. f x = g (f (g x))"
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   571
  have "f 0 = f 0 + 0" by simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   572
end
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   573
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   574
text {* \medskip Because assumptions may simplify each other, there
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   575
  can be very subtle cases of nontermination. For example, the regular
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   576
  @{method simp} method applied to @{prop "P (f x) \<Longrightarrow> y = x \<Longrightarrow> f x = f y
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   577
  \<Longrightarrow> Q"} gives rise to the infinite reduction sequence
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   578
  \[
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   579
  @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   580
  @{text "P (f y)"} \stackrel{@{text "y \<equiv> x"}}{\longmapsto}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   581
  @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto} \cdots
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   582
  \]
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   583
  whereas applying the same to @{prop "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow>
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   584
  Q"} terminates (without solving the goal):
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   585
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   586
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   587
lemma "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow> Q"
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   588
  apply simp
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   589
  oops
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   590
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   591
text {* See also \secref{sec:simp-config} for options to enable
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   592
  Simplifier trace mode, which often helps to diagnose problems with
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   593
  rewrite systems.
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   594
*}
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   595
e08cc8b20564 refurbished Simplifier examples;
wenzelm
parents: 50063
diff changeset
   596
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   597
subsection {* Declaring rules \label{sec:simp-rules} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   598
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   599
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   600
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   601
    @{command_def "print_simpset"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   602
    @{attribute_def simp} & : & @{text attribute} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   603
    @{attribute_def split} & : & @{text attribute} \\
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   604
    @{attribute_def cong} & : & @{text attribute} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   605
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   606
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   607
  @{rail "
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   608
    (@@{attribute simp} | @@{attribute split} | @@{attribute cong})
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   609
      (() | 'add' | 'del')
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   610
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   611
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   612
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   613
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   614
  \item @{command "print_simpset"} prints the collection of rules
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   615
  declared to the Simplifier, which is also known as ``simpset''
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   616
  internally.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   617
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   618
  For historical reasons, simpsets may occur independently from the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   619
  current context, but are conceptually dependent on it.  When the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   620
  Simplifier is invoked via one of its main entry points in the Isar
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   621
  source language (as proof method \secref{sec:simp-meth} or rule
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   622
  attribute \secref{sec:simp-meth}), its simpset is derived from the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   623
  current proof context, and carries a back-reference to that for
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   624
  other tools that might get invoked internally (e.g.\ simplification
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   625
  procedures \secref{sec:simproc}).  A mismatch of the context of the
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   626
  simpset and the context of the problem being simplified may lead to
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   627
  unexpected results.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   628
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   629
  \item @{attribute simp} declares simplification rules.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   630
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   631
  \item @{attribute split} declares case split rules.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   632
45645
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   633
  \item @{attribute cong} declares congruence rules to the Simplifier
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   634
  context.
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   635
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   636
  Congruence rules are equalities of the form @{text [display]
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   637
  "\<dots> \<Longrightarrow> f ?x\<^sub>1 \<dots> ?x\<^sub>n = f ?y\<^sub>1 \<dots> ?y\<^sub>n"}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   638
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   639
  This controls the simplification of the arguments of @{text f}.  For
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   640
  example, some arguments can be simplified under additional
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   641
  assumptions: @{text [display] "?P\<^sub>1 \<longleftrightarrow> ?Q\<^sub>1 \<Longrightarrow> (?Q\<^sub>1 \<Longrightarrow> ?P\<^sub>2 \<longleftrightarrow> ?Q\<^sub>2) \<Longrightarrow>
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   642
  (?P\<^sub>1 \<longrightarrow> ?P\<^sub>2) \<longleftrightarrow> (?Q\<^sub>1 \<longrightarrow> ?Q\<^sub>2)"}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   643
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   644
  Given this rule, the simplifier assumes @{text "?Q\<^sub>1"} and extracts
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   645
  rewrite rules from it when simplifying @{text "?P\<^sub>2"}.  Such local
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   646
  assumptions are effective for rewriting formulae such as @{text "x =
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   647
  0 \<longrightarrow> y + x = y"}.
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   648
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   649
  %FIXME
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   650
  %The local assumptions are also provided as theorems to the solver;
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   651
  %see \secref{sec:simp-solver} below.
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   652
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   653
  \medskip The following congruence rule for bounded quantifiers also
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   654
  supplies contextual information --- about the bound variable:
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   655
  @{text [display] "(?A = ?B) \<Longrightarrow> (\<And>x. x \<in> ?B \<Longrightarrow> ?P x \<longleftrightarrow> ?Q x) \<Longrightarrow>
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   656
    (\<forall>x \<in> ?A. ?P x) \<longleftrightarrow> (\<forall>x \<in> ?B. ?Q x)"}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   657
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   658
  \medskip This congruence rule for conditional expressions can
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   659
  supply contextual information for simplifying the arms:
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   660
  @{text [display] "?p = ?q \<Longrightarrow> (?q \<Longrightarrow> ?a = ?c) \<Longrightarrow> (\<not> ?q \<Longrightarrow> ?b = ?d) \<Longrightarrow>
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   661
    (if ?p then ?a else ?b) = (if ?q then ?c else ?d)"}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   662
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   663
  A congruence rule can also \emph{prevent} simplification of some
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   664
  arguments.  Here is an alternative congruence rule for conditional
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   665
  expressions that conforms to non-strict functional evaluation:
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   666
  @{text [display] "?p = ?q \<Longrightarrow> (if ?p then ?a else ?b) = (if ?q then ?a else ?b)"}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   667
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   668
  Only the first argument is simplified; the others remain unchanged.
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   669
  This can make simplification much faster, but may require an extra
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   670
  case split over the condition @{text "?q"} to prove the goal.
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   671
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   672
  \end{description}
45645
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   673
*}
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   674
4014bc2a09ff modernized section about congruence rules;
wenzelm
parents: 44911
diff changeset
   675
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   676
subsection {* Configuration options \label{sec:simp-config} *}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   677
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   678
text {*
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   679
  \begin{tabular}{rcll}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   680
    @{attribute_def simp_depth_limit} & : & @{text attribute} & default @{text 100} \\
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   681
    @{attribute_def simp_trace} & : & @{text attribute} & default @{text false} \\
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   682
    @{attribute_def simp_trace_depth_limit} & : & @{text attribute} & default @{text 1} \\
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   683
    @{attribute_def simp_debug} & : & @{text attribute} & default @{text false} \\
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   684
  \end{tabular}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   685
  \medskip
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   686
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   687
  These configurations options control further aspects of the Simplifier.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   688
  See also \secref{sec:config}.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   689
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   690
  \begin{description}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   691
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   692
  \item @{attribute simp_depth_limit} limits the number of recursive
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   693
  invocations of the Simplifier during conditional rewriting.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   694
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   695
  \item @{attribute simp_trace} makes the Simplifier output internal
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   696
  operations.  This includes rewrite steps, but also bookkeeping like
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   697
  modifications of the simpset.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   698
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   699
  \item @{attribute simp_trace_depth_limit} limits the effect of
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   700
  @{attribute simp_trace} to the given depth of recursive Simplifier
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   701
  invocations (when solving conditions of rewrite rules).
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   702
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   703
  \item @{attribute simp_debug} makes the Simplifier output some extra
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   704
  information about internal operations.  This includes any attempted
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   705
  invocation of simplification procedures.
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   706
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   707
  \end{description}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   708
*}
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   709
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   710
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   711
subsection {* Simplification procedures \label{sec:simproc} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   712
42925
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   713
text {* Simplification procedures are ML functions that produce proven
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   714
  rewrite rules on demand.  They are associated with higher-order
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   715
  patterns that approximate the left-hand sides of equations.  The
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   716
  Simplifier first matches the current redex against one of the LHS
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   717
  patterns; if this succeeds, the corresponding ML function is
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   718
  invoked, passing the Simplifier context and redex term.  Thus rules
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   719
  may be specifically fashioned for particular situations, resulting
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   720
  in a more powerful mechanism than term rewriting by a fixed set of
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   721
  rules.
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   722
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   723
  Any successful result needs to be a (possibly conditional) rewrite
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   724
  rule @{text "t \<equiv> u"} that is applicable to the current redex.  The
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   725
  rule will be applied just as any ordinary rewrite rule.  It is
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   726
  expected to be already in \emph{internal form}, bypassing the
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   727
  automatic preprocessing of object-level equivalences.
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   728
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   729
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   730
    @{command_def "simproc_setup"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   731
    simproc & : & @{text attribute} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   732
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   733
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   734
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   735
    @@{command simproc_setup} @{syntax name} '(' (@{syntax term} + '|') ')' '='
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   736
      @{syntax text} \\ (@'identifier' (@{syntax nameref}+))?
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   737
    ;
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   738
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   739
    @@{attribute simproc} (('add' ':')? | 'del' ':') (@{syntax name}+)
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   740
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   741
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   742
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   743
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   744
  \item @{command "simproc_setup"} defines a named simplification
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   745
  procedure that is invoked by the Simplifier whenever any of the
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   746
  given term patterns match the current redex.  The implementation,
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   747
  which is provided as ML source text, needs to be of type @{ML_type
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   748
  "morphism -> simpset -> cterm -> thm option"}, where the @{ML_type
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   749
  cterm} represents the current redex @{text r} and the result is
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   750
  supposed to be some proven rewrite rule @{text "r \<equiv> r'"} (or a
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   751
  generalized version), or @{ML NONE} to indicate failure.  The
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   752
  @{ML_type simpset} argument holds the full context of the current
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   753
  Simplifier invocation, including the actual Isar proof context.  The
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   754
  @{ML_type morphism} informs about the difference of the original
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   755
  compilation context wrt.\ the one of the actual application later
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   756
  on.  The optional @{keyword "identifier"} specifies theorems that
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   757
  represent the logical content of the abstract theory of this
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   758
  simproc.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   759
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   760
  Morphisms and identifiers are only relevant for simprocs that are
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   761
  defined within a local target context, e.g.\ in a locale.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   762
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   763
  \item @{text "simproc add: name"} and @{text "simproc del: name"}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   764
  add or delete named simprocs to the current Simplifier context.  The
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   765
  default is to add a simproc.  Note that @{command "simproc_setup"}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   766
  already adds the new simproc to the subsequent context.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   767
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   768
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   769
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   770
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   771
42925
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   772
subsubsection {* Example *}
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   773
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   774
text {* The following simplification procedure for @{thm
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   775
  [source=false, show_types] unit_eq} in HOL performs fine-grained
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   776
  control over rule application, beyond higher-order pattern matching.
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   777
  Declaring @{thm unit_eq} as @{attribute simp} directly would make
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   778
  the simplifier loop!  Note that a version of this simplification
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   779
  procedure is already active in Isabelle/HOL.  *}
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   780
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   781
simproc_setup unit ("x::unit") = {*
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   782
  fn _ => fn _ => fn ct =>
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   783
    if HOLogic.is_unit (term_of ct) then NONE
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   784
    else SOME (mk_meta_eq @{thm unit_eq})
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   785
*}
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   786
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   787
text {* Since the Simplifier applies simplification procedures
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   788
  frequently, it is important to make the failure check in ML
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   789
  reasonably fast. *}
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   790
c6c4f997ad87 updated and re-unified material on simprocs;
wenzelm
parents: 42705
diff changeset
   791
50063
7e491da6bcbd more on the Simplifier, based on old material;
wenzelm
parents: 48985
diff changeset
   792
subsection {* Forward simplification \label{sec:simp-forward} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   793
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   794
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   795
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
   796
    @{attribute_def simplified} & : & @{text attribute} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   797
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   798
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   799
  @{rail "
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   800
    @@{attribute simplified} opt? @{syntax thmrefs}?
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   801
    ;
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   802
40255
9ffbc25e1606 eliminated obsolete \_ escapes in rail environments;
wenzelm
parents: 35613
diff changeset
   803
    opt: '(' ('no_asm' | 'no_asm_simp' | 'no_asm_use') ')'
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
   804
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   805
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   806
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   807
  
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   808
  \item @{attribute simplified}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} causes a theorem to
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   809
  be simplified, either by exactly the specified rules @{text "a\<^sub>1, \<dots>,
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   810
  a\<^sub>n"}, or the implicit Simplifier context if no arguments are given.
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   811
  The result is fully simplified by default, including assumptions and
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   812
  conclusion; the options @{text no_asm} etc.\ tune the Simplifier in
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   813
  the same way as the for the @{text simp} method.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   814
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   815
  Note that forward simplification restricts the simplifier to its
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   816
  most basic operation of term rewriting; solver and looper tactics
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   817
  \cite{isabelle-ref} are \emph{not} involved here.  The @{text
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   818
  simplified} attribute should be only rarely required under normal
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   819
  circumstances.
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   820
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
   821
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   822
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   823
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   824
27040
3d3e6e07b931 major reorganization of document structure;
wenzelm
parents: 26901
diff changeset
   825
section {* The Classical Reasoner \label{sec:classical} *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
   826
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
   827
subsection {* Basic concepts *}
42927
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   828
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   829
text {* Although Isabelle is generic, many users will be working in
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   830
  some extension of classical first-order logic.  Isabelle/ZF is built
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   831
  upon theory FOL, while Isabelle/HOL conceptually contains
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   832
  first-order logic as a fragment.  Theorem-proving in predicate logic
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   833
  is undecidable, but many automated strategies have been developed to
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   834
  assist in this task.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   835
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   836
  Isabelle's classical reasoner is a generic package that accepts
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   837
  certain information about a logic and delivers a suite of automatic
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   838
  proof tools, based on rules that are classified and declared in the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   839
  context.  These proof procedures are slow and simplistic compared
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   840
  with high-end automated theorem provers, but they can save
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   841
  considerable time and effort in practice.  They can prove theorems
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   842
  such as Pelletier's \cite{pelletier86} problems 40 and 41 in a few
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   843
  milliseconds (including full proof reconstruction): *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   844
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   845
lemma "(\<exists>y. \<forall>x. F x y \<longleftrightarrow> F x x) \<longrightarrow> \<not> (\<forall>x. \<exists>y. \<forall>z. F z y \<longleftrightarrow> \<not> F z x)"
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   846
  by blast
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   847
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   848
lemma "(\<forall>z. \<exists>y. \<forall>x. f x y \<longleftrightarrow> f x z \<and> \<not> f x x) \<longrightarrow> \<not> (\<exists>z. \<forall>x. f x z)"
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   849
  by blast
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   850
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   851
text {* The proof tools are generic.  They are not restricted to
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   852
  first-order logic, and have been heavily used in the development of
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   853
  the Isabelle/HOL library and applications.  The tactics can be
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   854
  traced, and their components can be called directly; in this manner,
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   855
  any proof can be viewed interactively.  *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   856
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   857
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   858
subsubsection {* The sequent calculus *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   859
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   860
text {* Isabelle supports natural deduction, which is easy to use for
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   861
  interactive proof.  But natural deduction does not easily lend
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   862
  itself to automation, and has a bias towards intuitionism.  For
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   863
  certain proofs in classical logic, it can not be called natural.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   864
  The \emph{sequent calculus}, a generalization of natural deduction,
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   865
  is easier to automate.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   866
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   867
  A \textbf{sequent} has the form @{text "\<Gamma> \<turnstile> \<Delta>"}, where @{text "\<Gamma>"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   868
  and @{text "\<Delta>"} are sets of formulae.\footnote{For first-order
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   869
  logic, sequents can equivalently be made from lists or multisets of
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   870
  formulae.} The sequent @{text "P\<^sub>1, \<dots>, P\<^sub>m \<turnstile> Q\<^sub>1, \<dots>, Q\<^sub>n"} is
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   871
  \textbf{valid} if @{text "P\<^sub>1 \<and> \<dots> \<and> P\<^sub>m"} implies @{text "Q\<^sub>1 \<or> \<dots> \<or>
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   872
  Q\<^sub>n"}.  Thus @{text "P\<^sub>1, \<dots>, P\<^sub>m"} represent assumptions, each of which
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   873
  is true, while @{text "Q\<^sub>1, \<dots>, Q\<^sub>n"} represent alternative goals.  A
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   874
  sequent is \textbf{basic} if its left and right sides have a common
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   875
  formula, as in @{text "P, Q \<turnstile> Q, R"}; basic sequents are trivially
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   876
  valid.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   877
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   878
  Sequent rules are classified as \textbf{right} or \textbf{left},
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   879
  indicating which side of the @{text "\<turnstile>"} symbol they operate on.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   880
  Rules that operate on the right side are analogous to natural
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   881
  deduction's introduction rules, and left rules are analogous to
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   882
  elimination rules.  The sequent calculus analogue of @{text "(\<longrightarrow>I)"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   883
  is the rule
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   884
  \[
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   885
  \infer[@{text "(\<longrightarrow>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, P \<longrightarrow> Q"}}{@{text "P, \<Gamma> \<turnstile> \<Delta>, Q"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   886
  \]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   887
  Applying the rule backwards, this breaks down some implication on
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   888
  the right side of a sequent; @{text "\<Gamma>"} and @{text "\<Delta>"} stand for
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   889
  the sets of formulae that are unaffected by the inference.  The
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   890
  analogue of the pair @{text "(\<or>I1)"} and @{text "(\<or>I2)"} is the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   891
  single rule
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   892
  \[
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   893
  \infer[@{text "(\<or>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, P \<or> Q"}}{@{text "\<Gamma> \<turnstile> \<Delta>, P, Q"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   894
  \]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   895
  This breaks down some disjunction on the right side, replacing it by
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   896
  both disjuncts.  Thus, the sequent calculus is a kind of
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   897
  multiple-conclusion logic.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   898
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   899
  To illustrate the use of multiple formulae on the right, let us
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   900
  prove the classical theorem @{text "(P \<longrightarrow> Q) \<or> (Q \<longrightarrow> P)"}.  Working
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   901
  backwards, we reduce this formula to a basic sequent:
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   902
  \[
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   903
  \infer[@{text "(\<or>R)"}]{@{text "\<turnstile> (P \<longrightarrow> Q) \<or> (Q \<longrightarrow> P)"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   904
    {\infer[@{text "(\<longrightarrow>R)"}]{@{text "\<turnstile> (P \<longrightarrow> Q), (Q \<longrightarrow> P)"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   905
      {\infer[@{text "(\<longrightarrow>R)"}]{@{text "P \<turnstile> Q, (Q \<longrightarrow> P)"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   906
        {@{text "P, Q \<turnstile> Q, P"}}}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   907
  \]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   908
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   909
  This example is typical of the sequent calculus: start with the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   910
  desired theorem and apply rules backwards in a fairly arbitrary
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   911
  manner.  This yields a surprisingly effective proof procedure.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   912
  Quantifiers add only few complications, since Isabelle handles
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   913
  parameters and schematic variables.  See \cite[Chapter
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   914
  10]{paulson-ml2} for further discussion.  *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   915
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   916
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   917
subsubsection {* Simulating sequents by natural deduction *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   918
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   919
text {* Isabelle can represent sequents directly, as in the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   920
  object-logic LK.  But natural deduction is easier to work with, and
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   921
  most object-logics employ it.  Fortunately, we can simulate the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   922
  sequent @{text "P\<^sub>1, \<dots>, P\<^sub>m \<turnstile> Q\<^sub>1, \<dots>, Q\<^sub>n"} by the Isabelle formula
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   923
  @{text "P\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> P\<^sub>m \<Longrightarrow> \<not> Q\<^sub>2 \<Longrightarrow> ... \<Longrightarrow> \<not> Q\<^sub>n \<Longrightarrow> Q\<^sub>1"} where the order of
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   924
  the assumptions and the choice of @{text "Q\<^sub>1"} are arbitrary.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   925
  Elim-resolution plays a key role in simulating sequent proofs.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   926
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   927
  We can easily handle reasoning on the left.  Elim-resolution with
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   928
  the rules @{text "(\<or>E)"}, @{text "(\<bottom>E)"} and @{text "(\<exists>E)"} achieves
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   929
  a similar effect as the corresponding sequent rules.  For the other
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   930
  connectives, we use sequent-style elimination rules instead of
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   931
  destruction rules such as @{text "(\<and>E1, 2)"} and @{text "(\<forall>E)"}.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   932
  But note that the rule @{text "(\<not>L)"} has no effect under our
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   933
  representation of sequents!
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   934
  \[
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   935
  \infer[@{text "(\<not>L)"}]{@{text "\<not> P, \<Gamma> \<turnstile> \<Delta>"}}{@{text "\<Gamma> \<turnstile> \<Delta>, P"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   936
  \]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   937
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   938
  What about reasoning on the right?  Introduction rules can only
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   939
  affect the formula in the conclusion, namely @{text "Q\<^sub>1"}.  The
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   940
  other right-side formulae are represented as negated assumptions,
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   941
  @{text "\<not> Q\<^sub>2, \<dots>, \<not> Q\<^sub>n"}.  In order to operate on one of these, it
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   942
  must first be exchanged with @{text "Q\<^sub>1"}.  Elim-resolution with the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   943
  @{text swap} rule has this effect: @{text "\<not> P \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> R"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   944
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   945
  To ensure that swaps occur only when necessary, each introduction
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   946
  rule is converted into a swapped form: it is resolved with the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   947
  second premise of @{text "(swap)"}.  The swapped form of @{text
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   948
  "(\<and>I)"}, which might be called @{text "(\<not>\<and>E)"}, is
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   949
  @{text [display] "\<not> (P \<and> Q) \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> (\<not> R \<Longrightarrow> Q) \<Longrightarrow> R"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   950
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   951
  Similarly, the swapped form of @{text "(\<longrightarrow>I)"} is
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   952
  @{text [display] "\<not> (P \<longrightarrow> Q) \<Longrightarrow> (\<not> R \<Longrightarrow> P \<Longrightarrow> Q) \<Longrightarrow> R"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   953
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   954
  Swapped introduction rules are applied using elim-resolution, which
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   955
  deletes the negated formula.  Our representation of sequents also
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   956
  requires the use of ordinary introduction rules.  If we had no
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   957
  regard for readability of intermediate goal states, we could treat
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   958
  the right side more uniformly by representing sequents as @{text
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   959
  [display] "P\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> P\<^sub>m \<Longrightarrow> \<not> Q\<^sub>1 \<Longrightarrow> \<dots> \<Longrightarrow> \<not> Q\<^sub>n \<Longrightarrow> \<bottom>"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   960
*}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   961
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   962
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   963
subsubsection {* Extra rules for the sequent calculus *}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   964
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   965
text {* As mentioned, destruction rules such as @{text "(\<and>E1, 2)"} and
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   966
  @{text "(\<forall>E)"} must be replaced by sequent-style elimination rules.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   967
  In addition, we need rules to embody the classical equivalence
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   968
  between @{text "P \<longrightarrow> Q"} and @{text "\<not> P \<or> Q"}.  The introduction
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   969
  rules @{text "(\<or>I1, 2)"} are replaced by a rule that simulates
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   970
  @{text "(\<or>R)"}: @{text [display] "(\<not> Q \<Longrightarrow> P) \<Longrightarrow> P \<or> Q"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   971
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   972
  The destruction rule @{text "(\<longrightarrow>E)"} is replaced by @{text [display]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   973
  "(P \<longrightarrow> Q) \<Longrightarrow> (\<not> P \<Longrightarrow> R) \<Longrightarrow> (Q \<Longrightarrow> R) \<Longrightarrow> R"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   974
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   975
  Quantifier replication also requires special rules.  In classical
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   976
  logic, @{text "\<exists>x. P x"} is equivalent to @{text "\<not> (\<forall>x. \<not> P x)"};
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   977
  the rules @{text "(\<exists>R)"} and @{text "(\<forall>L)"} are dual:
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   978
  \[
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   979
  \infer[@{text "(\<exists>R)"}]{@{text "\<Gamma> \<turnstile> \<Delta>, \<exists>x. P x"}}{@{text "\<Gamma> \<turnstile> \<Delta>, \<exists>x. P x, P t"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   980
  \qquad
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   981
  \infer[@{text "(\<forall>L)"}]{@{text "\<forall>x. P x, \<Gamma> \<turnstile> \<Delta>"}}{@{text "P t, \<forall>x. P x, \<Gamma> \<turnstile> \<Delta>"}}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   982
  \]
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   983
  Thus both kinds of quantifier may be replicated.  Theorems requiring
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   984
  multiple uses of a universal formula are easy to invent; consider
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   985
  @{text [display] "(\<forall>x. P x \<longrightarrow> P (f x)) \<and> P a \<longrightarrow> P (f\<^sup>n a)"} for any
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   986
  @{text "n > 1"}.  Natural examples of the multiple use of an
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   987
  existential formula are rare; a standard one is @{text "\<exists>x. \<forall>y. P x
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   988
  \<longrightarrow> P y"}.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   989
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   990
  Forgoing quantifier replication loses completeness, but gains
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   991
  decidability, since the search space becomes finite.  Many useful
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   992
  theorems can be proved without replication, and the search generally
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   993
  delivers its verdict in a reasonable time.  To adopt this approach,
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   994
  represent the sequent rules @{text "(\<exists>R)"}, @{text "(\<exists>L)"} and
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   995
  @{text "(\<forall>R)"} by @{text "(\<exists>I)"}, @{text "(\<exists>E)"} and @{text "(\<forall>I)"},
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   996
  respectively, and put @{text "(\<forall>E)"} into elimination form: @{text
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   997
  [display] "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> Q) \<Longrightarrow> Q"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   998
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
   999
  Elim-resolution with this rule will delete the universal formula
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1000
  after a single use.  To replicate universal quantifiers, replace the
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1001
  rule by @{text [display] "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> \<forall>x. P x \<Longrightarrow> Q) \<Longrightarrow> Q"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1002
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1003
  To replicate existential quantifiers, replace @{text "(\<exists>I)"} by
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1004
  @{text [display] "(\<not> (\<exists>x. P x) \<Longrightarrow> P t) \<Longrightarrow> \<exists>x. P x"}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1005
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1006
  All introduction rules mentioned above are also useful in swapped
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1007
  form.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1008
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1009
  Replication makes the search space infinite; we must apply the rules
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1010
  with care.  The classical reasoner distinguishes between safe and
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1011
  unsafe rules, applying the latter only when there is no alternative.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1012
  Depth-first search may well go down a blind alley; best-first search
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1013
  is better behaved in an infinite search space.  However, quantifier
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1014
  replication is too expensive to prove any but the simplest theorems.
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1015
*}
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1016
c40adab7568e moved/updated introduction to Classical Reasoner;
wenzelm
parents: 42925
diff changeset
  1017
42928
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1018
subsection {* Rule declarations *}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1019
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1020
text {* The proof tools of the Classical Reasoner depend on
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1021
  collections of rules declared in the context, which are classified
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1022
  as introduction, elimination or destruction and as \emph{safe} or
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1023
  \emph{unsafe}.  In general, safe rules can be attempted blindly,
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1024
  while unsafe rules must be used with care.  A safe rule must never
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1025
  reduce a provable goal to an unprovable set of subgoals.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1026
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1027
  The rule @{text "P \<Longrightarrow> P \<or> Q"} is unsafe because it reduces @{text "P
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1028
  \<or> Q"} to @{text "P"}, which might turn out as premature choice of an
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1029
  unprovable subgoal.  Any rule is unsafe whose premises contain new
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1030
  unknowns.  The elimination rule @{text "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> Q) \<Longrightarrow> Q"} is
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1031
  unsafe, since it is applied via elim-resolution, which discards the
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1032
  assumption @{text "\<forall>x. P x"} and replaces it by the weaker
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1033
  assumption @{text "P t"}.  The rule @{text "P t \<Longrightarrow> \<exists>x. P x"} is
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1034
  unsafe for similar reasons.  The quantifier duplication rule @{text
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1035
  "\<forall>x. P x \<Longrightarrow> (P t \<Longrightarrow> \<forall>x. P x \<Longrightarrow> Q) \<Longrightarrow> Q"} is unsafe in a different sense:
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1036
  since it keeps the assumption @{text "\<forall>x. P x"}, it is prone to
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1037
  looping.  In classical first-order logic, all rules are safe except
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1038
  those mentioned above.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1039
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1040
  The safe~/ unsafe distinction is vague, and may be regarded merely
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1041
  as a way of giving some rules priority over others.  One could argue
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1042
  that @{text "(\<or>E)"} is unsafe, because repeated application of it
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1043
  could generate exponentially many subgoals.  Induction rules are
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1044
  unsafe because inductive proofs are difficult to set up
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1045
  automatically.  Any inference is unsafe that instantiates an unknown
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1046
  in the proof state --- thus matching must be used, rather than
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1047
  unification.  Even proof by assumption is unsafe if it instantiates
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1048
  unknowns shared with other subgoals.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1049
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1050
  \begin{matharray}{rcl}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1051
    @{command_def "print_claset"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1052
    @{attribute_def intro} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1053
    @{attribute_def elim} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1054
    @{attribute_def dest} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1055
    @{attribute_def rule} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1056
    @{attribute_def iff} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1057
    @{attribute_def swapped} & : & @{text attribute} \\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1058
  \end{matharray}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1059
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1060
  @{rail "
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1061
    (@@{attribute intro} | @@{attribute elim} | @@{attribute dest}) ('!' | () | '?') @{syntax nat}?
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1062
    ;
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1063
    @@{attribute rule} 'del'
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1064
    ;
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1065
    @@{attribute iff} (((() | 'add') '?'?) | 'del')
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1066
  "}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1067
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1068
  \begin{description}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1069
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1070
  \item @{command "print_claset"} prints the collection of rules
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1071
  declared to the Classical Reasoner, i.e.\ the @{ML_type claset}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1072
  within the context.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1073
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1074
  \item @{attribute intro}, @{attribute elim}, and @{attribute dest}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1075
  declare introduction, elimination, and destruction rules,
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1076
  respectively.  By default, rules are considered as \emph{unsafe}
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1077
  (i.e.\ not applied blindly without backtracking), while ``@{text
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1078
  "!"}'' classifies as \emph{safe}.  Rule declarations marked by
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1079
  ``@{text "?"}'' coincide with those of Isabelle/Pure, cf.\
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1080
  \secref{sec:pure-meth-att} (i.e.\ are only applied in single steps
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1081
  of the @{method rule} method).  The optional natural number
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1082
  specifies an explicit weight argument, which is ignored by the
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1083
  automated reasoning tools, but determines the search order of single
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1084
  rule steps.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1085
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1086
  Introduction rules are those that can be applied using ordinary
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1087
  resolution.  Their swapped forms are generated internally, which
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1088
  will be applied using elim-resolution.  Elimination rules are
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1089
  applied using elim-resolution.  Rules are sorted by the number of
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1090
  new subgoals they will yield; rules that generate the fewest
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1091
  subgoals will be tried first.  Otherwise, later declarations take
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1092
  precedence over earlier ones.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1093
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1094
  Rules already present in the context with the same classification
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1095
  are ignored.  A warning is printed if the rule has already been
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1096
  added with some other classification, but the rule is added anyway
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1097
  as requested.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1098
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1099
  \item @{attribute rule}~@{text del} deletes all occurrences of a
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1100
  rule from the classical context, regardless of its classification as
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1101
  introduction~/ elimination~/ destruction and safe~/ unsafe.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1102
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1103
  \item @{attribute iff} declares logical equivalences to the
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1104
  Simplifier and the Classical reasoner at the same time.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1105
  Non-conditional rules result in a safe introduction and elimination
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1106
  pair; conditional ones are considered unsafe.  Rules with negative
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1107
  conclusion are automatically inverted (using @{text "\<not>"}-elimination
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1108
  internally).
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1109
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1110
  The ``@{text "?"}'' version of @{attribute iff} declares rules to
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1111
  the Isabelle/Pure context only, and omits the Simplifier
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1112
  declaration.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1113
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1114
  \item @{attribute swapped} turns an introduction rule into an
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1115
  elimination, by resolving with the classical swap principle @{text
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1116
  "\<not> P \<Longrightarrow> (\<not> R \<Longrightarrow> P) \<Longrightarrow> R"} in the second position.  This is mainly for
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1117
  illustrative purposes: the Classical Reasoner already swaps rules
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1118
  internally as explained above.
9d946de41120 updated and re-unified classical rule declarations;
wenzelm
parents: 42927
diff changeset
  1119
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
  1120
  \end{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1121
*}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1122
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1123
43365
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1124
subsection {* Structured methods *}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1125
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1126
text {*
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1127
  \begin{matharray}{rcl}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1128
    @{method_def rule} & : & @{text method} \\
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1129
    @{method_def contradiction} & : & @{text method} \\
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1130
  \end{matharray}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1131
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1132
  @{rail "
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1133
    @@{method rule} @{syntax thmrefs}?
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1134
  "}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1135
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1136
  \begin{description}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1137
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1138
  \item @{method rule} as offered by the Classical Reasoner is a
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1139
  refinement over the Pure one (see \secref{sec:pure-meth-att}).  Both
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1140
  versions work the same, but the classical version observes the
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1141
  classical rule context in addition to that of Isabelle/Pure.
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1142
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1143
  Common object logics (HOL, ZF, etc.) declare a rich collection of
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1144
  classical rules (even if these would qualify as intuitionistic
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1145
  ones), but only few declarations to the rule context of
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1146
  Isabelle/Pure (\secref{sec:pure-meth-att}).
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1147
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1148
  \item @{method contradiction} solves some goal by contradiction,
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1149
  deriving any result from both @{text "\<not> A"} and @{text A}.  Chained
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1150
  facts, which are guaranteed to participate, may appear in either
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1151
  order.
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1152
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1153
  \end{description}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1154
*}
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1155
f8944cb2468f tuned sections;
wenzelm
parents: 43332
diff changeset
  1156
27040
3d3e6e07b931 major reorganization of document structure;
wenzelm
parents: 26901
diff changeset
  1157
subsection {* Automated methods *}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1158
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1159
text {*
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1160
  \begin{matharray}{rcl}
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1161
    @{method_def blast} & : & @{text method} \\
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1162
    @{method_def auto} & : & @{text method} \\
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1163
    @{method_def force} & : & @{text method} \\
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1164
    @{method_def fast} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1165
    @{method_def slow} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1166
    @{method_def best} & : & @{text method} \\
44911
884d27ede438 fastsimp -> fastforce in doc
nipkow
parents: 44094
diff changeset
  1167
    @{method_def fastforce} & : & @{text method} \\
28761
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1168
    @{method_def slowsimp} & : & @{text method} \\
9ec4482c9201 updated/refined types of Isar language elements, removed special LaTeX macros;
wenzelm
parents: 28760
diff changeset
  1169
    @{method_def bestsimp} & : & @{text method} \\
43367
3f1469de9e47 cover method "deepen" concisely;
wenzelm
parents: 43366
diff changeset
  1170
    @{method_def deepen} & : & @{text method} \\
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1171
  \end{matharray}
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1172
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
  1173
  @{rail "
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1174
    @@{method blast} @{syntax nat}? (@{syntax clamod} * )
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1175
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
  1176
    @@{method auto} (@{syntax nat} @{syntax nat})? (@{syntax clasimpmod} * )
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1177
    ;
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1178
    @@{method force} (@{syntax clasimpmod} * )
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1179
    ;
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1180
    (@@{method fast} | @@{method slow} | @@{method best}) (@{syntax clamod} * )
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1181
    ;
44911
884d27ede438 fastsimp -> fastforce in doc
nipkow
parents: 44094
diff changeset
  1182
    (@@{method fastforce} | @@{method slowsimp} | @@{method bestsimp})
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1183
      (@{syntax clasimpmod} * )
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1184
    ;
43367
3f1469de9e47 cover method "deepen" concisely;
wenzelm
parents: 43366
diff changeset
  1185
    @@{method deepen} (@{syntax nat} ?) (@{syntax clamod} * )
3f1469de9e47 cover method "deepen" concisely;
wenzelm
parents: 43366
diff changeset
  1186
    ;
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1187
    @{syntax_def clamod}:
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1188
      (('intro' | 'elim' | 'dest') ('!' | () | '?') | 'del') ':' @{syntax thmrefs}
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1189
    ;
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
  1190
    @{syntax_def clasimpmod}: ('simp' (() | 'add' | 'del' | 'only') |
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1191
      ('cong' | 'split') (() | 'add' | 'del') |
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1192
      'iff' (((() | 'add') '?'?) | 'del') |
42596
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
  1193
      (('intro' | 'elim' | 'dest') ('!' | () | '?') | 'del')) ':' @{syntax thmrefs}
6c621a9d612a modernized rail diagrams using @{rail} antiquotation;
wenzelm
parents: 40291
diff changeset
  1194
  "}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1195
28760
cbc435f7b16b unified use of declaration environment with IsarImplementation;
wenzelm
parents: 28754
diff changeset
  1196
  \begin{description}
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1197
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1198
  \item @{method blast} is a separate classical tableau prover that
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1199
  uses the same classical rule declarations as explained before.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1200
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1201
  Proof search is coded directly in ML using special data structures.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1202
  A successful proof is then reconstructed using regular Isabelle
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1203
  inferences.  It is faster and more powerful than the other classical
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1204
  reasoning tools, but has major limitations too.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1205
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1206
  \begin{itemize}
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1207
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1208
  \item It does not use the classical wrapper tacticals, such as the
44911
884d27ede438 fastsimp -> fastforce in doc
nipkow
parents: 44094
diff changeset
  1209
  integration with the Simplifier of @{method fastforce}.
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1210
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1211
  \item It does not perform higher-order unification, as needed by the
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1212
  rule @{thm [source=false] rangeI} in HOL.  There are often
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1213
  alternatives to such rules, for example @{thm [source=false]
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1214
  range_eqI}.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1215
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1216
  \item Function variables may only be applied to parameters of the
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1217
  subgoal.  (This restriction arises because the prover does not use
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1218
  higher-order unification.)  If other function variables are present
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1219
  then the prover will fail with the message \texttt{Function Var's
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1220
  argument not a bound variable}.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1221
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1222
  \item Its proof strategy is more general than @{method fast} but can
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1223
  be slower.  If @{method blast} fails or seems to be running forever,
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1224
  try @{method fast} and the other proof tools described below.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1225
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1226
  \end{itemize}
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1227
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1228
  The optional integer argument specifies a bound for the number of
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1229
  unsafe steps used in a proof.  By default, @{method blast} starts
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1230
  with a bound of 0 and increases it successively to 20.  In contrast,
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1231
  @{text "(blast lim)"} tries to prove the goal using a search bound
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1232
  of @{text "lim"}.  Sometimes a slow proof using @{method blast} can
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1233
  be made much faster by supplying the successful search bound to this
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1234
  proof method instead.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1235
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1236
  \item @{method auto} combines classical reasoning with
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1237
  simplification.  It is intended for situations where there are a lot
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1238
  of mostly trivial subgoals; it proves all the easy ones, leaving the
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1239
  ones it cannot prove.  Occasionally, attempting to prove the hard
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1240
  ones may take a long time.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1241
43332
dca2c7c598f0 document depth arguments of method "auto";
wenzelm
parents: 42930
diff changeset
  1242
  The optional depth arguments in @{text "(auto m n)"} refer to its
dca2c7c598f0 document depth arguments of method "auto";
wenzelm
parents: 42930
diff changeset
  1243
  builtin classical reasoning procedures: @{text m} (default 4) is for
dca2c7c598f0 document depth arguments of method "auto";
wenzelm
parents: 42930
diff changeset
  1244
  @{method blast}, which is tried first, and @{text n} (default 2) is
dca2c7c598f0 document depth arguments of method "auto";
wenzelm
parents: 42930
diff changeset
  1245
  for a slower but more general alternative that also takes wrappers
dca2c7c598f0 document depth arguments of method "auto";
wenzelm
parents: 42930
diff changeset
  1246
  into account.
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1247
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1248
  \item @{method force} is intended to prove the first subgoal
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1249
  completely, using many fancy proof tools and performing a rather
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1250
  exhaustive search.  As a result, proof attempts may take rather long
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1251
  or diverge easily.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1252
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1253
  \item @{method fast}, @{method best}, @{method slow} attempt to
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1254
  prove the first subgoal using sequent-style reasoning as explained
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1255
  before.  Unlike @{method blast}, they construct proofs directly in
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1256
  Isabelle.
26782
19363c70b5c4 converted generic.tex to Thy/Generic.thy;
wenzelm
parents:
diff changeset
  1257
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1258
  There is a difference in search strategy and back-tracking: @{method
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1259
  fast} uses depth-first search and @{method best} uses best-first
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1260
  search (guided by a heuristic function: normally the total size of
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1261
  the proof state).
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1262
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1263
  Method @{method slow} is like @{method fast}, but conducts a broader
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1264
  search: it may, when backtracking from a failed proof attempt, undo
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1265
  even the step of proving a subgoal by assumption.
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1266
47967
c422128d3889 discontinued obsolete method fastsimp / tactic fast_simp_tac;
wenzelm
parents: 47497
diff changeset
  1267
  \item @{method fastforce}, @{method slowsimp}, @{method bestsimp}
c422128d3889 discontinued obsolete method fastsimp / tactic fast_simp_tac;
wenzelm
parents: 47497
diff changeset
  1268
  are like @{method fast}, @{method slow}, @{method best},
c422128d3889 discontinued obsolete method fastsimp / tactic fast_simp_tac;
wenzelm
parents: 47497
diff changeset
  1269
  respectively, but use the Simplifier as additional wrapper. The name
c422128d3889 discontinued obsolete method fastsimp / tactic fast_simp_tac;
wenzelm
parents: 47497
diff changeset
  1270
  @{method fastforce}, reflects the behaviour of this popular method
c422128d3889 discontinued obsolete method fastsimp / tactic fast_simp_tac;
wenzelm
parents: 47497
diff changeset
  1271
  better without requiring an understanding of its implementation.
42930
41394a61cca9 updated and re-unified classical proof methods;
wenzelm
parents: 42929
diff changeset
  1272
43367
3f1469de9e47 cover method "deepen" concisely;
wenzelm
parents: 43366
diff changeset
  1273
  \item @{method deepen} works by exhaustive search up to a certain
3f1469de9e47 cover method "deepen" concisely;
wenzelm
parents: 43366
diff changeset
  1274
  de