Debian Codegraph @

Formal_ineqs/arith/num_exp_theory.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Exponential representation of natural numbers *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/arith/arith_nat.hl";;
15
16 module Num_exp_theory = struct
17
18 let base_const = mk_small_numeral Arith_num.arith_base;;
19
20 (* num_exp definition *)
21 let num_exp_tm = mk_eq (`(num_exp:num->num->num) n e`,
22 mk_binop `( * ):num->num->num` `n:num` (mk_binop `EXP` base_const `e:num`));;
23 (* let num_exp = new_definition `num_exp n e = n * 2 EXP e`;; *)
24 let num_exp = new_definition num_exp_tm;;
25
26 (**********************************)
27 (* Theorems *)
28
29 let NUM_EXP_EXP = prove(`!n e1 e2. num_exp (num_exp n e1) e2 = num_exp n (e1 + e2)`,
30 REPEAT GEN_TAC THEN
31 REWRITE_TAC[num_exp; EXP_ADD] THEN
32 ARITH_TAC);;
33
34 let NUM_EXP_SUM = prove(`!n e1 e2. num_exp n (e1 + e2) = num_exp n e1 * num_exp 1 e2`,
35 REPEAT GEN_TAC THEN
36 REWRITE_TAC[num_exp; EXP_ADD] THEN
37 ARITH_TAC);;
38
39 let NUM_EXP_SUM1 = prove(`!n e1 e2. num_exp n (e1 + e2) = num_exp 1 e1 * num_exp n e2`,
40 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp; EXP_ADD] THEN ARITH_TAC);;
41
42 let NUM_EXP_0 = prove(`!n. n = num_exp n 0`,
43 GEN_TAC THEN REWRITE_TAC[num_exp; EXP; MULT_CLAUSES]);;
44
45 let NUM_EXP_LE = prove(`!m n e. m <= n ==> num_exp m e <= num_exp n e`,
46 SIMP_TAC[num_exp; LE_MULT_RCANCEL]);;
47
48 let NUM_EXP_LT = prove(`!m n e. m < n ==> num_exp m e < num_exp n e`,
49 SIMP_TAC[num_exp; LT_MULT_RCANCEL; EXP_EQ_0] THEN
50 ARITH_TAC);;
51
52 let NUM_EXP_EQ_0 = prove(`!n e. num_exp n e = 0 <=> n = 0`,
53 REPEAT STRIP_TAC THEN
54 ASM_REWRITE_TAC[num_exp; MULT_EQ_0; EXP_EQ_0] THEN
55 ARITH_TAC);;
56
57 let NUM_EXP_MUL = prove(`!n1 e1 n2 e2. num_exp n1 e1 * num_exp n2 e2 = num_exp (n1 * n2) (e1 + e2)`,
58 REWRITE_TAC[num_exp; EXP_ADD] THEN ARITH_TAC);;
59
60 let NUM_EXP_ADD = prove(`!n1 e1 n2 e2. e1 <= e2 ==>
61 num_exp n1 e1 + num_exp n2 e2 = num_exp (n1 + num_exp n2 (e2 - e1)) e1`,
62 REPEAT STRIP_TAC THEN
63 REWRITE_TAC[num_exp] THEN
64 REWRITE_TAC[ARITH_RULE `(a + b * c) * d = a * d + b * (c * d):num`] THEN
65 REWRITE_TAC[GSYM EXP_ADD] THEN
66 ASM_SIMP_TAC[ARITH_RULE `e1 <= e2 ==> e2 - e1 + e1 = e2:num`]);;
67
68 let NUM_EXP_SUB2 = prove(`!n1 e1 n2 e2 r. e1 <= e2 /\ e2 - e1 = r ==>
69 num_exp n1 e1 - num_exp n2 e2 = num_exp (n1 - num_exp n2 r) e1`,
70 REPEAT STRIP_TAC THEN
71 POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
72 REWRITE_TAC[num_exp] THEN
73 MP_TAC (ARITH_RULE `e1 <= e2 ==> e2 = (e2 - e1) + e1:num`) THEN
74 ASM_REWRITE_TAC[] THEN
75 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o ONCE_DEPTH_CONV) [th]) THEN
76 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
77 REWRITE_TAC[GSYM RIGHT_SUB_DISTRIB]);;
78
79 let NUM_EXP_SUB1 = prove(`!n1 e1 n2 e2 r. e2 <= e1 /\ e1 - e2 = r ==>
80 num_exp n1 e1 - num_exp n2 e2 = num_exp (num_exp n1 r - n2) e2`,
81 REPEAT STRIP_TAC THEN
82 POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
83 REWRITE_TAC[num_exp] THEN
84 MP_TAC (ARITH_RULE `e2 <= e1 ==> e1 = (e1 - e2) + e2:num`) THEN
85 ASM_REWRITE_TAC[] THEN
86 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o ONCE_DEPTH_CONV) [th]) THEN
87 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
88 REWRITE_TAC[GSYM RIGHT_SUB_DISTRIB]);;
89
90 (* NUM_EXP_LE *)
91
92 let NUM_EXP_LE1 = prove(`!n1 e1 n2 e2 r. e2 <= e1 /\ e1 - e2 = r /\ n2 <= num_exp n1 r
93 ==> num_exp n2 e2 <= num_exp n1 e1`,
94 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
95 STRIP_TAC THEN
96 POP_ASSUM MP_TAC THEN POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN DISCH_TAC THEN
97 MP_TAC (ARITH_RULE `e2 <= e1 ==> e1 = (e1 - e2) + e2:num`) THEN
98 ASM_REWRITE_TAC[] THEN
99 DISCH_THEN(fun th -> ONCE_REWRITE_TAC[th]) THEN
100 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
101 ASM_REWRITE_TAC[LE_MULT_RCANCEL]);;
102
103 let NUM_EXP_LE2 = prove(`!n1 e1 n2 e2 r. e1 <= e2 /\ e2 - e1 = r /\ num_exp n2 r <= n1
104 ==> num_exp n2 e2 <= num_exp n1 e1`,
105 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
106 STRIP_TAC THEN
107 POP_ASSUM MP_TAC THEN POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN DISCH_TAC THEN
108 MP_TAC (ARITH_RULE `e1 <= e2 ==> e2 = (e2 - e1) + e1:num`) THEN
109 ASM_REWRITE_TAC[] THEN
110 DISCH_THEN(fun th -> ONCE_REWRITE_TAC[th]) THEN
111 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
112 ASM_REWRITE_TAC[LE_MULT_RCANCEL]);;
113
114 let NUM_EXP_LE1_EQ = prove(`!n1 e1 n2 e2 r x. e2 <= e1 /\ e1 - e2 = r /\ num_exp n1 r = x ==>
115 (num_exp n1 e1 <= num_exp n2 e2 <=> x <= n2)`,
116 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
117 STRIP_TAC THEN
118 REPLICATE_TAC 2 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
119 MP_TAC (ARITH_RULE `e2 <= e1 ==> e1 = (e1 - e2) + e2:num`) THEN
120 ASM_REWRITE_TAC[] THEN
121 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [th]) THEN
122 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
123 ASM_REWRITE_TAC[LE_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
124
125 let NUM_EXP_LE2_EQ = prove(`!n1 e1 n2 e2 r x. e1 <= e2 /\ e2 - e1 = r /\ num_exp n2 r = x ==>
126 (num_exp n1 e1 <= num_exp n2 e2 <=> n1 <= x)`,
127 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
128 STRIP_TAC THEN
129 REPLICATE_TAC 2 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
130 MP_TAC (ARITH_RULE `e1 <= e2 ==> e2 = (e2 - e1) + e1:num`) THEN
131 ASM_REWRITE_TAC[] THEN
132 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [th]) THEN
133 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
134 ASM_REWRITE_TAC[LE_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
135
136 (* NUM_EXP_LT *)
137
138 let NUM_EXP_LT1 = prove(`!n1 e1 n2 e2 r. e2 <= e1 /\ e1 - e2 = r /\ n2 < num_exp n1 r
139 ==> num_exp n2 e2 < num_exp n1 e1`,
140 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
141 STRIP_TAC THEN
142 POP_ASSUM MP_TAC THEN POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN DISCH_TAC THEN
143 MP_TAC (ARITH_RULE `e2 <= e1 ==> e1 = (e1 - e2) + e2:num`) THEN
144 ASM_REWRITE_TAC[] THEN
145 DISCH_THEN (fun th -> ONCE_REWRITE_TAC[th]) THEN
146 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
147 ASM_REWRITE_TAC[LT_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
148
149 let NUM_EXP_LT2 = prove(`!n1 e1 n2 e2 r. e1 <= e2 /\ e2 - e1 = r /\ num_exp n2 r < n1
150 ==> num_exp n2 e2 < num_exp n1 e1`,
151 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
152 STRIP_TAC THEN
153 POP_ASSUM MP_TAC THEN POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN DISCH_TAC THEN
154 MP_TAC (ARITH_RULE `e1 <= e2 ==> e2 = (e2 - e1) + e1:num`) THEN
155 ASM_REWRITE_TAC[] THEN
156 DISCH_THEN (fun th -> ONCE_REWRITE_TAC[th]) THEN
157 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
158 ASM_REWRITE_TAC[LT_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
159
160 let NUM_EXP_LT1_EQ = prove(`!n1 e1 n2 e2 r x. e2 <= e1 /\ e1 - e2 = r /\ num_exp n1 r = x ==>
161 (num_exp n1 e1 < num_exp n2 e2 <=> x < n2)`,
162 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
163 STRIP_TAC THEN
164 REPLICATE_TAC 2 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
165 MP_TAC (ARITH_RULE `e2 <= e1 ==> e1 = (e1 - e2) + e2:num`) THEN
166 ASM_REWRITE_TAC[] THEN
167 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [th]) THEN
168 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
169 ASM_REWRITE_TAC[LT_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
170
171 let NUM_EXP_LT2_EQ = prove(`!n1 e1 n2 e2 r x. e1 <= e2 /\ e2 - e1 = r /\ num_exp n2 r = x ==>
172 (num_exp n1 e1 < num_exp n2 e2 <=> n1 < x)`,
173 REPEAT GEN_TAC THEN REWRITE_TAC[num_exp] THEN
174 STRIP_TAC THEN
175 REPLICATE_TAC 2 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
176 MP_TAC (ARITH_RULE `e1 <= e2 ==> e2 = (e2 - e1) + e1:num`) THEN
177 ASM_REWRITE_TAC[] THEN
178 DISCH_THEN (fun th -> GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [th]) THEN
179 REWRITE_TAC[EXP_ADD; MULT_ASSOC] THEN
180 ASM_REWRITE_TAC[LT_MULT_RCANCEL; EXP_EQ_0; ARITH_EQ]);;
181
182 (* NUM_EXP_DIV *)
183
184 let mul_op_num = `( * ):num->num->num`;;
185
186 let NUM_EXP_DIV1 = prove(`~(n2 = 0) /\ e2 <= e1 ==>
187 num_exp n1 e1 DIV num_exp n2 e2 = num_exp n1 (e1 - e2) DIV n2`,
188 STRIP_TAC THEN
189 (*`num_exp n1 e1 = 16 EXP e2 * num_exp n1 (e1 - e2)` MP_TAC THENL*)
190 SUBGOAL_THEN (mk_eq(`num_exp n1 e1`, mk_binop mul_op_num (mk_binop `EXP` base_const `e2:num`) `num_exp n1 (e1 - e2)`)) MP_TAC THENL
191 [
192 REWRITE_TAC[num_exp] THEN
193 ONCE_REWRITE_TAC[ARITH_RULE `a * b * c = b * (a * c:num)`] THEN
194 REWRITE_TAC[GSYM EXP_ADD] THEN
195 ASM_SIMP_TAC[ARITH_RULE `e2 <= e1 ==> e2 + e1 - e2 = e1:num`];
196 ALL_TAC
197 ] THEN
198 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
199 SUBGOAL_THEN (mk_eq(`num_exp n2 e2`, mk_binop mul_op_num (mk_binop `EXP` base_const `e2:num`) `n2:num`)) MP_TAC THENL
200 [
201 REWRITE_TAC[num_exp; MULT_AC];
202 ALL_TAC
203 ] THEN
204 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
205 MATCH_MP_TAC DIV_MULT2 THEN
206 ASM_REWRITE_TAC[MULT_EQ_0; DE_MORGAN_THM; EXP_EQ_0] THEN
207 ARITH_TAC);;
208
209 let NUM_EXP_DIV2 = prove(`~(n2 = 0) /\ e1 <= e2 ==>
210 num_exp n1 e1 DIV num_exp n2 e2 = n1 DIV num_exp n2 (e2 - e1)`,
211 STRIP_TAC THEN
212 (*`num_exp n2 e2 = 16 EXP e1 * num_exp n2 (e2 - e1)` MP_TAC THENL*)
213 SUBGOAL_THEN (mk_eq(`num_exp n2 e2`, mk_binop mul_op_num (mk_binop `EXP` base_const `e1:num`) `num_exp n2 (e2 - e1)`)) MP_TAC THENL
214 [
215 REWRITE_TAC[num_exp] THEN
216 ONCE_REWRITE_TAC[ARITH_RULE `a * b * c = b * (a * c:num)`] THEN
217 REWRITE_TAC[GSYM EXP_ADD] THEN
218 ASM_SIMP_TAC[ARITH_RULE `e1 <= e2 ==> e1 + e2 - e1 = e2:num`];
219 ALL_TAC
220 ] THEN
221 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
222 SUBGOAL_THEN (mk_eq(`num_exp n1 e1`, mk_binop mul_op_num (mk_binop `EXP` base_const `e1:num`) `n1:num`)) MP_TAC THENL
223 [
224 REWRITE_TAC[num_exp; MULT_AC];
225 ALL_TAC
226 ] THEN
227 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
228 MATCH_MP_TAC DIV_MULT2 THEN
229 ASM_REWRITE_TAC[num_exp; MULT_EQ_0; DE_MORGAN_THM; EXP_EQ_0] THEN
230 ARITH_TAC);;
231
232
233 let EXP_INV_lemma = prove(`!n e1 e2. ~(n = 0) /\ e2 <= e1 ==> &(n EXP (e1 - e2)) =
234 &(n EXP e1) * inv(&(n EXP e2))`,
235 REPEAT STRIP_TAC THEN
236 REWRITE_TAC[GSYM REAL_OF_NUM_POW] THEN
237 MP_TAC (SPECL [`&n`; `e2:num`; `e1:num`] REAL_POW_SUB) THEN
238 ASM_REWRITE_TAC[REAL_OF_NUM_EQ; real_div]);;
239
240 let NUM_EXP_SUB_lemma = prove(`!n e1 e2. e2 <= e1 ==> &(num_exp n (e1 - e2)) =
241 &(num_exp n e1) * inv(&(num_exp 1 e2))`,
242 REPEAT STRIP_TAC THEN
243 REWRITE_TAC[num_exp] THEN
244 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
245 MP_TAC (SPECL [base_const; `e1:num`; `e2:num`] EXP_INV_lemma) THEN
246 ANTS_TAC THENL
247 [
248 ASM_REWRITE_TAC[] THEN ARITH_TAC;
249 ALL_TAC
250 ] THEN
251 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
252 REAL_ARITH_TAC);;
253
254
255
256 end;;