doc-src/TutorialI/IsarOverview/Isar/Logic.thy
changeset 13765 e3c444e805c4
parent 13700 80010ca1310c
child 13766 fb78ee03c391
equal deleted inserted replaced
13764:3e180bf68496 13765:e3c444e805c4
    49 proof
    49 proof
    50   assume "A"
    50   assume "A"
    51   show "A \<and> A" by(rule conjI)
    51   show "A \<and> A" by(rule conjI)
    52 qed
    52 qed
    53 text{*\noindent Rule @{thm[source]conjI} is of course @{thm conjI}.
    53 text{*\noindent Rule @{thm[source]conjI} is of course @{thm conjI}.
    54 A drawback of these implicit proofs by assumption is that it
    54 A drawback of implicit proofs by assumption is that it
    55 is no longer obvious where an assumption is used.
    55 is no longer obvious where an assumption is used.
    56 
    56 
    57 Proofs of the form \isakeyword{by}@{text"(rule"}~\emph{name}@{text")"} can be
    57 Proofs of the form \isakeyword{by}@{text"(rule"}~\emph{name}@{text")"} can be
    58 abbreviated to ``..''
    58 abbreviated to ``..''
    59 if \emph{name} refers to one of the predefined introduction rules:
    59 if \emph{name} refers to one of the predefined introduction rules:
   329     assume A show ?thesis ..
   329     assume A show ?thesis ..
   330   next
   330   next
   331     assume B show ?thesis ..
   331     assume B show ?thesis ..
   332   qed
   332   qed
   333 qed
   333 qed
   334 text{*\noindent Could \isakeyword{using} help to eliminate this ``@{text"-"}''? *}
   334 
   335 
   335 
   336 subsection{*Predicate calculus*}
   336 subsection{*Predicate calculus*}
   337 
   337 
   338 text{* Command \isakeyword{fix} introduces new local variables into a
   338 text{* Command \isakeyword{fix} introduces new local variables into a
   339 proof. The pair \isakeyword{fix}-\isakeyword{show} corresponds to @{text"\<And>"}
   339 proof. The pair \isakeyword{fix}-\isakeyword{show} corresponds to @{text"\<And>"}
   459 navigates through the large search space:
   459 navigates through the large search space:
   460 *}
   460 *}
   461 
   461 
   462 theorem "\<exists>S. S \<notin> range (f :: 'a \<Rightarrow> 'a set)"
   462 theorem "\<exists>S. S \<notin> range (f :: 'a \<Rightarrow> 'a set)"
   463 by best
   463 by best
   464 text{*\noindent Of course this only works in the context of HOL's carefully
   464 (* Of course this only works in the context of HOL's carefully
   465 constructed introduction and elimination rules for set theory.*}
   465 constructed introduction and elimination rules for set theory.*)
   466 
   466 
   467 subsection{*Raw proof blocks*}
   467 subsection{*Raw proof blocks*}
   468 
   468 
   469 text{* Although we have shown how to employ powerful automatic methods like
   469 text{* Although we have shown how to employ powerful automatic methods like
   470 @{text blast} to achieve bigger proof steps, there may still be the
   470 @{text blast} to achieve bigger proof steps, there may still be the
   500   qed
   500   qed
   501   thus ?thesis by blast
   501   thus ?thesis by blast
   502 qed
   502 qed
   503 
   503 
   504 text{*\noindent
   504 text{*\noindent
   505 This can be simplified further by \emph{raw proof blocks},
   505 This can be simplified further by \emph{raw proof blocks}, i.e.\
   506 which are proofs enclosed in braces: *}
   506 proofs enclosed in braces: *}
   507 
   507 
   508 lemma "\<forall>x y. A x y \<and> B x y \<longrightarrow> C x y"
   508 lemma "\<forall>x y. A x y \<and> B x y \<longrightarrow> C x y"
   509 proof -
   509 proof -
   510   { fix x y assume "A x y" "B x y"
   510   { fix x y assume "A x y" "B x y"
   511     have "C x y" sorry }
   511     have "C x y" sorry }
   518 some explicitly stated property but that the property emerges directly
   518 some explicitly stated property but that the property emerges directly
   519 out of the \isakeyword{fixe}s, \isakeyword{assume}s and
   519 out of the \isakeyword{fixe}s, \isakeyword{assume}s and
   520 \isakeyword{have} in the block. Thus they again serve to avoid
   520 \isakeyword{have} in the block. Thus they again serve to avoid
   521 duplication. Note that the conclusion of a raw proof block is stated with
   521 duplication. Note that the conclusion of a raw proof block is stated with
   522 \isakeyword{have} rather than \isakeyword{show} because it is not the
   522 \isakeyword{have} rather than \isakeyword{show} because it is not the
   523 conclusion of some pending goal but some independent claim.  If you
   523 conclusion of some pending goal but some independent claim.
   524 would like to name the result of a raw proof block simply follow it
   524 
   525 with *}
   525 The general idea demonstrated in this subsection is very
   526 
       
   527 (*<*)
       
   528 lemma "P"
       
   529 proof -
       
   530   { assume A hence A . }
       
   531 (*>*)
       
   532 note some_name = this
       
   533 (*<*)oops(*>*)
       
   534 
       
   535 text{* The general idea demonstrated in this subsection is very
       
   536 important in Isar and distinguishes it from tactic-style proofs:
   526 important in Isar and distinguishes it from tactic-style proofs:
   537 \begin{quote}\em
   527 \begin{quote}\em
   538 Do not manipulate the proof state into a particular form by applying
   528 Do not manipulate the proof state into a particular form by applying
   539 tactics but state the desired form explictly and let the tactic verify
   529 tactics but state the desired form explictly and let the tactic verify
   540 that from this form the original goal follows.
   530 that from this form the original goal follows.
   542 This yields more readable and also more robust proofs. *}
   532 This yields more readable and also more robust proofs. *}
   543 
   533 
   544 subsection{*Further refinements*}
   534 subsection{*Further refinements*}
   545 
   535 
   546 text{* This subsection discusses some further tricks that can make
   536 text{* This subsection discusses some further tricks that can make
   547 life easier although they are not essential. We start with some small
   537 life easier although they are not essential. *}
   548 syntactic items.*}
       
   549 
   538 
   550 subsubsection{*\isakeyword{and}*}
   539 subsubsection{*\isakeyword{and}*}
   551 
   540 
   552 text{* Propositions (following \isakeyword{assume} etc) may but need not be
   541 text{* Propositions (following \isakeyword{assume} etc) may but need not be
   553 separated by \isakeyword{and}. This is not just for readability
   542 separated by \isakeyword{and}. This is not just for readability
   554 (\isakeyword{from} \isa{A} \isakeyword{and} \isa{B} looks nicer than
   543 (\isakeyword{from} \isa{A} \isakeyword{and} \isa{B} looks nicer than
   555 \isakeyword{from} \isa{A} \isa{B}) but for structuring lists of propositions
   544 \isakeyword{from} \isa{A} \isa{B}) but for structuring lists of propositions
   556 into possibly named blocks. For example in
   545 into possibly named blocks. In
   557 \begin{center}
   546 \begin{center}
   558 \isakeyword{assume} \isa{A:} $A_1$ $A_2$ \isakeyword{and} \isa{B:} $A_3$
   547 \isakeyword{assume} \isa{A:} $A_1$ $A_2$ \isakeyword{and} \isa{B:} $A_3$
   559 \isakeyword{and} $A_4$
   548 \isakeyword{and} $A_4$
   560 \end{center}
   549 \end{center}
   561 label \isa{A} refers to the list of propositions $A_1$ $A_2$ and
   550 label \isa{A} refers to the list of propositions $A_1$ $A_2$ and
   562 label \isa{B} to $A_3$. *}
   551 label \isa{B} to $A_3$. *}
   563 
   552 
       
   553 subsubsection{*\isakeyword{note}*}
       
   554 text{* If you want to remember intermediate fact(s) that cannot be
       
   555 named directly, use \isakeyword{note}. For example the result of raw
       
   556 proof block can be named by following it with
       
   557 \isakeyword{note}~@{text"note some_name = this"}.  As a side effect
       
   558 @{text this} is set to the list of facts on the right-hand side. You
       
   559 can also say @{text"note some_fact"}, which simply sets @{text this},
       
   560 i.e.\ recalls @{text"some_fact"}. *}
       
   561 
       
   562 
   564 subsubsection{*\isakeyword{fixes}*}
   563 subsubsection{*\isakeyword{fixes}*}
   565 
   564 
   566 text{* Sometimes it is necessary to decorate a proposition with type
   565 text{* Sometimes it is necessary to decorate a proposition with type
   567 constraints, as in Cantor's theorem above. These type constraints tend
   566 constraints, as in Cantor's theorem above. These type constraints tend
   568 to make the theorem less readable. The situation can be improved a
   567 to make the theorem less readable. The situation can be improved a
   575 This is avoided by \isakeyword{fixes}: *}
   574 This is avoided by \isakeyword{fixes}: *}
   576 
   575 
   577 theorem fixes f :: "'a \<Rightarrow> 'a set" shows "\<exists>S. S \<notin> range f"
   576 theorem fixes f :: "'a \<Rightarrow> 'a set" shows "\<exists>S. S \<notin> range f"
   578 (*<*)oops(*>*)
   577 (*<*)oops(*>*)
   579 text{* \noindent
   578 text{* \noindent
   580 But the real strength of \isakeyword{fixes} lies in the possibility to
   579 Even better, \isakeyword{fixes} allows to introduce concrete syntax locally:*}
   581 introduce concrete syntax locally:*}
       
   582 
   580 
   583 lemma comm_mono:
   581 lemma comm_mono:
   584   fixes r :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix ">" 60) and
   582   fixes r :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix ">" 60) and
   585        f :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"   (infixl "++" 70)
   583        f :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"   (infixl "++" 70)
   586   assumes comm: "\<And>x y::'a. x ++ y = y ++ x" and
   584   assumes comm: "\<And>x y::'a. x ++ y = y ++ x" and
   587           mono: "\<And>x y z::'a. x > y \<Longrightarrow> x ++ z > y ++ z"
   585           mono: "\<And>x y z::'a. x > y \<Longrightarrow> x ++ z > y ++ z"
   588   shows "x > y \<Longrightarrow> z ++ x > z ++ y"
   586   shows "x > y \<Longrightarrow> z ++ x > z ++ y"
   589 by(simp add: comm mono)
   587 by(simp add: comm mono)
   590 
   588 
   591 text{*\noindent The concrete syntax is dropped at the end of the proof and the
   589 text{*\noindent The concrete syntax is dropped at the end of the proof and the
   592 theorem becomes @{thm[display,margin=50]comm_mono} *}
   590 theorem becomes @{thm[display,margin=60]comm_mono} *}
   593 
   591 
   594 subsubsection{*\isakeyword{obtain}*}
   592 subsubsection{*\isakeyword{obtain}*}
   595 
   593 
   596 text{* The \isakeyword{obtain} construct can introduce multiple
   594 text{* The \isakeyword{obtain} construct can introduce multiple
   597 witnesses and propositions as in the following proof fragment:*}
   595 witnesses and propositions as in the following proof fragment:*}