User Tools
pvs:libraries
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
pvs:libraries [2016/08/24 21:56] jonathan |
pvs:libraries [2016/09/13 18:06] (current) jonathan |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Reals ====== | ====== Reals ====== | ||
| - | Hypatheon is useful for browsing libraries. In the Prelude, we have real_axioms, reals and real_props. For example, in real_props we have the Lemma "both_sides_div_pos_neg_ge1" which allows us to divide both sides of an inequality ''x >= y'' by the same value ''n0z: VAR nonzero_real'': | + | Hypatheon is useful for browsing libraries. In the Prelude, we have |
| + | * real_axioms, | ||
| + | * reals | ||
| + | * real_props | ||
| + | * extra_real_props. | ||
| + | |||
| + | For example, in real_props we have the Lemma "both_sides_div_pos_neg_ge1" which allows us to divide both sides of an inequality ''x >= y'' by the same value ''n0z: VAR nonzero_real'': | ||
| <code> | <code> | ||
| Line 14: | Line 20: | ||
| There are also libraries of decision procedures such as | There are also libraries of decision procedures such as | ||
| - | * [[http://shemesh.larc.nasa.gov/people/cam/Sturm/|sturm]]: Sturm's Theorem is a well-known result in real algebraic geometry that provides a function that computes the number of roots of a univariate polynomial in a semi-open interval, and is included in the NASA PVS libraries. | + | * [[http://shemesh.larc.nasa.gov/people/cam/Sturm/|sturm]]: Sturm's Theorem is a well-known result in real algebraic geometry that provides a function that computes the number of roots of a univariate polynomial in a semi-open interval, and is included in the NASA PVS libraries. Strategy ''mono-poly'' automatically discharges monotinicity properties of polynomials on a real interval. |
| * [[http://shemesh.larc.nasa.gov/people/cam/Tarski/|tarski]].Tarski's Theorem is a generalization of Sturm's theorem that provides a linear relationship between functions known as Tarski queries and cardinalities of certain sets. It's also in the NASA library. | * [[http://shemesh.larc.nasa.gov/people/cam/Tarski/|tarski]].Tarski's Theorem is a generalization of Sturm's theorem that provides a linear relationship between functions known as Tarski queries and cardinalities of certain sets. It's also in the NASA library. | ||
| Line 20: | Line 26: | ||
| IMPORTING Sturm@strategies | IMPORTING Sturm@strategies | ||
| IMPORTING Tarski@strategies | IMPORTING Tarski@strategies | ||
| - | (Tarski is heavy so wait for it to load and finish). | + | (Tarski is heavy so wait for it to load and finish). Note that the ''(eval-formula)'' from PVSio can also be used to prove the D2 example. |
| + | |||
| + | ===== Example Theory ===== | ||
| + | |||
| + | <file text real.pvs> | ||
| + | real : THEORY | ||
| + | BEGIN | ||
| + | %(sturm) and (mono-poly) incorporate some nice decision procedures | ||
| + | IMPORTING Sturm@strategies | ||
| + | %IMPORTING Tarski@strategies | ||
| + | |||
| + | % Subtypes D1 and D2 which is the set {1,2,3,4,5} | ||
| + | D1: TYPE = {i: nat | i = 1 OR i= 2 OR i=3 OR i=4 OR i=5} | ||
| + | D2: TYPE = {i: nat | 1 <= i AND i <= 5} | ||
| + | |||
| + | conja1: CONJECTURE (FORALL (x:D1) : x*x >= x) | ||
| + | |||
| + | % The abobe proves wih (grind) or the proof below (saved with with C-c 2p): | ||
| + | %|- conja1 : PROOF | ||
| + | %|- (then (skeep) (typepred "x") (assert)) | ||
| + | %|- QED | ||
| + | |||
| + | conja2: CONJECTURE (FORALL (x:D2) : x*x >= x) | ||
| + | |||
| + | %|- conja2 : PROOF | ||
| + | %|- (then (skeep) (lemma "both_sides_div_pos_neg_ge1") (grind)) | ||
| + | %|- QED | ||
| + | % Lemma is: FORALL (n0z: nonzero_real, x, y: real): | ||
| + | % IF n0z > 0 THEN x/n0z >= y/n0z ELSE y/n0z >= x/n0z ENDIF | ||
| + | % IFF x >= y | ||
| + | |||
| + | % We could also prove the above automatically in one step using (sturm). | ||
| + | |||
| + | % The following should not prove because e.g. x = 0.5 is a counter-example | ||
| + | conjb: CONJECTURE (FORALL (x:real) : x^2 >= x) | ||
| + | |||
| + | conjc: CONJECTURE (FORALL (x: real): x >= 1.0 IMPLIES x * x >= x) | ||
| + | |||
| + | % (sturm) proves the above automatically. | ||
| + | % Alternatively, manip introduces additional rules such as (div-by): | ||
| + | %|- conj4 : PROOF | ||
| + | %|- (then (skeep) (div-by 1 "x")) | ||
| + | %|- QED | ||
| + | |||
| + | example_14 : LEMMA | ||
| + | FORALL (x:real) : x ## [| 0, oo |] IMPLIES -x^3 <= 0 | ||
| + | %|- example_14 : PROOF | ||
| + | %|- (sturm) | ||
| + | %|- QED | ||
| + | |||
| + | mono_example_4: LEMMA | ||
| + | FORALL (x,y:real): x /= y IMPLIES x^3 /= y^3 | ||
| + | %|- mono_example_4 : PROOF | ||
| + | %|- (mono-poly) | ||
| + | %|- QED | ||
| + | |||
| + | |||
| + | END real | ||
| + | </file> | ||
| + | |||
| + | <code> | ||
| + | Proof summary for theory real | ||
| + | conja1................................proved - complete [shostak](0.06 s) | ||
| + | conja2................................proved - complete [shostak](0.39 s) | ||
| + | conjb_TCC1............................proved - complete [shostak](0.00 s) | ||
| + | conjb.................................unfinished [shostak](0.03 s) | ||
| + | conjc.................................proved - complete [shostak](0.41 s) | ||
| + | example_14_TCC1.......................proved - complete [shostak](0.01 s) | ||
| + | example_14............................proved - complete [shostak](0.36 s) | ||
| + | mono_example_4_TCC1...................proved - complete [shostak](0.01 s) | ||
| + | mono_example_4_TCC2...................proved - complete [shostak](0.00 s) | ||
| + | mono_example_4........................proved - complete [shostak](0.54 s) | ||
| + | Theory totals: 10 formulas, 10 attempted, 9 succeeded (1.81 s) | ||
| + | |||
| + | Grand Totals: 10 proofs, 10 attempted, 9 succeeded (1.81 s) | ||
| + | </code> | ||
pvs/libraries.1472075786.txt.gz · Last modified: 2016/08/24 21:56 by jonathan
Page Tools
