doc-src/TutorialI/Misc/case_splits.thy
changeset 9792 bbefb6ce5cb2
parent 9723 a977245dfc8a
equal deleted inserted replaced
9791:a39e5d43de55 9792:bbefb6ce5cb2
     1 (*<*)
     1 (*<*)
     2 theory case_splits = Main:;
     2 theory case_splits = Main:;
     3 (*>*)
     3 (*>*)
     4 
     4 
     5 text{*
     5 text{*
     6 Goals containing \isaindex{if}-expressions are usually proved by case
     6 Goals containing @{text"if"}-expressions are usually proved by case
     7 distinction on the condition of the \isa{if}. For example the goal
     7 distinction on the condition of the @{text"if"}. For example the goal
     8 *}
     8 *}
     9 
     9 
    10 lemma "\\<forall>xs. if xs = [] then rev xs = [] else rev xs \\<noteq> []";
    10 lemma "\\<forall>xs. if xs = [] then rev xs = [] else rev xs \\<noteq> []";
    11 
    11 
    12 txt{*\noindent
    12 txt{*\noindent
    13 can be split into
    13 can be split into
    14 \begin{isabelle}
    14 \begin{isabelle}
    15 ~1.~{\isasymforall}xs.~(xs~=~[]~{\isasymlongrightarrow}~rev~xs~=~[])~{\isasymand}~(xs~{\isasymnoteq}~[]~{\isasymlongrightarrow}~rev~xs~{\isasymnoteq}~[])%
    15 ~1.~{\isasymforall}xs.~(xs~=~[]~{\isasymlongrightarrow}~rev~xs~=~[])~{\isasymand}~(xs~{\isasymnoteq}~[]~{\isasymlongrightarrow}~rev~xs~{\isasymnoteq}~[])
    16 \end{isabelle}
    16 \end{isabelle}
    17 by a degenerate form of simplification
    17 by a degenerate form of simplification
    18 *}
    18 *}
    19 
    19 
    20 apply(simp only: split: split_if);
    20 apply(simp only: split: split_if);
    21 (*<*)oops;(*>*)
    21 (*<*)oops;(*>*)
    22 
    22 
    23 text{*\noindent
    23 text{*\noindent
    24 where no simplification rules are included (\isa{only:} is followed by the
    24 where no simplification rules are included (@{text"only:"} is followed by the
    25 empty list of theorems) but the rule \isaindexbold{split_if} for
    25 empty list of theorems) but the rule \isaindexbold{split_if} for
    26 splitting \isa{if}s is added (via the modifier \isa{split:}). Because
    26 splitting @{text"if"}s is added (via the modifier @{text"split:"}). Because
    27 case-splitting on \isa{if}s is almost always the right proof strategy, the
    27 case-splitting on @{text"if"}s is almost always the right proof strategy, the
    28 simplifier performs it automatically. Try \isacommand{apply}\isa{(simp)}
    28 simplifier performs it automatically. Try \isacommand{apply}@{text"(simp)"}
    29 on the initial goal above.
    29 on the initial goal above.
    30 
    30 
    31 This splitting idea generalizes from \isa{if} to \isaindex{case}:
    31 This splitting idea generalizes from @{text"if"} to \isaindex{case}:
    32 *}
    32 *}
    33 
    33 
    34 lemma "(case xs of [] \\<Rightarrow> zs | y#ys \\<Rightarrow> y#(ys@zs)) = xs@zs";
    34 lemma "(case xs of [] \\<Rightarrow> zs | y#ys \\<Rightarrow> y#(ys@zs)) = xs@zs";
    35 txt{*\noindent
    35 txt{*\noindent
    36 becomes
    36 becomes
    37 \begin{isabelle}
    37 \begin{isabelle}
    38 ~1.~(xs~=~[]~{\isasymlongrightarrow}~zs~=~xs~@~zs)~{\isasymand}\isanewline
    38 ~1.~(xs~=~[]~{\isasymlongrightarrow}~zs~=~xs~@~zs)~{\isasymand}\isanewline
    39 ~~~~({\isasymforall}a~list.~xs~=~a~\#~list~{\isasymlongrightarrow}~a~\#~list~@~zs~=~xs~@~zs)%
    39 ~~~~({\isasymforall}a~list.~xs~=~a~\#~list~{\isasymlongrightarrow}~a~\#~list~@~zs~=~xs~@~zs)
    40 \end{isabelle}
    40 \end{isabelle}
    41 by typing
    41 by typing
    42 *}
    42 *}
    43 
    43 
    44 apply(simp only: split: list.split);
    44 apply(simp only: split: list.split);
    45 (*<*)oops;(*>*)
    45 (*<*)oops;(*>*)
    46 
    46 
    47 text{*\noindent
    47 text{*\noindent
    48 In contrast to \isa{if}-expressions, the simplifier does not split
    48 In contrast to @{text"if"}-expressions, the simplifier does not split
    49 \isa{case}-expressions by default because this can lead to nontermination
    49 @{text"case"}-expressions by default because this can lead to nontermination
    50 in case of recursive datatypes. Again, if the \isa{only:} modifier is
    50 in case of recursive datatypes. Again, if the @{text"only:"} modifier is
    51 dropped, the above goal is solved,
    51 dropped, the above goal is solved,
    52 *}
    52 *}
    53 (*<*)
    53 (*<*)
    54 lemma "(case xs of [] \\<Rightarrow> zs | y#ys \\<Rightarrow> y#(ys@zs)) = xs@zs";
    54 lemma "(case xs of [] \\<Rightarrow> zs | y#ys \\<Rightarrow> y#(ys@zs)) = xs@zs";
    55 (*>*)
    55 (*>*)
    56 by(simp split: list.split);
    56 by(simp split: list.split);
    57 
    57 
    58 text{*\noindent%
    58 text{*\noindent%
    59 which \isacommand{apply}\isa{(simp)} alone will not do.
    59 which \isacommand{apply}@{text"(simp)"} alone will not do.
    60 
    60 
    61 In general, every datatype $t$ comes with a theorem
    61 In general, every datatype $t$ comes with a theorem
    62 \isa{$t$.split} which can be declared to be a \bfindex{split rule} either
    62 $t$@{text".split"} which can be declared to be a \bfindex{split rule} either
    63 locally as above, or by giving it the \isa{split} attribute globally:
    63 locally as above, or by giving it the @{text"split"} attribute globally:
    64 *}
    64 *}
    65 
    65 
    66 lemmas [split] = list.split;
    66 lemmas [split] = list.split;
    67 
    67 
    68 text{*\noindent
    68 text{*\noindent
    69 The \isa{split} attribute can be removed with the \isa{del} modifier,
    69 The @{text"split"} attribute can be removed with the @{text"del"} modifier,
    70 either locally
    70 either locally
    71 *}
    71 *}
    72 (*<*)
    72 (*<*)
    73 lemma "dummy=dummy";
    73 lemma "dummy=dummy";
    74 (*>*)
    74 (*>*)
    81 *}
    81 *}
    82 lemmas [split del] = list.split;
    82 lemmas [split del] = list.split;
    83 
    83 
    84 text{*
    84 text{*
    85 The above split rules intentionally only affect the conclusion of a
    85 The above split rules intentionally only affect the conclusion of a
    86 subgoal.  If you want to split an \isa{if} or \isa{case}-expression in
    86 subgoal.  If you want to split an @{text"if"} or @{text"case"}-expression in
    87 the assumptions, you have to apply \isa{split\_if\_asm} or $t$\isa{.split_asm}:
    87 the assumptions, you have to apply @{thm[source]split_if_asm} or
       
    88 $t$@{text".split_asm"}:
    88 *}
    89 *}
    89 
    90 
    90 lemma "if xs = [] then ys ~= [] else ys = [] ==> xs @ ys ~= []"
    91 lemma "if xs = [] then ys ~= [] else ys = [] ==> xs @ ys ~= []"
    91 apply(simp only: split: split_if_asm);
    92 apply(simp only: split: split_if_asm);
    92 
    93 
    93 txt{*\noindent
    94 txt{*\noindent
    94 In contrast to splitting the conclusion, this actually creates two
    95 In contrast to splitting the conclusion, this actually creates two
    95 separate subgoals (which are solved by \isa{simp\_all}):
    96 separate subgoals (which are solved by @{text"simp_all"}):
    96 \begin{isabelle}
    97 \begin{isabelle}
    97 \ \isadigit{1}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\isanewline
    98 \ \isadigit{1}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ \mbox{ys}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\isanewline
    98 \ \isadigit{2}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ \mbox{xs}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}
    99 \ \isadigit{2}{\isachardot}\ {\isasymlbrakk}\mbox{xs}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ \mbox{ys}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ \mbox{xs}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}
    99 \end{isabelle}
   100 \end{isabelle}
   100 If you need to split both in the assumptions and the conclusion,
   101 If you need to split both in the assumptions and the conclusion,
   101 use $t$\isa{.splits} which subsumes $t$\isa{.split} and $t$\isa{.split_asm}.
   102 use $t$@{text".splits"} which subsumes $t$@{text".split"} and
       
   103 $t$@{text".split_asm"}. Analogously, there is @{thm[source]if_splits}.
   102 *}
   104 *}
   103 
   105 
   104 (*<*)
   106 (*<*)
   105 by(simp_all)
   107 by(simp_all)
   106 end
   108 end