equal
deleted
inserted
replaced
93 \item @{method erule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, @{method |
93 \item @{method erule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, @{method |
94 drule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, and @{method frule}~@{text |
94 drule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"}, and @{method frule}~@{text |
95 "a\<^sub>1 \<dots> a\<^sub>n"} are similar to the basic @{method rule} |
95 "a\<^sub>1 \<dots> a\<^sub>n"} are similar to the basic @{method rule} |
96 method (see \secref{sec:pure-meth-att}), but apply rules by |
96 method (see \secref{sec:pure-meth-att}), but apply rules by |
97 elim-resolution, destruct-resolution, and forward-resolution, |
97 elim-resolution, destruct-resolution, and forward-resolution, |
98 respectively \cite{isabelle-implementation}. The optional natural |
98 respectively @{cite "isabelle-implementation"}. The optional natural |
99 number argument (default 0) specifies additional assumption steps to |
99 number argument (default 0) specifies additional assumption steps to |
100 be performed here. |
100 be performed here. |
101 |
101 |
102 Note that these methods are improper ones, mainly serving for |
102 Note that these methods are improper ones, mainly serving for |
103 experimentation and tactic script emulation. Different modes of |
103 experimentation and tactic script emulation. Different modes of |
156 Note that @{attribute untagged} removes any tags of the same name. |
156 Note that @{attribute untagged} removes any tags of the same name. |
157 |
157 |
158 \item @{attribute THEN}~@{text a} composes rules by resolution; it |
158 \item @{attribute THEN}~@{text a} composes rules by resolution; it |
159 resolves with the first premise of @{text a} (an alternative |
159 resolves with the first premise of @{text a} (an alternative |
160 position may be also specified). See also @{ML_op "RS"} in |
160 position may be also specified). See also @{ML_op "RS"} in |
161 \cite{isabelle-implementation}. |
161 @{cite "isabelle-implementation"}. |
162 |
162 |
163 \item @{attribute unfolded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{attribute |
163 \item @{attribute unfolded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} and @{attribute |
164 folded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} expand and fold back again the given |
164 folded}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} expand and fold back again the given |
165 definitions throughout a rule. |
165 definitions throughout a rule. |
166 |
166 |
317 |
317 |
318 \begin{description} |
318 \begin{description} |
319 |
319 |
320 \item @{method rule_tac} etc. do resolution of rules with explicit |
320 \item @{method rule_tac} etc. do resolution of rules with explicit |
321 instantiation. This works the same way as the ML tactics @{ML |
321 instantiation. This works the same way as the ML tactics @{ML |
322 res_inst_tac} etc. (see \cite{isabelle-implementation}) |
322 res_inst_tac} etc.\ (see @{cite "isabelle-implementation"}). |
323 |
323 |
324 Multiple rules may be only given if there is no instantiation; then |
324 Multiple rules may be only given if there is no instantiation; then |
325 @{method rule_tac} is the same as @{ML resolve_tac} in ML (see |
325 @{method rule_tac} is the same as @{ML resolve_tac} in ML (see |
326 \cite{isabelle-implementation}). |
326 @{cite "isabelle-implementation"}). |
327 |
327 |
328 \item @{method cut_tac} inserts facts into the proof state as |
328 \item @{method cut_tac} inserts facts into the proof state as |
329 assumption of a subgoal; instantiations may be given as well. Note |
329 assumption of a subgoal; instantiations may be given as well. Note |
330 that the scope of schematic variables is spread over the main goal |
330 that the scope of schematic variables is spread over the main goal |
331 statement and rule premises are turned into new subgoals. This is |
331 statement and rule premises are turned into new subgoals. This is |
647 For example: |
647 For example: |
648 |
648 |
649 @{text "(?x + ?y) + ?z \<equiv> ?x + (?y + ?z)"} \\ |
649 @{text "(?x + ?y) + ?z \<equiv> ?x + (?y + ?z)"} \\ |
650 @{text "f (f ?x ?y) ?z \<equiv> f ?x (f ?y ?z)"} |
650 @{text "f (f ?x ?y) ?z \<equiv> f ?x (f ?y ?z)"} |
651 |
651 |
652 \item Higher-order patterns in the sense of \cite{nipkow-patterns}. |
652 \item Higher-order patterns in the sense of @{cite "nipkow-patterns"}. |
653 These are terms in @{text "\<beta>"}-normal form (this will always be the |
653 These are terms in @{text "\<beta>"}-normal form (this will always be the |
654 case unless you have done something strange) where each occurrence |
654 case unless you have done something strange) where each occurrence |
655 of an unknown is of the form @{text "?F x\<^sub>1 \<dots> x\<^sub>n"}, where the |
655 of an unknown is of the form @{text "?F x\<^sub>1 \<dots> x\<^sub>n"}, where the |
656 @{text "x\<^sub>i"} are distinct bound variables. |
656 @{text "x\<^sub>i"} are distinct bound variables. |
657 |
657 |
844 lemma "(b \<bullet> c) \<bullet> a = c \<bullet> (b \<bullet> a)" by (simp only: AC_rules) |
844 lemma "(b \<bullet> c) \<bullet> a = c \<bullet> (b \<bullet> a)" by (simp only: AC_rules) |
845 lemma "(b \<bullet> c) \<bullet> a = (c \<bullet> b) \<bullet> a" by (simp only: AC_rules) |
845 lemma "(b \<bullet> c) \<bullet> a = (c \<bullet> b) \<bullet> a" by (simp only: AC_rules) |
846 |
846 |
847 end |
847 end |
848 |
848 |
849 text {* Martin and Nipkow \cite{martin-nipkow} discuss the theory and |
849 text {* Martin and Nipkow @{cite "martin-nipkow"} discuss the theory and |
850 give many examples; other algebraic structures are amenable to |
850 give many examples; other algebraic structures are amenable to |
851 ordered rewriting, such as Boolean rings. The Boyer-Moore theorem |
851 ordered rewriting, such as Boolean rings. The Boyer-Moore theorem |
852 prover \cite{bm88book} also employs ordered rewriting. |
852 prover @{cite bm88book} also employs ordered rewriting. |
853 *} |
853 *} |
854 |
854 |
855 |
855 |
856 subsubsection {* Re-orienting equalities *} |
856 subsubsection {* Re-orienting equalities *} |
857 |
857 |
901 \item @{attribute simp_debug} makes the Simplifier output some extra |
901 \item @{attribute simp_debug} makes the Simplifier output some extra |
902 information about internal operations. This includes any attempted |
902 information about internal operations. This includes any attempted |
903 invocation of simplification procedures. |
903 invocation of simplification procedures. |
904 |
904 |
905 \item @{attribute simp_trace_new} controls Simplifier tracing within |
905 \item @{attribute simp_trace_new} controls Simplifier tracing within |
906 Isabelle/PIDE applications, notably Isabelle/jEdit \cite{isabelle-jedit}. |
906 Isabelle/PIDE applications, notably Isabelle/jEdit @{cite "isabelle-jedit"}. |
907 This provides a hierarchical representation of the rewriting steps |
907 This provides a hierarchical representation of the rewriting steps |
908 performed by the Simplifier. |
908 performed by the Simplifier. |
909 |
909 |
910 Users can configure the behaviour by specifying breakpoints, verbosity and |
910 Users can configure the behaviour by specifying breakpoints, verbosity and |
911 enabling or disabling the interactive mode. In normal verbosity (the |
911 enabling or disabling the interactive mode. In normal verbosity (the |
1297 certain information about a logic and delivers a suite of automatic |
1297 certain information about a logic and delivers a suite of automatic |
1298 proof tools, based on rules that are classified and declared in the |
1298 proof tools, based on rules that are classified and declared in the |
1299 context. These proof procedures are slow and simplistic compared |
1299 context. These proof procedures are slow and simplistic compared |
1300 with high-end automated theorem provers, but they can save |
1300 with high-end automated theorem provers, but they can save |
1301 considerable time and effort in practice. They can prove theorems |
1301 considerable time and effort in practice. They can prove theorems |
1302 such as Pelletier's \cite{pelletier86} problems 40 and 41 in a few |
1302 such as Pelletier's @{cite pelletier86} problems 40 and 41 in a few |
1303 milliseconds (including full proof reconstruction): *} |
1303 milliseconds (including full proof reconstruction): *} |
1304 |
1304 |
1305 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)" |
1305 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)" |
1306 by blast |
1306 by blast |
1307 |
1307 |
1368 |
1368 |
1369 This example is typical of the sequent calculus: start with the |
1369 This example is typical of the sequent calculus: start with the |
1370 desired theorem and apply rules backwards in a fairly arbitrary |
1370 desired theorem and apply rules backwards in a fairly arbitrary |
1371 manner. This yields a surprisingly effective proof procedure. |
1371 manner. This yields a surprisingly effective proof procedure. |
1372 Quantifiers add only few complications, since Isabelle handles |
1372 Quantifiers add only few complications, since Isabelle handles |
1373 parameters and schematic variables. See \cite[Chapter |
1373 parameters and schematic variables. See @{cite \<open>Chapter 10\<close> |
1374 10]{paulson-ml2} for further discussion. *} |
1374 "paulson-ml2"} for further discussion. *} |
1375 |
1375 |
1376 |
1376 |
1377 subsubsection {* Simulating sequents by natural deduction *} |
1377 subsubsection {* Simulating sequents by natural deduction *} |
1378 |
1378 |
1379 text {* Isabelle can represent sequents directly, as in the |
1379 text {* Isabelle can represent sequents directly, as in the |