paulson@14259
|
1 |
(* Title: HOL/Integ/IntArith.thy
|
paulson@14259
|
2 |
ID: $Id$
|
paulson@14259
|
3 |
Authors: Larry Paulson and Tobias Nipkow
|
paulson@14259
|
4 |
*)
|
wenzelm@12023
|
5 |
|
wenzelm@12023
|
6 |
header {* Integer arithmetic *}
|
wenzelm@12023
|
7 |
|
wenzelm@9436
|
8 |
theory IntArith = Bin
|
paulson@14259
|
9 |
files ("int_arith1.ML"):
|
wenzelm@9436
|
10 |
|
paulson@14353
|
11 |
|
paulson@14272
|
12 |
subsection{*Inequality Reasoning for the Arithmetic Simproc*}
|
paulson@14272
|
13 |
|
paulson@14272
|
14 |
lemma zless_imp_add1_zle: "w<z ==> w + (1::int) \<le> z"
|
paulson@14378
|
15 |
apply (rule eq_Abs_Integ [of z])
|
paulson@14378
|
16 |
apply (rule eq_Abs_Integ [of w])
|
paulson@14378
|
17 |
apply (simp add: linorder_not_le [symmetric] zle int_def zadd One_int_def)
|
paulson@14378
|
18 |
done
|
paulson@14378
|
19 |
|
paulson@14272
|
20 |
|
wenzelm@12023
|
21 |
use "int_arith1.ML"
|
wenzelm@12023
|
22 |
setup int_arith_setup
|
paulson@14259
|
23 |
|
paulson@14353
|
24 |
|
paulson@14272
|
25 |
subsection{*More inequality reasoning*}
|
paulson@14272
|
26 |
|
paulson@14272
|
27 |
lemma zless_add1_eq: "(w < z + (1::int)) = (w<z | w=z)"
|
paulson@14259
|
28 |
by arith
|
paulson@14259
|
29 |
|
paulson@14272
|
30 |
lemma add1_zle_eq: "(w + (1::int) \<le> z) = (w<z)"
|
paulson@14272
|
31 |
by arith
|
paulson@14272
|
32 |
|
paulson@14272
|
33 |
lemma zle_diff1_eq [simp]: "(w \<le> z - (1::int)) = (w<(z::int))"
|
paulson@14272
|
34 |
by arith
|
paulson@14272
|
35 |
|
paulson@14272
|
36 |
lemma zle_add1_eq_le [simp]: "(w < z + 1) = (w\<le>(z::int))"
|
paulson@14259
|
37 |
by arith
|
paulson@14259
|
38 |
|
paulson@14259
|
39 |
lemma zadd_left_cancel0 [simp]: "(z = z + w) = (w = (0::int))"
|
paulson@14259
|
40 |
by arith
|
paulson@14259
|
41 |
|
paulson@14365
|
42 |
lemma int_one_le_iff_zero_less: "((1::int) \<le> z) = (0 < z)"
|
paulson@14365
|
43 |
by arith
|
paulson@14365
|
44 |
|
paulson@14353
|
45 |
|
paulson@14353
|
46 |
subsection{*The Functions @{term nat} and @{term int}*}
|
paulson@14259
|
47 |
|
paulson@14272
|
48 |
lemma nonneg_eq_int: "[| 0 \<le> z; !!m. z = int m ==> P |] ==> P"
|
paulson@14259
|
49 |
by (blast dest: nat_0_le sym)
|
paulson@14259
|
50 |
|
paulson@14272
|
51 |
lemma nat_eq_iff: "(nat w = m) = (if 0 \<le> w then w = int m else m=0)"
|
paulson@14259
|
52 |
by auto
|
paulson@14259
|
53 |
|
paulson@14272
|
54 |
lemma nat_eq_iff2: "(m = nat w) = (if 0 \<le> w then w = int m else m=0)"
|
paulson@14259
|
55 |
by auto
|
paulson@14259
|
56 |
|
paulson@14272
|
57 |
lemma nat_less_iff: "0 \<le> w ==> (nat w < m) = (w < int m)"
|
paulson@14259
|
58 |
apply (rule iffI)
|
paulson@14259
|
59 |
apply (erule nat_0_le [THEN subst])
|
paulson@14259
|
60 |
apply (simp_all del: zless_int add: zless_int [symmetric])
|
paulson@14259
|
61 |
done
|
paulson@14259
|
62 |
|
paulson@14272
|
63 |
lemma int_eq_iff: "(int m = z) = (m = nat z & 0 \<le> z)"
|
paulson@14259
|
64 |
by (auto simp add: nat_eq_iff2)
|
paulson@14259
|
65 |
|
paulson@14259
|
66 |
|
paulson@14353
|
67 |
text{*Simplify the terms @{term "int 0"}, @{term "int(Suc 0)"} and
|
paulson@14353
|
68 |
@{term "w + - z"}*}
|
paulson@14259
|
69 |
declare Zero_int_def [symmetric, simp]
|
paulson@14259
|
70 |
declare One_int_def [symmetric, simp]
|
paulson@14259
|
71 |
|
paulson@14259
|
72 |
text{*cooper.ML refers to this theorem*}
|
paulson@14259
|
73 |
lemmas zdiff_def_symmetric = zdiff_def [symmetric, simp]
|
paulson@14259
|
74 |
|
paulson@14259
|
75 |
lemma nat_0: "nat 0 = 0"
|
paulson@14259
|
76 |
by (simp add: nat_eq_iff)
|
paulson@14259
|
77 |
|
paulson@14259
|
78 |
lemma nat_1: "nat 1 = Suc 0"
|
paulson@14259
|
79 |
by (subst nat_eq_iff, simp)
|
paulson@14259
|
80 |
|
paulson@14259
|
81 |
lemma nat_2: "nat 2 = Suc (Suc 0)"
|
paulson@14259
|
82 |
by (subst nat_eq_iff, simp)
|
paulson@14259
|
83 |
|
paulson@14272
|
84 |
lemma nat_less_eq_zless: "0 \<le> w ==> (nat w < nat z) = (w<z)"
|
paulson@14378
|
85 |
apply (case_tac "z < 0")
|
paulson@14259
|
86 |
apply (auto simp add: nat_less_iff)
|
paulson@14259
|
87 |
done
|
paulson@14259
|
88 |
|
paulson@14378
|
89 |
|
paulson@14272
|
90 |
lemma nat_le_eq_zle: "0 < w | 0 \<le> z ==> (nat w \<le> nat z) = (w\<le>z)"
|
paulson@14259
|
91 |
by (auto simp add: linorder_not_less [symmetric] zless_nat_conj)
|
paulson@14259
|
92 |
|
paulson@14259
|
93 |
|
paulson@14259
|
94 |
text{*This simplifies expressions of the form @{term "int n = z"} where
|
paulson@14259
|
95 |
z is an integer literal.*}
|
paulson@14259
|
96 |
declare int_eq_iff [of _ "number_of v", standard, simp]
|
paulson@13837
|
97 |
|
paulson@13849
|
98 |
lemma int_nat_eq [simp]: "int (nat z) = (if 0 \<le> z then z else 0)"
|
paulson@13849
|
99 |
by simp
|
paulson@13849
|
100 |
|
paulson@14295
|
101 |
lemma split_nat [arith_split]:
|
paulson@14259
|
102 |
"P(nat(i::int)) = ((\<forall>n. i = int n \<longrightarrow> P n) & (i < 0 \<longrightarrow> P 0))"
|
nipkow@13575
|
103 |
(is "?P = (?L & ?R)")
|
nipkow@13575
|
104 |
proof (cases "i < 0")
|
nipkow@13575
|
105 |
case True thus ?thesis by simp
|
nipkow@13575
|
106 |
next
|
nipkow@13575
|
107 |
case False
|
nipkow@13575
|
108 |
have "?P = ?L"
|
nipkow@13575
|
109 |
proof
|
nipkow@13575
|
110 |
assume ?P thus ?L using False by clarsimp
|
nipkow@13575
|
111 |
next
|
nipkow@13575
|
112 |
assume ?L thus ?P using False by simp
|
nipkow@13575
|
113 |
qed
|
nipkow@13575
|
114 |
with False show ?thesis by simp
|
nipkow@13575
|
115 |
qed
|
nipkow@13575
|
116 |
|
nipkow@13685
|
117 |
subsubsection "Induction principles for int"
|
nipkow@13685
|
118 |
|
nipkow@13685
|
119 |
(* `set:int': dummy construction *)
|
nipkow@13685
|
120 |
theorem int_ge_induct[case_names base step,induct set:int]:
|
nipkow@13685
|
121 |
assumes ge: "k \<le> (i::int)" and
|
nipkow@13685
|
122 |
base: "P(k)" and
|
nipkow@13685
|
123 |
step: "\<And>i. \<lbrakk>k \<le> i; P i\<rbrakk> \<Longrightarrow> P(i+1)"
|
nipkow@13685
|
124 |
shows "P i"
|
nipkow@13685
|
125 |
proof -
|
paulson@14272
|
126 |
{ fix n have "\<And>i::int. n = nat(i-k) \<Longrightarrow> k \<le> i \<Longrightarrow> P i"
|
nipkow@13685
|
127 |
proof (induct n)
|
nipkow@13685
|
128 |
case 0
|
nipkow@13685
|
129 |
hence "i = k" by arith
|
nipkow@13685
|
130 |
thus "P i" using base by simp
|
nipkow@13685
|
131 |
next
|
nipkow@13685
|
132 |
case (Suc n)
|
nipkow@13685
|
133 |
hence "n = nat((i - 1) - k)" by arith
|
nipkow@13685
|
134 |
moreover
|
nipkow@13685
|
135 |
have ki1: "k \<le> i - 1" using Suc.prems by arith
|
nipkow@13685
|
136 |
ultimately
|
nipkow@13685
|
137 |
have "P(i - 1)" by(rule Suc.hyps)
|
nipkow@13685
|
138 |
from step[OF ki1 this] show ?case by simp
|
nipkow@13685
|
139 |
qed
|
nipkow@13685
|
140 |
}
|
nipkow@13685
|
141 |
from this ge show ?thesis by fast
|
nipkow@13685
|
142 |
qed
|
nipkow@13685
|
143 |
|
nipkow@13685
|
144 |
(* `set:int': dummy construction *)
|
nipkow@13685
|
145 |
theorem int_gr_induct[case_names base step,induct set:int]:
|
nipkow@13685
|
146 |
assumes gr: "k < (i::int)" and
|
nipkow@13685
|
147 |
base: "P(k+1)" and
|
nipkow@13685
|
148 |
step: "\<And>i. \<lbrakk>k < i; P i\<rbrakk> \<Longrightarrow> P(i+1)"
|
nipkow@13685
|
149 |
shows "P i"
|
nipkow@13685
|
150 |
apply(rule int_ge_induct[of "k + 1"])
|
nipkow@13685
|
151 |
using gr apply arith
|
nipkow@13685
|
152 |
apply(rule base)
|
paulson@14259
|
153 |
apply (rule step, simp+)
|
nipkow@13685
|
154 |
done
|
nipkow@13685
|
155 |
|
nipkow@13685
|
156 |
theorem int_le_induct[consumes 1,case_names base step]:
|
nipkow@13685
|
157 |
assumes le: "i \<le> (k::int)" and
|
nipkow@13685
|
158 |
base: "P(k)" and
|
nipkow@13685
|
159 |
step: "\<And>i. \<lbrakk>i \<le> k; P i\<rbrakk> \<Longrightarrow> P(i - 1)"
|
nipkow@13685
|
160 |
shows "P i"
|
nipkow@13685
|
161 |
proof -
|
paulson@14272
|
162 |
{ fix n have "\<And>i::int. n = nat(k-i) \<Longrightarrow> i \<le> k \<Longrightarrow> P i"
|
nipkow@13685
|
163 |
proof (induct n)
|
nipkow@13685
|
164 |
case 0
|
nipkow@13685
|
165 |
hence "i = k" by arith
|
nipkow@13685
|
166 |
thus "P i" using base by simp
|
nipkow@13685
|
167 |
next
|
nipkow@13685
|
168 |
case (Suc n)
|
nipkow@13685
|
169 |
hence "n = nat(k - (i+1))" by arith
|
nipkow@13685
|
170 |
moreover
|
nipkow@13685
|
171 |
have ki1: "i + 1 \<le> k" using Suc.prems by arith
|
nipkow@13685
|
172 |
ultimately
|
nipkow@13685
|
173 |
have "P(i+1)" by(rule Suc.hyps)
|
nipkow@13685
|
174 |
from step[OF ki1 this] show ?case by simp
|
nipkow@13685
|
175 |
qed
|
nipkow@13685
|
176 |
}
|
nipkow@13685
|
177 |
from this le show ?thesis by fast
|
nipkow@13685
|
178 |
qed
|
nipkow@13685
|
179 |
|
nipkow@13685
|
180 |
theorem int_less_induct[consumes 1,case_names base step]:
|
nipkow@13685
|
181 |
assumes less: "(i::int) < k" and
|
nipkow@13685
|
182 |
base: "P(k - 1)" and
|
nipkow@13685
|
183 |
step: "\<And>i. \<lbrakk>i < k; P i\<rbrakk> \<Longrightarrow> P(i - 1)"
|
nipkow@13685
|
184 |
shows "P i"
|
nipkow@13685
|
185 |
apply(rule int_le_induct[of _ "k - 1"])
|
nipkow@13685
|
186 |
using less apply arith
|
nipkow@13685
|
187 |
apply(rule base)
|
paulson@14259
|
188 |
apply (rule step, simp+)
|
nipkow@13685
|
189 |
done
|
nipkow@13685
|
190 |
|
paulson@14259
|
191 |
subsection{*Intermediate value theorems*}
|
paulson@14259
|
192 |
|
paulson@14259
|
193 |
lemma int_val_lemma:
|
paulson@14259
|
194 |
"(\<forall>i<n::nat. abs(f(i+1) - f i) \<le> 1) -->
|
paulson@14259
|
195 |
f 0 \<le> k --> k \<le> f n --> (\<exists>i \<le> n. f i = (k::int))"
|
paulson@14271
|
196 |
apply (induct_tac "n", simp)
|
paulson@14259
|
197 |
apply (intro strip)
|
paulson@14259
|
198 |
apply (erule impE, simp)
|
paulson@14259
|
199 |
apply (erule_tac x = n in allE, simp)
|
paulson@14259
|
200 |
apply (case_tac "k = f (n+1) ")
|
paulson@14259
|
201 |
apply force
|
paulson@14259
|
202 |
apply (erule impE)
|
paulson@14259
|
203 |
apply (simp add: zabs_def split add: split_if_asm)
|
paulson@14259
|
204 |
apply (blast intro: le_SucI)
|
paulson@14259
|
205 |
done
|
paulson@14259
|
206 |
|
paulson@14259
|
207 |
lemmas nat0_intermed_int_val = int_val_lemma [rule_format (no_asm)]
|
paulson@14259
|
208 |
|
paulson@14259
|
209 |
lemma nat_intermed_int_val:
|
paulson@14259
|
210 |
"[| \<forall>i. m \<le> i & i < n --> abs(f(i + 1::nat) - f i) \<le> 1; m < n;
|
paulson@14259
|
211 |
f m \<le> k; k \<le> f n |] ==> ? i. m \<le> i & i \<le> n & f i = (k::int)"
|
paulson@14259
|
212 |
apply (cut_tac n = "n-m" and f = "%i. f (i+m) " and k = k
|
paulson@14259
|
213 |
in int_val_lemma)
|
paulson@14259
|
214 |
apply simp
|
paulson@14259
|
215 |
apply (erule impE)
|
paulson@14259
|
216 |
apply (intro strip)
|
paulson@14259
|
217 |
apply (erule_tac x = "i+m" in allE, arith)
|
paulson@14259
|
218 |
apply (erule exE)
|
paulson@14259
|
219 |
apply (rule_tac x = "i+m" in exI, arith)
|
paulson@14259
|
220 |
done
|
paulson@14259
|
221 |
|
paulson@14259
|
222 |
|
paulson@14259
|
223 |
subsection{*Products and 1, by T. M. Rasmussen*}
|
paulson@14259
|
224 |
|
paulson@14259
|
225 |
lemma zmult_eq_self_iff: "(m = m*(n::int)) = (n = 1 | m = 0)"
|
paulson@14259
|
226 |
apply auto
|
paulson@14259
|
227 |
apply (subgoal_tac "m*1 = m*n")
|
paulson@14378
|
228 |
apply (drule mult_cancel_left [THEN iffD1], auto)
|
paulson@14259
|
229 |
done
|
paulson@14259
|
230 |
|
paulson@14259
|
231 |
lemma zless_1_zmult: "[| 1 < m; 1 < n |] ==> 1 < m*(n::int)"
|
paulson@14259
|
232 |
apply (rule_tac y = "1*n" in order_less_trans)
|
paulson@14378
|
233 |
apply (rule_tac [2] mult_strict_right_mono)
|
paulson@14259
|
234 |
apply (simp_all (no_asm_simp))
|
paulson@14259
|
235 |
done
|
paulson@14259
|
236 |
|
paulson@14259
|
237 |
lemma pos_zmult_eq_1_iff: "0 < (m::int) ==> (m * n = 1) = (m = 1 & n = 1)"
|
paulson@14259
|
238 |
apply auto
|
paulson@14259
|
239 |
apply (case_tac "m=1")
|
paulson@14259
|
240 |
apply (case_tac [2] "n=1")
|
paulson@14259
|
241 |
apply (case_tac [4] "m=1")
|
paulson@14259
|
242 |
apply (case_tac [5] "n=1", auto)
|
paulson@14259
|
243 |
apply (tactic"distinct_subgoals_tac")
|
paulson@14259
|
244 |
apply (subgoal_tac "1<m*n", simp)
|
paulson@14259
|
245 |
apply (rule zless_1_zmult, arith)
|
paulson@14259
|
246 |
apply (subgoal_tac "0<n", arith)
|
paulson@14259
|
247 |
apply (subgoal_tac "0<m*n")
|
paulson@14353
|
248 |
apply (drule zero_less_mult_iff [THEN iffD1], auto)
|
paulson@14259
|
249 |
done
|
paulson@14259
|
250 |
|
paulson@14259
|
251 |
lemma zmult_eq_1_iff: "(m*n = (1::int)) = ((m = 1 & n = 1) | (m = -1 & n = -1))"
|
paulson@14259
|
252 |
apply (case_tac "0<m")
|
paulson@14271
|
253 |
apply (simp add: pos_zmult_eq_1_iff)
|
paulson@14259
|
254 |
apply (case_tac "m=0")
|
paulson@14271
|
255 |
apply (simp del: number_of_reorient)
|
paulson@14259
|
256 |
apply (subgoal_tac "0 < -m")
|
paulson@14259
|
257 |
apply (drule_tac n = "-n" in pos_zmult_eq_1_iff, auto)
|
paulson@14259
|
258 |
done
|
paulson@14259
|
259 |
|
paulson@14259
|
260 |
|
paulson@14259
|
261 |
subsection{*More about nat*}
|
paulson@14259
|
262 |
|
paulson@14271
|
263 |
(*Analogous to zadd_int*)
|
paulson@14271
|
264 |
lemma zdiff_int: "n \<le> m ==> int m - int n = int (m-n)"
|
paulson@14271
|
265 |
by (induct m n rule: diff_induct, simp_all)
|
paulson@14271
|
266 |
|
paulson@14259
|
267 |
lemma nat_add_distrib:
|
paulson@14259
|
268 |
"[| (0::int) \<le> z; 0 \<le> z' |] ==> nat (z+z') = nat z + nat z'"
|
paulson@14259
|
269 |
apply (rule inj_int [THEN injD])
|
paulson@14271
|
270 |
apply (simp add: zadd_int [symmetric])
|
paulson@14259
|
271 |
done
|
paulson@14259
|
272 |
|
paulson@14259
|
273 |
lemma nat_diff_distrib:
|
paulson@14259
|
274 |
"[| (0::int) \<le> z'; z' \<le> z |] ==> nat (z-z') = nat z - nat z'"
|
paulson@14259
|
275 |
apply (rule inj_int [THEN injD])
|
paulson@14271
|
276 |
apply (simp add: zdiff_int [symmetric] nat_le_eq_zle)
|
paulson@14259
|
277 |
done
|
paulson@14259
|
278 |
|
paulson@14259
|
279 |
lemma nat_mult_distrib: "(0::int) \<le> z ==> nat (z*z') = nat z * nat z'"
|
paulson@14259
|
280 |
apply (case_tac "0 \<le> z'")
|
paulson@14259
|
281 |
apply (rule inj_int [THEN injD])
|
paulson@14353
|
282 |
apply (simp add: zmult_int [symmetric] zero_le_mult_iff)
|
paulson@14353
|
283 |
apply (simp add: mult_le_0_iff)
|
paulson@14259
|
284 |
done
|
paulson@14259
|
285 |
|
paulson@14259
|
286 |
lemma nat_mult_distrib_neg: "z \<le> (0::int) ==> nat(z*z') = nat(-z) * nat(-z')"
|
paulson@14259
|
287 |
apply (rule trans)
|
paulson@14259
|
288 |
apply (rule_tac [2] nat_mult_distrib, auto)
|
paulson@14259
|
289 |
done
|
paulson@14259
|
290 |
|
paulson@14259
|
291 |
lemma nat_abs_mult_distrib: "nat (abs (w * z)) = nat (abs w) * nat (abs z)"
|
paulson@14259
|
292 |
apply (case_tac "z=0 | w=0")
|
paulson@14259
|
293 |
apply (auto simp add: zabs_def nat_mult_distrib [symmetric]
|
paulson@14353
|
294 |
nat_mult_distrib_neg [symmetric] mult_less_0_iff)
|
paulson@14259
|
295 |
done
|
paulson@14259
|
296 |
|
paulson@14353
|
297 |
|
paulson@14259
|
298 |
ML
|
paulson@14259
|
299 |
{*
|
paulson@14259
|
300 |
val zle_diff1_eq = thm "zle_diff1_eq";
|
paulson@14259
|
301 |
val zle_add1_eq_le = thm "zle_add1_eq_le";
|
paulson@14259
|
302 |
val nonneg_eq_int = thm "nonneg_eq_int";
|
paulson@14259
|
303 |
val nat_eq_iff = thm "nat_eq_iff";
|
paulson@14259
|
304 |
val nat_eq_iff2 = thm "nat_eq_iff2";
|
paulson@14259
|
305 |
val nat_less_iff = thm "nat_less_iff";
|
paulson@14259
|
306 |
val int_eq_iff = thm "int_eq_iff";
|
paulson@14259
|
307 |
val nat_0 = thm "nat_0";
|
paulson@14259
|
308 |
val nat_1 = thm "nat_1";
|
paulson@14259
|
309 |
val nat_2 = thm "nat_2";
|
paulson@14259
|
310 |
val nat_less_eq_zless = thm "nat_less_eq_zless";
|
paulson@14259
|
311 |
val nat_le_eq_zle = thm "nat_le_eq_zle";
|
paulson@14259
|
312 |
|
paulson@14259
|
313 |
val nat_intermed_int_val = thm "nat_intermed_int_val";
|
paulson@14259
|
314 |
val zmult_eq_self_iff = thm "zmult_eq_self_iff";
|
paulson@14259
|
315 |
val zless_1_zmult = thm "zless_1_zmult";
|
paulson@14259
|
316 |
val pos_zmult_eq_1_iff = thm "pos_zmult_eq_1_iff";
|
paulson@14259
|
317 |
val zmult_eq_1_iff = thm "zmult_eq_1_iff";
|
paulson@14259
|
318 |
val nat_add_distrib = thm "nat_add_distrib";
|
paulson@14259
|
319 |
val nat_diff_distrib = thm "nat_diff_distrib";
|
paulson@14259
|
320 |
val nat_mult_distrib = thm "nat_mult_distrib";
|
paulson@14259
|
321 |
val nat_mult_distrib_neg = thm "nat_mult_distrib_neg";
|
paulson@14259
|
322 |
val nat_abs_mult_distrib = thm "nat_abs_mult_distrib";
|
paulson@14259
|
323 |
*}
|
paulson@14259
|
324 |
|
wenzelm@7707
|
325 |
end
|