From 5b7eafd0f00a16d78f99a27f5c7d5a0de77dc7e6 Mon Sep 17 00:00:00 2001
From: Stephane Glondu <steph@glondu.net>
Date: Wed, 21 Jul 2010 09:46:51 +0200
Subject: Imported Upstream snapshot 8.3~beta0+13298

---
 theories/Arith/MinMax.v | 113 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 theories/Arith/MinMax.v

(limited to 'theories/Arith/MinMax.v')

diff --git a/theories/Arith/MinMax.v b/theories/Arith/MinMax.v
new file mode 100644
index 00000000..6e86a88c
--- /dev/null
+++ b/theories/Arith/MinMax.v
@@ -0,0 +1,113 @@
+(************************************************************************)
+(*  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 Orders NatOrderedType GenericMinMax.
+
+(** * Maximum and Minimum of two natural numbers *)
+
+Fixpoint max n m : nat :=
+  match n, m with
+    | O, _ => m
+    | S n', O => n
+    | S n', S m' => S (max n' m')
+  end.
+
+Fixpoint min n m : nat :=
+  match n, m with
+    | O, _ => 0
+    | S n', O => 0
+    | S n', S m' => S (min n' m')
+  end.
+
+(** These functions implement indeed a maximum and a minimum *)
+
+Lemma max_l : forall x y, y<=x -> max x y = x.
+Proof.
+ induction x; destruct y; simpl; auto with arith.
+Qed.
+
+Lemma max_r : forall x y, x<=y -> max x y = y.
+Proof.
+ induction x; destruct y; simpl; auto with arith.
+Qed.
+
+Lemma min_l : forall x y, x<=y -> min x y = x.
+Proof.
+ induction x; destruct y; simpl; auto with arith.
+Qed.
+
+Lemma min_r : forall x y, y<=x -> min x y = y.
+Proof.
+ induction x; destruct y; simpl; auto with arith.
+Qed.
+
+
+Module NatHasMinMax <: HasMinMax Nat_as_OT.
+ Definition max := max.
+ Definition min := min.
+ Definition max_l := max_l.
+ Definition max_r := max_r.
+ Definition min_l := min_l.
+ Definition min_r := min_r.
+End NatHasMinMax.
+
+(** We obtain hence all the generic properties of [max] and [min],
+    see file [GenericMinMax] or use SearchAbout. *)
+
+Module Export MMP := UsualMinMaxProperties Nat_as_OT NatHasMinMax.
+
+
+(** * Properties specific to the [nat] domain *)
+
+(** Simplifications *)
+
+Lemma max_0_l : forall n, max 0 n = n.
+Proof. reflexivity. Qed.
+
+Lemma max_0_r : forall n, max n 0 = n.
+Proof. destruct n; auto. Qed.
+
+Lemma min_0_l : forall n, min 0 n = 0.
+Proof. reflexivity. Qed.
+
+Lemma min_0_r : forall n, min n 0 = 0.
+Proof. destruct n; auto. Qed.
+
+(** Compatibilities (consequences of monotonicity) *)
+
+Lemma succ_max_distr : forall n m, S (max n m) = max (S n) (S m).
+Proof. auto. Qed.
+
+Lemma succ_min_distr : forall n m, S (min n m) = min (S n) (S m).
+Proof. auto. Qed.
+
+Lemma plus_max_distr_l : forall n m p, max (p + n) (p + m) = p + max n m.
+Proof.
+intros. apply max_monotone. repeat red; auto with arith.
+Qed.
+
+Lemma plus_max_distr_r : forall n m p, max (n + p) (m + p) = max n m + p.
+Proof.
+intros. apply max_monotone with (f:=fun x => x + p).
+repeat red; auto with arith.
+Qed.
+
+Lemma plus_min_distr_l : forall n m p, min (p + n) (p + m) = p + min n m.
+Proof.
+intros. apply min_monotone. repeat red; auto with arith.
+Qed.
+
+Lemma plus_min_distr_r : forall n m p, min (n + p) (m + p) = min n m + p.
+Proof.
+intros. apply min_monotone with (f:=fun x => x + p).
+repeat red; auto with arith.
+Qed.
+
+Hint Resolve
+ max_l max_r le_max_l le_max_r
+ min_l min_r le_min_l le_min_r : arith v62.
-- 
cgit v1.2.3