| 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 |
(* Theoretical results for interval arithmetic *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 14 |
|
| 15 |
module Interval_arith = struct |
| 16 |
|
| 17 |
prioritize_real();; |
| 18 |
|
| 19 |
(*******************************) |
| 20 |
(* The main definition *) |
| 21 |
let interval_arith = |
| 22 |
new_definition `interval_arith (x:real) (lo, hi) <=> lo <= x /\ x <= hi`;; |
| 23 |
|
| 24 |
(* Additional definitions *) |
| 25 |
let bounded_on = new_definition `bounded_on f s f_bounds <=> |
| 26 |
!x. x IN s ==> interval_arith (f x) f_bounds`;; |
| 27 |
|
| 28 |
let bounded_on_int = new_definition `bounded_on_int f int f_bounds <=> |
| 29 |
!x. interval_arith x int ==> interval_arith (f x) f_bounds`;; |
| 30 |
|
| 31 |
let iabs = new_definition `iabs (x_lo, x_hi) = max x_hi (-- x_lo)`;; |
| 32 |
let interval_not_zero = new_definition `interval_not_zero (lo, hi) <=> &0 < lo \/ hi < &0`;; |
| 33 |
let interval_pos = new_definition `interval_pos (lo, hi) <=> &0 < lo`;; |
| 34 |
let interval_neg = new_definition `interval_neg (lo, hi) <=> hi < &0`;; |
| 35 |
let interval_gt = new_definition `interval_gt f (lo, hi) <=> f < lo`;; |
| 36 |
|
| 37 |
|
| 38 |
(********************************) |
| 39 |
(* Lemmas *) |
| 40 |
let CONST_INTERVAL = prove(`!x. interval_arith x (x,x)`, |
| 41 |
REWRITE_TAC[interval_arith; REAL_LE_REFL]);; |
| 42 |
|
| 43 |
let APPROX_INTERVAL = (GEN_ALL o prove)(`(a <= lo /\ hi <= b) /\ interval_arith x (lo, hi) |
| 44 |
==> interval_arith x (a,b)`, |
| 45 |
REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; |
| 46 |
|
| 47 |
let INTERVAL_NEG = (GEN_ALL o prove)(`interval_arith x (a, b) ==> |
| 48 |
interval_arith (--x) (--b, --a)`, |
| 49 |
REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; |
| 50 |
|
| 51 |
let INTERVAL_NEG_EQ = prove(`!x a b. interval_arith (--x) (--b, --a) <=> |
| 52 |
interval_arith x (a, b)`, |
| 53 |
REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; |
| 54 |
|
| 55 |
|
| 56 |
|
| 57 |
(**************************************) |
| 58 |
(* Conversions *) |
| 59 |
open Misc_vars;; |
| 60 |
|
| 61 |
let interval_tm = `interval_arith`;; |
| 62 |
|
| 63 |
let dest_interval_arith tm = |
| 64 |
let lhs, int_tm = dest_comb tm in |
| 65 |
rand lhs, int_tm;; |
| 66 |
|
| 67 |
let mk_interval tm bounds = |
| 68 |
mk_comb (mk_comb (interval_tm, tm), bounds);; |
| 69 |
|
| 70 |
let mk_const_interval = |
| 71 |
let lemma = SPEC_ALL CONST_INTERVAL in |
| 72 |
fun tm -> INST[tm, x_var_real] lemma;; |
| 73 |
|
| 74 |
end;; |