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 |