doc-src/IsarRef/Thy/Proof.thy
changeset 30240 5b25fee0362c
parent 28856 5e009a80fe6d
child 30242 aea5d7fa7ef5
equal deleted inserted replaced
30239:179ff9cb160b 30240:5b25fee0362c
     1 (* $Id$ *)
       
     2 
       
     3 theory Proof
     1 theory Proof
     4 imports Main
     2 imports Main
     5 begin
     3 begin
     6 
     4 
     7 chapter {* Proofs *}
     5 chapter {* Proofs \label{ch:proofs} *}
     8 
     6 
     9 text {*
     7 text {*
    10   Proof commands perform transitions of Isar/VM machine
     8   Proof commands perform transitions of Isar/VM machine
    11   configurations, which are block-structured, consisting of a stack of
     9   configurations, which are block-structured, consisting of a stack of
    12   nodes with three main components: logical proof context, current
    10   nodes with three main components: logical proof context, current
    13   facts, and open goals.  Isar/VM transitions are \emph{typed}
    11   facts, and open goals.  Isar/VM transitions are typed according to
    14   according to the following three different modes of operation:
    12   the following three different modes of operation:
    15 
    13 
    16   \begin{description}
    14   \begin{description}
    17 
    15 
    18   \item @{text "proof(prove)"} means that a new goal has just been
    16   \item @{text "proof(prove)"} means that a new goal has just been
    19   stated that is now to be \emph{proven}; the next command may refine
    17   stated that is now to be \emph{proven}; the next command may refine
    30   just picked up in order to be used when refining the goal claimed
    28   just picked up in order to be used when refining the goal claimed
    31   next.
    29   next.
    32 
    30 
    33   \end{description}
    31   \end{description}
    34 
    32 
    35   The proof mode indicator may be read as a verb telling the writer
    33   The proof mode indicator may be understood as an instruction to the
    36   what kind of operation may be performed next.  The corresponding
    34   writer, telling what kind of operation may be performed next.  The
    37   typings of proof commands restricts the shape of well-formed proof
    35   corresponding typings of proof commands restricts the shape of
    38   texts to particular command sequences.  So dynamic arrangements of
    36   well-formed proof texts to particular command sequences.  So dynamic
    39   commands eventually turn out as static texts of a certain structure.
    37   arrangements of commands eventually turn out as static texts of a
    40   \Appref{ap:refcard} gives a simplified grammar of the overall
    38   certain structure.
    41   (extensible) language emerging that way.
    39 
       
    40   \Appref{ap:refcard} gives a simplified grammar of the (extensible)
       
    41   language emerging that way from the different types of proof
       
    42   commands.  The main ideas of the overall Isar framework are
       
    43   explained in \chref{ch:isar-framework}.
    42 *}
    44 *}
    43 
    45 
    44 
    46 
    45 section {* Proof structure *}
    47 section {* Proof structure *}
    46 
    48 
   679     @{method_def "-"} & : & @{text method} \\
   681     @{method_def "-"} & : & @{text method} \\
   680     @{method_def "fact"} & : & @{text method} \\
   682     @{method_def "fact"} & : & @{text method} \\
   681     @{method_def "assumption"} & : & @{text method} \\
   683     @{method_def "assumption"} & : & @{text method} \\
   682     @{method_def "this"} & : & @{text method} \\
   684     @{method_def "this"} & : & @{text method} \\
   683     @{method_def "rule"} & : & @{text method} \\
   685     @{method_def "rule"} & : & @{text method} \\
   684     @{method_def "iprover"} & : & @{text method} \\[0.5ex]
       
   685     @{attribute_def (Pure) "intro"} & : & @{text attribute} \\
   686     @{attribute_def (Pure) "intro"} & : & @{text attribute} \\
   686     @{attribute_def (Pure) "elim"} & : & @{text attribute} \\
   687     @{attribute_def (Pure) "elim"} & : & @{text attribute} \\
   687     @{attribute_def (Pure) "dest"} & : & @{text attribute} \\
   688     @{attribute_def (Pure) "dest"} & : & @{text attribute} \\
   688     @{attribute_def "rule"} & : & @{text attribute} \\[0.5ex]
   689     @{attribute_def "rule"} & : & @{text attribute} \\[0.5ex]
   689     @{attribute_def "OF"} & : & @{text attribute} \\
   690     @{attribute_def "OF"} & : & @{text attribute} \\
   693 
   694 
   694   \begin{rail}
   695   \begin{rail}
   695     'fact' thmrefs?
   696     'fact' thmrefs?
   696     ;
   697     ;
   697     'rule' thmrefs?
   698     'rule' thmrefs?
   698     ;
       
   699     'iprover' ('!' ?) (rulemod *)
       
   700     ;
   699     ;
   701     rulemod: ('intro' | 'elim' | 'dest') ((('!' | () | '?') nat?) | 'del') ':' thmrefs
   700     rulemod: ('intro' | 'elim' | 'dest') ((('!' | () | '?') nat?) | 'del') ':' thmrefs
   702     ;
   701     ;
   703     ('intro' | 'elim' | 'dest') ('!' | () | '?') nat?
   702     ('intro' | 'elim' | 'dest') ('!' | () | '?') nat?
   704     ;
   703     ;
   754   using the @{attribute (Pure) intro}, @{attribute (Pure) elim},
   753   using the @{attribute (Pure) intro}, @{attribute (Pure) elim},
   755   @{attribute (Pure) dest} attributes (see below).  This is the
   754   @{attribute (Pure) dest} attributes (see below).  This is the
   756   default behavior of @{command "proof"} and ``@{command ".."}'' 
   755   default behavior of @{command "proof"} and ``@{command ".."}'' 
   757   (double-dot) steps (see \secref{sec:proof-steps}).
   756   (double-dot) steps (see \secref{sec:proof-steps}).
   758   
   757   
   759   \item @{method iprover} performs intuitionistic proof search,
       
   760   depending on specifically declared rules from the context, or given
       
   761   as explicit arguments.  Chained facts are inserted into the goal
       
   762   before commencing proof search; ``@{method iprover}@{text "!"}''
       
   763   means to include the current @{fact prems} as well.
       
   764   
       
   765   Rules need to be classified as @{attribute (Pure) intro},
       
   766   @{attribute (Pure) elim}, or @{attribute (Pure) dest}; here the
       
   767   ``@{text "!"}'' indicator refers to ``safe'' rules, which may be
       
   768   applied aggressively (without considering back-tracking later).
       
   769   Rules declared with ``@{text "?"}'' are ignored in proof search (the
       
   770   single-step @{method rule} method still observes these).  An
       
   771   explicit weight annotation may be given as well; otherwise the
       
   772   number of rule premises will be taken into account here.
       
   773   
       
   774   \item @{attribute (Pure) intro}, @{attribute (Pure) elim}, and
   758   \item @{attribute (Pure) intro}, @{attribute (Pure) elim}, and
   775   @{attribute (Pure) dest} declare introduction, elimination, and
   759   @{attribute (Pure) dest} declare introduction, elimination, and
   776   destruct rules, to be used with the @{method rule} and @{method
   760   destruct rules, to be used with method @{method rule}, and similar
   777   iprover} methods.  Note that the latter will ignore rules declared
   761   tools.  Note that the latter will ignore rules declared with
   778   with ``@{text "?"}'', while ``@{text "!"}''  are used most
   762   ``@{text "?"}'', while ``@{text "!"}''  are used most aggressively.
   779   aggressively.
       
   780   
   763   
   781   The classical reasoner (see \secref{sec:classical}) introduces its
   764   The classical reasoner (see \secref{sec:classical}) introduces its
   782   own variants of these attributes; use qualified names to access the
   765   own variants of these attributes; use qualified names to access the
   783   present versions of Isabelle/Pure, i.e.\ @{attribute (Pure)
   766   present versions of Isabelle/Pure, i.e.\ @{attribute (Pure)
   784   "Pure.intro"}.
   767   "Pure.intro"}.
   961   (where @{text "b\<^sub>1, \<dots>, b\<^sub>k"} shall refer to (optional)
   944   (where @{text "b\<^sub>1, \<dots>, b\<^sub>k"} shall refer to (optional)
   962   facts indicated for forward chaining).
   945   facts indicated for forward chaining).
   963   \begin{matharray}{l}
   946   \begin{matharray}{l}
   964     @{text "\<langle>using b\<^sub>1 \<dots> b\<^sub>k\<rangle>"}~~@{command "obtain"}~@{text "x\<^sub>1 \<dots> x\<^sub>m \<WHERE> a: \<phi>\<^sub>1 \<dots> \<phi>\<^sub>n  \<langle>proof\<rangle> \<equiv>"} \\[1ex]
   947     @{text "\<langle>using b\<^sub>1 \<dots> b\<^sub>k\<rangle>"}~~@{command "obtain"}~@{text "x\<^sub>1 \<dots> x\<^sub>m \<WHERE> a: \<phi>\<^sub>1 \<dots> \<phi>\<^sub>n  \<langle>proof\<rangle> \<equiv>"} \\[1ex]
   965     \quad @{command "have"}~@{text "\<And>thesis. (\<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis) \<Longrightarrow> thesis"} \\
   948     \quad @{command "have"}~@{text "\<And>thesis. (\<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis) \<Longrightarrow> thesis"} \\
   966     \quad @{command "proof"}~@{text succeed} \\
   949     \quad @{command "proof"}~@{method succeed} \\
   967     \qquad @{command "fix"}~@{text thesis} \\
   950     \qquad @{command "fix"}~@{text thesis} \\
   968     \qquad @{command "assume"}~@{text "that [Pure.intro?]: \<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis"} \\
   951     \qquad @{command "assume"}~@{text "that [Pure.intro?]: \<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis"} \\
   969     \qquad @{command "then"}~@{command "show"}~@{text thesis} \\
   952     \qquad @{command "then"}~@{command "show"}~@{text thesis} \\
   970     \quad\qquad @{command "apply"}~@{text -} \\
   953     \quad\qquad @{command "apply"}~@{text -} \\
   971     \quad\qquad @{command "using"}~@{text "b\<^sub>1 \<dots> b\<^sub>k  \<langle>proof\<rangle>"} \\
   954     \quad\qquad @{command "using"}~@{text "b\<^sub>1 \<dots> b\<^sub>k  \<langle>proof\<rangle>"} \\