| 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;; |