src/HOL/Lambda/NormalForm.thy
changeset 32960 69916a850301
parent 24537 57c7dfaa0153
child 33704 6aeb8454efc1
equal deleted inserted replaced
32959:23a8c5ac35f8 32960:69916a850301
     1 (*  Title:      HOL/Lambda/NormalForm.thy
     1 (*  Title:      HOL/Lambda/NormalForm.thy
     2     ID:         $Id$
       
     3     Author:     Stefan Berghofer, TU Muenchen, 2003
     2     Author:     Stefan Berghofer, TU Muenchen, 2003
     4 *)
     3 *)
     5 
     4 
     6 header {* Inductive characterization of lambda terms in normal form *}
     5 header {* Inductive characterization of lambda terms in normal form *}
     7 
     6 
   198     case (App ts t)
   197     case (App ts t)
   199     show ?case
   198     show ?case
   200     proof
   199     proof
   201       assume "Var t \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> t'"
   200       assume "Var t \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> t'"
   202       then obtain rs where "ts => rs"
   201       then obtain rs where "ts => rs"
   203 	by (iprover dest: head_Var_reduction)
   202         by (iprover dest: head_Var_reduction)
   204       with App show False
   203       with App show False
   205 	by (induct rs arbitrary: ts) auto
   204         by (induct rs arbitrary: ts) auto
   206     qed
   205     qed
   207   next
   206   next
   208     case (Abs t)
   207     case (Abs t)
   209     show ?case
   208     show ?case
   210     proof
   209     proof
   227     case (2 u ts)
   226     case (2 u ts)
   228     show ?case
   227     show ?case
   229     proof (cases ts)
   228     proof (cases ts)
   230       case Nil
   229       case Nil
   231       from 2 have "\<forall>u'. \<not> u \<rightarrow>\<^sub>\<beta> u'"
   230       from 2 have "\<forall>u'. \<not> u \<rightarrow>\<^sub>\<beta> u'"
   232 	by (auto intro: apps_preserves_beta)
   231         by (auto intro: apps_preserves_beta)
   233       then have "NF u" by (rule 2)
   232       then have "NF u" by (rule 2)
   234       then have "NF (Abs u)" by (rule NF.Abs)
   233       then have "NF (Abs u)" by (rule NF.Abs)
   235       with Nil show ?thesis by simp
   234       with Nil show ?thesis by simp
   236     next
   235     next
   237       case (Cons r rs)
   236       case (Cons r rs)
   238       have "Abs u \<degree> r \<rightarrow>\<^sub>\<beta> u[r/0]" ..
   237       have "Abs u \<degree> r \<rightarrow>\<^sub>\<beta> u[r/0]" ..
   239       then have "Abs u \<degree> r \<degree>\<degree> rs \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs"
   238       then have "Abs u \<degree> r \<degree>\<degree> rs \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs"
   240 	by (rule apps_preserves_beta)
   239         by (rule apps_preserves_beta)
   241       with Cons have "Abs u \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs"
   240       with Cons have "Abs u \<degree>\<degree> ts \<rightarrow>\<^sub>\<beta> u[r/0] \<degree>\<degree> rs"
   242 	by simp
   241         by simp
   243       with 2 show ?thesis by iprover
   242       with 2 show ?thesis by iprover
   244     qed
   243     qed
   245   qed
   244   qed
   246 qed
   245 qed
   247 
   246