Differences

This shows you the differences between two versions of the page.

--- pvs:libraries [2016/08/24 21:34]
jonathan
+++ pvs:libraries [2016/09/13 18:06] (current)
jonathan
@@ Line 1: / Line 1: @@
 ====== 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>
@@ Line 9: / Line 15: @@
 </code>
-This can be used to show, e.g. that ''x*x >= x''.
+This can be used to show, e.g. that ''x*x >= x'', under the right assumptions.
+The [[http://shemesh.larc.nasa.gov/people/bld/manip.html|manip]] package introduces additional rules. For example, in Hypatheon, select Type = Defined_rule and search for ''div-by''.
+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. 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.
+These libraries can be imported as
+  IMPORTING Sturm@strategies
+  IMPORTING Tarski@strategies
+(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>
-There are also libraries of decision procedures such as [[http://shemesh.larc.nasa.gov/people/cam/Sturm/|sturm]] and [[http://shemesh.larc.nasa.gov/people/cam/Tarski/|tarski]].

Software Engineering Documentation

User Tools

Site Tools

Differences

Page Tools