From c4b5c7ebd6f316bb53e1a53f94c367f4f0129dae Mon Sep 17 00:00:00 2001
From: letouzey
Date: Tue, 9 Feb 2010 17:45:06 +0000
Subject: Numbers: properties of min/max with respect to 0,S,P,add,sub,mul

 With these properties, we can kill Arith/MinMax, NArith/Nminmax,
 and leave ZArith/Zminmax as a compatibility file only. Now
 the instanciations NPeano.Nat, NBinary.N, ZBinary.Z, BigZ, BigN
 contains all theses facts.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12718 85f007b7-540e-0410-9357-904b9bb8a0f7
---
 theories/Numbers/Integer/Abstract/ZMaxMin.v     | 179 ++++++++++++++++++++++++
 theories/Numbers/Integer/Abstract/ZProperties.v |   6 +-
 2 files changed, 182 insertions(+), 3 deletions(-)
 create mode 100644 theories/Numbers/Integer/Abstract/ZMaxMin.v

(limited to 'theories/Numbers/Integer')

diff --git a/theories/Numbers/Integer/Abstract/ZMaxMin.v b/theories/Numbers/Integer/Abstract/ZMaxMin.v
new file mode 100644
index 0000000000..93b7966b08
--- /dev/null
+++ b/theories/Numbers/Integer/Abstract/ZMaxMin.v
@@ -0,0 +1,179 @@
+(************************************************************************)
+(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
+(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
+(*   \VV/  **************************************************************)
+(*    //   *      This file is distributed under the terms of the       *)
+(*         *       GNU Lesser General Public License Version 2.1        *)
+(************************************************************************)
+
+Require Import ZAxioms ZMulOrder GenericMinMax.
+
+(** * Properties of minimum and maximum specific to integer numbers *)
+
+Module Type ZMaxMinProp (Import Z : ZAxiomsSig').
+Include ZMulOrderPropFunct Z.
+
+(** The following results are concrete instances of [max_monotone]
+    and similar lemmas. *)
+
+(** Succ *)
+
+Lemma succ_max_distr : forall n m, S (max n m) == max (S n) (S m).
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?succ_le_mono.
+Qed.
+
+Lemma succ_min_distr : forall n m, S (min n m) == min (S n) (S m).
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?succ_le_mono.
+Qed.
+
+(** Pred *)
+
+Lemma pred_max_distr : forall n m, P (max n m) == max (P n) (P m).
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?pred_le_mono.
+Qed.
+
+Lemma pred_min_distr : forall n m, P (min n m) == min (P n) (P m).
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?pred_le_mono.
+Qed.
+
+(** Add *)
+
+Lemma add_max_distr_l : forall n m p, max (p + n) (p + m) == p + max n m.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?add_le_mono_l.
+Qed.
+
+Lemma add_max_distr_r : forall n m p, max (n + p) (m + p) == max n m + p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; now rewrite <- ?add_le_mono_r.
+Qed.
+
+Lemma add_min_distr_l : forall n m p, min (p + n) (p + m) == p + min n m.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?add_le_mono_l.
+Qed.
+
+Lemma add_min_distr_r : forall n m p, min (n + p) (m + p) == min n m + p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; now rewrite <- ?add_le_mono_r.
+Qed.
+
+(** Opp *)
+
+Lemma opp_max_distr : forall n m, -(max n m) == min (-n) (-m).
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite max_r by trivial. symmetry. apply min_r. now rewrite <- opp_le_mono.
+ rewrite max_l by trivial. symmetry. apply min_l. now rewrite <- opp_le_mono.
+Qed.
+
+Lemma opp_min_distr : forall n m, -(min n m) == max (-n) (-m).
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite min_l by trivial. symmetry. apply max_l. now rewrite <- opp_le_mono.
+ rewrite min_r by trivial. symmetry. apply max_r. now rewrite <- opp_le_mono.
+Qed.
+
+(** Sub *)
+
+Lemma sub_max_distr_l : forall n m p, max (p - n) (p - m) == p - min n m.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite min_l by trivial. apply max_l. now rewrite <- sub_le_mono_l.
+ rewrite min_r by trivial. apply max_r. now rewrite <- sub_le_mono_l.
+Qed.
+
+Lemma sub_max_distr_r : forall n m p, max (n - p) (m - p) == max n m - p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply sub_le_mono_r.
+Qed.
+
+Lemma sub_min_distr_l : forall n m p, min (p - n) (p - m) == p - max n m.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite max_r by trivial. apply min_r. now rewrite <- sub_le_mono_l.
+ rewrite max_l by trivial. apply min_l. now rewrite <- sub_le_mono_l.
+Qed.
+
+Lemma sub_min_distr_r : forall n m p, min (n - p) (m - p) == min n m - p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply sub_le_mono_r.
+Qed.
+
+(** Mul *)
+
+Lemma mul_max_distr_nonneg_l : forall n m p, 0 <= p ->
+ max (p * n) (p * m) == p * max n m.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply mul_le_mono_nonneg_l.
+Qed.
+
+Lemma mul_max_distr_nonneg_r : forall n m p, 0 <= p ->
+ max (n * p) (m * p) == max n m * p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 max_r | rewrite 2 max_l]; try order; now apply mul_le_mono_nonneg_r.
+Qed.
+
+Lemma mul_min_distr_nonneg_l : forall n m p, 0 <= p ->
+ min (p * n) (p * m) == p * min n m.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply mul_le_mono_nonneg_l.
+Qed.
+
+Lemma mul_min_distr_nonneg_r : forall n m p, 0 <= p ->
+ min (n * p) (m * p) == min n m * p.
+Proof.
+ intros. destruct (le_ge_cases n m);
+  [rewrite 2 min_l | rewrite 2 min_r]; try order; now apply mul_le_mono_nonneg_r.
+Qed.
+
+Lemma mul_max_distr_nonpos_l : forall n m p, p <= 0 ->
+ max (p * n) (p * m) == p * min n m.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite min_l by trivial. rewrite max_l. reflexivity. now apply mul_le_mono_nonpos_l.
+ rewrite min_r by trivial. rewrite max_r. reflexivity. now apply mul_le_mono_nonpos_l.
+Qed.
+
+Lemma mul_max_distr_nonpos_r : forall n m p, p <= 0 ->
+ max (n * p) (m * p) == min n m * p.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite min_l by trivial. rewrite max_l. reflexivity. now apply mul_le_mono_nonpos_r.
+ rewrite min_r by trivial. rewrite max_r. reflexivity. now apply mul_le_mono_nonpos_r.
+Qed.
+
+Lemma mul_min_distr_nonpos_l : forall n m p, p <= 0 ->
+ min (p * n) (p * m) == p * max n m.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite max_r by trivial. rewrite min_r. reflexivity. now apply mul_le_mono_nonpos_l.
+ rewrite max_l by trivial. rewrite min_l. reflexivity. now apply mul_le_mono_nonpos_l.
+Qed.
+
+Lemma mul_min_distr_nonpos_r : forall n m p, p <= 0 ->
+ min (n * p) (m * p) == max n m * p.
+Proof.
+ intros. destruct (le_ge_cases n m).
+ rewrite max_r by trivial. rewrite min_r. reflexivity. now apply mul_le_mono_nonpos_r.
+ rewrite max_l by trivial. rewrite min_l. reflexivity. now apply mul_le_mono_nonpos_r.
+Qed.
+
+End ZMaxMinProp.
diff --git a/theories/Numbers/Integer/Abstract/ZProperties.v b/theories/Numbers/Integer/Abstract/ZProperties.v
index dc46eddab6..45662d3b66 100644
--- a/theories/Numbers/Integer/Abstract/ZProperties.v
+++ b/theories/Numbers/Integer/Abstract/ZProperties.v
@@ -8,15 +8,15 @@
 
 (*i $Id$ i*)
 
-Require Export ZAxioms ZMulOrder ZSgnAbs.
+Require Export ZAxioms ZMaxMin ZSgnAbs.
 
 (** This functor summarizes all known facts about Z.
-    For the moment it is only an alias to [ZMulOrderPropFunct], which
+    For the moment it is only an alias to the last functor which
     subsumes all others, plus properties of [sgn] and [abs].
 *)
 
 Module Type ZPropSig (Z:ZAxiomsExtSig) :=
- ZMulOrderPropFunct Z <+ ZSgnAbsPropSig Z.
+ ZMaxMinProp Z <+ ZSgnAbsPropSig Z.
 
 Module ZPropFunct (Z:ZAxiomsExtSig) <: ZPropSig Z.
  Include ZPropSig Z.
-- 
cgit v1.2.3