equal
deleted
inserted
replaced
20 zfact :: "int => int" |
20 zfact :: "int => int" |
21 setprod :: "int set => int" |
21 setprod :: "int set => int" |
22 d22set :: "int => int set" |
22 d22set :: "int => int set" |
23 |
23 |
24 recdef zfact "measure ((\<lambda>n. nat n) :: int => nat)" |
24 recdef zfact "measure ((\<lambda>n. nat n) :: int => nat)" |
25 "zfact n = (if n \<le> Numeral0 then Numeral1 else n * zfact (n - Numeral1))" |
25 "zfact n = (if n \<le> 0 then 1 else n * zfact (n - 1))" |
26 |
26 |
27 defs |
27 defs |
28 setprod_def: "setprod A == (if finite A then fold (op *) Numeral1 A else Numeral1)" |
28 setprod_def: "setprod A == (if finite A then fold (op *) 1 A else 1)" |
29 |
29 |
30 recdef d22set "measure ((\<lambda>a. nat a) :: int => nat)" |
30 recdef d22set "measure ((\<lambda>a. nat a) :: int => nat)" |
31 "d22set a = (if Numeral1 < a then insert a (d22set (a - Numeral1)) else {})" |
31 "d22set a = (if 1 < a then insert a (d22set (a - 1)) else {})" |
32 |
32 |
33 |
33 |
34 text {* \medskip @{term setprod} --- product of finite set *} |
34 text {* \medskip @{term setprod} --- product of finite set *} |
35 |
35 |
36 lemma setprod_empty [simp]: "setprod {} = Numeral1" |
36 lemma setprod_empty [simp]: "setprod {} = 1" |
37 apply (simp add: setprod_def) |
37 apply (simp add: setprod_def) |
38 done |
38 done |
39 |
39 |
40 lemma setprod_insert [simp]: |
40 lemma setprod_insert [simp]: |
41 "finite A ==> a \<notin> A ==> setprod (insert a A) = a * setprod A" |
41 "finite A ==> a \<notin> A ==> setprod (insert a A) = a * setprod A" |
52 declare d22set.simps [simp del] |
52 declare d22set.simps [simp del] |
53 |
53 |
54 |
54 |
55 lemma d22set_induct: |
55 lemma d22set_induct: |
56 "(!!a. P {} a) ==> |
56 "(!!a. P {} a) ==> |
57 (!!a. Numeral1 < (a::int) ==> P (d22set (a - Numeral1)) (a - Numeral1) |
57 (!!a. 1 < (a::int) ==> P (d22set (a - 1)) (a - 1) |
58 ==> P (d22set a) a) |
58 ==> P (d22set a) a) |
59 ==> P (d22set u) u" |
59 ==> P (d22set u) u" |
60 proof - |
60 proof - |
61 case rule_context |
61 case rule_context |
62 show ?thesis |
62 show ?thesis |
63 apply (rule d22set.induct) |
63 apply (rule d22set.induct) |
64 apply safe |
64 apply safe |
65 apply (case_tac [2] "Numeral1 < a") |
65 apply (case_tac [2] "1 < a") |
66 apply (rule_tac [2] rule_context) |
66 apply (rule_tac [2] rule_context) |
67 apply (simp_all (no_asm_simp)) |
67 apply (simp_all (no_asm_simp)) |
68 apply (simp_all (no_asm_simp) add: d22set.simps rule_context) |
68 apply (simp_all (no_asm_simp) add: d22set.simps rule_context) |
69 done |
69 done |
70 qed |
70 qed |
71 |
71 |
72 lemma d22set_g_1 [rule_format]: "b \<in> d22set a --> Numeral1 < b" |
72 lemma d22set_g_1 [rule_format]: "b \<in> d22set a --> 1 < b" |
73 apply (induct a rule: d22set_induct) |
73 apply (induct a rule: d22set_induct) |
74 prefer 2 |
74 prefer 2 |
75 apply (subst d22set.simps) |
75 apply (subst d22set.simps) |
76 apply auto |
76 apply auto |
77 done |
77 done |
85 |
85 |
86 lemma d22set_le_swap: "a < b ==> b \<notin> d22set a" |
86 lemma d22set_le_swap: "a < b ==> b \<notin> d22set a" |
87 apply (auto dest: d22set_le) |
87 apply (auto dest: d22set_le) |
88 done |
88 done |
89 |
89 |
90 lemma d22set_mem [rule_format]: "Numeral1 < b --> b \<le> a --> b \<in> d22set a" |
90 lemma d22set_mem [rule_format]: "1 < b --> b \<le> a --> b \<in> d22set a" |
91 apply (induct a rule: d22set.induct) |
91 apply (induct a rule: d22set.induct) |
92 apply auto |
92 apply auto |
93 apply (simp_all add: d22set.simps) |
93 apply (simp_all add: d22set.simps) |
94 done |
94 done |
95 |
95 |
107 apply (induct a rule: d22set.induct) |
107 apply (induct a rule: d22set.induct) |
108 apply safe |
108 apply safe |
109 apply (simp add: d22set.simps zfact.simps) |
109 apply (simp add: d22set.simps zfact.simps) |
110 apply (subst d22set.simps) |
110 apply (subst d22set.simps) |
111 apply (subst zfact.simps) |
111 apply (subst zfact.simps) |
112 apply (case_tac "Numeral1 < a") |
112 apply (case_tac "1 < a") |
113 prefer 2 |
113 prefer 2 |
114 apply (simp add: d22set.simps zfact.simps) |
114 apply (simp add: d22set.simps zfact.simps) |
115 apply (simp add: d22set_fin d22set_le_swap) |
115 apply (simp add: d22set_fin d22set_le_swap) |
116 done |
116 done |
117 |
117 |