1 (* Title: HOL/Induct/Term.thy |
1 (* Title: HOL/Induct/Term.thy |
2 Author: Stefan Berghofer, TU Muenchen |
2 Author: Stefan Berghofer, TU Muenchen |
3 *) |
3 *) |
4 |
4 |
5 section {* Terms over a given alphabet *} |
5 section \<open>Terms over a given alphabet\<close> |
6 |
6 |
7 theory Term |
7 theory Term |
8 imports Main |
8 imports Main |
9 begin |
9 begin |
10 |
10 |
11 datatype ('a, 'b) "term" = |
11 datatype ('a, 'b) "term" = |
12 Var 'a |
12 Var 'a |
13 | App 'b "('a, 'b) term list" |
13 | App 'b "('a, 'b) term list" |
14 |
14 |
15 |
15 |
16 text {* \medskip Substitution function on terms *} |
16 text \<open>\medskip Substitution function on terms\<close> |
17 |
17 |
18 primrec subst_term :: "('a => ('a, 'b) term) => ('a, 'b) term => ('a, 'b) term" |
18 primrec subst_term :: "('a => ('a, 'b) term) => ('a, 'b) term => ('a, 'b) term" |
19 and subst_term_list :: "('a => ('a, 'b) term) => ('a, 'b) term list => ('a, 'b) term list" |
19 and subst_term_list :: "('a => ('a, 'b) term) => ('a, 'b) term list => ('a, 'b) term list" |
20 where |
20 where |
21 "subst_term f (Var a) = f a" |
21 "subst_term f (Var a) = f a" |
22 | "subst_term f (App b ts) = App b (subst_term_list f ts)" |
22 | "subst_term f (App b ts) = App b (subst_term_list f ts)" |
23 | "subst_term_list f [] = []" |
23 | "subst_term_list f [] = []" |
24 | "subst_term_list f (t # ts) = subst_term f t # subst_term_list f ts" |
24 | "subst_term_list f (t # ts) = subst_term f t # subst_term_list f ts" |
25 |
25 |
26 |
26 |
27 text {* \medskip A simple theorem about composition of substitutions *} |
27 text \<open>\medskip A simple theorem about composition of substitutions\<close> |
28 |
28 |
29 lemma subst_comp: |
29 lemma subst_comp: |
30 "subst_term (subst_term f1 \<circ> f2) t = |
30 "subst_term (subst_term f1 \<circ> f2) t = |
31 subst_term f1 (subst_term f2 t)" |
31 subst_term f1 (subst_term f2 t)" |
32 and "subst_term_list (subst_term f1 \<circ> f2) ts = |
32 and "subst_term_list (subst_term f1 \<circ> f2) ts = |
33 subst_term_list f1 (subst_term_list f2 ts)" |
33 subst_term_list f1 (subst_term_list f2 ts)" |
34 by (induct t and ts rule: subst_term.induct subst_term_list.induct) simp_all |
34 by (induct t and ts rule: subst_term.induct subst_term_list.induct) simp_all |
35 |
35 |
36 |
36 |
37 text {* \medskip Alternative induction rule *} |
37 text \<open>\medskip Alternative induction rule\<close> |
38 |
38 |
39 lemma |
39 lemma |
40 assumes var: "!!v. P (Var v)" |
40 assumes var: "!!v. P (Var v)" |
41 and app: "!!f ts. (\<forall>t \<in> set ts. P t) ==> P (App f ts)" |
41 and app: "!!f ts. (\<forall>t \<in> set ts. P t) ==> P (App f ts)" |
42 shows term_induct2: "P t" |
42 shows term_induct2: "P t" |