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} \\ |
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>"} \\ |