doc-src/TutorialI/IsarOverview/Isar/Logic.thy
changeset 13700 80010ca1310c
parent 13620 61a23a43b783
child 13765 e3c444e805c4
equal deleted inserted replaced
13699:d041e5ce52d7 13700:80010ca1310c
   308 text{*\noindent Command \isakeyword{using} can appear before a proof
   308 text{*\noindent Command \isakeyword{using} can appear before a proof
   309 and adds further facts to those piped into the proof. Here @{text AB}
   309 and adds further facts to those piped into the proof. Here @{text AB}
   310 is the only such fact and it triggers $\land$-elimination. Another
   310 is the only such fact and it triggers $\land$-elimination. Another
   311 frequent idiom is as follows:
   311 frequent idiom is as follows:
   312 \begin{center}
   312 \begin{center}
   313 \isakeyword{from} \emph{major facts}~
   313 \isakeyword{from} \emph{major-facts}~
   314 \isakeyword{show} \emph{proposition}~
   314 \isakeyword{show} \emph{proposition}~
   315 \isakeyword{using} \emph{minor facts}~
   315 \isakeyword{using} \emph{minor-facts}~
   316 \emph{proof}
   316 \emph{proof}
   317 \end{center}
   317 \end{center}
   318 \medskip
   318 \medskip
   319 
   319 
   320 Sometimes it is necessary to suppress the implicit application of rules in a
   320 Sometimes it is necessary to suppress the implicit application of rules in a
   386   fix y
   386   fix y
   387   from ex obtain x where "\<forall>y. P x y" ..
   387   from ex obtain x where "\<forall>y. P x y" ..
   388   hence "P x y" ..
   388   hence "P x y" ..
   389   thus "\<exists>x. P x y" ..
   389   thus "\<exists>x. P x y" ..
   390 qed
   390 qed
       
   391 
       
   392 subsection{*Making bigger steps*}
   391 
   393 
   392 text{* So far we have confined ourselves to single step proofs. Of course
   394 text{* So far we have confined ourselves to single step proofs. Of course
   393 powerful automatic methods can be used just as well. Here is an example,
   395 powerful automatic methods can be used just as well. Here is an example,
   394 Cantor's theorem that there is no surjective function from a set to its
   396 Cantor's theorem that there is no surjective function from a set to its
   395 powerset: *}
   397 powerset: *}
   458 *}
   460 *}
   459 
   461 
   460 theorem "\<exists>S. S \<notin> range (f :: 'a \<Rightarrow> 'a set)"
   462 theorem "\<exists>S. S \<notin> range (f :: 'a \<Rightarrow> 'a set)"
   461 by best
   463 by best
   462 text{*\noindent Of course this only works in the context of HOL's carefully
   464 text{*\noindent Of course this only works in the context of HOL's carefully
   463 constructed introduction and elimination rules for set theory.
   465 constructed introduction and elimination rules for set theory.*}
   464 *}
   466 
       
   467 subsection{*Raw proof blocks*}
       
   468 
       
   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
       
   471 tendency to use the default introduction and elimination rules to
       
   472 decompose goals and facts. This can lead to very tedious proofs:
       
   473 *}
       
   474 (*<*)ML"set quick_and_dirty"(*>*)
       
   475 lemma "\<forall>x y. A x y \<and> B x y \<longrightarrow> C x y"
       
   476 proof
       
   477   fix x show "\<forall>y. A x y \<and> B x y \<longrightarrow> C x y"
       
   478   proof
       
   479     fix y show "A x y \<and> B x y \<longrightarrow> C x y"
       
   480     proof
       
   481       assume "A x y \<and> B x y"
       
   482       show "C x y" sorry
       
   483     qed
       
   484   qed
       
   485 qed
       
   486 text{*\noindent Since we are only interested in the decomposition and not the
       
   487 actual proof, the latter has been replaced by
       
   488 \isakeyword{sorry}. Command \isakeyword{sorry} proves anything but is
       
   489 only allowed in quick and dirty mode, the default interactive mode. It
       
   490 is very convenient for top down proof development.
       
   491 
       
   492 Luckily we can avoid this step by step decomposition very easily: *}
       
   493 
       
   494 lemma "\<forall>x y. A x y \<and> B x y \<longrightarrow> C x y"
       
   495 proof -
       
   496   have "\<And>x y. \<lbrakk> A x y; B x y \<rbrakk> \<Longrightarrow> C x y"
       
   497   proof -
       
   498     fix x y assume "A x y" "B x y"
       
   499     show "C x y" sorry
       
   500   qed
       
   501   thus ?thesis by blast
       
   502 qed
       
   503 
       
   504 text{*\noindent
       
   505 This can be simplified further by \emph{raw proof blocks},
       
   506 which are proofs enclosed in braces: *}
       
   507 
       
   508 lemma "\<forall>x y. A x y \<and> B x y \<longrightarrow> C x y"
       
   509 proof -
       
   510   { fix x y assume "A x y" "B x y"
       
   511     have "C x y" sorry }
       
   512   thus ?thesis by blast
       
   513 qed
       
   514 
       
   515 text{*\noindent The result of the raw proof block is the same theorem
       
   516 as above, namely @{prop"\<And>x y. \<lbrakk> A x y; B x y \<rbrakk> \<Longrightarrow> C x y"}.  Raw
       
   517 proof blocks are like ordinary proofs except that they do not prove
       
   518 some explicitly stated property but that the property emerges directly
       
   519 out of the \isakeyword{fixe}s, \isakeyword{assume}s and
       
   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
       
   522 \isakeyword{have} rather than \isakeyword{show} because it is not the
       
   523 conclusion of some pending goal but some independent claim.  If you
       
   524 would like to name the result of a raw proof block simply follow it
       
   525 with *}
       
   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:
       
   537 \begin{quote}\em
       
   538 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
       
   540 that from this form the original goal follows.
       
   541 \end{quote}
       
   542 This yields more readable and also more robust proofs. *}
   465 
   543 
   466 subsection{*Further refinements*}
   544 subsection{*Further refinements*}
   467 
   545 
   468 text{* Thus subsection discusses some further tricks that can make
   546 text{* This subsection discusses some further tricks that can make
   469 life easier although they are not essential. We start with some small
   547 life easier although they are not essential. We start with some small
   470 syntactic items.*}
   548 syntactic items.*}
   471 
   549 
   472 subsubsection{*\isakeyword{and}*}
   550 subsubsection{*\isakeyword{and}*}
   473 
   551