author | kleing |
Mon, 21 Jun 2004 10:25:57 +0200 | |
changeset 14981 | e73f8140af78 |
parent 12218 | 6597093b77e7 |
child 17244 | 0b2ff9541727 |
permissions | -rw-r--r-- |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
1 |
(* Title: HOL/IOA/NTP/Multiset.ML |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
2 |
ID: $Id$ |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
3 |
Author: Tobias Nipkow & Konrad Slind |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
4 |
|
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
5 |
Axiomatic multisets. |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
6 |
Should be done as a subtype and moved to a global place. |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
7 |
*) |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
8 |
|
5068 | 9 |
Goalw [Multiset.count_def, Multiset.countm_empty_def] |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
10 |
"count {|} x = 0"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
11 |
by (rtac refl 1); |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
12 |
qed "count_empty"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
13 |
|
5068 | 14 |
Goal |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
15 |
"count (addm M x) y = (if y=x then Suc(count M y) else count M y)"; |
4098 | 16 |
by (asm_simp_tac (simpset() addsimps |
4833 | 17 |
[Multiset.count_def,Multiset.countm_nonempty_def]) 1); |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
18 |
qed "count_addm_simp"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
19 |
|
5068 | 20 |
Goal "count M y <= count (addm M x) y"; |
4833 | 21 |
by (simp_tac (simpset() addsimps [count_addm_simp]) 1); |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
22 |
qed "count_leq_addm"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
23 |
|
5068 | 24 |
Goalw [Multiset.count_def] |
4710 | 25 |
"count (delm M x) y = (if y=x then count M y - 1 else count M y)"; |
4833 | 26 |
by (res_inst_tac [("M","M")] Multiset.induction 1); |
27 |
by (asm_simp_tac (simpset() |
|
28 |
addsimps [Multiset.delm_empty_def,Multiset.countm_empty_def]) 1); |
|
29 |
by (asm_full_simp_tac (simpset() |
|
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
30 |
addsimps [Multiset.delm_nonempty_def, |
4833 | 31 |
Multiset.countm_nonempty_def]) 1); |
32 |
by Safe_tac; |
|
33 |
by (Asm_full_simp_tac 1); |
|
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
34 |
qed "count_delm_simp"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
35 |
|
5068 | 36 |
Goal "!!M. (!x. P(x) --> Q(x)) ==> (countm M P <= countm M Q)"; |
4681 | 37 |
by (res_inst_tac [("M","M")] Multiset.induction 1); |
38 |
by (simp_tac (simpset() addsimps [Multiset.countm_empty_def]) 1); |
|
39 |
by (simp_tac (simpset() addsimps[Multiset.countm_nonempty_def]) 1); |
|
5132 | 40 |
by Auto_tac; |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
41 |
qed "countm_props"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
42 |
|
5068 | 43 |
Goal "!!P. ~P(obj) ==> countm M P = countm (delm M obj) P"; |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
44 |
by (res_inst_tac [("M","M")] Multiset.induction 1); |
4098 | 45 |
by (simp_tac (simpset() addsimps [Multiset.delm_empty_def, |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
46 |
Multiset.countm_empty_def]) 1); |
4098 | 47 |
by (asm_simp_tac (simpset() addsimps[Multiset.countm_nonempty_def, |
4833 | 48 |
Multiset.delm_nonempty_def]) 1); |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
49 |
qed "countm_spurious_delm"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
50 |
|
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
51 |
|
5068 | 52 |
Goal "!!P. P(x) ==> 0<count M x --> 0<countm M P"; |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
53 |
by (res_inst_tac [("M","M")] Multiset.induction 1); |
4098 | 54 |
by (simp_tac (simpset() addsimps |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
55 |
[Multiset.delm_empty_def,Multiset.count_def, |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
56 |
Multiset.countm_empty_def]) 1); |
4098 | 57 |
by (asm_simp_tac (simpset() addsimps |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
58 |
[Multiset.count_def,Multiset.delm_nonempty_def, |
4833 | 59 |
Multiset.countm_nonempty_def]) 1); |
4681 | 60 |
qed_spec_mp "pos_count_imp_pos_countm"; |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
61 |
|
5068 | 62 |
Goal |
4710 | 63 |
"!!P. P(x) ==> 0<count M x --> countm (delm M x) P = countm M P - 1"; |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
64 |
by (res_inst_tac [("M","M")] Multiset.induction 1); |
4098 | 65 |
by (simp_tac (simpset() addsimps |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
66 |
[Multiset.delm_empty_def, |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
67 |
Multiset.countm_empty_def]) 1); |
4098 | 68 |
by (asm_simp_tac (simpset() addsimps |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
69 |
[eq_sym_conv,count_addm_simp,Multiset.delm_nonempty_def, |
4833 | 70 |
Multiset.countm_nonempty_def,pos_count_imp_pos_countm]) 1); |
3073
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
71 |
qed "countm_done_delm"; |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
72 |
|
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
73 |
|
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
74 |
Addsimps [count_addm_simp, count_delm_simp, |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
75 |
Multiset.countm_empty_def, Multiset.delm_empty_def, |
88366253a09a
Old NTP files now running under the IOA meta theory based on HOLCF;
mueller
parents:
diff
changeset
|
76 |
count_empty]; |