diff options
Diffstat (limited to 'theories/Arith/MinMax.v')
-rw-r--r-- | theories/Arith/MinMax.v | 113 |
1 files changed, 113 insertions, 0 deletions
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. |