author | paulson |
Tue, 23 May 2000 18:06:22 +0200 | |
changeset 8935 | 548901d05a0e |
parent 8864 | a12ccd629e2c |
child 9064 | eacebbcafe57 |
permissions | -rw-r--r-- |
7032 | 1 |
(* Title: HOL/NatBin.ML |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1999 University of Cambridge |
|
5 |
||
6 |
Binary arithmetic for the natural numbers |
|
7 |
*) |
|
8 |
||
9 |
(** nat (coercion from int to nat) **) |
|
10 |
||
11 |
Goal "nat (number_of w) = number_of w"; |
|
12 |
by (simp_tac (simpset() addsimps [nat_number_of_def]) 1); |
|
13 |
qed "nat_number_of"; |
|
14 |
Addsimps [nat_number_of]; |
|
15 |
||
16 |
(*These rewrites should one day be re-oriented...*) |
|
17 |
||
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
18 |
Goal "#0 = (0::nat)"; |
7032 | 19 |
by (simp_tac (simpset_of Int.thy addsimps [nat_0, nat_number_of_def]) 1); |
20 |
qed "numeral_0_eq_0"; |
|
21 |
||
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
22 |
Goal "#1 = (1::nat)"; |
7032 | 23 |
by (simp_tac (simpset_of Int.thy addsimps [nat_1, nat_number_of_def]) 1); |
24 |
qed "numeral_1_eq_1"; |
|
25 |
||
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
26 |
Goal "#2 = (2::nat)"; |
7032 | 27 |
by (simp_tac (simpset_of Int.thy addsimps [nat_2, nat_number_of_def]) 1); |
28 |
qed "numeral_2_eq_2"; |
|
29 |
||
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
30 |
bind_thm ("zero_eq_numeral_0", numeral_0_eq_0 RS sym); |
7032 | 31 |
|
32 |
(** int (coercion from nat to int) **) |
|
33 |
||
34 |
(*"neg" is used in rewrite rules for binary comparisons*) |
|
35 |
Goal "int (number_of v :: nat) = \ |
|
36 |
\ (if neg (number_of v) then #0 \ |
|
37 |
\ else (number_of v :: int))"; |
|
38 |
by (simp_tac |
|
39 |
(simpset_of Int.thy addsimps [neg_nat, nat_number_of_def, |
|
40 |
not_neg_nat, int_0]) 1); |
|
41 |
qed "int_nat_number_of"; |
|
42 |
Addsimps [int_nat_number_of]; |
|
43 |
||
44 |
||
45 |
(** Successor **) |
|
46 |
||
47 |
Goal "(#0::int) <= z ==> Suc (nat z) = nat (#1 + z)"; |
|
7086 | 48 |
by (rtac sym 1); |
7032 | 49 |
by (asm_simp_tac (simpset() addsimps [nat_eq_iff]) 1); |
50 |
qed "Suc_nat_eq_nat_zadd1"; |
|
51 |
||
52 |
Goal "Suc (number_of v) = \ |
|
53 |
\ (if neg (number_of v) then #1 else number_of (bin_succ v))"; |
|
54 |
by (simp_tac |
|
55 |
(simpset_of Int.thy addsimps [neg_nat, nat_1, not_neg_eq_ge_0, |
|
56 |
nat_number_of_def, int_Suc, |
|
57 |
Suc_nat_eq_nat_zadd1, number_of_succ]) 1); |
|
58 |
qed "Suc_nat_number_of"; |
|
8737
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
59 |
Addsimps [Suc_nat_number_of]; |
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
60 |
|
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
61 |
Goal "Suc (number_of v + n) = \ |
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
62 |
\ (if neg (number_of v) then #1+n else number_of (bin_succ v) + n)"; |
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
63 |
by (Simp_tac 1); |
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
64 |
qed "Suc_nat_number_of_add"; |
7032 | 65 |
|
66 |
Goal "Suc #0 = #1"; |
|
8737
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
67 |
by (Simp_tac 1); |
7032 | 68 |
qed "Suc_numeral_0_eq_1"; |
69 |
||
70 |
Goal "Suc #1 = #2"; |
|
8737
f9733879ff25
instantiates new simprocs for numerals of type "nat"
paulson
parents:
8698
diff
changeset
|
71 |
by (Simp_tac 1); |
7032 | 72 |
qed "Suc_numeral_1_eq_2"; |
73 |
||
74 |
(** Addition **) |
|
75 |
||
8028 | 76 |
Goal "[| (#0::int) <= z; #0 <= z' |] ==> nat (z+z') = nat z + nat z'"; |
7032 | 77 |
by (rtac (inj_int RS injD) 1); |
78 |
by (asm_simp_tac (simpset() addsimps [zadd_int RS sym]) 1); |
|
8028 | 79 |
qed "nat_add_distrib"; |
7032 | 80 |
|
81 |
(*"neg" is used in rewrite rules for binary comparisons*) |
|
82 |
Goal "(number_of v :: nat) + number_of v' = \ |
|
83 |
\ (if neg (number_of v) then number_of v' \ |
|
84 |
\ else if neg (number_of v') then number_of v \ |
|
85 |
\ else number_of (bin_add v v'))"; |
|
86 |
by (simp_tac |
|
87 |
(simpset_of Int.thy addsimps [neg_nat, not_neg_eq_ge_0, nat_number_of_def, |
|
8028 | 88 |
nat_add_distrib RS sym, number_of_add]) 1); |
7032 | 89 |
qed "add_nat_number_of"; |
90 |
||
91 |
Addsimps [add_nat_number_of]; |
|
92 |
||
93 |
||
94 |
(** Subtraction **) |
|
95 |
||
8028 | 96 |
Goal "[| (#0::int) <= z'; z' <= z |] ==> nat (z-z') = nat z - nat z'"; |
7032 | 97 |
by (rtac (inj_int RS injD) 1); |
98 |
by (asm_simp_tac (simpset() addsimps [zdiff_int RS sym, nat_le_eq_zle]) 1); |
|
8028 | 99 |
qed "nat_diff_distrib"; |
7032 | 100 |
|
101 |
||
102 |
Goal "nat z - nat z' = \ |
|
103 |
\ (if neg z' then nat z \ |
|
104 |
\ else let d = z-z' in \ |
|
105 |
\ if neg d then 0 else nat d)"; |
|
8028 | 106 |
by (simp_tac (simpset() addsimps [Let_def, nat_diff_distrib RS sym, |
7032 | 107 |
neg_eq_less_0, not_neg_eq_ge_0]) 1); |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
108 |
by (simp_tac (simpset() addsimps [diff_is_0_eq, nat_le_eq_zle]) 1); |
7032 | 109 |
qed "diff_nat_eq_if"; |
110 |
||
111 |
Goalw [nat_number_of_def] |
|
112 |
"(number_of v :: nat) - number_of v' = \ |
|
113 |
\ (if neg (number_of v') then number_of v \ |
|
114 |
\ else let d = number_of (bin_add v (bin_minus v')) in \ |
|
115 |
\ if neg d then #0 else nat d)"; |
|
116 |
by (simp_tac |
|
117 |
(simpset_of Int.thy delcongs [if_weak_cong] |
|
118 |
addsimps [not_neg_eq_ge_0, nat_0, |
|
119 |
diff_nat_eq_if, diff_number_of_eq]) 1); |
|
120 |
qed "diff_nat_number_of"; |
|
121 |
||
122 |
Addsimps [diff_nat_number_of]; |
|
123 |
||
124 |
||
125 |
(** Multiplication **) |
|
126 |
||
8028 | 127 |
Goal "(#0::int) <= z ==> nat (z*z') = nat z * nat z'"; |
7032 | 128 |
by (case_tac "#0 <= z'" 1); |
129 |
by (subgoal_tac "z'*z <= #0" 2); |
|
130 |
by (rtac (neg_imp_zmult_nonpos_iff RS iffD2) 3); |
|
7075 | 131 |
by (auto_tac (claset(), |
132 |
simpset() addsimps [zmult_commute])); |
|
7032 | 133 |
by (subgoal_tac "#0 <= z*z'" 1); |
134 |
by (force_tac (claset() addDs [zmult_zle_mono1], simpset()) 2); |
|
135 |
by (rtac (inj_int RS injD) 1); |
|
136 |
by (asm_simp_tac (simpset() addsimps [zmult_int RS sym]) 1); |
|
8028 | 137 |
qed "nat_mult_distrib"; |
7032 | 138 |
|
139 |
Goal "(number_of v :: nat) * number_of v' = \ |
|
140 |
\ (if neg (number_of v) then #0 else number_of (bin_mult v v'))"; |
|
141 |
by (simp_tac |
|
142 |
(simpset_of Int.thy addsimps [neg_nat, not_neg_eq_ge_0, nat_number_of_def, |
|
8028 | 143 |
nat_mult_distrib RS sym, number_of_mult, |
7032 | 144 |
nat_0]) 1); |
145 |
qed "mult_nat_number_of"; |
|
146 |
||
147 |
Addsimps [mult_nat_number_of]; |
|
148 |
||
149 |
||
150 |
(** Quotient **) |
|
151 |
||
8028 | 152 |
Goal "(#0::int) <= z ==> nat (z div z') = nat z div nat z'"; |
7032 | 153 |
by (case_tac "#0 <= z'" 1); |
154 |
by (auto_tac (claset(), |
|
7127
48e235179ffb
added parentheses to cope with a possible reduction of the precedence of unary
paulson
parents:
7086
diff
changeset
|
155 |
simpset() addsimps [div_nonneg_neg_le0, DIVISION_BY_ZERO_DIV])); |
7032 | 156 |
by (zdiv_undefined_case_tac "z' = #0" 1); |
157 |
by (simp_tac (simpset() addsimps [numeral_0_eq_0, DIVISION_BY_ZERO_DIV]) 1); |
|
158 |
by (auto_tac (claset() addSEs [nonneg_eq_int], simpset())); |
|
159 |
by (rename_tac "m m'" 1); |
|
160 |
by (subgoal_tac "#0 <= int m div int m'" 1); |
|
161 |
by (asm_simp_tac (simpset() addsimps [nat_less_iff RS sym, numeral_0_eq_0, |
|
162 |
pos_imp_zdiv_nonneg_iff]) 2); |
|
163 |
by (rtac (inj_int RS injD) 1); |
|
164 |
by (Asm_simp_tac 1); |
|
165 |
by (res_inst_tac [("r", "int (m mod m')")] quorem_div 1); |
|
166 |
by (Force_tac 2); |
|
167 |
by (asm_simp_tac (simpset() addsimps [nat_less_iff RS sym, quorem_def, |
|
8698 | 168 |
numeral_0_eq_0, zadd_int, zmult_int]) 1); |
7032 | 169 |
by (rtac (mod_div_equality RS sym RS trans) 1); |
170 |
by (asm_simp_tac (simpset() addsimps add_ac@mult_ac) 1); |
|
8028 | 171 |
qed "nat_div_distrib"; |
7032 | 172 |
|
173 |
Goal "(number_of v :: nat) div number_of v' = \ |
|
174 |
\ (if neg (number_of v) then #0 \ |
|
175 |
\ else nat (number_of v div number_of v'))"; |
|
176 |
by (simp_tac |
|
177 |
(simpset_of Int.thy addsimps [not_neg_eq_ge_0, nat_number_of_def, neg_nat, |
|
8028 | 178 |
nat_div_distrib RS sym, nat_0]) 1); |
7032 | 179 |
qed "div_nat_number_of"; |
180 |
||
181 |
Addsimps [div_nat_number_of]; |
|
182 |
||
183 |
||
184 |
(** Remainder **) |
|
185 |
||
186 |
(*Fails if z'<0: the LHS collapses to (nat z) but the RHS doesn't*) |
|
8028 | 187 |
Goal "[| (#0::int) <= z; #0 <= z' |] ==> nat (z mod z') = nat z mod nat z'"; |
7032 | 188 |
by (zdiv_undefined_case_tac "z' = #0" 1); |
189 |
by (simp_tac (simpset() addsimps [numeral_0_eq_0, DIVISION_BY_ZERO_MOD]) 1); |
|
190 |
by (auto_tac (claset() addSEs [nonneg_eq_int], simpset())); |
|
191 |
by (rename_tac "m m'" 1); |
|
192 |
by (subgoal_tac "#0 <= int m mod int m'" 1); |
|
193 |
by (asm_simp_tac (simpset() addsimps [nat_less_iff RS sym, numeral_0_eq_0, |
|
194 |
pos_mod_sign]) 2); |
|
195 |
by (rtac (inj_int RS injD) 1); |
|
196 |
by (Asm_simp_tac 1); |
|
197 |
by (res_inst_tac [("q", "int (m div m')")] quorem_mod 1); |
|
198 |
by (Force_tac 2); |
|
199 |
by (asm_simp_tac (simpset() addsimps [nat_less_iff RS sym, quorem_def, |
|
8698 | 200 |
numeral_0_eq_0, zadd_int, zmult_int]) 1); |
7032 | 201 |
by (rtac (mod_div_equality RS sym RS trans) 1); |
202 |
by (asm_simp_tac (simpset() addsimps add_ac@mult_ac) 1); |
|
8028 | 203 |
qed "nat_mod_distrib"; |
7032 | 204 |
|
205 |
Goal "(number_of v :: nat) mod number_of v' = \ |
|
206 |
\ (if neg (number_of v) then #0 \ |
|
207 |
\ else if neg (number_of v') then number_of v \ |
|
208 |
\ else nat (number_of v mod number_of v'))"; |
|
209 |
by (simp_tac |
|
210 |
(simpset_of Int.thy addsimps [not_neg_eq_ge_0, nat_number_of_def, |
|
211 |
neg_nat, nat_0, DIVISION_BY_ZERO_MOD, |
|
8028 | 212 |
nat_mod_distrib RS sym]) 1); |
7032 | 213 |
qed "mod_nat_number_of"; |
214 |
||
215 |
Addsimps [mod_nat_number_of]; |
|
216 |
||
217 |
||
218 |
(*** Comparisons ***) |
|
219 |
||
220 |
(** Equals (=) **) |
|
221 |
||
222 |
Goal "[| (#0::int) <= z; #0 <= z' |] ==> (nat z = nat z') = (z=z')"; |
|
223 |
by (auto_tac (claset() addSEs [nonneg_eq_int], simpset())); |
|
224 |
qed "eq_nat_nat_iff"; |
|
225 |
||
226 |
(*"neg" is used in rewrite rules for binary comparisons*) |
|
227 |
Goal "((number_of v :: nat) = number_of v') = \ |
|
8795 | 228 |
\ (if neg (number_of v) then (iszero (number_of v') | neg (number_of v')) \ |
229 |
\ else if neg (number_of v') then iszero (number_of v) \ |
|
230 |
\ else iszero (number_of (bin_add v (bin_minus v'))))"; |
|
7032 | 231 |
by (simp_tac |
232 |
(simpset_of Int.thy addsimps [neg_nat, not_neg_eq_ge_0, nat_number_of_def, |
|
233 |
eq_nat_nat_iff, eq_number_of_eq, nat_0]) 1); |
|
8795 | 234 |
by (simp_tac (simpset_of Int.thy addsimps [nat_eq_iff, nat_eq_iff2, |
235 |
iszero_def]) 1); |
|
236 |
by (simp_tac (simpset_of Int.thy addsimps [not_neg_eq_ge_0 RS sym]) 1); |
|
7032 | 237 |
qed "eq_nat_number_of"; |
238 |
||
239 |
Addsimps [eq_nat_number_of]; |
|
240 |
||
241 |
(** Less-than (<) **) |
|
242 |
||
243 |
(*"neg" is used in rewrite rules for binary comparisons*) |
|
244 |
Goal "((number_of v :: nat) < number_of v') = \ |
|
245 |
\ (if neg (number_of v) then neg (number_of (bin_minus v')) \ |
|
246 |
\ else neg (number_of (bin_add v (bin_minus v'))))"; |
|
247 |
by (simp_tac |
|
248 |
(simpset_of Int.thy addsimps [neg_nat, not_neg_eq_ge_0, nat_number_of_def, |
|
249 |
nat_less_eq_zless, less_number_of_eq_neg, |
|
250 |
nat_0]) 1); |
|
251 |
by (simp_tac (simpset_of Int.thy addsimps [neg_eq_less_int0, zminus_zless, |
|
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
252 |
number_of_minus, zless_nat_eq_int_zless]) 1); |
7032 | 253 |
qed "less_nat_number_of"; |
254 |
||
255 |
Addsimps [less_nat_number_of]; |
|
256 |
||
257 |
||
258 |
(** Less-than-or-equals (<=) **) |
|
259 |
||
260 |
Goal "(number_of x <= (number_of y::nat)) = \ |
|
261 |
\ (~ number_of y < (number_of x::nat))"; |
|
262 |
by (rtac (linorder_not_less RS sym) 1); |
|
263 |
qed "le_nat_number_of_eq_not_less"; |
|
264 |
||
265 |
Addsimps [le_nat_number_of_eq_not_less]; |
|
266 |
||
267 |
(*** New versions of existing theorems involving 0, 1, 2 ***) |
|
268 |
||
269 |
fun change_theory thy th = |
|
270 |
[th, read_instantiate_sg (sign_of thy) [("t","dummyVar")] refl] |
|
271 |
MRS (conjI RS conjunct1) |> standard; |
|
272 |
||
273 |
(*Maps n to #n for n = 0, 1, 2*) |
|
274 |
val numeral_sym_ss = |
|
275 |
HOL_ss addsimps [numeral_0_eq_0 RS sym, |
|
276 |
numeral_1_eq_1 RS sym, |
|
277 |
numeral_2_eq_2 RS sym, |
|
278 |
Suc_numeral_1_eq_2, Suc_numeral_0_eq_1]; |
|
279 |
||
280 |
fun rename_numerals thy th = simplify numeral_sym_ss (change_theory thy th); |
|
281 |
||
282 |
(*Maps #n to n for n = 0, 1, 2*) |
|
283 |
val numeral_ss = |
|
284 |
simpset() addsimps [numeral_0_eq_0, numeral_1_eq_1, numeral_2_eq_2]; |
|
285 |
||
286 |
(** Nat **) |
|
287 |
||
288 |
Goal "#0 < n ==> n = Suc(n - #1)"; |
|
289 |
by (asm_full_simp_tac numeral_ss 1); |
|
290 |
qed "Suc_pred'"; |
|
291 |
||
292 |
(*Expresses a natural number constant as the Suc of another one. |
|
293 |
NOT suitable for rewriting because n recurs in the condition.*) |
|
294 |
bind_thm ("expand_Suc", inst "n" "number_of ?v" Suc_pred'); |
|
295 |
||
7056
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
296 |
(** NatDef & Nat **) |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
297 |
|
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
298 |
Addsimps (map (rename_numerals thy) |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
299 |
[min_0L, min_0R, max_0L, max_0R]); |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
300 |
|
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
301 |
AddIffs (map (rename_numerals thy) |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
302 |
[Suc_not_Zero, Zero_not_Suc, zero_less_Suc, not_less0, less_one, |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
303 |
le0, le_0_eq, |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
304 |
neq0_conv, zero_neq_conv, not_gr0]); |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
305 |
|
7032 | 306 |
(** Arith **) |
307 |
||
8776 | 308 |
(*Identity laws for + - * *) |
309 |
val basic_renamed_arith_simps = |
|
310 |
map (rename_numerals thy) |
|
311 |
[diff_0, diff_0_eq_0, add_0, add_0_right, |
|
312 |
mult_0, mult_0_right, mult_1, mult_1_right]; |
|
313 |
||
314 |
(*Non-trivial simplifications*) |
|
315 |
val other_renamed_arith_simps = |
|
316 |
map (rename_numerals thy) |
|
317 |
[add_pred, diff_is_0_eq, zero_is_diff_eq, zero_less_diff, |
|
318 |
mult_is_0, zero_is_mult, zero_less_mult_iff, mult_eq_1_iff]; |
|
319 |
||
320 |
Addsimps (basic_renamed_arith_simps @ other_renamed_arith_simps); |
|
7032 | 321 |
|
322 |
AddIffs (map (rename_numerals thy) [add_is_0, zero_is_add, add_gr_0]); |
|
323 |
||
7056
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
324 |
Goal "Suc n = n + #1"; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
325 |
by (asm_simp_tac numeral_ss 1); |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
326 |
qed "Suc_eq_add_numeral_1"; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
327 |
|
7032 | 328 |
(* These two can be useful when m = number_of... *) |
329 |
||
330 |
Goal "(m::nat) + n = (if m=#0 then n else Suc ((m - #1) + n))"; |
|
8442
96023903c2df
case_tac now subsumes both boolean and datatype cases;
wenzelm
parents:
8423
diff
changeset
|
331 |
by (case_tac "m" 1); |
7032 | 332 |
by (ALLGOALS (asm_simp_tac numeral_ss)); |
333 |
qed "add_eq_if"; |
|
334 |
||
335 |
Goal "(m::nat) * n = (if m=#0 then #0 else n + ((m - #1) * n))"; |
|
8442
96023903c2df
case_tac now subsumes both boolean and datatype cases;
wenzelm
parents:
8423
diff
changeset
|
336 |
by (case_tac "m" 1); |
7032 | 337 |
by (ALLGOALS (asm_simp_tac numeral_ss)); |
338 |
qed "mult_eq_if"; |
|
339 |
||
7056
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
340 |
Goal "(p ^ m :: nat) = (if m=#0 then #1 else p * (p ^ (m - #1)))"; |
8442
96023903c2df
case_tac now subsumes both boolean and datatype cases;
wenzelm
parents:
8423
diff
changeset
|
341 |
by (case_tac "m" 1); |
7056
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
342 |
by (ALLGOALS (asm_simp_tac numeral_ss)); |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
343 |
qed "power_eq_if"; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
344 |
|
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
345 |
Goal "[| #0<n; #0<m |] ==> m - n < (m::nat)"; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
346 |
by (asm_full_simp_tac (numeral_ss addsimps [diff_less]) 1); |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
347 |
qed "diff_less'"; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
348 |
|
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
349 |
Addsimps [inst "n" "number_of ?v" diff_less']; |
522a7013d7df
more existing theorems renamed to use #0; also new results
paulson
parents:
7032
diff
changeset
|
350 |
|
7032 | 351 |
(*various theorems that aren't in the default simpset*) |
352 |
val add_is_one' = rename_numerals thy add_is_1; |
|
353 |
val one_is_add' = rename_numerals thy one_is_add; |
|
354 |
val zero_induct' = rename_numerals thy zero_induct; |
|
355 |
val diff_self_eq_0' = rename_numerals thy diff_self_eq_0; |
|
356 |
val mult_eq_self_implies_10' = rename_numerals thy mult_eq_self_implies_10; |
|
357 |
val le_pred_eq' = rename_numerals thy le_pred_eq; |
|
358 |
val less_pred_eq' = rename_numerals thy less_pred_eq; |
|
359 |
||
360 |
(** Divides **) |
|
361 |
||
8776 | 362 |
Addsimps (map (rename_numerals thy) [mod_1, mod_0, div_1, div_0]); |
7032 | 363 |
|
364 |
AddIffs (map (rename_numerals thy) |
|
365 |
[dvd_1_left, dvd_0_right]); |
|
366 |
||
367 |
(*useful?*) |
|
368 |
val mod_self' = rename_numerals thy mod_self; |
|
369 |
val div_self' = rename_numerals thy div_self; |
|
370 |
val div_less' = rename_numerals thy div_less; |
|
371 |
val mod_mult_self_is_zero' = rename_numerals thy mod_mult_self_is_0; |
|
372 |
||
373 |
(** Power **) |
|
374 |
||
375 |
Goal "(p::nat) ^ #0 = #1"; |
|
376 |
by (simp_tac numeral_ss 1); |
|
377 |
qed "power_zero"; |
|
8792 | 378 |
|
379 |
Goal "(p::nat) ^ #1 = p"; |
|
380 |
by (simp_tac numeral_ss 1); |
|
381 |
qed "power_one"; |
|
382 |
Addsimps [power_zero, power_one]; |
|
383 |
||
384 |
Goal "(p::nat) ^ #2 = p*p"; |
|
385 |
by (simp_tac numeral_ss 1); |
|
386 |
qed "power_two"; |
|
7032 | 387 |
|
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
388 |
Goal "#0 < (i::nat) ==> #0 < i^n"; |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
389 |
by (asm_simp_tac numeral_ss 1); |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
390 |
qed "zero_less_power'"; |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
391 |
Addsimps [zero_less_power']; |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
392 |
|
7032 | 393 |
val binomial_zero = rename_numerals thy binomial_0; |
394 |
val binomial_Suc' = rename_numerals thy binomial_Suc; |
|
395 |
val binomial_n_n' = rename_numerals thy binomial_n_n; |
|
396 |
||
397 |
(*binomial_0_Suc doesn't work well on numerals*) |
|
398 |
Addsimps (map (rename_numerals thy) |
|
399 |
[binomial_n_0, binomial_zero, binomial_1]); |
|
400 |
||
8792 | 401 |
Addsimps [rename_numerals thy card_Pow]; |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
402 |
|
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
403 |
(*** Comparisons involving (0::nat) ***) |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
404 |
|
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
405 |
Goal "(number_of v = (0::nat)) = \ |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
406 |
\ (if neg (number_of v) then True else iszero (number_of v))"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
407 |
by (simp_tac (simpset() addsimps [numeral_0_eq_0 RS sym]) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
408 |
qed "eq_number_of_0"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
409 |
|
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
410 |
Goal "((0::nat) = number_of v) = \ |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
411 |
\ (if neg (number_of v) then True else iszero (number_of v))"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
412 |
by (rtac ([eq_sym_conv, eq_number_of_0] MRS trans) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
413 |
qed "eq_0_number_of"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
414 |
|
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
415 |
Goal "((0::nat) < number_of v) = neg (number_of (bin_minus v))"; |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
416 |
by (simp_tac (simpset() addsimps [numeral_0_eq_0 RS sym]) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
417 |
qed "less_0_number_of"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
418 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
419 |
(*Simplification already handles n<0, n<=0 and 0<=n.*) |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
420 |
Addsimps [eq_number_of_0, eq_0_number_of, less_0_number_of]; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
421 |
|
8935
548901d05a0e
added type constraint ::nat because 0 is now overloaded
paulson
parents:
8864
diff
changeset
|
422 |
Goal "neg (number_of v) ==> number_of v = (0::nat)"; |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
423 |
by (asm_simp_tac (simpset() addsimps [numeral_0_eq_0 RS sym]) 1); |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
424 |
qed "neg_imp_number_of_eq_0"; |
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
425 |
|
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
426 |
|
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
427 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
428 |
(*** Comparisons involving Suc ***) |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
429 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
430 |
Goal "(number_of v = Suc n) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
431 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
432 |
\ if neg pv then False else nat pv = n)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
433 |
by (simp_tac |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
434 |
(simpset_of Int.thy addsimps |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
435 |
[Let_def, neg_eq_less_0, linorder_not_less, number_of_pred, |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
436 |
nat_number_of_def, zadd_0] @ zadd_ac) 1); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
437 |
by (res_inst_tac [("x", "number_of v")] spec 1); |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
438 |
by (auto_tac (claset(), simpset() addsimps [nat_eq_iff])); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
439 |
qed "eq_number_of_Suc"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
440 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
441 |
Goal "(Suc n = number_of v) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
442 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
443 |
\ if neg pv then False else nat pv = n)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
444 |
by (rtac ([eq_sym_conv, eq_number_of_Suc] MRS trans) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
445 |
qed "Suc_eq_number_of"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
446 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
447 |
Goal "(number_of v < Suc n) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
448 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
449 |
\ if neg pv then True else nat pv < n)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
450 |
by (simp_tac |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
451 |
(simpset_of Int.thy addsimps |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
452 |
[Let_def, neg_eq_less_0, linorder_not_less, number_of_pred, |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
453 |
nat_number_of_def, zadd_0] @ zadd_ac) 1); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
454 |
by (res_inst_tac [("x", "number_of v")] spec 1); |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
455 |
by (auto_tac (claset(), simpset() addsimps [nat_less_iff])); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
456 |
qed "less_number_of_Suc"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
457 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
458 |
Goal "(Suc n < number_of v) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
459 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
460 |
\ if neg pv then False else n < nat pv)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
461 |
by (simp_tac |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
462 |
(simpset_of Int.thy addsimps |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
463 |
[Let_def, neg_eq_less_0, linorder_not_less, number_of_pred, |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
464 |
nat_number_of_def, zadd_0] @ zadd_ac) 1); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
465 |
by (res_inst_tac [("x", "number_of v")] spec 1); |
8864
a12ccd629e2c
tidying, especially to remove zcompare_rls from proofs
paulson
parents:
8798
diff
changeset
|
466 |
by (auto_tac (claset(), simpset() addsimps [zless_nat_eq_int_zless])); |
7519
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
467 |
qed "less_Suc_number_of"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
468 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
469 |
Goal "(number_of v <= Suc n) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
470 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
471 |
\ if neg pv then True else nat pv <= n)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
472 |
by (simp_tac |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
473 |
(simpset_of Int.thy addsimps |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
474 |
[Let_def, less_Suc_number_of, linorder_not_less RS sym]) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
475 |
qed "le_number_of_Suc"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
476 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
477 |
Goal "(Suc n <= number_of v) = \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
478 |
\ (let pv = number_of (bin_pred v) in \ |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
479 |
\ if neg pv then False else n <= nat pv)"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
480 |
by (simp_tac |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
481 |
(simpset_of Int.thy addsimps |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
482 |
[Let_def, less_number_of_Suc, linorder_not_less RS sym]) 1); |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
483 |
qed "le_Suc_number_of"; |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
484 |
|
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
485 |
Addsimps [eq_number_of_Suc, Suc_eq_number_of, |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
486 |
less_number_of_Suc, less_Suc_number_of, |
8e4a21d1ba4f
simplification of relations involving 0, Suc and natural-number numerals
paulson
parents:
7127
diff
changeset
|
487 |
le_number_of_Suc, le_Suc_number_of]; |
8116 | 488 |
|
8257 | 489 |
(* Push int(.) inwards: *) |
8116 | 490 |
Addsimps [int_Suc,zadd_int RS sym]; |
8798 | 491 |
|
492 |
Goal "(m+m = n+n) = (m = (n::int))"; |
|
493 |
by Auto_tac; |
|
494 |
val lemma1 = result(); |
|
495 |
||
496 |
Goal "m+m ~= int 1 + n + n"; |
|
497 |
by Auto_tac; |
|
498 |
by (dres_inst_tac [("f", "%x. x mod #2")] arg_cong 1); |
|
499 |
by (full_simp_tac (simpset() addsimps [zmod_zadd1_eq]) 1); |
|
500 |
val lemma2 = result(); |
|
501 |
||
502 |
Goal "((number_of (v BIT x) ::int) = number_of (w BIT y)) = \ |
|
503 |
\ (x=y & (((number_of v) ::int) = number_of w))"; |
|
504 |
by (simp_tac (simpset_of Int.thy addsimps |
|
505 |
[number_of_BIT, lemma1, lemma2, eq_commute]) 1); |
|
506 |
qed "eq_number_of_BIT_BIT"; |
|
507 |
||
508 |
Goal "((number_of (v BIT x) ::int) = number_of Pls) = \ |
|
509 |
\ (x=False & (((number_of v) ::int) = number_of Pls))"; |
|
510 |
by (simp_tac (simpset_of Int.thy addsimps |
|
511 |
[number_of_BIT, number_of_Pls, eq_commute]) 1); |
|
512 |
by (res_inst_tac [("x", "number_of v")] spec 1); |
|
513 |
by Safe_tac; |
|
514 |
by (ALLGOALS Full_simp_tac); |
|
515 |
by (dres_inst_tac [("f", "%x. x mod #2")] arg_cong 1); |
|
516 |
by (full_simp_tac (simpset() addsimps [zmod_zadd1_eq]) 1); |
|
517 |
qed "eq_number_of_BIT_Pls"; |
|
518 |
||
519 |
Goal "((number_of (v BIT x) ::int) = number_of Min) = \ |
|
520 |
\ (x=True & (((number_of v) ::int) = number_of Min))"; |
|
521 |
by (simp_tac (simpset_of Int.thy addsimps |
|
522 |
[number_of_BIT, number_of_Min, eq_commute]) 1); |
|
523 |
by (res_inst_tac [("x", "number_of v")] spec 1); |
|
524 |
by Auto_tac; |
|
525 |
by (dres_inst_tac [("f", "%x. x mod #2")] arg_cong 1); |
|
526 |
by Auto_tac; |
|
527 |
qed "eq_number_of_BIT_Min"; |
|
528 |
||
529 |
Goal "(number_of Pls ::int) ~= number_of Min"; |
|
530 |
by Auto_tac; |
|
531 |
qed "eq_number_of_Pls_Min"; |