doc-src/Ref/classical.tex
changeset 11181 d04f57b91166
parent 9695 ec7d7f877712
child 12366 f0fd3c4f2f49
equal deleted inserted replaced
11180:39d3b8e8ad5c 11181:d04f57b91166
   124 where the order of the assumptions and the choice of~$Q@1$ are arbitrary.
   124 where the order of the assumptions and the choice of~$Q@1$ are arbitrary.
   125 Elim-resolution plays a key role in simulating sequent proofs.
   125 Elim-resolution plays a key role in simulating sequent proofs.
   126 
   126 
   127 We can easily handle reasoning on the left.
   127 We can easily handle reasoning on the left.
   128 As discussed in
   128 As discussed in
   129 \iflabelundefined{destruct}{{\it Introduction to Isabelle}}{\S\ref{destruct}}, 
   129 \iflabelundefined{destruct}{{\it Introduction to Isabelle}}{{\S}\ref{destruct}}, 
   130 elim-resolution with the rules $(\disj E)$, $(\bot E)$ and $(\exists E)$
   130 elim-resolution with the rules $(\disj E)$, $(\bot E)$ and $(\exists E)$
   131 achieves a similar effect as the corresponding sequent rules.  For the
   131 achieves a similar effect as the corresponding sequent rules.  For the
   132 other connectives, we use sequent-style elimination rules instead of
   132 other connectives, we use sequent-style elimination rules instead of
   133 destruction rules such as $({\conj}E1,2)$ and $(\forall E)$.  But note that
   133 destruction rules such as $({\conj}E1,2)$ and $(\forall E)$.  But note that
   134 the rule $(\neg L)$ has no effect under our representation of sequents!
   134 the rule $(\neg L)$ has no effect under our representation of sequents!
   309 Introduction rules are those that can be applied using ordinary resolution.
   309 Introduction rules are those that can be applied using ordinary resolution.
   310 The classical set automatically generates their swapped forms, which will
   310 The classical set automatically generates their swapped forms, which will
   311 be applied using elim-resolution.  Elimination rules are applied using
   311 be applied using elim-resolution.  Elimination rules are applied using
   312 elim-resolution.  In a classical set, rules are sorted by the number of new
   312 elim-resolution.  In a classical set, rules are sorted by the number of new
   313 subgoals they will yield; rules that generate the fewest subgoals will be
   313 subgoals they will yield; rules that generate the fewest subgoals will be
   314 tried first (see \S\ref{biresolve_tac}).
   314 tried first (see {\S}\ref{biresolve_tac}).
   315 
   315 
   316 For elimination and destruction rules there are variants of the add operations
   316 For elimination and destruction rules there are variants of the add operations
   317 adding a rule in a way such that it is applied only if also its second premise
   317 adding a rule in a way such that it is applied only if also its second premise
   318 can be unified with an assumption of the current proof state:
   318 can be unified with an assumption of the current proof state:
   319 \indexbold{*addSE2}\indexbold{*addSD2}\indexbold{*addE2}\indexbold{*addD2}
   319 \indexbold{*addSE2}\indexbold{*addSD2}\indexbold{*addE2}\indexbold{*addD2}
   335 \label{sec:modifying-search}
   335 \label{sec:modifying-search}
   336 For a given classical set, the proof strategy is simple.  Perform as many safe
   336 For a given classical set, the proof strategy is simple.  Perform as many safe
   337 inferences as possible; or else, apply certain safe rules, allowing
   337 inferences as possible; or else, apply certain safe rules, allowing
   338 instantiation of unknowns; or else, apply an unsafe rule.  The tactics also
   338 instantiation of unknowns; or else, apply an unsafe rule.  The tactics also
   339 eliminate assumptions of the form $x=t$ by substitution if they have been set
   339 eliminate assumptions of the form $x=t$ by substitution if they have been set
   340 up to do so (see \texttt{hyp_subst_tacs} in~\S\ref{sec:classical-setup} below).
   340 up to do so (see \texttt{hyp_subst_tacs} in~{\S}\ref{sec:classical-setup} below).
   341 They may perform a form of Modus Ponens: if there are assumptions $P\imp Q$
   341 They may perform a form of Modus Ponens: if there are assumptions $P\imp Q$
   342 and~$P$, then replace $P\imp Q$ by~$Q$.
   342 and~$P$, then replace $P\imp Q$ by~$Q$.
   343 
   343 
   344 The classical reasoning tactics --- except \texttt{blast_tac}! --- allow
   344 The classical reasoning tactics --- except \texttt{blast_tac}! --- allow
   345 you to modify this basic proof strategy by applying two lists of arbitrary 
   345 you to modify this basic proof strategy by applying two lists of arbitrary 
   360 \begin{ttbox} 
   360 \begin{ttbox} 
   361 type wrapper = (int -> tactic) -> (int -> tactic);
   361 type wrapper = (int -> tactic) -> (int -> tactic);
   362 
   362 
   363 addSWrapper  : claset * (string *  wrapper       ) -> claset \hfill{\bf infix 4}
   363 addSWrapper  : claset * (string *  wrapper       ) -> claset \hfill{\bf infix 4}
   364 addSbefore   : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   364 addSbefore   : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   365 addSaltern   : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   365 addSafter    : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   366 delSWrapper  : claset *  string                    -> claset \hfill{\bf infix 4}
   366 delSWrapper  : claset *  string                    -> claset \hfill{\bf infix 4}
   367 
   367 
   368 addWrapper   : claset * (string *  wrapper       ) -> claset \hfill{\bf infix 4}
   368 addWrapper   : claset * (string *  wrapper       ) -> claset \hfill{\bf infix 4}
   369 addbefore    : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   369 addbefore    : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   370 addaltern    : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   370 addafter     : claset * (string * (int -> tactic)) -> claset \hfill{\bf infix 4}
   371 delWrapper   : claset *  string                    -> claset \hfill{\bf infix 4}
   371 delWrapper   : claset *  string                    -> claset \hfill{\bf infix 4}
   372 
   372 
   373 addSss       : claset * simpset -> claset                 \hfill{\bf infix 4}
   373 addSss       : claset * simpset -> claset                 \hfill{\bf infix 4}
   374 addss        : claset * simpset -> claset                 \hfill{\bf infix 4}
   374 addss        : claset * simpset -> claset                 \hfill{\bf infix 4}
   375 \end{ttbox}
   375 \end{ttbox}
   382 
   382 
   383 \item[$cs$ addSbefore $(name,tac)$] \indexbold{*addSbefore}
   383 \item[$cs$ addSbefore $(name,tac)$] \indexbold{*addSbefore}
   384 adds the given tactic as a safe wrapper, such that it is tried 
   384 adds the given tactic as a safe wrapper, such that it is tried 
   385 {\em before} each safe step of the search.
   385 {\em before} each safe step of the search.
   386 
   386 
   387 \item[$cs$ addSaltern $(name,tac)$] \indexbold{*addSaltern}
   387 \item[$cs$ addSafter $(name,tac)$] \indexbold{*addSafter}
   388 adds the given tactic as a safe wrapper, such that it is tried 
   388 adds the given tactic as a safe wrapper, such that it is tried 
   389 when a safe step of the search would fail.
   389 when a safe step of the search would fail.
   390 
   390 
   391 \item[$cs$ delSWrapper $name$] \indexbold{*delSWrapper}
   391 \item[$cs$ delSWrapper $name$] \indexbold{*delSWrapper}
   392 deletes the safe wrapper with the given name.
   392 deletes the safe wrapper with the given name.
   396 
   396 
   397 \item[$cs$ addbefore $(name,tac)$] \indexbold{*addbefore}
   397 \item[$cs$ addbefore $(name,tac)$] \indexbold{*addbefore}
   398 adds the given tactic as an unsafe wrapper, such that it its result is 
   398 adds the given tactic as an unsafe wrapper, such that it its result is 
   399 concatenated {\em before} the result of each unsafe step.
   399 concatenated {\em before} the result of each unsafe step.
   400 
   400 
   401 \item[$cs$ addaltern $(name,tac)$] \indexbold{*addaltern}
   401 \item[$cs$ addafter $(name,tac)$] \indexbold{*addafter}
   402 adds the given tactic as an unsafe wrapper, such that it its result is 
   402 adds the given tactic as an unsafe wrapper, such that it its result is 
   403 concatenated {\em after} the result of each unsafe step.
   403 concatenated {\em after} the result of each unsafe step.
   404 
   404 
   405 \item[$cs$ delWrapper $name$] \indexbold{*delWrapper}
   405 \item[$cs$ delWrapper $name$] \indexbold{*delWrapper}
   406 deletes the unsafe wrapper with the given name.
   406 deletes the unsafe wrapper with the given name.
   417 
   417 
   418 \index{simplification!from classical reasoner} 
   418 \index{simplification!from classical reasoner} 
   419 Strictly speaking, the operators \texttt{addss} and \texttt{addSss}
   419 Strictly speaking, the operators \texttt{addss} and \texttt{addSss}
   420 are not part of the classical reasoner.
   420 are not part of the classical reasoner.
   421 , which are used as primitives 
   421 , which are used as primitives 
   422 for the automatic tactics described in \S\ref{sec:automatic-tactics}, are
   422 for the automatic tactics described in {\S}\ref{sec:automatic-tactics}, are
   423 implemented as wrapper tacticals.
   423 implemented as wrapper tacticals.
   424 they  
   424 they  
   425 \begin{warn}
   425 \begin{warn}
   426 Being defined as wrappers, these operators are inappropriate for adding more 
   426 Being defined as wrappers, these operators are inappropriate for adding more 
   427 than one simpset at a time: the simpset added last overwrites any earlier ones.
   427 than one simpset at a time: the simpset added last overwrites any earlier ones.
   431 
   431 
   432 
   432 
   433 \section{The classical tactics}
   433 \section{The classical tactics}
   434 \index{classical reasoner!tactics} If installed, the classical module provides
   434 \index{classical reasoner!tactics} If installed, the classical module provides
   435 powerful theorem-proving tactics.  Most of them have capitalized analogues
   435 powerful theorem-proving tactics.  Most of them have capitalized analogues
   436 that use the default claset; see \S\ref{sec:current-claset}.
   436 that use the default claset; see {\S}\ref{sec:current-claset}.
   437 
   437 
   438 
   438 
   439 \subsection{The tableau prover}
   439 \subsection{The tableau prover}
   440 The tactic \texttt{blast_tac} searches for a proof using a fast tableau prover,
   440 The tactic \texttt{blast_tac} searches for a proof using a fast tableau prover,
   441 coded directly in \ML.  It then reconstructs the proof using Isabelle
   441 coded directly in \ML.  It then reconstructs the proof using Isabelle
   502 completely. It tries to apply all fancy tactics it knows about, 
   502 completely. It tries to apply all fancy tactics it knows about, 
   503 performing a rather exhaustive search.
   503 performing a rather exhaustive search.
   504 \end{ttdescription}
   504 \end{ttdescription}
   505 They must be supplied both a simpset and a claset; therefore 
   505 They must be supplied both a simpset and a claset; therefore 
   506 they are most easily called as \texttt{Auto_tac} and \texttt{Force_tac}, which 
   506 they are most easily called as \texttt{Auto_tac} and \texttt{Force_tac}, which 
   507 use the default claset and simpset (see \S\ref{sec:current-claset} below). 
   507 use the default claset and simpset (see {\S}\ref{sec:current-claset} below). 
   508 For interactive use, 
   508 For interactive use, 
   509 the shorthand \texttt{auto();} abbreviates \texttt{by Auto_tac;} 
   509 the shorthand \texttt{auto();} abbreviates \texttt{by Auto_tac;} 
   510 while \texttt{force 1;} abbreviates \texttt{by (Force_tac 1);}
   510 while \texttt{force 1;} abbreviates \texttt{by (Force_tac 1);}
   511 
   511 
   512 
   512 
   627 \subsection{The current claset}\label{sec:current-claset}
   627 \subsection{The current claset}\label{sec:current-claset}
   628 
   628 
   629 Each theory is equipped with an implicit \emph{current claset}
   629 Each theory is equipped with an implicit \emph{current claset}
   630 \index{claset!current}.  This is a default set of classical
   630 \index{claset!current}.  This is a default set of classical
   631 rules.  The underlying idea is quite similar to that of a current
   631 rules.  The underlying idea is quite similar to that of a current
   632 simpset described in \S\ref{sec:simp-for-dummies}; please read that
   632 simpset described in {\S}\ref{sec:simp-for-dummies}; please read that
   633 section, including its warnings.  
   633 section, including its warnings.  
   634 
   634 
   635 The tactics
   635 The tactics
   636 \begin{ttbox}
   636 \begin{ttbox}
   637 Blast_tac        : int -> tactic
   637 Blast_tac        : int -> tactic