| 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 |
(* Additional list definitions and theorems *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
module More_list = struct |
| 14 |
|
| 15 |
(* definitions *) |
| 16 |
let REVERSE_TABLE = define `(REVERSE_TABLE (f:num->A) 0 = []) /\ |
| 17 |
(REVERSE_TABLE f (SUC i) = CONS (f i) ( REVERSE_TABLE f i))`;; |
| 18 |
|
| 19 |
let TABLE = new_definition `!(f:num->A) k. TABLE f k = REVERSE (REVERSE_TABLE f k)`;; |
| 20 |
|
| 21 |
let l_seq = new_definition `l_seq n m = TABLE (\i. n + i) ((m + 1) - n)`;; |
| 22 |
|
| 23 |
(* lemmas *) |
| 24 |
let LENGTH_REVERSE_TABLE = prove(`!(f:num->A) n. LENGTH (REVERSE_TABLE f n) = n`, |
| 25 |
GEN_TAC THEN INDUCT_TAC THEN ASM_REWRITE_TAC[REVERSE_TABLE; LENGTH]);; |
| 26 |
|
| 27 |
let LENGTH_REVERSE = prove(`!(l:(A)list). LENGTH (REVERSE l) = LENGTH l`, |
| 28 |
MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[REVERSE] THEN |
| 29 |
REPEAT STRIP_TAC THEN |
| 30 |
ASM_REWRITE_TAC[LENGTH_APPEND; LENGTH] THEN |
| 31 |
ARITH_TAC);; |
| 32 |
|
| 33 |
let LENGTH_TABLE = prove(`!(f:num->A) n. LENGTH (TABLE f n) = n`, |
| 34 |
REWRITE_TAC[TABLE; LENGTH_REVERSE; LENGTH_REVERSE_TABLE]);; |
| 35 |
|
| 36 |
let EL_TABLE = prove(`!(f:num->A) n i. i < n ==> EL i (TABLE f n) = f i`, |
| 37 |
REPEAT GEN_TAC THEN SPEC_TAC (`n:num`, `n:num`) THEN |
| 38 |
INDUCT_TAC THENL [ ARITH_TAC; ALL_TAC ] THEN |
| 39 |
REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE; EL_APPEND] THEN |
| 40 |
REWRITE_TAC[GSYM TABLE; LENGTH_TABLE] THEN |
| 41 |
DISCH_TAC THEN COND_CASES_TAC THENL |
| 42 |
[ |
| 43 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]; |
| 44 |
ALL_TAC |
| 45 |
] THEN |
| 46 |
SUBGOAL_THEN `i = n:num` (fun th -> REWRITE_TAC[th]) THENL |
| 47 |
[ |
| 48 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN |
| 49 |
ARITH_TAC; |
| 50 |
ALL_TAC |
| 51 |
] THEN |
| 52 |
REWRITE_TAC[ARITH_RULE `n - n = 0`; EL; HD]);; |
| 53 |
|
| 54 |
let TABLE_0 = prove(`!(f:num->A). TABLE f 0 = []`, |
| 55 |
REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE]);; |
| 56 |
|
| 57 |
let TABLE_SUC = prove(`!(f:num->A) n. TABLE f (SUC n) = APPEND (TABLE f n) [f n]`, |
| 58 |
GEN_TAC THEN INDUCT_TAC THEN REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE]);; |
| 59 |
|
| 60 |
let LIST_EL_EQ = prove(`!ul vl:(A)list. ul = vl <=> |
| 61 |
(LENGTH ul = LENGTH vl /\ (!j. j < LENGTH ul ==> EL j ul = EL j vl))`, |
| 62 |
REPEAT STRIP_TAC THEN |
| 63 |
EQ_TAC THEN STRIP_TAC THEN ASM_REWRITE_TAC[] THEN |
| 64 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN |
| 65 |
SPEC_TAC (`vl:(A)list`, `vl:(A)list`) THEN SPEC_TAC (`ul:(A)list`, `ul:(A)list`) THEN |
| 66 |
LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN SIMP_TAC[LENGTH_EQ_NIL; EQ_SYM_EQ; LENGTH; ARITH_RULE `~(0 = SUC a)`] THEN |
| 67 |
POP_ASSUM (fun th -> ALL_TAC) THEN |
| 68 |
REWRITE_TAC[ARITH_RULE `SUC a = SUC b <=> a = b`] THEN |
| 69 |
REPEAT STRIP_TAC THEN |
| 70 |
FIRST_X_ASSUM (MP_TAC o SPEC `t':(A)list`) THEN |
| 71 |
ASM_REWRITE_TAC[] THEN |
| 72 |
ANTS_TAC THENL |
| 73 |
[ |
| 74 |
REPEAT STRIP_TAC THEN |
| 75 |
FIRST_X_ASSUM (MP_TAC o SPEC `SUC j`) THEN |
| 76 |
ASM_REWRITE_TAC[ARITH_RULE `SUC a < SUC b <=> a < b`; EL; TL]; |
| 77 |
ALL_TAC |
| 78 |
] THEN |
| 79 |
DISCH_TAC THEN |
| 80 |
FIRST_X_ASSUM (MP_TAC o SPEC `0`) THEN |
| 81 |
ASM_SIMP_TAC[ARITH_RULE `0 < SUC a`; EL; HD]);; |
| 82 |
|
| 83 |
|
| 84 |
let LENGTH_L_SEQ = prove(`LENGTH (l_seq n m) = (m + 1) - n`, REWRITE_TAC[l_seq; LENGTH_TABLE]);; |
| 85 |
|
| 86 |
let EL_L_SEQ = prove(`!i m n. i < (m + 1) - n ==> EL i (l_seq n m) = n + i`, |
| 87 |
REWRITE_TAC[l_seq] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC EL_TABLE THEN ASM_REWRITE_TAC[]);; |
| 88 |
|
| 89 |
let L_SEQ_NIL = prove(`!n m. l_seq n m = [] <=> (m < n)`, |
| 90 |
GEN_TAC THEN GEN_TAC THEN REWRITE_TAC[GSYM LENGTH_EQ_NIL; LENGTH_L_SEQ] THEN ARITH_TAC);; |
| 91 |
|
| 92 |
let L_SEQ_NN = prove(`!n. l_seq n n = [n]`, |
| 93 |
GEN_TAC THEN REWRITE_TAC[l_seq; ARITH_RULE `(n + 1) - n = 1`; ONE; TABLE; REVERSE_TABLE; REVERSE] THEN |
| 94 |
REWRITE_TAC[APPEND; ADD_0]);; |
| 95 |
|
| 96 |
let L_SEQ_CONS = prove(`!n m. n <= m ==> l_seq n m = CONS n (l_seq (n + 1) m)`, |
| 97 |
REPEAT STRIP_TAC THEN |
| 98 |
REWRITE_TAC[LIST_EL_EQ; LENGTH_L_SEQ; LENGTH] THEN CONJ_TAC THENL |
| 99 |
[ |
| 100 |
ASM_ARITH_TAC; |
| 101 |
ALL_TAC |
| 102 |
] THEN |
| 103 |
INDUCT_TAC THENL |
| 104 |
[ |
| 105 |
ASM_SIMP_TAC[EL_L_SEQ] THEN ASM_REWRITE_TAC[EL; HD] THEN ARITH_TAC; |
| 106 |
DISCH_TAC THEN |
| 107 |
ASM_SIMP_TAC[EL_L_SEQ] THEN ASM_REWRITE_TAC[EL; TL] THEN |
| 108 |
MP_TAC (SPECL [`j:num`; `m:num`; `n + 1`] EL_L_SEQ) THEN ANTS_TAC THENL |
| 109 |
[ |
| 110 |
ASM_ARITH_TAC; |
| 111 |
ALL_TAC |
| 112 |
] THEN |
| 113 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN ARITH_TAC |
| 114 |
]);; |
| 115 |
|
| 116 |
|
| 117 |
let LENGTH_BUTLAST = prove(`!l. LENGTH (BUTLAST l) = LENGTH l - 1`, |
| 118 |
MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[BUTLAST; LENGTH; ARITH] THEN REPEAT STRIP_TAC THEN |
| 119 |
COND_CASES_TAC THEN ASM_REWRITE_TAC[LENGTH; ARITH] THEN |
| 120 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[GSYM LENGTH_EQ_NIL] THEN |
| 121 |
ARITH_TAC);; |
| 122 |
|
| 123 |
let EL_BUTLAST = prove(`!(l:(A)list) i. i < LENGTH l - 1 ==> EL i (BUTLAST l) = EL i l`, |
| 124 |
MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[BUTLAST; LENGTH] THEN REPEAT STRIP_TAC THEN |
| 125 |
COND_CASES_TAC THENL |
| 126 |
[ |
| 127 |
UNDISCH_TAC `i < SUC (LENGTH (a1:(A)list)) - 1` THEN |
| 128 |
ASM_REWRITE_TAC[LENGTH] THEN ARITH_TAC; |
| 129 |
ALL_TAC |
| 130 |
] THEN |
| 131 |
REWRITE_TAC[EL_CONS] THEN COND_CASES_TAC THEN ASM_REWRITE_TAC[] THEN |
| 132 |
FIRST_X_ASSUM (MP_TAC o SPEC `i - 1`) THEN |
| 133 |
ANTS_TAC THENL |
| 134 |
[ |
| 135 |
ASM_ARITH_TAC; |
| 136 |
ALL_TAC |
| 137 |
] THEN |
| 138 |
REWRITE_TAC[]);; |
| 139 |
|
| 140 |
end;; |