src/HOL/Word/WordArith.thy
changeset 24397 eaf37b780683
parent 24382 54da7d61372d
child 24408 058c5613a86f
equal deleted inserted replaced
24396:c1e20c65a3be 24397:eaf37b780683
    36   by (rule word_number_of_alt)
    36   by (rule word_number_of_alt)
    37 
    37 
    38 lemma word_m1_wi_Min: "-1 = word_of_int Numeral.Min"
    38 lemma word_m1_wi_Min: "-1 = word_of_int Numeral.Min"
    39   by (simp add: word_m1_wi number_of_eq)
    39   by (simp add: word_m1_wi number_of_eq)
    40 
    40 
    41 lemma word_0_bl: "of_bl [] = 0" 
       
    42   unfolding word_0_wi of_bl_def by (simp add : Pls_def)
       
    43 
       
    44 lemma word_1_bl: "of_bl [True] = 1" 
       
    45   unfolding word_1_wi of_bl_def
       
    46   by (simp add : bl_to_bin_def Bit_def Pls_def)
       
    47 
       
    48 lemma uint_0 [simp] : "(uint 0 = 0)" 
    41 lemma uint_0 [simp] : "(uint 0 = 0)" 
    49   unfolding word_0_wi
    42   unfolding word_0_wi
    50   by (simp add: word_ubin.eq_norm Pls_def [symmetric])
    43   by (simp add: word_ubin.eq_norm Pls_def [symmetric])
    51 
       
    52 lemma of_bl_0 [simp] : "of_bl (replicate n False) = 0"
       
    53   by (simp add : word_0_wi of_bl_def bl_to_bin_rep_False Pls_def)
       
    54 
       
    55 lemma to_bl_0: 
       
    56   "to_bl (0::'a::len0 word) = replicate (len_of TYPE('a)) False"
       
    57   unfolding uint_bl
       
    58   by (simp add : word_size bin_to_bl_Pls Pls_def [symmetric])
       
    59 
    44 
    60 lemma uint_0_iff: "(uint x = 0) = (x = 0)"
    45 lemma uint_0_iff: "(uint x = 0) = (x = 0)"
    61   by (auto intro!: word_uint.Rep_eqD)
    46   by (auto intro!: word_uint.Rep_eqD)
    62 
    47 
    63 lemma unat_0_iff: "(unat x = 0) = (x = 0)"
    48 lemma unat_0_iff: "(unat x = 0) = (x = 0)"
   740   apply (drule less_le_mult)
   725   apply (drule less_le_mult)
   741    apply arith
   726    apply arith
   742   apply simp
   727   apply simp
   743   done
   728   done
   744 
   729 
   745 (* links with rbl operations *)
       
   746 lemma word_succ_rbl:
       
   747   "to_bl w = bl ==> to_bl (word_succ w) = (rev (rbl_succ (rev bl)))"
       
   748   apply (unfold word_succ_def)
       
   749   apply clarify
       
   750   apply (simp add: to_bl_of_bin)
       
   751   apply (simp add: to_bl_def rbl_succ)
       
   752   done
       
   753 
       
   754 lemma word_pred_rbl:
       
   755   "to_bl w = bl ==> to_bl (word_pred w) = (rev (rbl_pred (rev bl)))"
       
   756   apply (unfold word_pred_def)
       
   757   apply clarify
       
   758   apply (simp add: to_bl_of_bin)
       
   759   apply (simp add: to_bl_def rbl_pred)
       
   760   done
       
   761 
       
   762 lemma word_add_rbl:
       
   763   "to_bl v = vbl ==> to_bl w = wbl ==> 
       
   764     to_bl (v + w) = (rev (rbl_add (rev vbl) (rev wbl)))"
       
   765   apply (unfold word_add_def)
       
   766   apply clarify
       
   767   apply (simp add: to_bl_of_bin)
       
   768   apply (simp add: to_bl_def rbl_add)
       
   769   done
       
   770 
       
   771 lemma word_mult_rbl:
       
   772   "to_bl v = vbl ==> to_bl w = wbl ==> 
       
   773     to_bl (v * w) = (rev (rbl_mult (rev vbl) (rev wbl)))"
       
   774   apply (unfold word_mult_def)
       
   775   apply clarify
       
   776   apply (simp add: to_bl_of_bin)
       
   777   apply (simp add: to_bl_def rbl_mult)
       
   778   done
       
   779 
       
   780 lemma rtb_rbl_ariths:
       
   781   "rev (to_bl w) = ys \<Longrightarrow> rev (to_bl (word_succ w)) = rbl_succ ys"
       
   782 
       
   783   "rev (to_bl w) = ys \<Longrightarrow> rev (to_bl (word_pred w)) = rbl_pred ys"
       
   784 
       
   785   "[| rev (to_bl v) = ys; rev (to_bl w) = xs |] 
       
   786   ==> rev (to_bl (v * w)) = rbl_mult ys xs"
       
   787 
       
   788   "[| rev (to_bl v) = ys; rev (to_bl w) = xs |] 
       
   789   ==> rev (to_bl (v + w)) = rbl_add ys xs"
       
   790   by (auto simp: rev_swap [symmetric] word_succ_rbl 
       
   791                  word_pred_rbl word_mult_rbl word_add_rbl)
       
   792 
       
   793 
       
   794 subsection "Arithmetic type class instantiations"
   730 subsection "Arithmetic type class instantiations"
   795 
   731 
   796 instance word :: (len0) comm_monoid_add ..
   732 instance word :: (len0) comm_monoid_add ..
   797 
   733 
   798 instance word :: (len0) comm_monoid_mult
   734 instance word :: (len0) comm_monoid_mult
  1230 
  1166 
  1231 lemma word_arith_power_alt: 
  1167 lemma word_arith_power_alt: 
  1232   "a ^ n = (word_of_int (uint a ^ n) :: 'a :: len word)"
  1168   "a ^ n = (word_of_int (uint a ^ n) :: 'a :: len word)"
  1233   by (simp add : word_of_int_power_hom [symmetric])
  1169   by (simp add : word_of_int_power_hom [symmetric])
  1234 
  1170 
  1235 lemma of_bl_length_less: 
       
  1236   "length x = k ==> k < len_of TYPE('a) ==> (of_bl x :: 'a :: len word) < 2 ^ k"
       
  1237   apply (unfold of_bl_no [unfolded word_number_of_def]
       
  1238                 word_less_alt word_number_of_alt)
       
  1239   apply safe
       
  1240   apply (simp (no_asm) add: word_of_int_power_hom word_uint.eq_norm 
       
  1241                        del: word_of_int_bin)
       
  1242   apply (simp add: mod_pos_pos_trivial)
       
  1243   apply (subst mod_pos_pos_trivial)
       
  1244     apply (rule bl_to_bin_ge0)
       
  1245    apply (rule order_less_trans)
       
  1246     apply (rule bl_to_bin_lt2p)
       
  1247    apply simp
       
  1248   apply (rule bl_to_bin_lt2p)    
       
  1249   done
       
  1250 
       
  1251 
  1171 
  1252 subsection "Cardinality, finiteness of set of words"
  1172 subsection "Cardinality, finiteness of set of words"
  1253 
  1173 
  1254 lemmas card_lessThan' = card_lessThan [unfolded lessThan_def]
  1174 lemmas card_lessThan' = card_lessThan [unfolded lessThan_def]
  1255 
  1175