diff options
Diffstat (limited to 'theories/Arith/MinMax.v')
-rw-r--r-- | theories/Arith/MinMax.v | 113 |
1 files changed, 0 insertions, 113 deletions
diff --git a/theories/Arith/MinMax.v b/theories/Arith/MinMax.v deleted file mode 100644 index 8a23c8f6..00000000 --- a/theories/Arith/MinMax.v +++ /dev/null @@ -1,113 +0,0 @@ -(************************************************************************) -(* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2011 *) -(* \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. |