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:

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

This can be used to show, e.g. that x*x >= x, under the right assumptions.

The 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

• 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.
• 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).

<file pvs logic.pvs> logic : 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 logic </code>

 Proof summary for theory logic
    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)