| 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 |
(* Formal natural arithmetic with an arbitrary base *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
module type Arith_num_sig = |
| 14 |
sig |
| 15 |
val arith_base : int |
| 16 |
val num_def : thm |
| 17 |
val NUM_THM : thm |
| 18 |
val num_const : term |
| 19 |
val const_array : term array |
| 20 |
val def_array: thm array |
| 21 |
val def_thm_array: thm array |
| 22 |
val mk_numeral_hash : num -> term |
| 23 |
val mk_numeral_array : num -> term |
| 24 |
val mk_small_numeral_array : int -> term |
| 25 |
val raw_dest_hash : term -> num |
| 26 |
val dest_numeral_hash : term -> num |
| 27 |
val NUMERAL_TO_NUM_CONV : term -> thm |
| 28 |
val NUM_TO_NUMERAL_CONV : term -> thm |
| 29 |
(* SUC *) |
| 30 |
val raw_suc_conv_hash : term -> thm |
| 31 |
val NUM_SUC_HASH_CONV : term -> thm |
| 32 |
(* eq0 *) |
| 33 |
val raw_eq0_hash_conv : term -> thm |
| 34 |
val NUM_EQ0_HASH_CONV : term -> thm |
| 35 |
(* PRE *) |
| 36 |
val raw_pre_hash_conv : term -> thm |
| 37 |
val NUM_PRE_HASH_CONV : term -> thm |
| 38 |
(* gt0 *) |
| 39 |
val raw_gt0_hash_conv : term -> thm |
| 40 |
val NUM_GT0_HASH_CONV : term -> thm |
| 41 |
(* eq *) |
| 42 |
val raw_eq_hash_conv : term -> thm |
| 43 |
val NUM_EQ_HASH_CONV : term -> thm |
| 44 |
(* lt, le *) |
| 45 |
val raw_lt_hash_conv : term -> thm |
| 46 |
val raw_le_hash_conv : term -> thm |
| 47 |
val NUM_LT_HASH_CONV : term -> thm |
| 48 |
val NUM_LE_HASH_CONV : term -> thm |
| 49 |
(* add *) |
| 50 |
val raw_add_conv_hash : term -> thm |
| 51 |
val NUM_ADD_HASH_CONV : term -> thm |
| 52 |
(* sub *) |
| 53 |
val raw_sub_hash_conv : term -> thm |
| 54 |
val raw_sub_and_le_hash_conv : term -> term -> thm * thm |
| 55 |
val NUM_SUB_HASH_CONV : term -> thm |
| 56 |
(* mul *) |
| 57 |
val raw_mul_conv_hash : term -> thm |
| 58 |
val NUM_MULT_HASH_CONV : term -> thm |
| 59 |
(* DIV *) |
| 60 |
val raw_div_hash_conv : term -> thm |
| 61 |
val NUM_DIV_HASH_CONV : term -> thm |
| 62 |
(* EVEN, ODD *) |
| 63 |
val raw_even_hash_conv : term -> thm |
| 64 |
val raw_odd_hash_conv : term -> thm |
| 65 |
val NUM_EVEN_HASH_CONV : term -> thm |
| 66 |
val NUM_ODD_HASH_CONV : term -> thm |
| 67 |
end;; |
| 68 |
|
| 69 |
(* Dependencies *) |
| 70 |
needs "Formal_ineqs/misc/misc_functions.hl";; |
| 71 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 72 |
needs "Formal_ineqs/arith_options.hl";; |
| 73 |
|
| 74 |
module Arith_num : Arith_num_sig = struct |
| 75 |
|
| 76 |
open Misc_functions;; |
| 77 |
open Misc_vars;; |
| 78 |
|
| 79 |
let arith_base = !Arith_options.base;; |
| 80 |
let maximum = arith_base;; |
| 81 |
|
| 82 |
(******************) |
| 83 |
|
| 84 |
(* Generate definitions and constants *) |
| 85 |
|
| 86 |
let fnum_type = `:num->num` and |
| 87 |
numeral_const = `NUMERAL` and |
| 88 |
bit0_const = `BIT0` and |
| 89 |
bit1_const = `BIT1`;; |
| 90 |
|
| 91 |
(* Names of constants which define "digits" *) |
| 92 |
let names_array = Array.init maximum (fun i -> "D"^(string_of_int i));; |
| 93 |
|
| 94 |
(* Definitions *) |
| 95 |
let num_name = "NUM"^(string_of_int arith_base);; |
| 96 |
let num_def = new_basic_definition (mk_eq(mk_var(num_name, fnum_type), numeral_const));; |
| 97 |
let num_const = mk_const(num_name, []);; |
| 98 |
let num_def_sym = SYM num_def;; |
| 99 |
|
| 100 |
(* |- NUM n = n *) |
| 101 |
let NUM_THM = prove(mk_eq(mk_comb(num_const, n_var_num), n_var_num), |
| 102 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 103 |
|
| 104 |
(* |- D_i(n) = i + D_0(n) *) |
| 105 |
let mk_bit_definition i = |
| 106 |
let lhs = mk_var (names_array.(i), fnum_type) in |
| 107 |
let tm1 = mk_binop mul_op_num (mk_small_numeral arith_base) n_var_num in |
| 108 |
let tm2 = mk_binop add_op_num tm1 (mk_small_numeral i) in |
| 109 |
let rhs = mk_abs (n_var_num, tm2) in |
| 110 |
new_basic_definition (mk_eq (lhs, rhs));; |
| 111 |
|
| 112 |
let def_basic_array = Array.init maximum mk_bit_definition;; |
| 113 |
let def_array = Array.init maximum (fun i -> |
| 114 |
let basic = def_basic_array.(i) in |
| 115 |
let th1 = AP_THM basic n_var_num in |
| 116 |
TRANS th1 (BETA (rand (concl th1))));; |
| 117 |
let def_table = Hashtbl.create maximum;; |
| 118 |
let def_basic_table = Hashtbl.create maximum;; |
| 119 |
|
| 120 |
for i = 0 to maximum - 1 do |
| 121 |
let _ = Hashtbl.add def_table names_array.(i) def_array.(i) in |
| 122 |
Hashtbl.add def_basic_table names_array.(i) def_basic_array.(i) |
| 123 |
done;; |
| 124 |
|
| 125 |
|
| 126 |
(* Constants *) |
| 127 |
let const_array = Array.init maximum (fun i -> mk_const(names_array.(i),[]));; |
| 128 |
|
| 129 |
let b0_def = def_array.(0);; |
| 130 |
let b0_const = const_array.(0);; |
| 131 |
let b0_name = names_array.(0);; |
| 132 |
|
| 133 |
let max_const = mk_small_numeral maximum;; |
| 134 |
|
| 135 |
|
| 136 |
(* Alternative definition of D_i *) |
| 137 |
let ADD_0_n = prove(`_0 + n = n`, |
| 138 |
ONCE_REWRITE_TAC[GSYM NUMERAL] THEN |
| 139 |
REWRITE_TAC[GSYM ARITH_ADD; ADD_CLAUSES]);; |
| 140 |
let ADD_n_0 = prove(`n + _0 = n`, |
| 141 |
ONCE_REWRITE_TAC[GSYM NUMERAL] THEN |
| 142 |
REWRITE_TAC[GSYM ARITH_ADD; ADD_CLAUSES]);; |
| 143 |
|
| 144 |
let MUL_n_0 = prove(`n * _0 = 0`, |
| 145 |
REWRITE_TAC[NUMERAL] THEN |
| 146 |
SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN |
| 147 |
DISCH_THEN (fun th -> ONCE_REWRITE_TAC[th]) THEN |
| 148 |
ARITH_TAC);; |
| 149 |
|
| 150 |
(* D_i(n) = i + D_0(n) *) |
| 151 |
let def_thm i = |
| 152 |
let bin = mk_comb(const_array.(i), n_var_num) in |
| 153 |
let bi0 = mk_comb(const_array.(i), zero_const) in |
| 154 |
let b0n = mk_comb(const_array.(0), n_var_num) in |
| 155 |
let rhs = mk_binop add_op_num bi0 b0n in |
| 156 |
prove(mk_eq(bin, rhs), REWRITE_TAC[def_array.(i); def_array.(0)] THEN |
| 157 |
REWRITE_TAC[MUL_n_0; ADD_CLAUSES] THEN ARITH_TAC);; |
| 158 |
|
| 159 |
let def_thm_array = Array.init maximum def_thm;; |
| 160 |
|
| 161 |
let B0_0 = prove(mk_eq(mk_comb(b0_const, zero_const), zero_const), |
| 162 |
REWRITE_TAC[b0_def; MUL_n_0; ADD_CLAUSES; NUMERAL]);; |
| 163 |
|
| 164 |
let B0_EXPLICIT = prove(mk_eq(mk_comb(b0_const, n_var_num), |
| 165 |
mk_binop mul_op_num max_const n_var_num), |
| 166 |
REWRITE_TAC[b0_def; ADD_CLAUSES]);; |
| 167 |
|
| 168 |
(******************************) |
| 169 |
(* mk_numeral and dest_numeral *) |
| 170 |
|
| 171 |
(* mk_table *) |
| 172 |
|
| 173 |
let mk_table = Hashtbl.create maximum;; |
| 174 |
|
| 175 |
for i = 0 to maximum - 1 do |
| 176 |
Hashtbl.add mk_table (Num.num_of_int i) const_array.(i) |
| 177 |
done;; |
| 178 |
|
| 179 |
(* mk_numeral *) |
| 180 |
let max_num = Num.num_of_int maximum;; |
| 181 |
|
| 182 |
let mk_numeral_hash = |
| 183 |
let rec mk_num n = |
| 184 |
if (n =/ num_0) then |
| 185 |
zero_const |
| 186 |
else |
| 187 |
let m = mod_num n max_num in |
| 188 |
let bit = Hashtbl.find mk_table m in |
| 189 |
mk_comb(bit, mk_num(quo_num n max_num)) in |
| 190 |
fun n -> if n </ num_0 then failwith "mk_numeral_hash: negative argument" |
| 191 |
else mk_comb(num_const, mk_num n);; |
| 192 |
|
| 193 |
let mk_numeral_array = |
| 194 |
let rec mk_num n = |
| 195 |
if (n =/ num_0) then |
| 196 |
zero_const |
| 197 |
else |
| 198 |
let m = Num.int_of_num (mod_num n max_num) in |
| 199 |
let bit = const_array.(m) in |
| 200 |
mk_comb(bit, mk_num(quo_num n max_num)) in |
| 201 |
fun n -> if n </ num_0 then failwith "mk_numeral_array: negative argument" |
| 202 |
else mk_comb(num_const, mk_num n);; |
| 203 |
|
| 204 |
let mk_small_numeral_array = |
| 205 |
let rec mk_num n = |
| 206 |
if (n = 0) then zero_const |
| 207 |
else |
| 208 |
let m = n mod maximum in |
| 209 |
let bit = const_array.(m) in |
| 210 |
mk_comb(bit, mk_num(n / maximum)) in |
| 211 |
fun n -> if n < 0 then failwith "mk_small_numeral_array: negative argument" |
| 212 |
else mk_comb (num_const, mk_num n);; |
| 213 |
|
| 214 |
(* dest_table *) |
| 215 |
let dest_table_num = Hashtbl.create maximum;; |
| 216 |
|
| 217 |
for i = 0 to maximum - 1 do |
| 218 |
Hashtbl.add dest_table_num names_array.(i) (Num.num_of_int i) |
| 219 |
done;; |
| 220 |
|
| 221 |
|
| 222 |
(* dest_numeral *) |
| 223 |
let max_num = Num.num_of_int maximum;; |
| 224 |
|
| 225 |
let rec raw_dest_hash tm = |
| 226 |
if tm = zero_const then |
| 227 |
num_0 |
| 228 |
else |
| 229 |
let l, r = dest_comb tm in |
| 230 |
let n = max_num */ raw_dest_hash r in |
| 231 |
let cn = fst(dest_const l) in |
| 232 |
n +/ (Hashtbl.find dest_table_num cn);; |
| 233 |
|
| 234 |
|
| 235 |
let dest_numeral_hash tm = raw_dest_hash (rand tm);; |
| 236 |
|
| 237 |
|
| 238 |
(******************************) |
| 239 |
(* NUMERAL_TO_NUM_CONV: coverts usual HOL numerals into k-bit numerals *) |
| 240 |
|
| 241 |
let th_num_conv = Array.init maximum (fun i -> (SYM o SPEC_ALL) def_array.(i));; |
| 242 |
let mod_op_num = `MOD`;; |
| 243 |
|
| 244 |
let DIV_BASE = |
| 245 |
let h1 = mk_eq(mk_binop div_op_num m_var_num max_const, q_var_num) in |
| 246 |
let h2 = mk_eq(mk_binop mod_op_num m_var_num max_const, r_var_num) in |
| 247 |
let c = mk_eq(m_var_num, mk_binop add_op_num (mk_binop mul_op_num max_const q_var_num) r_var_num) in |
| 248 |
(UNDISCH_ALL o ARITH_RULE) (mk_imp(h1, mk_imp(h2, c)));; |
| 249 |
|
| 250 |
let ZERO_EQ_ZERO = (EQT_ELIM o REWRITE_CONV[NUMERAL]) `0 = _0`;; |
| 251 |
let SYM_ZERO_EQ_ZERO = SYM ZERO_EQ_ZERO;; |
| 252 |
let SYM_NUM_THM = SYM NUM_THM;; |
| 253 |
|
| 254 |
let NUMERAL_TO_NUM_CONV tm = |
| 255 |
let rec raw_conv tm = |
| 256 |
if (rand tm = zero_const) then |
| 257 |
ZERO_EQ_ZERO |
| 258 |
else |
| 259 |
let th_div = NUM_DIV_CONV (mk_binop div_op_num tm max_const) in |
| 260 |
let th_mod = NUM_MOD_CONV (mk_binop mod_op_num tm max_const) in |
| 261 |
let q_tm = rand(concl th_div) in |
| 262 |
let r_tm = rand(concl th_mod) in |
| 263 |
let th0 = INST[tm, m_var_num; q_tm, q_var_num; r_tm, r_var_num] DIV_BASE in |
| 264 |
let th1 = MY_PROVE_HYP th_mod (MY_PROVE_HYP th_div th0) in |
| 265 |
let r = dest_small_numeral r_tm in |
| 266 |
let th2 = INST[q_tm, n_var_num] th_num_conv.(r) in |
| 267 |
let th = TRANS th1 th2 in |
| 268 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 269 |
let r_th = raw_conv rtm in |
| 270 |
TRANS th (AP_TERM ltm r_th) in |
| 271 |
|
| 272 |
if (fst o dest_const o rator) tm <> "NUMERAL" then |
| 273 |
failwith "NUMERAL_TO_NUM_CONV" |
| 274 |
else |
| 275 |
let th0 = raw_conv tm in |
| 276 |
let n_tm = rand(concl th0) in |
| 277 |
TRANS th0 (INST[n_tm, n_var_num] SYM_NUM_THM);; |
| 278 |
|
| 279 |
let replace_numerals = rand o concl o DEPTH_CONV NUMERAL_TO_NUM_CONV;; |
| 280 |
let REPLACE_NUMERALS = CONV_RULE (DEPTH_CONV NUMERAL_TO_NUM_CONV);; |
| 281 |
|
| 282 |
(* NUM_TO_NUMERAL_CONV *) |
| 283 |
let NUM_TO_NUMERAL_CONV tm = |
| 284 |
let rec raw_conv tm = |
| 285 |
if tm = zero_const then |
| 286 |
SYM_ZERO_EQ_ZERO |
| 287 |
else |
| 288 |
let b_tm, n_tm = dest_comb tm in |
| 289 |
let n_th = raw_conv n_tm in |
| 290 |
let n_tm' = rand(concl n_th) in |
| 291 |
let cb = (fst o dest_const) b_tm in |
| 292 |
let th0 = Hashtbl.find def_table cb in |
| 293 |
let th1 = AP_TERM b_tm n_th in |
| 294 |
let th2 = TRANS th1 (INST[n_tm', n_var_num] th0) in |
| 295 |
let ltm, rtm = dest_comb(rand(concl th2)) in |
| 296 |
let mul_th = NUM_MULT_CONV (rand ltm) in |
| 297 |
let add_th0 = AP_THM (AP_TERM add_op_num mul_th) rtm in |
| 298 |
let add_th = TRANS add_th0 (NUM_ADD_CONV (rand(concl add_th0))) in |
| 299 |
TRANS th2 add_th in |
| 300 |
let ltm, rtm = dest_comb tm in |
| 301 |
if (fst o dest_const) ltm <> num_name then |
| 302 |
failwith "NUM_TO_NUMERAL_CONV" |
| 303 |
else |
| 304 |
let num_th = INST[rtm, n_var_num] NUM_THM in |
| 305 |
let th0 = raw_conv rtm in |
| 306 |
TRANS num_th th0;; |
| 307 |
|
| 308 |
(*************************) |
| 309 |
(* SUC_CONV *) |
| 310 |
|
| 311 |
(* Theorems *) |
| 312 |
let SUC_NUM = prove(mk_eq(mk_comb(suc_op_num, mk_comb (num_const, n_var_num)), |
| 313 |
mk_comb(num_const, mk_comb (suc_op_num, n_var_num))), |
| 314 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 315 |
|
| 316 |
let SUC_0 = prove(mk_eq(`SUC _0`, mk_comb (const_array.(1), zero_const)), |
| 317 |
REWRITE_TAC[def_array.(1); MUL_n_0; ARITH_SUC; NUMERAL; ARITH_ADD]);; |
| 318 |
|
| 319 |
let suc_th i = |
| 320 |
let cflag = (i + 1 >= maximum) in |
| 321 |
let suc = if (cflag) then 0 else i + 1 in |
| 322 |
let lhs = mk_comb(suc_op_num, (mk_comb (const_array.(i), n_var_num))) in |
| 323 |
let rhs = mk_comb(const_array.(suc), |
| 324 |
if (cflag) then mk_comb(suc_op_num, n_var_num) else n_var_num) in |
| 325 |
let proof = REWRITE_TAC [def_array.(i); def_array.(suc)] THEN ARITH_TAC in |
| 326 |
prove(mk_eq(lhs, rhs), proof);; |
| 327 |
|
| 328 |
let th_suc_array = Array.init maximum suc_th;; |
| 329 |
let th_suc_table = Hashtbl.create maximum;; |
| 330 |
|
| 331 |
for i = 0 to maximum - 1 do |
| 332 |
Hashtbl.add th_suc_table names_array.(i) th_suc_array.(i) |
| 333 |
done;; |
| 334 |
|
| 335 |
let SUC_MAX = th_suc_array.(maximum - 1);; |
| 336 |
let bit_max_name = names_array.(maximum - 1);; |
| 337 |
|
| 338 |
(* Conversion *) |
| 339 |
let rec raw_suc_conv_hash tm = |
| 340 |
let otm = rand tm in |
| 341 |
if (otm = zero_const) then |
| 342 |
SUC_0 |
| 343 |
else |
| 344 |
let btm, ntm = dest_comb otm in |
| 345 |
let cn = fst(dest_const btm) in |
| 346 |
if (cn = bit_max_name) then |
| 347 |
let th = INST [ntm, n_var_num] SUC_MAX in |
| 348 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 349 |
TRANS th (AP_TERM ltm (raw_suc_conv_hash rtm)) |
| 350 |
else |
| 351 |
INST [ntm, n_var_num] (Hashtbl.find th_suc_table cn);; |
| 352 |
|
| 353 |
let NUM_SUC_HASH_CONV tm = |
| 354 |
let ntm = rand (rand tm) in |
| 355 |
let th = INST [ntm, n_var_num] SUC_NUM in |
| 356 |
let lhs, rhs = dest_eq(concl th) in |
| 357 |
if (lhs <> tm) then failwith("NUM_SUC_HASH_CONV") |
| 358 |
else |
| 359 |
let ltm, rtm = dest_comb rhs in |
| 360 |
TRANS th (AP_TERM ltm (raw_suc_conv_hash rtm));; |
| 361 |
|
| 362 |
|
| 363 |
(**************************************) |
| 364 |
(* EQ_0_CONV *) |
| 365 |
let EQ_0_NUM = prove(mk_eq(mk_eq(mk_comb(num_const, n_var_num), `_0`), `n = _0`), |
| 366 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 367 |
|
| 368 |
let EQ_B0_0 = prove(mk_eq(mk_eq(mk_comb(b0_const, n_var_num), `_0`), `n = _0`), |
| 369 |
REWRITE_TAC[b0_def; ADD_CLAUSES; NUMERAL; REWRITE_RULE[NUMERAL] MULT_EQ_0; ARITH_EQ]);; |
| 370 |
|
| 371 |
let EQ_0_0 = prove(`_0 = _0 <=> T`, REWRITE_TAC[ARITH_EQ]);; |
| 372 |
|
| 373 |
let eq_0_lemma = REWRITE_RULE[NUMERAL] (ARITH_RULE `a + b = 0 <=> a = 0 /\ b = 0`);; |
| 374 |
|
| 375 |
let eq_0_i i = |
| 376 |
let concl = mk_eq(mk_eq(mk_comb(const_array.(i), n_var_num), zero_const), f_const) in |
| 377 |
prove(concl, REWRITE_TAC[def_array.(i); eq_0_lemma; NUMERAL; ARITH_EQ]);; |
| 378 |
|
| 379 |
let th_eq0_array = Array.init maximum (fun i -> if (i = 0) then EQ_0_0 else eq_0_i i);; |
| 380 |
|
| 381 |
let th_eq0_table = Hashtbl.create maximum;; |
| 382 |
|
| 383 |
for i = 0 to maximum - 1 do |
| 384 |
Hashtbl.add th_eq0_table names_array.(i) th_eq0_array.(i) |
| 385 |
done;; |
| 386 |
|
| 387 |
let rec raw_eq0_hash_conv rtm = |
| 388 |
if (rtm = zero_const) then |
| 389 |
EQ_0_0 |
| 390 |
else |
| 391 |
let b_tm, n_tm = dest_comb rtm in |
| 392 |
let cn = (fst o dest_const) b_tm in |
| 393 |
if (cn = b0_name) then |
| 394 |
let th0 = INST[n_tm, n_var_num] EQ_B0_0 in |
| 395 |
let th1 = raw_eq0_hash_conv n_tm in |
| 396 |
TRANS th0 th1 |
| 397 |
else |
| 398 |
INST[n_tm, n_var_num] (Hashtbl.find th_eq0_table cn);; |
| 399 |
|
| 400 |
let NUM_EQ0_HASH_CONV rtm = |
| 401 |
let n_tm = rand rtm in |
| 402 |
let th = INST [n_tm, n_var_num] EQ_0_NUM in |
| 403 |
TRANS th (raw_eq0_hash_conv n_tm);; |
| 404 |
|
| 405 |
(**************************************) |
| 406 |
(* PRE_CONV *) |
| 407 |
|
| 408 |
(* Theorems *) |
| 409 |
let PRE_NUM = prove(mk_eq(mk_comb(pre_op_num, mk_comb (num_const, n_var_num)), |
| 410 |
mk_comb(num_const, mk_comb (pre_op_num, n_var_num))), |
| 411 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 412 |
|
| 413 |
let PRE_0 = prove(`PRE _0 = _0`, |
| 414 |
MP_TAC (CONJUNCT1 PRE) THEN SIMP_TAC[NUMERAL]);; |
| 415 |
|
| 416 |
let PRE_B1_0 = prove(mk_eq(mk_comb(`PRE`, mk_comb(const_array.(1), `_0`)), `_0`), |
| 417 |
REWRITE_TAC[def_array.(1); MUL_n_0; ARITH_ADD; NUMERAL; ARITH_PRE; ARITH_EQ]);; |
| 418 |
|
| 419 |
|
| 420 |
let PRE_B0_n0 = (UNDISCH_ALL o prove)(mk_imp(`n = _0 <=> T`, |
| 421 |
mk_eq(mk_comb(`PRE`, mk_comb(b0_const, `n:num`)), `_0`)), |
| 422 |
REWRITE_TAC[B0_EXPLICIT] THEN |
| 423 |
DISCH_THEN (fun th -> REWRITE_TAC[th; MUL_n_0]) THEN |
| 424 |
REWRITE_TAC[NUMERAL; ARITH_PRE]);; |
| 425 |
|
| 426 |
let PRE_B0_n1 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)(mk_imp(`n = 0 <=> F`, |
| 427 |
mk_eq(mk_comb(`PRE`, mk_comb(b0_const, `n:num`)), |
| 428 |
mk_comb(const_array.(maximum - 1), `PRE n`))), |
| 429 |
REWRITE_TAC[B0_EXPLICIT; def_array.(maximum - 1)] THEN ARITH_TAC);; |
| 430 |
|
| 431 |
let PRE_lemma = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o ARITH_RULE) `((n = 0) <=> F) ==> (SUC m = n <=> PRE n = m)`;; |
| 432 |
|
| 433 |
let pre_th i = |
| 434 |
let pre = i - 1 in |
| 435 |
let pre_tm = mk_comb(const_array.(pre), n_var_num) in |
| 436 |
let suc_tm = mk_comb(suc_op_num, pre_tm) in |
| 437 |
let suc_th = raw_suc_conv_hash suc_tm in |
| 438 |
let n_tm = rand(concl suc_th) in |
| 439 |
let n0_th = raw_eq0_hash_conv n_tm in |
| 440 |
let th0 = INST[pre_tm, m_var_num; n_tm, n_var_num] PRE_lemma in |
| 441 |
MY_PROVE_HYP n0_th (EQ_MP th0 suc_th);; |
| 442 |
|
| 443 |
|
| 444 |
let th_pre_array = Array.init maximum (fun i -> if i = 0 then REFL `_0` else pre_th i);; |
| 445 |
|
| 446 |
let th_pre_table = Hashtbl.create maximum;; |
| 447 |
|
| 448 |
for i = 0 to maximum - 1 do |
| 449 |
Hashtbl.add th_pre_table names_array.(i) th_pre_array.(i) |
| 450 |
done;; |
| 451 |
|
| 452 |
(* Conversion *) |
| 453 |
let b1_name = names_array.(1);; |
| 454 |
let b1_pre_thm = th_pre_array.(1);; |
| 455 |
|
| 456 |
let rec raw_pre_hash_conv tm = |
| 457 |
let otm = rand tm in |
| 458 |
if (otm = zero_const) then |
| 459 |
PRE_0 |
| 460 |
else |
| 461 |
let btm, ntm = dest_comb otm in |
| 462 |
let cn = fst(dest_const btm) in |
| 463 |
if (cn = b0_name) then |
| 464 |
let n_th = raw_eq0_hash_conv ntm in |
| 465 |
if (rand(concl n_th) = f_const) then |
| 466 |
let th0 = INST[ntm, n_var_num] PRE_B0_n1 in |
| 467 |
let th1 = MY_PROVE_HYP n_th th0 in |
| 468 |
let ltm, rtm = dest_comb(rand(concl th1)) in |
| 469 |
let th2 = raw_pre_hash_conv rtm in |
| 470 |
TRANS th1 (AP_TERM ltm th2) |
| 471 |
else |
| 472 |
let th = INST[ntm, n_var_num] PRE_B0_n0 in |
| 473 |
MY_PROVE_HYP n_th th |
| 474 |
else |
| 475 |
if (cn = b1_name) then |
| 476 |
if (ntm = zero_const) then |
| 477 |
PRE_B1_0 |
| 478 |
else |
| 479 |
INST[ntm, n_var_num] b1_pre_thm |
| 480 |
else |
| 481 |
INST [ntm, n_var_num] (Hashtbl.find th_pre_table cn);; |
| 482 |
|
| 483 |
let NUM_PRE_HASH_CONV tm = |
| 484 |
let ntm = rand (rand tm) in |
| 485 |
let th = INST [ntm, n_var_num] PRE_NUM in |
| 486 |
let lhs, rhs = dest_eq(concl th) in |
| 487 |
if (lhs <> tm) then failwith("NUM_PRE_HASH_CONV") |
| 488 |
else |
| 489 |
let ltm, rtm = dest_comb rhs in |
| 490 |
TRANS th (AP_TERM ltm (raw_pre_hash_conv rtm));; |
| 491 |
|
| 492 |
(**************************************) |
| 493 |
(* GT0_CONV *) |
| 494 |
|
| 495 |
let gt0_table = Hashtbl.create maximum;; |
| 496 |
|
| 497 |
let GT0_NUM = (REWRITE_RULE[GSYM num_def] o prove)(`0 < NUMERAL n <=> _0 < n`, REWRITE_TAC[NUMERAL]);; |
| 498 |
|
| 499 |
let gt0_0 = prove(`_0 < _0 <=> F`, REWRITE_TAC[ARITH_LT]);; |
| 500 |
let gt0_b0 = (REWRITE_RULE[NUMERAL] o prove)(mk_eq (mk_binop lt_op_num `0` (mk_comb(b0_const, n_var_num)), `0 < n`), |
| 501 |
REWRITE_TAC[b0_def] THEN ARITH_TAC);; |
| 502 |
|
| 503 |
let gt0_th i = |
| 504 |
let bi = const_array.(i) in |
| 505 |
let concl = mk_eq (mk_binop lt_op_num zero_num (mk_comb(bi, n_var_num)), t_const) in |
| 506 |
let proof = REWRITE_TAC[def_array.(i)] THEN ARITH_TAC in |
| 507 |
(PURE_REWRITE_RULE[NUMERAL] o prove)(concl, proof);; |
| 508 |
|
| 509 |
for i = 1 to maximum - 1 do |
| 510 |
Hashtbl.add gt0_table names_array.(i) (gt0_th i) |
| 511 |
done;; |
| 512 |
|
| 513 |
let rec raw_gt0_hash_conv rtm = |
| 514 |
if (rtm = zero_const) then |
| 515 |
gt0_0 |
| 516 |
else |
| 517 |
let b_tm, n_tm = dest_comb rtm in |
| 518 |
let cn = (fst o dest_const) b_tm in |
| 519 |
if (cn = b0_name) then |
| 520 |
let th0 = INST[n_tm, n_var_num] gt0_b0 in |
| 521 |
let th1 = raw_gt0_hash_conv n_tm in |
| 522 |
TRANS th0 th1 |
| 523 |
else |
| 524 |
INST[n_tm, n_var_num] (Hashtbl.find gt0_table cn);; |
| 525 |
|
| 526 |
let NUM_GT0_HASH_CONV rtm = |
| 527 |
let n_tm = rand rtm in |
| 528 |
let th = INST [n_tm, n_var_num] GT0_NUM in |
| 529 |
TRANS th (raw_gt0_hash_conv n_tm);; |
| 530 |
|
| 531 |
(*************************************) |
| 532 |
(* EQ *) |
| 533 |
|
| 534 |
let EQ_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m = NUMERAL n <=> m = n`, REWRITE_TAC[NUMERAL]);; |
| 535 |
|
| 536 |
|
| 537 |
(* EQ tables *) |
| 538 |
|
| 539 |
(* Generates the theorem |- D_i(m) = D_j(n) <=> F if i <> j and D_i(m) = D_i(n) <=> m = n *) |
| 540 |
let gen_bi_eq_bj = |
| 541 |
let aux_th = prove(`i < b /\ j < b /\ ~(i = j) ==> ~(b * m + i = b * n + j:num)`, |
| 542 |
ONCE_REWRITE_TAC[ARITH_RULE `b * m + i = b * n + j <=> m * b + i = n * b + j:num`] THEN |
| 543 |
STRIP_TAC THEN POP_ASSUM MP_TAC THEN |
| 544 |
SUBGOAL_THEN `~(b = 0)` ASSUME_TAC THENL [POP_ASSUM MP_TAC THEN ARITH_TAC; ALL_TAC] THEN |
| 545 |
REWRITE_TAC[CONTRAPOS_THM] THEN |
| 546 |
DISCH_TAC THEN FIRST_ASSUM (MP_TAC o AP_TERM `\x. x DIV b`) THEN REWRITE_TAC[] THEN |
| 547 |
FIRST_ASSUM (MP_TAC o MATCH_MP (CONJUNCT1 DIV_MULT_ADD)) THEN |
| 548 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 549 |
SUBGOAL_THEN `i DIV b = 0 /\ j DIV b = 0` (fun th -> REWRITE_TAC[th]) THENL |
| 550 |
[ |
| 551 |
FIRST_ASSUM (ASSUME_TAC o MATCH_MP DIV_EQ_0) THEN ASM_REWRITE_TAC[]; |
| 552 |
ALL_TAC |
| 553 |
] THEN |
| 554 |
REWRITE_TAC[ADD_0] THEN DISCH_TAC THEN |
| 555 |
UNDISCH_TAC `m * b + i = n * b + j:num` THEN |
| 556 |
ASM_REWRITE_TAC[] THEN ARITH_TAC) in |
| 557 |
fun i j -> |
| 558 |
let bi_m = mk_comb (const_array.(i), m_var_num) in |
| 559 |
let bj_n = mk_comb (const_array.(j), n_var_num) in |
| 560 |
let eq_tm = mk_binop eq_op_num bi_m bj_n in |
| 561 |
if i = j then |
| 562 |
prove (mk_eq (eq_tm, mk_binop eq_op_num m_var_num n_var_num), REWRITE_TAC[def_array.(i)] THEN ARITH_TAC) |
| 563 |
else |
| 564 |
prove (mk_eq (eq_tm, f_const), REWRITE_TAC[def_array.(i); def_array.(j)] THEN |
| 565 |
MATCH_MP_TAC aux_th THEN CONV_TAC NUM_REDUCE_CONV);; |
| 566 |
|
| 567 |
|
| 568 |
let gen_next_eq_thm = |
| 569 |
let suc_eq_th = ARITH_RULE `SUC m = SUC n <=> m = n` in |
| 570 |
fun th -> |
| 571 |
let ltm, n_tm = (dest_comb o lhand o concl) th in |
| 572 |
let m_tm = rand ltm in |
| 573 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] suc_eq_th in |
| 574 |
let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in |
| 575 |
let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in |
| 576 |
let th1 = SYM (MK_COMB ((AP_TERM eq_op_num suc_m), suc_n)) in |
| 577 |
TRANS (TRANS th1 th0) th;; |
| 578 |
|
| 579 |
|
| 580 |
let th_eq_table = Hashtbl.create (maximum * maximum);; |
| 581 |
|
| 582 |
|
| 583 |
for i = 0 to maximum - 1 do |
| 584 |
let sym = INST[n_var_num, m_var_num; m_var_num, n_var_num] o CONV_RULE (LAND_CONV SYM_CONV) in |
| 585 |
let th = ref (gen_bi_eq_bj 0 i) in |
| 586 |
let name_left = names_array.(0) and |
| 587 |
name_right = names_array.(i) in |
| 588 |
let _ = Hashtbl.add th_eq_table (name_left ^ name_right) !th in |
| 589 |
let _ = if i > 0 then |
| 590 |
Hashtbl.add th_eq_table (name_right ^ name_left) (sym !th) |
| 591 |
else () in |
| 592 |
for k = 1 to maximum - i - 1 do |
| 593 |
let x = k and y = i + k in |
| 594 |
let name_left = names_array.(x) and |
| 595 |
name_right = names_array.(y) in |
| 596 |
let _ = th := gen_next_eq_thm (!th) in |
| 597 |
let _ = Hashtbl.add th_eq_table (name_left ^ name_right) !th in |
| 598 |
if y > x then |
| 599 |
Hashtbl.add th_eq_table (name_right ^ name_left) (sym !th) |
| 600 |
else |
| 601 |
() |
| 602 |
done; |
| 603 |
done;; |
| 604 |
|
| 605 |
|
| 606 |
(* Conversion *) |
| 607 |
|
| 608 |
let eq_0_sym = (REWRITE_RULE[NUMERAL] o prove)(`0 = n <=> n = 0`, REWRITE_TAC[EQ_SYM_EQ]);; |
| 609 |
|
| 610 |
let rec raw_eq_hash_conv tm = |
| 611 |
let ltm, rtm = dest_comb tm in |
| 612 |
let ltm = rand ltm in |
| 613 |
if is_const rtm then |
| 614 |
(* n = _0 *) |
| 615 |
raw_eq0_hash_conv ltm |
| 616 |
else |
| 617 |
(* n <> _0 *) |
| 618 |
if is_const ltm then |
| 619 |
(* m = _0 *) |
| 620 |
let th0 = raw_eq0_hash_conv rtm in |
| 621 |
let th1 = INST[rtm, n_var_num] eq_0_sym in |
| 622 |
TRANS th1 th0 |
| 623 |
else |
| 624 |
(* m <> _0 *) |
| 625 |
let bm_tm, m_tm = dest_comb ltm in |
| 626 |
let bn_tm, n_tm = dest_comb rtm in |
| 627 |
let cbm = (fst o dest_const) bm_tm in |
| 628 |
let cbn = (fst o dest_const) bn_tm in |
| 629 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_eq_table (cbm^cbn)) in |
| 630 |
if cbm <> cbn then |
| 631 |
th0 |
| 632 |
else |
| 633 |
let th1 = raw_eq_hash_conv (rand (concl th0)) in |
| 634 |
TRANS th0 th1;; |
| 635 |
|
| 636 |
|
| 637 |
let NUM_EQ_HASH_CONV tm = |
| 638 |
let atm, rtm = dest_comb tm in |
| 639 |
let ltm = rand atm in |
| 640 |
let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] EQ_NUM in |
| 641 |
let rtm = rand(concl th) in |
| 642 |
TRANS th (raw_eq_hash_conv rtm);; |
| 643 |
|
| 644 |
|
| 645 |
|
| 646 |
(*************************************) |
| 647 |
(* LT and LE *) |
| 648 |
|
| 649 |
let LT_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m < NUMERAL n <=> m < n`, REWRITE_TAC[NUMERAL]);; |
| 650 |
let LE_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m <= NUMERAL n <=> m <= n`, REWRITE_TAC[NUMERAL]);; |
| 651 |
|
| 652 |
let LT_n_0 = prove(`n < _0 <=> F`, |
| 653 |
SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN |
| 654 |
DISCH_THEN (fun th -> PURE_ONCE_REWRITE_TAC[th]) THEN |
| 655 |
ARITH_TAC);; |
| 656 |
|
| 657 |
let LE_0_n = prove(`_0 <= n <=> T`, |
| 658 |
SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN |
| 659 |
DISCH_THEN (fun th -> PURE_ONCE_REWRITE_TAC[th]) THEN |
| 660 |
ARITH_TAC);; |
| 661 |
|
| 662 |
let SUC_LT_THM = ARITH_RULE `SUC m < SUC n <=> m < n`;; |
| 663 |
let SUC_LE_THM = ARITH_RULE `SUC m <= SUC n <=> m <= n`;; |
| 664 |
|
| 665 |
(* LT tables *) |
| 666 |
|
| 667 |
(* Generates the theorem |- _0 < bi(n) <=> T (or |- _0 < b0(n) <=> _0 < n) *) |
| 668 |
let gen_0_lt_bi i = |
| 669 |
let bin = mk_comb (const_array.(i), n_var_num) in |
| 670 |
let lt_tm = mk_binop lt_op_num zero_num bin in |
| 671 |
if i > 0 then |
| 672 |
(PURE_REWRITE_RULE[NUMERAL] o EQT_INTRO o prove)(lt_tm, REWRITE_TAC[def_array.(i)] THEN ARITH_TAC) |
| 673 |
else |
| 674 |
(PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, `0 < n`), REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);; |
| 675 |
|
| 676 |
let th_lt0_table = Hashtbl.create maximum;; |
| 677 |
for i = 0 to maximum - 1 do |
| 678 |
let th = gen_0_lt_bi i in |
| 679 |
let name = names_array.(i) in |
| 680 |
Hashtbl.add th_lt0_table name th |
| 681 |
done;; |
| 682 |
|
| 683 |
|
| 684 |
(* Generates the theorem |- bi(m) < bj(n) <=> m <= n (or m < n) *) |
| 685 |
let gen_bi_lt_bj i j = |
| 686 |
let bim = mk_comb (const_array.(i), m_var_num) in |
| 687 |
let bjn = mk_comb (const_array.(j), n_var_num) in |
| 688 |
let lt_tm = mk_binop lt_op_num bim bjn in |
| 689 |
let rhs = |
| 690 |
if i >= j then |
| 691 |
mk_binop lt_op_num m_var_num n_var_num |
| 692 |
else |
| 693 |
mk_binop le_op_num m_var_num n_var_num in |
| 694 |
prove(mk_eq(lt_tm, rhs), REWRITE_TAC[def_array.(i); def_array.(j)] THEN ARITH_TAC);; |
| 695 |
|
| 696 |
(* Given a theorem |- bi(m) < bj(n) <=> P m n, generates the theorem |
| 697 |
|- SUC(bi(m)) < SUC(bj(n)) <=> P m n *) |
| 698 |
let gen_next_lt_thm th = |
| 699 |
let ltm, n_tm = (dest_comb o lhand o concl) th in |
| 700 |
let m_tm = rand ltm in |
| 701 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] SUC_LT_THM in |
| 702 |
let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in |
| 703 |
let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in |
| 704 |
let th1 = SYM (MK_COMB ((AP_TERM lt_op_num suc_m), suc_n)) in |
| 705 |
TRANS (TRANS th1 th0) th;; |
| 706 |
|
| 707 |
let th_lt_table = Hashtbl.create (maximum * maximum);; |
| 708 |
|
| 709 |
for i = 0 to maximum - 1 do |
| 710 |
let th = ref (gen_bi_lt_bj 0 i) in |
| 711 |
let name_left = names_array.(0) and |
| 712 |
name_right = names_array.(i) in |
| 713 |
let _ = Hashtbl.add th_lt_table (name_left ^ name_right) !th in |
| 714 |
|
| 715 |
for k = 1 to maximum - i - 1 do |
| 716 |
let x = k and y = i + k in |
| 717 |
let name_left = names_array.(x) and |
| 718 |
name_right = names_array.(y) in |
| 719 |
th := gen_next_lt_thm (!th); |
| 720 |
Hashtbl.add th_lt_table (name_left ^ name_right) !th |
| 721 |
done; |
| 722 |
done;; |
| 723 |
|
| 724 |
for i = 1 to maximum - 1 do |
| 725 |
let th = ref (gen_bi_lt_bj i 0) in |
| 726 |
let name_left = names_array.(i) and |
| 727 |
name_right = names_array.(0) in |
| 728 |
let _ = Hashtbl.add th_lt_table (name_left ^ name_right) !th in |
| 729 |
|
| 730 |
for k = 1 to maximum - i - 1 do |
| 731 |
let x = i + k and y = k in |
| 732 |
let name_left = names_array.(x) and |
| 733 |
name_right = names_array.(y) in |
| 734 |
th := gen_next_lt_thm (!th); |
| 735 |
Hashtbl.add th_lt_table (name_left ^ name_right) !th |
| 736 |
done; |
| 737 |
done;; |
| 738 |
|
| 739 |
(* LE tables *) |
| 740 |
|
| 741 |
(* Generates the theorem |- bi(n) <= _0 <=> F (or |- b0(n) <= _0 <=> n <= _0) *) |
| 742 |
let gen_bi_le_0 i = |
| 743 |
let bin = mk_comb (const_array.(i), n_var_num) in |
| 744 |
let lt_tm = mk_binop le_op_num bin zero_num in |
| 745 |
if i > 0 then |
| 746 |
(PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, f_const), REWRITE_TAC[def_array.(i)] THEN ARITH_TAC) |
| 747 |
else |
| 748 |
(PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, `n <= 0`), REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);; |
| 749 |
|
| 750 |
let th_le0_table = Hashtbl.create maximum;; |
| 751 |
for i = 0 to maximum - 1 do |
| 752 |
let th = gen_bi_le_0 i in |
| 753 |
let name = names_array.(i) in |
| 754 |
Hashtbl.add th_le0_table name th |
| 755 |
done;; |
| 756 |
|
| 757 |
|
| 758 |
(* Generates the theorem |- bi(m) <= bj(n) <=> m <= n (or m < n) *) |
| 759 |
let gen_bi_le_bj i j = |
| 760 |
let bim = mk_comb (const_array.(i), m_var_num) in |
| 761 |
let bjn = mk_comb (const_array.(j), n_var_num) in |
| 762 |
let lt_tm = mk_binop le_op_num bim bjn in |
| 763 |
let rhs = |
| 764 |
if i > j then |
| 765 |
mk_binop lt_op_num m_var_num n_var_num |
| 766 |
else |
| 767 |
mk_binop le_op_num m_var_num n_var_num in |
| 768 |
prove(mk_eq(lt_tm, rhs), REWRITE_TAC[def_array.(i); def_array.(j)] THEN ARITH_TAC);; |
| 769 |
|
| 770 |
(* Given the theorem |- bi(m) <= bj(n) <=> P m n, generates the theorem |
| 771 |
|- SUC(bi(m)) <= SUC(bj(n)) <=> P m n *) |
| 772 |
let gen_next_le_thm th = |
| 773 |
let ltm, n_tm = (dest_comb o lhand o concl) th in |
| 774 |
let m_tm = rand ltm in |
| 775 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] SUC_LE_THM in |
| 776 |
let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in |
| 777 |
let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in |
| 778 |
let th1 = SYM (MK_COMB ((AP_TERM le_op_num suc_m), suc_n)) in |
| 779 |
TRANS (TRANS th1 th0) th;; |
| 780 |
|
| 781 |
let th_le_table = Hashtbl.create (maximum * maximum);; |
| 782 |
|
| 783 |
for i = 0 to maximum - 1 do |
| 784 |
let th = ref (gen_bi_le_bj 0 i) in |
| 785 |
let name_left = names_array.(0) and |
| 786 |
name_right = names_array.(i) in |
| 787 |
let _ = Hashtbl.add th_le_table (name_left ^ name_right) !th in |
| 788 |
|
| 789 |
for k = 1 to maximum - i - 1 do |
| 790 |
let x = k and y = i + k in |
| 791 |
let name_left = names_array.(x) and |
| 792 |
name_right = names_array.(y) in |
| 793 |
th := gen_next_le_thm (!th); |
| 794 |
Hashtbl.add th_le_table (name_left ^ name_right) !th |
| 795 |
done; |
| 796 |
done;; |
| 797 |
|
| 798 |
for i = 1 to maximum - 1 do |
| 799 |
let th = ref (gen_bi_le_bj i 0) in |
| 800 |
let name_left = names_array.(i) and |
| 801 |
name_right = names_array.(0) in |
| 802 |
let _ = Hashtbl.add th_le_table (name_left ^ name_right) !th in |
| 803 |
|
| 804 |
for k = 1 to maximum - i - 1 do |
| 805 |
let x = i + k and y = k in |
| 806 |
let name_left = names_array.(x) and |
| 807 |
name_right = names_array.(y) in |
| 808 |
th := gen_next_le_thm (!th); |
| 809 |
Hashtbl.add th_le_table (name_left ^ name_right) !th |
| 810 |
done; |
| 811 |
done;; |
| 812 |
|
| 813 |
(* Conversions *) |
| 814 |
|
| 815 |
let rec raw_lt_hash_conv tm = |
| 816 |
let ltm, rtm = dest_comb tm in |
| 817 |
let ltm = rand ltm in |
| 818 |
if is_const rtm then |
| 819 |
(* n < _0 <=> F *) |
| 820 |
INST[ltm, n_var_num] LT_n_0 |
| 821 |
else |
| 822 |
if is_const ltm then |
| 823 |
(* _0 < Bi(n) *) |
| 824 |
let bn_tm, n_tm = dest_comb rtm in |
| 825 |
let cbn = (fst o dest_const) bn_tm in |
| 826 |
let th0 = INST[n_tm, n_var_num] (Hashtbl.find th_lt0_table cbn) in |
| 827 |
if cbn = b0_name then |
| 828 |
let th1 = raw_lt_hash_conv (rand (concl th0)) in |
| 829 |
TRANS th0 th1 |
| 830 |
else |
| 831 |
th0 |
| 832 |
else |
| 833 |
(* Bi(n) < Bj(m) *) |
| 834 |
let bm_tm, m_tm = dest_comb ltm in |
| 835 |
let bn_tm, n_tm = dest_comb rtm in |
| 836 |
let cbm = (fst o dest_const) bm_tm in |
| 837 |
let cbn = (fst o dest_const) bn_tm in |
| 838 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_lt_table (cbm^cbn)) in |
| 839 |
let op = (fst o dest_const o rator o rator o rand o concl) th0 in |
| 840 |
let th1 = |
| 841 |
if op = "<" then |
| 842 |
raw_lt_hash_conv (rand (concl th0)) |
| 843 |
else |
| 844 |
raw_le_hash_conv (rand (concl th0)) in |
| 845 |
TRANS th0 th1 and |
| 846 |
|
| 847 |
raw_le_hash_conv tm = |
| 848 |
let ltm, rtm = dest_comb tm in |
| 849 |
let ltm = rand ltm in |
| 850 |
if is_const ltm then |
| 851 |
(* _0 <= n <=> T *) |
| 852 |
INST[rtm, n_var_num] LE_0_n |
| 853 |
else |
| 854 |
if is_const rtm then |
| 855 |
(* Bi(n) <= _0 *) |
| 856 |
let bn_tm, n_tm = dest_comb ltm in |
| 857 |
let cbn = (fst o dest_const) bn_tm in |
| 858 |
let th0 = INST[n_tm, n_var_num] (Hashtbl.find th_le0_table cbn) in |
| 859 |
if cbn = b0_name then |
| 860 |
let th1 = raw_le_hash_conv (rand (concl th0)) in |
| 861 |
TRANS th0 th1 |
| 862 |
else |
| 863 |
th0 |
| 864 |
else |
| 865 |
(* Bi(n) <= Bj(m) *) |
| 866 |
let bm_tm, m_tm = dest_comb ltm in |
| 867 |
let bn_tm, n_tm = dest_comb rtm in |
| 868 |
let cbm = (fst o dest_const) bm_tm in |
| 869 |
let cbn = (fst o dest_const) bn_tm in |
| 870 |
let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_le_table (cbm^cbn)) in |
| 871 |
let op = (fst o dest_const o rator o rator o rand o concl) th0 in |
| 872 |
let th1 = |
| 873 |
if op = "<" then |
| 874 |
raw_lt_hash_conv (rand (concl th0)) |
| 875 |
else |
| 876 |
raw_le_hash_conv (rand (concl th0)) in |
| 877 |
TRANS th0 th1;; |
| 878 |
|
| 879 |
let NUM_LT_HASH_CONV tm = |
| 880 |
let atm, rtm = dest_comb tm in |
| 881 |
let ltm = rand atm in |
| 882 |
let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] LT_NUM in |
| 883 |
let rtm = rand(concl th) in |
| 884 |
TRANS th (raw_lt_hash_conv rtm);; |
| 885 |
|
| 886 |
let NUM_LE_HASH_CONV tm = |
| 887 |
let atm, rtm = dest_comb tm in |
| 888 |
let ltm = rand atm in |
| 889 |
let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] LE_NUM in |
| 890 |
let rtm = rand(concl th) in |
| 891 |
TRANS th (raw_le_hash_conv rtm);; |
| 892 |
|
| 893 |
|
| 894 |
(**************************************) |
| 895 |
(* ADD_CONV *) |
| 896 |
|
| 897 |
(* ADD theorems *) |
| 898 |
|
| 899 |
let ADD_NUM = (REWRITE_RULE[GSYM num_def] o prove) |
| 900 |
(`NUMERAL m + NUMERAL n = NUMERAL (m + n)`, REWRITE_TAC[NUMERAL]);; |
| 901 |
|
| 902 |
|
| 903 |
let CADD_0_n = prove(`SUC (_0 + n) = SUC n`, REWRITE_TAC[ADD_0_n]);; |
| 904 |
let CADD_n_0 = prove(`SUC (n + _0) = SUC n`, REWRITE_TAC[ADD_n_0]);; |
| 905 |
|
| 906 |
(* B0 (SUC n) = B0 n + maximum *) |
| 907 |
let B0_SUC = prove(mk_eq(mk_comb(b0_const, mk_comb(suc_op_num, n_var_num)), |
| 908 |
mk_binop add_op_num max_const (mk_comb(b0_const, n_var_num))), |
| 909 |
REWRITE_TAC [B0_EXPLICIT] THEN ARITH_TAC);; |
| 910 |
|
| 911 |
let B0_ADD = prove(mk_eq(mk_binop add_op_num (mk_comb(b0_const, m_var_num)) (mk_comb(b0_const, n_var_num)), |
| 912 |
mk_comb(b0_const, mk_binop add_op_num m_var_num n_var_num)), |
| 913 |
REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);; |
| 914 |
|
| 915 |
let SUC_ADD_RIGHT = prove(`SUC(m + n) = m + SUC n`, ARITH_TAC);; |
| 916 |
|
| 917 |
|
| 918 |
(* Generate all theorems iteratively *) |
| 919 |
let th_add_right_next th = |
| 920 |
let lhs, rhs = dest_eq(concl th) in |
| 921 |
let ltm, rtm = dest_comb rhs in |
| 922 |
let cn = fst(dest_const ltm) in |
| 923 |
let suc_th = AP_TERM suc_op_num th in |
| 924 |
let th_rhs = INST[rtm, n_var_num] (Hashtbl.find th_suc_table cn) in |
| 925 |
let ltm, rarg = dest_comb lhs in |
| 926 |
let larg = rand ltm in |
| 927 |
let th1 = INST[larg, m_var_num; rarg, n_var_num] SUC_ADD_RIGHT in |
| 928 |
let cn = fst(dest_const(rator rarg)) in |
| 929 |
let th2 = Hashtbl.find th_suc_table cn in |
| 930 |
let th_lhs = TRANS th1 (AP_TERM ltm th2) in |
| 931 |
TRANS (TRANS (SYM th_lhs) suc_th) th_rhs;; |
| 932 |
|
| 933 |
let th_add_array = Array.make (maximum * maximum) (REFL zero_const);; |
| 934 |
|
| 935 |
for i = 0 to maximum - 1 do |
| 936 |
let th0 = |
| 937 |
if i = 0 then |
| 938 |
B0_ADD |
| 939 |
else |
| 940 |
INST[n_var_num, m_var_num; m_var_num, n_var_num] |
| 941 |
(ONCE_REWRITE_RULE[ADD_AC] th_add_array.(i)) in |
| 942 |
let _ = th_add_array.(i * maximum) <- th0 in |
| 943 |
|
| 944 |
for j = 1 to maximum - 1 do |
| 945 |
th_add_array.(i * maximum + j) <- th_add_right_next th_add_array.(i * maximum + j - 1) |
| 946 |
done; |
| 947 |
done;; |
| 948 |
|
| 949 |
(* SUC (B_i(m) + B_j(n)) = B_p(...) *) |
| 950 |
let th_cadd i j = |
| 951 |
let add_th = th_add_array.(i * maximum + j) in |
| 952 |
let th0 = AP_TERM suc_op_num add_th in |
| 953 |
let ltm, rtm = dest_comb(rand(concl th0)) in |
| 954 |
let ltm, rtm = dest_comb rtm in |
| 955 |
let cn = fst(dest_const ltm) in |
| 956 |
let suc_th = INST[rtm, n_var_num] (Hashtbl.find th_suc_table cn) in |
| 957 |
TRANS th0 suc_th;; |
| 958 |
|
| 959 |
let th_cadd_array = Array.make (maximum * maximum) (REFL zero_const);; |
| 960 |
|
| 961 |
for i = 0 to maximum - 1 do |
| 962 |
for j = 0 to maximum - 1 do |
| 963 |
th_cadd_array.(i * maximum + j) <- th_cadd i j |
| 964 |
done; |
| 965 |
done;; |
| 966 |
|
| 967 |
let th_add_table = Hashtbl.create (maximum * maximum);; |
| 968 |
|
| 969 |
for i = 0 to maximum - 1 do |
| 970 |
for j = 0 to maximum - 1 do |
| 971 |
let name = names_array.(i) ^ names_array.(j) in |
| 972 |
let th = th_add_array.(i * maximum + j) in |
| 973 |
let cflag = (i + j >= maximum) in |
| 974 |
Hashtbl.add th_add_table name (th, cflag) |
| 975 |
done; |
| 976 |
done;; |
| 977 |
|
| 978 |
let th_cadd_table = Hashtbl.create (maximum * maximum);; |
| 979 |
|
| 980 |
for i = 0 to maximum - 1 do |
| 981 |
for j = 0 to maximum - 1 do |
| 982 |
let name = names_array.(i) ^ names_array.(j) in |
| 983 |
let th = th_cadd_array.(i * maximum + j) in |
| 984 |
let cflag = (i + j + 1 >= maximum) in |
| 985 |
Hashtbl.add th_cadd_table name (th, cflag) |
| 986 |
done; |
| 987 |
done;; |
| 988 |
|
| 989 |
(* ADD conversion *) |
| 990 |
let rec raw_add_conv_hash tm = |
| 991 |
let atm,rtm = dest_comb tm in |
| 992 |
let ltm = rand atm in |
| 993 |
if ltm = zero_const then |
| 994 |
INST [rtm,n_var_num] ADD_0_n |
| 995 |
else if rtm = zero_const then |
| 996 |
INST [ltm,n_var_num] ADD_n_0 |
| 997 |
else |
| 998 |
let lbit,larg = dest_comb ltm |
| 999 |
and rbit,rarg = dest_comb rtm in |
| 1000 |
let name = fst(dest_const lbit) ^ fst(dest_const rbit) in |
| 1001 |
let th0, cflag = Hashtbl.find th_add_table name in |
| 1002 |
let th = INST [larg, m_var_num; rarg, n_var_num] th0 in |
| 1003 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1004 |
if cflag then |
| 1005 |
TRANS th (AP_TERM ltm (raw_adc_conv_hash rtm)) |
| 1006 |
else |
| 1007 |
TRANS th (AP_TERM ltm (raw_add_conv_hash rtm)) |
| 1008 |
and raw_adc_conv_hash tm = |
| 1009 |
let atm,rtm = dest_comb (rand tm) in |
| 1010 |
let ltm = rand atm in |
| 1011 |
if ltm = zero_const then |
| 1012 |
let th = INST [rtm,n_var_num] CADD_0_n in |
| 1013 |
TRANS th (raw_suc_conv_hash (rand(concl th))) |
| 1014 |
else if rtm = zero_const then |
| 1015 |
let th = INST [ltm,n_var_num] CADD_n_0 in |
| 1016 |
TRANS th (raw_suc_conv_hash (rand(concl th))) |
| 1017 |
else |
| 1018 |
let lbit,larg = dest_comb ltm |
| 1019 |
and rbit,rarg = dest_comb rtm in |
| 1020 |
let name = fst(dest_const lbit) ^ fst(dest_const rbit) in |
| 1021 |
let th0, cflag = Hashtbl.find th_cadd_table name in |
| 1022 |
let th = INST [larg, m_var_num; rarg, n_var_num] th0 in |
| 1023 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1024 |
if cflag then |
| 1025 |
TRANS th (AP_TERM ltm (raw_adc_conv_hash rtm)) |
| 1026 |
else |
| 1027 |
TRANS th (AP_TERM ltm (raw_add_conv_hash rtm));; |
| 1028 |
|
| 1029 |
let NUM_ADD_HASH_CONV tm = |
| 1030 |
let atm, rtm = dest_comb tm in |
| 1031 |
let ltm = rand atm in |
| 1032 |
let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] ADD_NUM in |
| 1033 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1034 |
TRANS th (AP_TERM ltm (raw_add_conv_hash rtm));; |
| 1035 |
|
| 1036 |
(********************************) |
| 1037 |
(* Subtraction *) |
| 1038 |
|
| 1039 |
let SUB_NUM = prove(mk_eq(mk_binop sub_op_num (mk_comb (num_const, m_var_num)) (mk_comb (num_const, n_var_num)), |
| 1040 |
mk_comb(num_const, mk_binop sub_op_num m_var_num n_var_num)), |
| 1041 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 1042 |
|
| 1043 |
let SUB_lemma1 = (UNDISCH_ALL o ARITH_RULE) `n + t = m ==> m - n = t:num`;; |
| 1044 |
let SUB_lemma2 = (UNDISCH_ALL o REWRITE_RULE[NUMERAL] o ARITH_RULE) `m + t = n ==> m - n = 0`;; |
| 1045 |
let LE_lemma = (UNDISCH_ALL o ARITH_RULE) `n + t = m ==> n <= m:num`;; |
| 1046 |
|
| 1047 |
let raw_sub_hash_conv tm = |
| 1048 |
let ltm, n_tm = dest_comb tm in |
| 1049 |
let m_tm = rand ltm in |
| 1050 |
let m = raw_dest_hash m_tm in |
| 1051 |
let n = raw_dest_hash n_tm in |
| 1052 |
let t = m -/ n in |
| 1053 |
if t >=/ num_0 then |
| 1054 |
let t_tm = rand (mk_numeral_array t) in |
| 1055 |
let th0 = INST[n_tm, n_var_num; t_tm, t_var_num; m_tm, m_var_num] SUB_lemma1 in |
| 1056 |
let th_add = raw_add_conv_hash (mk_binop add_op_num n_tm t_tm) in |
| 1057 |
MY_PROVE_HYP th_add th0 |
| 1058 |
else |
| 1059 |
let t_tm = rand (mk_numeral_array (Num.abs_num t)) in |
| 1060 |
let th0 = INST[m_tm, m_var_num; t_tm, t_var_num; n_tm, n_var_num] SUB_lemma2 in |
| 1061 |
let th_add = raw_add_conv_hash (mk_binop add_op_num m_tm t_tm) in |
| 1062 |
MY_PROVE_HYP th_add th0;; |
| 1063 |
|
| 1064 |
(* Returns either (tm1 - tm2, tm2 <= tm1) or (tm2 - tm1, tm1 <= tm2) *) |
| 1065 |
let raw_sub_and_le_hash_conv tm1 tm2 = |
| 1066 |
let m = raw_dest_hash tm1 in |
| 1067 |
let n = raw_dest_hash tm2 in |
| 1068 |
let t = m -/ n in |
| 1069 |
if t >=/ num_0 then |
| 1070 |
let t_tm = rand (mk_numeral_array t) in |
| 1071 |
let inst = INST[tm2, n_var_num; t_tm, t_var_num; tm1, m_var_num] in |
| 1072 |
let th_sub = inst SUB_lemma1 in |
| 1073 |
let th_le = inst LE_lemma in |
| 1074 |
let th_add = raw_add_conv_hash (mk_binop add_op_num tm2 t_tm) in |
| 1075 |
(MY_PROVE_HYP th_add th_sub, MY_PROVE_HYP th_add th_le) |
| 1076 |
else |
| 1077 |
let t_tm = rand (mk_numeral_array (Num.abs_num t)) in |
| 1078 |
let inst = INST[tm2, m_var_num; t_tm, t_var_num; tm1, n_var_num] in |
| 1079 |
let th_sub = inst SUB_lemma1 in |
| 1080 |
let th_le = inst LE_lemma in |
| 1081 |
let th_add = raw_add_conv_hash (mk_binop add_op_num tm1 t_tm) in |
| 1082 |
(MY_PROVE_HYP th_add th_sub, MY_PROVE_HYP th_add th_le);; |
| 1083 |
|
| 1084 |
let NUM_SUB_HASH_CONV tm = |
| 1085 |
let atm, rtm = dest_comb tm in |
| 1086 |
let ltm = rand atm in |
| 1087 |
let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] SUB_NUM in |
| 1088 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1089 |
TRANS th (AP_TERM ltm (raw_sub_hash_conv rtm));; |
| 1090 |
|
| 1091 |
|
| 1092 |
(********************************) |
| 1093 |
(* Multiplication *) |
| 1094 |
|
| 1095 |
let MUL_NUM = prove(mk_eq(mk_binop mul_op_num (mk_comb(num_const, m_var_num)) (mk_comb(num_const, n_var_num)), |
| 1096 |
mk_comb(num_const, mk_binop mul_op_num m_var_num n_var_num)), |
| 1097 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 1098 |
|
| 1099 |
let MUL_0_n = prove(`_0 * n = _0`, ONCE_REWRITE_TAC[GSYM NUM_THM] THEN |
| 1100 |
ONCE_REWRITE_TAC[GSYM MUL_NUM] THEN REWRITE_TAC[num_def] THEN |
| 1101 |
REWRITE_TAC[MULT_CLAUSES]);; |
| 1102 |
|
| 1103 |
let MUL_n_0 = ONCE_REWRITE_RULE[MULT_AC] MUL_0_n;; |
| 1104 |
|
| 1105 |
let MUL_1_n, MUL_n_1 = |
| 1106 |
let one_const = mk_comb (const_array.(1), zero_num) in |
| 1107 |
let cond = mk_eq(mk_binop mul_op_num one_const n_var_num, n_var_num) in |
| 1108 |
let th = (REWRITE_RULE[NUMERAL] o prove)(cond, REWRITE_TAC[def_array.(1)] THEN ARITH_TAC) in |
| 1109 |
th, ONCE_REWRITE_RULE[MULT_AC] th;; |
| 1110 |
|
| 1111 |
let MUL_B0_t = prove(mk_eq(mk_binop mul_op_num (mk_comb(b0_const, n_var_num)) t_var_num, |
| 1112 |
mk_comb(b0_const, mk_binop mul_op_num n_var_num t_var_num)), |
| 1113 |
REWRITE_TAC[def_array.(0)] THEN ARITH_TAC);; |
| 1114 |
|
| 1115 |
let MUL_t_B0 = ONCE_REWRITE_RULE[MULT_AC] MUL_B0_t;; |
| 1116 |
|
| 1117 |
let MUL_SUC_RIGHT = prove(`m * SUC(n) = m * n + m`, ARITH_TAC);; |
| 1118 |
|
| 1119 |
(* Multiplication table *) |
| 1120 |
let mul_th_next_right th = |
| 1121 |
let ltm, rtm = dest_comb(rand(rator(concl th))) in |
| 1122 |
let mtm = rand ltm in |
| 1123 |
let th0 = INST[mtm, m_var_num; rtm, n_var_num] MUL_SUC_RIGHT in |
| 1124 |
let th1 = AP_THM (AP_TERM add_op_num th) mtm in |
| 1125 |
let sum_th = raw_add_conv_hash (rand(concl th1)) in |
| 1126 |
let th2 = TRANS (TRANS th0 th1) sum_th in |
| 1127 |
let cn = fst(dest_const (rator rtm)) in |
| 1128 |
let th_suc = INST[zero_const, n_var_num] (Hashtbl.find th_suc_table cn) in |
| 1129 |
let th3 = AP_TERM (mk_comb (mul_op_num, mtm)) th_suc in |
| 1130 |
TRANS (SYM th3) th2;; |
| 1131 |
|
| 1132 |
let mul_array = Array.make (maximum * maximum) (REFL zero_const);; |
| 1133 |
for i = 1 to maximum - 1 do |
| 1134 |
let th1 = INST[mk_comb(const_array.(i), zero_const), n_var_num] MUL_n_1 in |
| 1135 |
let _ = mul_array.(i * maximum + 1) <- th1 in |
| 1136 |
|
| 1137 |
for j = 2 to maximum - 1 do |
| 1138 |
mul_array.(i * maximum + j) <- mul_th_next_right mul_array.(i * maximum + j - 1) |
| 1139 |
done; |
| 1140 |
done;; |
| 1141 |
|
| 1142 |
let mul_table = Hashtbl.create (maximum * maximum);; |
| 1143 |
for i = 1 to maximum - 1 do |
| 1144 |
for j = 1 to maximum - 1 do |
| 1145 |
Hashtbl.add mul_table (names_array.(i) ^ names_array.(j)) mul_array.(i * maximum + j) |
| 1146 |
done; |
| 1147 |
done;; |
| 1148 |
|
| 1149 |
(* General multiplication theorem *) |
| 1150 |
let prod_lemma = |
| 1151 |
let mul (a,b) = mk_binop mul_op_num a b and |
| 1152 |
add (a,b) = mk_binop add_op_num a b in |
| 1153 |
let lhs = mul(add(t_var_num, mk_comb(b0_const, m_var_num)), |
| 1154 |
add(r_var_num, mk_comb(b0_const, n_var_num))) in |
| 1155 |
let rhs = add(mul(t_var_num, r_var_num), |
| 1156 |
mk_comb(b0_const, add(mk_comb(b0_const, mul(m_var_num, n_var_num)), |
| 1157 |
add(mul(m_var_num, r_var_num), |
| 1158 |
mul(n_var_num, t_var_num))))) in |
| 1159 |
prove(mk_eq(lhs, rhs), |
| 1160 |
REWRITE_TAC[LEFT_ADD_DISTRIB; RIGHT_ADD_DISTRIB] THEN |
| 1161 |
REWRITE_TAC[MUL_B0_t; MUL_t_B0] THEN |
| 1162 |
ONCE_REWRITE_TAC[GSYM ADD_ASSOC] THEN |
| 1163 |
REWRITE_TAC[th_add_array.(0)] THEN |
| 1164 |
REWRITE_TAC[ADD_AC; MULT_AC]);; |
| 1165 |
|
| 1166 |
let ADD_ASSOC' = SPEC_ALL ADD_ASSOC;; |
| 1167 |
|
| 1168 |
let dest_op tm = |
| 1169 |
let ltm, rtm = dest_comb tm in |
| 1170 |
rand ltm, rtm;; |
| 1171 |
|
| 1172 |
(* B_i(m) * B_j(n) = B_p(B_q(m * n) + m * B_j(0) + n * B_i(0)) |
| 1173 |
where B_p(B_q(0)) = i * j *) |
| 1174 |
let gen_mul_thm i j = |
| 1175 |
let bi0 = mk_comb(const_array.(i), zero_const) and |
| 1176 |
bj0 = mk_comb(const_array.(j), zero_const) in |
| 1177 |
let def_i = INST[m_var_num, n_var_num] def_thm_array.(i) in |
| 1178 |
let def_j = def_thm_array.(j) in |
| 1179 |
let th0 = MK_COMB(AP_TERM mul_op_num def_i, def_j) in |
| 1180 |
let th1 = TRANS th0 (INST[bi0, t_var_num; bj0, r_var_num] prod_lemma) in |
| 1181 |
let mul_th = mul_array.(i * maximum + j) in |
| 1182 |
let larg, rarg = dest_op (rand (concl th1)) in |
| 1183 |
let th2 = TRANS th1 (AP_THM (AP_TERM add_op_num mul_th) rarg) in |
| 1184 |
let larg = rand(concl mul_th) in |
| 1185 |
let b_low, b_high = dest_comb larg in |
| 1186 |
let rtm = rand(rarg) in |
| 1187 |
let th_add = INST[b_high, m_var_num; rtm, n_var_num] |
| 1188 |
(fst(Hashtbl.find th_add_table (fst(dest_const b_low)^b0_name))) in |
| 1189 |
if i * j < maximum then |
| 1190 |
let ltm, rtm = dest_op(rand(rand(concl th_add))) in |
| 1191 |
let add_0 = AP_TERM b_low (INST[rtm, n_var_num] ADD_0_n) in |
| 1192 |
TRANS th2 (TRANS th_add add_0) |
| 1193 |
else |
| 1194 |
let larg, rtm = dest_op (rand(rand(concl th_add))) in |
| 1195 |
let rarg, rtm = dest_op rtm in |
| 1196 |
let th_assoc = INST[larg, m_var_num; rarg, n_var_num; rtm, p_var_num] ADD_ASSOC' in |
| 1197 |
let mn = rand(rarg) in |
| 1198 |
let b_high = rator b_high in |
| 1199 |
let th_add2' = INST[zero_const, m_var_num; mn, n_var_num] |
| 1200 |
(fst(Hashtbl.find th_add_table (fst(dest_const b_high)^b0_name))) in |
| 1201 |
let add_0 = AP_TERM b_high (INST[mn, n_var_num] ADD_0_n) in |
| 1202 |
let th_add2 = TRANS th_add2' add_0 in |
| 1203 |
let th3 = TRANS th_assoc (AP_THM (AP_TERM add_op_num th_add2) rtm) in |
| 1204 |
let th4 = TRANS th_add (AP_TERM b_low th3) in |
| 1205 |
TRANS th2 th4;; |
| 1206 |
|
| 1207 |
let gen_mul_table = Hashtbl.create (maximum * maximum);; |
| 1208 |
|
| 1209 |
for i = 1 to maximum - 1 do |
| 1210 |
for j = 1 to maximum - 1 do |
| 1211 |
let name = names_array.(i) ^ names_array.(j) in |
| 1212 |
Hashtbl.add gen_mul_table name (gen_mul_thm i j) |
| 1213 |
done; |
| 1214 |
done;; |
| 1215 |
|
| 1216 |
(* B_i(m) * B_j(0) = B_p(B_q(0) + m * B_j(0)) |
| 1217 |
where i * j = B_p(B_q(0)) *) |
| 1218 |
let mul1_right_th i j = |
| 1219 |
let th0 = INST[zero_const, n_var_num] |
| 1220 |
(Hashtbl.find gen_mul_table (names_array.(i)^names_array.(j))) in |
| 1221 |
let b_low, rtm = dest_comb(rand(concl th0)) in |
| 1222 |
let tm1, tm23 = dest_op rtm in |
| 1223 |
let tm2p, tm3 = dest_comb tm23 in |
| 1224 |
let tm3_th = INST[rand tm3, n_var_num] MUL_0_n in |
| 1225 |
let tm2_th = INST[rand(tm2p), n_var_num] ADD_n_0 in |
| 1226 |
let tm23_th = TRANS (AP_TERM tm2p tm3_th) tm2_th in |
| 1227 |
let ltm, rtm = dest_comb tm1 in |
| 1228 |
if (i * j < maximum) then |
| 1229 |
let tm1_th = TRANS (AP_TERM ltm (INST[m_var_num, n_var_num] MUL_n_0)) B0_0 in |
| 1230 |
let tm123_th' = TRANS (INST[tm23, n_var_num] ADD_0_n) tm23_th in |
| 1231 |
let tm123_th = TRANS (AP_THM (AP_TERM add_op_num tm1_th) tm23) tm123_th' in |
| 1232 |
TRANS th0 (AP_TERM b_low tm123_th) |
| 1233 |
else |
| 1234 |
let tm1_th = AP_TERM ltm (INST[m_var_num, n_var_num] MUL_n_0) in |
| 1235 |
let tm123_th = MK_COMB(AP_TERM add_op_num tm1_th, tm23_th) in |
| 1236 |
TRANS th0 (AP_TERM b_low tm123_th);; |
| 1237 |
|
| 1238 |
(* B_j(0) * B_i(m) = B_p(B_q(0) + B_j(0) * B_i(m) *) |
| 1239 |
let MULT_AC' = CONJUNCT1 MULT_AC;; |
| 1240 |
|
| 1241 |
let mul1_left_th th = |
| 1242 |
let lhs, rhs = dest_eq(concl th) in |
| 1243 |
let ltm, rtm = dest_op lhs in |
| 1244 |
let th_lhs = INST[ltm, n_var_num; rtm, m_var_num] MULT_AC' in |
| 1245 |
let btm, rtm = dest_comb rhs in |
| 1246 |
let larg, rarg = dest_op rtm in |
| 1247 |
if (is_comb larg) then |
| 1248 |
let ltm, rtm = dest_op rarg in |
| 1249 |
let th_rhs' = INST[ltm, m_var_num; rtm, n_var_num] MULT_AC' in |
| 1250 |
let th_rhs = AP_TERM (mk_comb(add_op_num, larg)) th_rhs' in |
| 1251 |
TRANS th_lhs (TRANS th (AP_TERM btm th_rhs)) |
| 1252 |
else |
| 1253 |
let th_rhs = INST[larg, m_var_num; rarg, n_var_num] MULT_AC' in |
| 1254 |
TRANS th_lhs (TRANS th (AP_TERM btm th_rhs));; |
| 1255 |
|
| 1256 |
let mul1_right_th_table = Hashtbl.create (maximum * maximum);; |
| 1257 |
let mul1_left_th_table = Hashtbl.create (maximum * maximum);; |
| 1258 |
|
| 1259 |
for i = 1 to maximum - 1 do |
| 1260 |
for j = 1 to maximum - 1 do |
| 1261 |
let name_right = names_array.(i) ^ names_array.(j) in |
| 1262 |
let name_left = names_array.(j) ^ names_array.(i) in |
| 1263 |
let th = mul1_right_th i j in |
| 1264 |
let add_flag = (i * j >= maximum) in |
| 1265 |
let _ = Hashtbl.add mul1_right_th_table name_right (add_flag, th) in |
| 1266 |
Hashtbl.add mul1_left_th_table name_left (add_flag, mul1_left_th th) |
| 1267 |
done; |
| 1268 |
done;; |
| 1269 |
|
| 1270 |
|
| 1271 |
(******************************************************) |
| 1272 |
(* Conversions *) |
| 1273 |
|
| 1274 |
(* Multiplies arg and (tm = tmname(_0)) *) |
| 1275 |
let rec raw_mul1_right_hash arg tm tmname = |
| 1276 |
if arg = zero_const then |
| 1277 |
INST [tm, n_var_num] MUL_0_n |
| 1278 |
else |
| 1279 |
let btm, mtm = dest_comb arg in |
| 1280 |
let cn = fst(dest_const btm) in |
| 1281 |
if (cn = b0_name) then |
| 1282 |
let th = INST[mtm, n_var_num; tm, t_var_num] MUL_B0_t in |
| 1283 |
TRANS th (AP_TERM b0_const (raw_mul1_right_hash mtm tm tmname)) |
| 1284 |
else |
| 1285 |
let name = cn ^ tmname in |
| 1286 |
if (mtm = zero_const) then |
| 1287 |
Hashtbl.find mul_table name |
| 1288 |
else |
| 1289 |
let add_flag, th' = Hashtbl.find mul1_right_th_table name in |
| 1290 |
let th = INST[mtm, m_var_num] th' in |
| 1291 |
if add_flag then |
| 1292 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1293 |
let lplus, rarg = dest_comb rtm in |
| 1294 |
let th2 = AP_TERM lplus (raw_mul1_right_hash mtm tm tmname) in |
| 1295 |
let th_add = raw_add_conv_hash (rand(concl th2)) in |
| 1296 |
TRANS th (AP_TERM ltm (TRANS th2 th_add)) |
| 1297 |
else |
| 1298 |
let ltm = rator(rand(concl th)) in |
| 1299 |
let th2 = AP_TERM ltm (raw_mul1_right_hash mtm tm tmname) in |
| 1300 |
TRANS th th2;; |
| 1301 |
|
| 1302 |
(* Multiplies (tm = tmname(_0)) and arg *) |
| 1303 |
let rec raw_mul1_left_hash tm tmname arg = |
| 1304 |
if arg = zero_const then |
| 1305 |
INST [tm, n_var_num] MUL_n_0 |
| 1306 |
else |
| 1307 |
let btm, mtm = dest_comb arg in |
| 1308 |
let cn = fst(dest_const btm) in |
| 1309 |
if (cn = b0_name) then |
| 1310 |
let th = INST[mtm, n_var_num; tm, t_var_num] MUL_t_B0 in |
| 1311 |
TRANS th (AP_TERM b0_const (raw_mul1_left_hash tm tmname mtm)) |
| 1312 |
else |
| 1313 |
let name = tmname ^ cn in |
| 1314 |
if (mtm = zero_const) then |
| 1315 |
Hashtbl.find mul_table name |
| 1316 |
else |
| 1317 |
let add_flag, th' = Hashtbl.find mul1_left_th_table name in |
| 1318 |
let th = INST[mtm, m_var_num] th' in |
| 1319 |
if add_flag then |
| 1320 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1321 |
let lplus, rarg = dest_comb rtm in |
| 1322 |
let th2 = AP_TERM lplus (raw_mul1_left_hash tm tmname mtm) in |
| 1323 |
let th_add = raw_add_conv_hash (rand(concl th2)) in |
| 1324 |
TRANS th (AP_TERM ltm (TRANS th2 th_add)) |
| 1325 |
else |
| 1326 |
let ltm = rator(rand(concl th)) in |
| 1327 |
let th2 = AP_TERM ltm (raw_mul1_left_hash tm tmname mtm) in |
| 1328 |
TRANS th th2;; |
| 1329 |
|
| 1330 |
(* Computes B_i(m) * B_j(n) *) |
| 1331 |
let rec raw_mul_conv_hash tm = |
| 1332 |
let larg, rarg = dest_comb tm in |
| 1333 |
let larg = rand larg in |
| 1334 |
if larg = zero_const then |
| 1335 |
INST [rarg, n_var_num] MUL_0_n |
| 1336 |
else if rarg = zero_const then |
| 1337 |
INST [larg, n_var_num] MUL_n_0 |
| 1338 |
else |
| 1339 |
|
| 1340 |
let lbtm, mtm = dest_comb larg in |
| 1341 |
let lcn = fst(dest_const lbtm) in |
| 1342 |
if (lcn = b0_name) then |
| 1343 |
let th = INST[rarg, t_var_num; mtm, n_var_num] MUL_B0_t in |
| 1344 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1345 |
TRANS th (AP_TERM ltm (raw_mul_conv_hash rtm)) |
| 1346 |
else |
| 1347 |
let rbtm, ntm = dest_comb rarg in |
| 1348 |
let rcn = fst(dest_const rbtm) in |
| 1349 |
if (rcn = b0_name) then |
| 1350 |
let th = INST[larg, t_var_num; ntm, n_var_num] MUL_t_B0 in |
| 1351 |
let ltm, rtm = dest_comb(rand(concl th)) in |
| 1352 |
TRANS th (AP_TERM ltm (raw_mul_conv_hash rtm)) |
| 1353 |
else |
| 1354 |
|
| 1355 |
if (ntm = zero_const) then |
| 1356 |
if (mtm = zero_const) then |
| 1357 |
Hashtbl.find mul_table (lcn ^ rcn) |
| 1358 |
else |
| 1359 |
raw_mul1_right_hash larg (mk_comb(rbtm, zero_const)) rcn |
| 1360 |
else if (mtm = zero_const) then |
| 1361 |
raw_mul1_left_hash (mk_comb(lbtm, zero_const)) lcn rarg |
| 1362 |
else |
| 1363 |
|
| 1364 |
let th0 = INST[mtm, m_var_num; ntm, n_var_num] |
| 1365 |
(Hashtbl.find gen_mul_table (lcn ^ rcn)) in |
| 1366 |
let b_low, expr = dest_comb(rand(concl th0)) in |
| 1367 |
let ltm, rsum = dest_comb expr in |
| 1368 |
let b_high, mul0 = dest_comb (rand ltm) in |
| 1369 |
let th_mul0 = raw_mul_conv_hash mul0 in |
| 1370 |
let th_mul1 = raw_mul1_right_hash mtm (mk_comb(rbtm, zero_const)) rcn in |
| 1371 |
let th_mul2 = raw_mul1_right_hash ntm (mk_comb(lbtm, zero_const)) lcn in |
| 1372 |
let th_larg = AP_TERM add_op_num (AP_TERM b_high th_mul0) in |
| 1373 |
let th_rarg = MK_COMB(AP_TERM add_op_num th_mul1, th_mul2) in |
| 1374 |
|
| 1375 |
let add_rarg = TRANS th_rarg (raw_add_conv_hash (rand(concl th_rarg))) in |
| 1376 |
let add_th = MK_COMB (th_larg, add_rarg) in |
| 1377 |
let add = TRANS add_th (raw_add_conv_hash (rand(concl add_th))) in |
| 1378 |
|
| 1379 |
TRANS th0 (AP_TERM b_low add);; |
| 1380 |
|
| 1381 |
(* The main multiplication conversion *) |
| 1382 |
let NUM_MULT_HASH_CONV tm = |
| 1383 |
let ltm, rtm = dest_comb tm in |
| 1384 |
let larg, rarg = rand (rand ltm), rand rtm in |
| 1385 |
let th0 = INST[larg, m_var_num; rarg, n_var_num] MUL_NUM in |
| 1386 |
if (rand(rator(concl th0)) <> tm) then |
| 1387 |
failwith "NUM_MULT_HASH_CONV" |
| 1388 |
else |
| 1389 |
let rtm = rand(rand(concl th0)) in |
| 1390 |
let th = raw_mul_conv_hash rtm in |
| 1391 |
TRANS th0 (AP_TERM num_const th);; |
| 1392 |
|
| 1393 |
|
| 1394 |
(************************************) |
| 1395 |
(* DIV *) |
| 1396 |
|
| 1397 |
let DIV_NUM = prove(mk_eq(mk_binop div_op_num (mk_comb(num_const, m_var_num)) (mk_comb(num_const, n_var_num)), |
| 1398 |
mk_comb(num_const, mk_binop div_op_num m_var_num n_var_num)), |
| 1399 |
REWRITE_TAC[num_def; NUMERAL]);; |
| 1400 |
|
| 1401 |
let DIV_UNIQ' = (UNDISCH_ALL o |
| 1402 |
PURE_ONCE_REWRITE_RULE[ARITH_RULE `a < b <=> (a < b:num <=> T)`] o |
| 1403 |
ONCE_REWRITE_RULE[ARITH_RULE `m = q * n + r <=> q * n + r = m:num`] o |
| 1404 |
REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) DIV_UNIQ;; |
| 1405 |
|
| 1406 |
(* Computes m DIV n *) |
| 1407 |
let raw_div_hash_conv tm = |
| 1408 |
let ltm, n_tm = dest_comb tm in |
| 1409 |
let m_tm = rand ltm in |
| 1410 |
let m = raw_dest_hash m_tm in |
| 1411 |
let n = raw_dest_hash n_tm in |
| 1412 |
let q = Num.quo_num m n and |
| 1413 |
r = Num.mod_num m n in |
| 1414 |
let q_tm = rand (mk_numeral_array q) and |
| 1415 |
r_tm = rand (mk_numeral_array r) in |
| 1416 |
|
| 1417 |
let qn_th = raw_mul_conv_hash (mk_binop mul_op_num q_tm n_tm) in |
| 1418 |
let qn_tm = rand (concl qn_th) in |
| 1419 |
let qnr_th = raw_add_conv_hash (mk_binop add_op_num qn_tm r_tm) in |
| 1420 |
let th1 = TRANS (AP_THM (AP_TERM add_op_num qn_th) r_tm) qnr_th in |
| 1421 |
let th2 = raw_lt_hash_conv (mk_binop lt_op_num r_tm n_tm) in |
| 1422 |
let th0 = INST[r_tm, r_var_num; n_tm, n_var_num; m_tm, m_var_num; q_tm, q_var_num] DIV_UNIQ' in |
| 1423 |
MY_PROVE_HYP th1 (MY_PROVE_HYP th2 th0);; |
| 1424 |
|
| 1425 |
(* The main division conversion *) |
| 1426 |
let NUM_DIV_HASH_CONV tm = |
| 1427 |
let ltm, rtm = dest_comb tm in |
| 1428 |
let larg, rarg = rand (rand ltm), rand rtm in |
| 1429 |
let th0 = INST[larg, m_var_num; rarg, n_var_num] DIV_NUM in |
| 1430 |
if (rand(rator(concl th0)) <> tm) then |
| 1431 |
failwith "NUM_DIV_HASH_CONV" |
| 1432 |
else |
| 1433 |
let rtm = rand(rand(concl th0)) in |
| 1434 |
let th = raw_div_hash_conv rtm in |
| 1435 |
TRANS th0 (AP_TERM num_const th);; |
| 1436 |
|
| 1437 |
|
| 1438 |
(*********************************************) |
| 1439 |
(* EVEN_CONV, ODD_CONV *) |
| 1440 |
|
| 1441 |
let even_const = `EVEN` and |
| 1442 |
odd_const = `ODD` and |
| 1443 |
eq_const = `<=>`;; |
| 1444 |
|
| 1445 |
let EVEN_NUM = (REWRITE_RULE[GSYM num_def] o prove) |
| 1446 |
(`EVEN (NUMERAL n) <=> EVEN n`, REWRITE_TAC[NUMERAL]);; |
| 1447 |
|
| 1448 |
let ODD_NUM = (REWRITE_RULE[GSYM num_def] o prove) |
| 1449 |
(`ODD (NUMERAL n) <=> ODD n`, REWRITE_TAC[NUMERAL]);; |
| 1450 |
|
| 1451 |
let EVEN_ZERO = prove(`EVEN _0 <=> T`, REWRITE_TAC[ARITH_EVEN]);; |
| 1452 |
let ODD_ZERO = prove(`ODD _0 <=> F`, REWRITE_TAC[ARITH_ODD]);; |
| 1453 |
|
| 1454 |
|
| 1455 |
let EVEN_B0 = prove(mk_eq(mk_comb(`EVEN`, mk_comb(b0_const, `n:num`)), `T`), |
| 1456 |
REWRITE_TAC[B0_EXPLICIT; EVEN_MULT] THEN |
| 1457 |
DISJ1_TAC THEN CONV_TAC NUM_EVEN_CONV);; |
| 1458 |
|
| 1459 |
|
| 1460 |
let ODD_B0 = prove(mk_eq(mk_comb(`ODD`, mk_comb(b0_const, `n:num`)), `F`), |
| 1461 |
REWRITE_TAC[NOT_ODD; EVEN_B0]);; |
| 1462 |
|
| 1463 |
let EVEN_SUC_T = prove(`(EVEN (SUC n) <=> T) <=> (EVEN n <=> F)`, REWRITE_TAC[EVEN]);; |
| 1464 |
let EVEN_SUC_F = prove(`(EVEN (SUC n) <=> F) <=> (EVEN n <=> T)`, REWRITE_TAC[EVEN]);; |
| 1465 |
|
| 1466 |
let ODD_SUC_T = prove(`(ODD (SUC n) <=> T) <=> (ODD n <=> F)`, REWRITE_TAC[ODD]);; |
| 1467 |
let ODD_SUC_F = prove(`(ODD (SUC n) <=> F) <=> (ODD n <=> T)`, REWRITE_TAC[ODD]);; |
| 1468 |
|
| 1469 |
let next_even_th th = |
| 1470 |
let ltm, rtm = dest_comb(concl th) in |
| 1471 |
let b_tm = rand(rand ltm) in |
| 1472 |
let suc_b = raw_suc_conv_hash (mk_comb (suc_op_num, b_tm)) in |
| 1473 |
let flag = (fst o dest_const) rtm = "T" in |
| 1474 |
let th0 = SYM (AP_TERM even_const suc_b) in |
| 1475 |
let th1 = AP_THM (AP_TERM eq_const th0) (if flag then f_const else t_const) in |
| 1476 |
let th2 = INST[b_tm, n_var_num] (if flag then EVEN_SUC_F else EVEN_SUC_T) in |
| 1477 |
EQ_MP (SYM (TRANS th1 th2)) th;; |
| 1478 |
|
| 1479 |
let next_odd_th th = |
| 1480 |
let ltm, rtm = dest_comb(concl th) in |
| 1481 |
let b_tm = rand(rand ltm) in |
| 1482 |
let suc_b = raw_suc_conv_hash (mk_comb (suc_op_num, b_tm)) in |
| 1483 |
let flag = (fst o dest_const) rtm = "T" in |
| 1484 |
let th0 = SYM (AP_TERM odd_const suc_b) in |
| 1485 |
let th1 = AP_THM (AP_TERM eq_const th0) (if flag then f_const else t_const) in |
| 1486 |
let th2 = INST[b_tm, n_var_num] (if flag then ODD_SUC_F else ODD_SUC_T) in |
| 1487 |
EQ_MP (SYM (TRANS th1 th2)) th;; |
| 1488 |
|
| 1489 |
let even_thm_table = Hashtbl.create maximum;; |
| 1490 |
|
| 1491 |
Hashtbl.add even_thm_table names_array.(0) EVEN_B0;; |
| 1492 |
|
| 1493 |
for i = 1 to maximum - 1 do |
| 1494 |
let th0 = next_even_th (Hashtbl.find even_thm_table names_array.(i - 1)) in |
| 1495 |
Hashtbl.add even_thm_table names_array.(i) th0 |
| 1496 |
done;; |
| 1497 |
|
| 1498 |
let odd_thm_table = Hashtbl.create maximum;; |
| 1499 |
Hashtbl.add odd_thm_table names_array.(0) ODD_B0;; |
| 1500 |
|
| 1501 |
for i = 1 to maximum - 1 do |
| 1502 |
let th0 = next_odd_th (Hashtbl.find odd_thm_table names_array.(i - 1)) in |
| 1503 |
Hashtbl.add odd_thm_table names_array.(i) th0 |
| 1504 |
done;; |
| 1505 |
|
| 1506 |
let raw_even_hash_conv tm = |
| 1507 |
let ltm, rtm = dest_comb tm in |
| 1508 |
if ((fst o dest_const) ltm <> "EVEN") then |
| 1509 |
failwith "raw_even_hash_conv: no EVEN" |
| 1510 |
else |
| 1511 |
if (is_const rtm) then |
| 1512 |
EVEN_ZERO |
| 1513 |
else |
| 1514 |
let b_tm, n_tm = dest_comb rtm in |
| 1515 |
let th0 = Hashtbl.find even_thm_table ((fst o dest_const) b_tm) in |
| 1516 |
INST[n_tm, n_var_num] th0;; |
| 1517 |
|
| 1518 |
let raw_odd_hash_conv tm = |
| 1519 |
let ltm, rtm = dest_comb tm in |
| 1520 |
if ((fst o dest_const) ltm <> "ODD") then |
| 1521 |
failwith "raw_odd_hash_conv: no ODD" |
| 1522 |
else |
| 1523 |
if (is_const rtm) then |
| 1524 |
ODD_ZERO |
| 1525 |
else |
| 1526 |
let b_tm, n_tm = dest_comb rtm in |
| 1527 |
let th0 = Hashtbl.find odd_thm_table ((fst o dest_const) b_tm) in |
| 1528 |
INST[n_tm, n_var_num] th0;; |
| 1529 |
|
| 1530 |
let NUM_EVEN_HASH_CONV tm = |
| 1531 |
let ltm, rtm = dest_comb tm in |
| 1532 |
let th0 = INST[rand rtm, n_var_num] EVEN_NUM in |
| 1533 |
let ltm, rtm = dest_comb(concl th0) in |
| 1534 |
if (rand ltm <> tm) then |
| 1535 |
failwith "NUM_EVEN_HASH_CONV" |
| 1536 |
else |
| 1537 |
let th1 = raw_even_hash_conv rtm in |
| 1538 |
TRANS th0 th1;; |
| 1539 |
|
| 1540 |
let NUM_ODD_HASH_CONV tm = |
| 1541 |
let ltm, rtm = dest_comb tm in |
| 1542 |
let th0 = INST[rand rtm, n_var_num] ODD_NUM in |
| 1543 |
let ltm, rtm = dest_comb(concl th0) in |
| 1544 |
if (rand ltm <> tm) then |
| 1545 |
failwith "NUM_ODD_HASH_CONV" |
| 1546 |
else |
| 1547 |
let th1 = raw_odd_hash_conv rtm in |
| 1548 |
TRANS th0 th1;; |
| 1549 |
|
| 1550 |
end;; |