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