src/HOL/Word/Bit_Int.thy
changeset 45847 b4254b2e2b4a
parent 45845 4158f35a5c6f
child 45955 fc303e8f5c20
equal deleted inserted replaced
45846:518a245a1ab6 45847:b4254b2e2b4a
    52   done
    52   done
    53   
    53   
    54 lemma bin_rec_Bit:
    54 lemma bin_rec_Bit:
    55   "f = bin_rec f1 f2 f3  ==> f3 Int.Pls (0::bit) f1 = f1 ==> 
    55   "f = bin_rec f1 f2 f3  ==> f3 Int.Pls (0::bit) f1 = f1 ==> 
    56     f3 Int.Min (1::bit) f2 = f2 ==> f (w BIT b) = f3 w b (f w)"
    56     f3 Int.Min (1::bit) f2 = f2 ==> f (w BIT b) = f3 w b (f w)"
    57   by (cases b, simp add: bin_rec_Bit0, simp add: bin_rec_Bit1)
    57   by (cases b, simp add: bin_rec_Bit0 BIT_simps, simp add: bin_rec_Bit1 BIT_simps)
    58 
    58 
    59 lemmas bin_rec_simps = refl [THEN bin_rec_Bit] bin_rec_Pls bin_rec_Min
    59 lemmas bin_rec_simps = refl [THEN bin_rec_Bit] bin_rec_Pls bin_rec_Min
    60   bin_rec_Bit0 bin_rec_Bit1
    60   bin_rec_Bit0 bin_rec_Bit1
    61 
    61 
    62 
    62 
    93   "NOT Int.Pls = Int.Min"
    93   "NOT Int.Pls = Int.Min"
    94   "NOT Int.Min = Int.Pls"
    94   "NOT Int.Min = Int.Pls"
    95   "NOT (Int.Bit0 w) = Int.Bit1 (NOT w)"
    95   "NOT (Int.Bit0 w) = Int.Bit1 (NOT w)"
    96   "NOT (Int.Bit1 w) = Int.Bit0 (NOT w)"
    96   "NOT (Int.Bit1 w) = Int.Bit0 (NOT w)"
    97   "NOT (w BIT b) = (NOT w) BIT (NOT b)"
    97   "NOT (w BIT b) = (NOT w) BIT (NOT b)"
    98   unfolding int_not_def Pls_def [symmetric] Min_def [symmetric] by (simp_all add: bin_rec_simps)
    98   unfolding int_not_def Pls_def [symmetric] Min_def [symmetric]
       
    99   by (simp_all add: bin_rec_simps BIT_simps)
    99 
   100 
   100 lemma int_xor_Pls [simp]: 
   101 lemma int_xor_Pls [simp]: 
   101   "Int.Pls XOR x = x"
   102   "Int.Pls XOR x = x"
   102   unfolding int_xor_def Pls_def [symmetric] Min_def [symmetric] by (simp add: bin_rec_PM)
   103   unfolding int_xor_def Pls_def [symmetric] Min_def [symmetric] by (simp add: bin_rec_PM)
   103 
   104 
   131   "Int.Min OR x = Int.Min"
   132   "Int.Min OR x = Int.Min"
   132   by (unfold int_or_def Pls_def [symmetric] Min_def [symmetric]) (simp add: bin_rec_PM)
   133   by (unfold int_or_def Pls_def [symmetric] Min_def [symmetric]) (simp add: bin_rec_PM)
   133 
   134 
   134 lemma int_or_Bits [simp]: 
   135 lemma int_or_Bits [simp]: 
   135   "(x BIT b) OR (y BIT c) = (x OR y) BIT (b OR c)"
   136   "(x BIT b) OR (y BIT c) = (x OR y) BIT (b OR c)"
   136   unfolding int_or_def Pls_def [symmetric] Min_def [symmetric] by (simp add: bin_rec_simps)
   137   unfolding int_or_def Pls_def [symmetric] Min_def [symmetric]
       
   138   by (simp add: bin_rec_simps BIT_simps)
   137 
   139 
   138 lemma int_or_Bits2 [simp]: 
   140 lemma int_or_Bits2 [simp]: 
   139   "(Int.Bit0 x) OR (Int.Bit0 y) = Int.Bit0 (x OR y)"
   141   "(Int.Bit0 x) OR (Int.Bit0 y) = Int.Bit0 (x OR y)"
   140   "(Int.Bit0 x) OR (Int.Bit1 y) = Int.Bit1 (x OR y)"
   142   "(Int.Bit0 x) OR (Int.Bit1 y) = Int.Bit1 (x OR y)"
   141   "(Int.Bit1 x) OR (Int.Bit0 y) = Int.Bit1 (x OR y)"
   143   "(Int.Bit1 x) OR (Int.Bit0 y) = Int.Bit1 (x OR y)"
   150   "Int.Min AND x = x"
   152   "Int.Min AND x = x"
   151   unfolding int_and_def by (simp add: bin_rec_PM)
   153   unfolding int_and_def by (simp add: bin_rec_PM)
   152 
   154 
   153 lemma int_and_Bits [simp]: 
   155 lemma int_and_Bits [simp]: 
   154   "(x BIT b) AND (y BIT c) = (x AND y) BIT (b AND c)" 
   156   "(x BIT b) AND (y BIT c) = (x AND y) BIT (b AND c)" 
   155   unfolding int_and_def Pls_def [symmetric] Min_def [symmetric] by (simp add: bin_rec_simps)
   157   unfolding int_and_def Pls_def [symmetric] Min_def [symmetric]
       
   158   by (simp add: bin_rec_simps BIT_simps)
   156 
   159 
   157 lemma int_and_Bits2 [simp]: 
   160 lemma int_and_Bits2 [simp]: 
   158   "(Int.Bit0 x) AND (Int.Bit0 y) = Int.Bit0 (x AND y)"
   161   "(Int.Bit0 x) AND (Int.Bit0 y) = Int.Bit0 (x AND y)"
   159   "(Int.Bit0 x) AND (Int.Bit1 y) = Int.Bit0 (x AND y)"
   162   "(Int.Bit0 x) AND (Int.Bit1 y) = Int.Bit0 (x AND y)"
   160   "(Int.Bit1 x) AND (Int.Bit0 y) = Int.Bit0 (x AND y)"
   163   "(Int.Bit1 x) AND (Int.Bit0 y) = Int.Bit0 (x AND y)"
   320     apply clarsimp
   323     apply clarsimp
   321    apply clarsimp
   324    apply clarsimp
   322   apply (case_tac x rule: bin_exhaust)
   325   apply (case_tac x rule: bin_exhaust)
   323   apply (case_tac b)
   326   apply (case_tac b)
   324    apply (case_tac [!] bit)
   327    apply (case_tac [!] bit)
   325      apply (auto simp: less_eq_int_code)
   328      apply (auto simp: less_eq_int_code BIT_simps)
   326   done
   329   done
   327 
   330 
   328 lemmas int_and_le =
   331 lemmas int_and_le =
   329   xtr3 [OF bbw_ao_absorbs (2) [THEN conjunct2, symmetric] le_int_or]
   332   xtr3 [OF bbw_ao_absorbs (2) [THEN conjunct2, symmetric] le_int_or]
   330 
   333 
   332 (* good example of bin_induction *)
   335 (* good example of bin_induction *)
   333 lemma bin_add_not: "x + NOT x = Int.Min"
   336 lemma bin_add_not: "x + NOT x = Int.Min"
   334   apply (induct x rule: bin_induct)
   337   apply (induct x rule: bin_induct)
   335     apply clarsimp
   338     apply clarsimp
   336    apply clarsimp
   339    apply clarsimp
   337   apply (case_tac bit, auto)
   340   apply (case_tac bit, auto simp: BIT_simps)
   338   done
   341   done
   339 
   342 
   340 subsubsection {* Truncating results of bit-wise operations *}
   343 subsubsection {* Truncating results of bit-wise operations *}
   341 
   344 
   342 lemma bin_trunc_ao: 
   345 lemma bin_trunc_ao: 
   445    apply (unfold Bit_def)
   448    apply (unfold Bit_def)
   446    apply (simp_all add: bitval_def split: bit.split)
   449    apply (simp_all add: bitval_def split: bit.split)
   447   done
   450   done
   448 
   451 
   449 lemma bin_sc_FP [simp]: "bin_sc n 0 Int.Pls = Int.Pls"
   452 lemma bin_sc_FP [simp]: "bin_sc n 0 Int.Pls = Int.Pls"
   450   by (induct n) auto
   453   by (induct n) (auto simp: BIT_simps)
   451 
   454 
   452 lemma bin_sc_TM [simp]: "bin_sc n 1 Int.Min = Int.Min"
   455 lemma bin_sc_TM [simp]: "bin_sc n 1 Int.Min = Int.Min"
   453   by (induct n) auto
   456   by (induct n) (auto simp: BIT_simps)
   454   
   457   
   455 lemmas bin_sc_simps = bin_sc.Z bin_sc.Suc bin_sc_TM bin_sc_FP
   458 lemmas bin_sc_simps = bin_sc.Z bin_sc.Suc bin_sc_TM bin_sc_FP
   456 
   459 
   457 lemma bin_sc_minus:
   460 lemma bin_sc_minus:
   458   "0 < n ==> bin_sc (Suc (n - 1)) b w = bin_sc n b w"
   461   "0 < n ==> bin_sc (Suc (n - 1)) b w = bin_sc n b w"
   564   "!!w. bin_split n (bin_cat v n w) = (v, bintrunc n w)"
   567   "!!w. bin_split n (bin_cat v n w) = (v, bintrunc n w)"
   565   by (induct n) auto
   568   by (induct n) auto
   566 
   569 
   567 lemma bin_split_Pls [simp]:
   570 lemma bin_split_Pls [simp]:
   568   "bin_split n Int.Pls = (Int.Pls, Int.Pls)"
   571   "bin_split n Int.Pls = (Int.Pls, Int.Pls)"
   569   by (induct n) (auto simp: Let_def split: ls_splits)
   572   by (induct n) (auto simp: Let_def BIT_simps split: ls_splits)
   570 
   573 
   571 lemma bin_split_Min [simp]:
   574 lemma bin_split_Min [simp]:
   572   "bin_split n Int.Min = (Int.Min, bintrunc n Int.Min)"
   575   "bin_split n Int.Min = (Int.Min, bintrunc n Int.Min)"
   573   by (induct n) (auto simp: Let_def split: ls_splits)
   576   by (induct n) (auto simp: Let_def split: ls_splits)
   574 
   577 
   576   "!!m b c. bin_split (min m n) c = (a, b) ==> 
   579   "!!m b c. bin_split (min m n) c = (a, b) ==> 
   577     bin_split n (bintrunc m c) = (bintrunc (m - n) a, b)"
   580     bin_split n (bintrunc m c) = (bintrunc (m - n) a, b)"
   578   apply (induct n, clarsimp)
   581   apply (induct n, clarsimp)
   579   apply (simp add: bin_rest_trunc Let_def split: ls_splits)
   582   apply (simp add: bin_rest_trunc Let_def split: ls_splits)
   580   apply (case_tac m)
   583   apply (case_tac m)
   581    apply (auto simp: Let_def split: ls_splits)
   584    apply (auto simp: Let_def BIT_simps split: ls_splits)
   582   done
   585   done
   583 
   586 
   584 lemma bin_split_trunc1:
   587 lemma bin_split_trunc1:
   585   "!!m b c. bin_split n c = (a, b) ==> 
   588   "!!m b c. bin_split n c = (a, b) ==> 
   586     bin_split n (bintrunc m c) = (bintrunc (m - n) a, bintrunc m b)"
   589     bin_split n (bintrunc m c) = (bintrunc (m - n) a, bintrunc m b)"
   587   apply (induct n, clarsimp)
   590   apply (induct n, clarsimp)
   588   apply (simp add: bin_rest_trunc Let_def split: ls_splits)
   591   apply (simp add: bin_rest_trunc Let_def split: ls_splits)
   589   apply (case_tac m)
   592   apply (case_tac m)
   590    apply (auto simp: Let_def split: ls_splits)
   593    apply (auto simp: Let_def BIT_simps split: ls_splits)
   591   done
   594   done
   592 
   595 
   593 lemma bin_cat_num:
   596 lemma bin_cat_num:
   594   "!!b. bin_cat a n b = a * 2 ^ n + bintrunc n b"
   597   "!!b. bin_cat a n b = a * 2 ^ n + bintrunc n b"
   595   apply (induct n, clarsimp)
   598   apply (induct n, clarsimp)