1051

1 
(* Title: HOL/IOA/NTP/Multiset.ML


2 
ID: $Id$


3 
Author: Tobias Nipkow & Konrad Slind


4 
Copyright 1994 TU Muenchen


5 


6 
Axiomatic multisets.


7 
Should be done as a subtype and moved to a global place.


8 
*)


9 


10 
goalw Multiset.thy [Multiset.count_def, Multiset.countm_empty_def]


11 
"count {} x = 0";


12 
by (rtac refl 1);


13 
qed "count_empty";


14 


15 
goal Multiset.thy


16 
"count (addm M x) y = (if y=x then Suc(count M y) else count M y)";

1266

17 
by (asm_simp_tac (!simpset addsimps

1051

18 
[Multiset.count_def,Multiset.countm_nonempty_def]


19 
setloop (split_tac [expand_if])) 1);


20 
qed "count_addm_simp";


21 


22 
goal Multiset.thy "count M y <= count (addm M x) y";

1266

23 
by (simp_tac (!simpset addsimps [count_addm_simp]

1051

24 
setloop (split_tac [expand_if])) 1);


25 
qed "count_leq_addm";


26 


27 
goalw Multiset.thy [Multiset.count_def]


28 
"count (delm M x) y = (if y=x then pred(count M y) else count M y)";


29 
by (res_inst_tac [("M","M")] Multiset.induction 1);

1266

30 
by (asm_simp_tac (!simpset

1051

31 
addsimps [Multiset.delm_empty_def,Multiset.countm_empty_def]


32 
setloop (split_tac [expand_if])) 1);

1266

33 
by (asm_full_simp_tac (!simpset

1051

34 
addsimps [Multiset.delm_nonempty_def,


35 
Multiset.countm_nonempty_def]


36 
setloop (split_tac [expand_if])) 1);

1894

37 
by (safe_tac (!claset));

1266

38 
by (Asm_full_simp_tac 1);

1051

39 
qed "count_delm_simp";


40 


41 
goal Multiset.thy "!!M. (!x. P(x) > Q(x)) ==> (countm M P <= countm M Q)";


42 
by (res_inst_tac [("M","M")] Multiset.induction 1);

1266

43 
by (simp_tac (!simpset addsimps [Multiset.countm_empty_def]) 1);


44 
by (simp_tac (!simpset addsimps[Multiset.countm_nonempty_def]) 1);

1051

45 
by (etac (less_eq_add_cong RS mp RS mp) 1);

1266

46 
by (asm_full_simp_tac (!simpset addsimps [le_eq_less_or_eq]

1051

47 
setloop (split_tac [expand_if])) 1);


48 
qed "countm_props";


49 


50 
goal Multiset.thy "!!P. ~P(obj) ==> countm M P = countm (delm M obj) P";


51 
by (res_inst_tac [("M","M")] Multiset.induction 1);

1266

52 
by (simp_tac (!simpset addsimps [Multiset.delm_empty_def,

1051

53 
Multiset.countm_empty_def]) 1);

1266

54 
by (asm_simp_tac (!simpset addsimps[Multiset.countm_nonempty_def,

1051

55 
Multiset.delm_nonempty_def]


56 
setloop (split_tac [expand_if])) 1);


57 
qed "countm_spurious_delm";


58 


59 


60 
goal Multiset.thy "!!P. P(x) ==> 0<count M x > 0<countm M P";


61 
by (res_inst_tac [("M","M")] Multiset.induction 1);

1266

62 
by (simp_tac (!simpset addsimps

1051

63 
[Multiset.delm_empty_def,Multiset.count_def,


64 
Multiset.countm_empty_def]) 1);

1266

65 
by (asm_simp_tac (!simpset addsimps

1051

66 
[Multiset.count_def,Multiset.delm_nonempty_def,


67 
Multiset.countm_nonempty_def]


68 
setloop (split_tac [expand_if])) 1);


69 
val pos_count_imp_pos_countm = store_thm("pos_count_imp_pos_countm", standard(result() RS mp));


70 


71 
goal Multiset.thy


72 
"!!P. P(x) ==> 0<count M x > countm (delm M x) P = pred (countm M P)";


73 
by (res_inst_tac [("M","M")] Multiset.induction 1);

1266

74 
by (simp_tac (!simpset addsimps

1051

75 
[Multiset.delm_empty_def,


76 
Multiset.countm_empty_def]) 1);

1266

77 
by (asm_simp_tac (!simpset addsimps

1051

78 
[eq_sym_conv,count_addm_simp,Multiset.delm_nonempty_def,


79 
Multiset.countm_nonempty_def,pos_count_imp_pos_countm,


80 
suc_pred_id]


81 
setloop (split_tac [expand_if])) 1);


82 
qed "countm_done_delm";

1328

83 


84 


85 
Addsimps [count_addm_simp, count_delm_simp,


86 
Multiset.countm_empty_def, Multiset.delm_empty_def,

1465

87 
count_empty];
