IOA/example/Multiset.ML
changeset 252 a4dc62a46ee4
parent 251 f04b33ce250f
child 253 132634d24019
equal deleted inserted replaced
251:f04b33ce250f 252:a4dc62a46ee4
     1 (*  Title:      HOL/IOA/example/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,Suc(count(M,y)),count(M,y))";
       
    17   by (asm_simp_tac (arith_ss addsimps 
       
    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)";
       
    23   by (simp_tac (arith_ss addsimps [count_addm_simp]
       
    24                          setloop (split_tac [expand_if])) 1);
       
    25   by (rtac impI 1);
       
    26   by (rtac (le_refl RS (leq_suc RS mp)) 1);
       
    27 qed "count_leq_addm";
       
    28 
       
    29 goalw Multiset.thy [Multiset.count_def] 
       
    30      "count(delm(M,x),y) = if(y=x,pred(count(M,y)),count(M,y))";
       
    31   by (res_inst_tac [("M","M")] Multiset.induction 1);
       
    32   by (asm_simp_tac (arith_ss 
       
    33                    addsimps [Multiset.delm_empty_def,Multiset.countm_empty_def]
       
    34                    setloop (split_tac [expand_if])) 1);
       
    35   by (asm_full_simp_tac (arith_ss 
       
    36                          addsimps [Multiset.delm_nonempty_def,
       
    37                                    Multiset.countm_nonempty_def]
       
    38                          setloop (split_tac [expand_if])) 1);
       
    39   by (safe_tac HOL_cs);
       
    40   by (asm_full_simp_tac HOL_ss 1);
       
    41 qed "count_delm_simp";
       
    42 
       
    43 goal Multiset.thy "!!M. (!x. P(x) --> Q(x)) ==> (countm(M,P) <= countm(M,Q))";
       
    44   by (res_inst_tac [("M","M")] Multiset.induction 1);
       
    45   by (simp_tac (arith_ss addsimps [Multiset.countm_empty_def]) 1);
       
    46   by (simp_tac (arith_ss addsimps[Multiset.countm_nonempty_def]) 1);
       
    47   by (etac (less_eq_add_cong RS mp RS mp) 1);
       
    48   by (asm_full_simp_tac (arith_ss addsimps [le_eq_less_or_eq]
       
    49                                   setloop (split_tac [expand_if])) 1);
       
    50 qed "countm_props";
       
    51 
       
    52 goal Multiset.thy "!!P. ~P(obj) ==> countm(M,P) = countm(delm(M,obj),P)";
       
    53   by (res_inst_tac [("M","M")] Multiset.induction 1);
       
    54   by (simp_tac (arith_ss addsimps [Multiset.delm_empty_def,
       
    55                                    Multiset.countm_empty_def]) 1);
       
    56   by (asm_simp_tac (arith_ss addsimps[Multiset.countm_nonempty_def,
       
    57                                       Multiset.delm_nonempty_def]
       
    58                              setloop (split_tac [expand_if])) 1);
       
    59 qed "countm_spurious_delm";
       
    60 
       
    61 
       
    62 goal Multiset.thy "!!P. P(x) ==> 0<count(M,x) --> 0<countm(M,P)";
       
    63   by (res_inst_tac [("M","M")] Multiset.induction 1);
       
    64   by (simp_tac (arith_ss addsimps 
       
    65                           [Multiset.delm_empty_def,Multiset.count_def,
       
    66                            Multiset.countm_empty_def]) 1);
       
    67   by (asm_simp_tac (arith_ss addsimps 
       
    68                        [Multiset.count_def,Multiset.delm_nonempty_def,
       
    69                         Multiset.countm_nonempty_def]
       
    70                     setloop (split_tac [expand_if])) 1);
       
    71 val pos_count_imp_pos_countm = store_thm("pos_count_imp_pos_countm", standard(result() RS mp));
       
    72 
       
    73 goal Multiset.thy
       
    74    "!!P. P(x) ==> 0<count(M,x) --> countm(delm(M,x),P) = pred(countm(M,P))";
       
    75   by (res_inst_tac [("M","M")] Multiset.induction 1);
       
    76   by (simp_tac (arith_ss addsimps 
       
    77                           [Multiset.delm_empty_def,
       
    78                            Multiset.countm_empty_def]) 1);
       
    79   by (asm_simp_tac (arith_ss addsimps 
       
    80                       [eq_sym_conv,count_addm_simp,Multiset.delm_nonempty_def,
       
    81                        Multiset.countm_nonempty_def,pos_count_imp_pos_countm,
       
    82                        suc_pred_id]
       
    83                     setloop (split_tac [expand_if])) 1);
       
    84 qed "countm_done_delm";