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)" |
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) |