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:*} |